Next Lua: nested coroutines?

[Thijs Schreijer]

Hello list,

I went over the git repo to check recent updates, and was wondering if there is any possibility to get a solution to the "nested coroutine" problem in the next Lua version?

It was briefly discussed at the Freiburg Lua Workshop (2022), but couldn't find anything in the repo. Is this even on the radar? Would love to see a solution to this long standing problem.

regards,

Thijs

[Andrew Starks]

Pleas to expand on the issue for those of us not familiar with the topic?

-- Andrew

--
You received this message because you are subscribed to the Google Groups "lua-l" group.
To unsubscribe from this group and stop receiving emails from it, send an email to lua-l+un...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/lua-l/ed822f3c-8346-4fb4-92be-523b695e87ee%40app.fastmail.com.

[Thijs Schreijer]

On Thu, 25 Apr 2024, at 21:35, Andrew Starks wrote:
> Pleas to expand on the issue for those of us not familiar with the topic?
> -- Andrew

Example code demonstrating the problem [1].

This problem occurs when you resume coroutine1, then from that coroutine1 resume coroutine2, from coroutine2 you resume couroutine3, and so on.

Effectively the resuming and yielding operate on a stack. In the example code there are 3 coroutines stacked like this:

scheduler (main loop)
-> fibonacci-counter
-> fibonacci-producer
-> character-counter

The "sleep" function takes a delay, and passes that through a yield to the mainloop, which then pauses and reschedules the coroutine.

This works in the first test. In the second test the sleep is called from the fibonacci-producer. And this is where the coroutine stack comes into play. The sleep function now yields and passes the delay. But this doesn't end up in the main scheduler loop (2 levels up the stack), but instead ends up in the fibonacci-counter (1 level up the stack).

Nett effect being that the sleep is never effectuated, the first task runs continuously (printing bad results, since they are from sleep and not from fibonacci-producer). Once it has finished, the 2nd task runs. And hence the 2 tasks no longer interleave their execution.

So core of the problem:
- There is a stack of unknown size depending on the nesting
- yielding only yields one level ever, and the "yielder" has no way to know nor change the yielding.

There are libraries that solve this issue, by "tagging" [2]. But if you write an application and compose it of multiple libraries, then the requirement is that all those libraries use the same mechanism, which is something users cannot rely on nor check. Hence the only way to properly solve this, is by providing a solution in Lua itself.

At the time Roberto suggested that adding a "coroutine.goto" function might be able to solve this problem.

Hopefully this explains the issue.

regards
Thijs

[1] example code: https://gist.github.com/Tieske/8b119a80fffc0fda5f66216987289bab
[2] tagged coroutines: https://github.com/mascarenhas/taggedcoro

[Rett Berg]

it looks to me like you are mainly using coroutines mainly to implement an iterator. IMO this is overkill and yes it will cause problems. The answer: don't do this if you need to yield from inside the iterator

My recommendation: don't use coroutines to implement iterators at all. Iterators ARE slightly difficult to understand, but once you have a "for template" that you can hold in your mind they become much easier. Basically: your iterator function takes as it's first argument the index (or state if you need more than just an index) and the second item is typically the value you are really returning. You then return the next index (or update and return the state) as well as the next value -- or nil if the iterator is done.

I've written a handy guide[1] which is similar to the one in the std Lua tutorial you may find helpful.

Best,

Rett

[1]: https://github.com/civboot/civlua/blob/main/lib/doc/doc.lua#L42

[Rett Berg]

I should have mentioned: if you absolutely have to you can use closures, but I really advise against implementing iterators using coroutines.

--
You received this message because you are subscribed to a topic in the Google Groups "lua-l" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/lua-l/TmsDXBslnxk/unsubscribe.
To unsubscribe from this group and all its topics, send an email to lua-l+un...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/lua-l/7563e20f-f151-4596-a78d-c5ef802e3a38n%40googlegroups.com.

[Thijs Schreijer]

On Fri, 26 Apr 2024, at 23:30, Rett Berg wrote:
> it looks to me like you are mainly using coroutines mainly to implement
> an iterator. IMO this is overkill and yes it will cause problems. The

> answer: don't do this if you need to *yield* from inside the iterator

I know how to fix the code that I control. But the main point from my explanation is:

> But if you write an application and compose it of multiple libraries, then
> the requirement is that all those libraries use the same mechanism, which
> is something users cannot rely on nor check. Hence the only way to properly
> solve this, is by providing a solution in Lua itself.

If I use a scheduler, just any, and also use a coroutine based library of some sorts, it might just break in unexpected ways.

Thijs

[Rett Berg]

> If I use a scheduler, just any, and also use a coroutine based library of some sorts, it might just break in unexpected ways.

If they are using coroutines as just an iterator (i.e. purely processing data) then there is no issue. The issue only occurs if they call a function/method which they EXPECT to return but yields because it's non-blocking. Or if you are monkey patching normally blocking APIs like file:read with yielding ones and they are using them.

I don't think there's a solution here. In theory you could make a protocol that modified a global error value or something and then you check it after a yield (like how errno works) but those APIs are pretty error prone and I wouldn't recommend it.

This is precisely why I created the LAP protocol: IMO we should write all (or near all) code in a "blocking style" but allow the application to switch between sync and async modes. This would obviously also require libraries to not use coroutines in the way you mention, which I personally think is fine.

FYI if you know they are going to yield you could also simply schedule them on your coroutine and then re-schedule your own thread when done (using coroutine.running())

Best

Rett

--
You received this message because you are subscribed to a topic in the Google Groups "lua-l" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/lua-l/TmsDXBslnxk/unsubscribe.
To unsubscribe from this group and all its topics, send an email to lua-l+un...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/lua-l/49fb7f68-8b3b-47b8-a187-df41b92ff89c%40app.fastmail.com.

[Roberto Ierusalimschy]

> I went over the git repo to check recent updates, and was wondering if there is any possibility to get a solution to the "nested coroutine" problem in the next Lua version?
>
> It was briefly discussed at the Freiburg Lua Workshop (2022), but couldn't find anything in the repo. Is this even on the radar? Would love to see a solution to this long standing problem.

It is in our radar, but we don't have a good fix for that. Is there
one?

-- Roberto

[bil til]

> Am Mo., 29. Apr. 2024 um 22:16 Uhr schrieb Roberto Ierusalimschy <rob...@inf.puc-rio.br>:
> Is there one?

I am frightened this is a "holy question of multithreading" without
"holy answer".

If you install multithreading in a "reasonably flexible way", there
will always be possibilities to "stall the system".

"Sandboxed multithreading" is not possible I think. So in Lua "sandbox
applications" better do NOT allow coroutines (resp. install your own
"task" system based on Lua resume/yield functionality with a subset of
"coroutine possibilities" which then depends quite strongly on the
specific applications you want your Lua users to drive...).

[云风 Cloud Wu]

bil til <bilt...@gmail.com> 于2024年4月30日周二 12:54写道：

> "Sandboxed multithreading" is not possible I think. So in Lua "sandbox
> applications" better do NOT allow coroutines (resp. install your own

I think lua is a good choice for sandboxed multithreading. I spent
years doing this (sandboxed multithreading) .
There is also a nested coroutine issue in my framework "skynet", and
this is my solution :
https://github.com/cloudwu/skynet/blob/master/lualib/skynet/coroutine.lua
It's not a general solution, but it works for "skynet".

I think the more important thing for "sandboxed multithreading" is
sharing constant objects (like strings, function prototypes, constant
tables, etc) in multi-sandboxes, and I hope future versions of lua
will have more relevant features.

--
http://blog.codingnow.com

[Pierre Chapuis]

One way to work around the problem is to have the scheduler hack the coroutine mechanism like this for instance: https://gist.github.com/catwell/191f589d66927ea340a2c6636bc52738 (I started from your gist so you can see the diff by clicking revisions).

I did it by overloading the global to keep things simple but in practice you would only change it in coroutines spawned by the scheduler (by hacking the environment in `add_task` for instance).

--
Pierre Chapuis

[Thijs Schreijer]

I think the `coroutine.goto()` can work, though I'd probably call it `coroutine.yieldto()`, since `goto` implies to jump to just any coroutine, where `yieldto` implies the target coroutine must be up the stack somewhere.

Signature: `coroutine.yieldto(co, ...)

- It behaves the same as `coroutine.yield(...)` except for the first argument being
the target coroutine.
- It should yield 1 or more levels up the stack of running coroutines, to the target
coroutine.
- It should throw an error if the target coroutine is not in the stack.
- The coroutine that called `yieldto` should get status "running" (because it is not
resumable). All intermediate coroutines should already have status "running". The
last one, that sits right above the target coroutine on the stack should become
"suspended" (since it is the only one that is now resumable).

Resuming:
- When the top one (the one with status "suspended") is resumed, it should switch status
to "running" again, and then resume the original coroutine that called
`coroutine.yieldto`, passing all the "resume" parameters.

I have no clue though how this would work in the implementation.

thoughts?

Regards,
Thijs

[Rett Berg]

Keep in mind it would also have to work with the C-API's lua_yieldk/resumek. Those are already fairly complex and I haven't fully wrapped my brain around them. Anything which adds complexity to that API would be a "no" from me (not that my vote counts).

You can already do effectively what you are suggesting if all the libraries follow the LAP protocol I've mentioned in this list:

https://github.com/civboot/civlua/blob/main/lib/lap/README.md

Effectively you would:

• local cor = coroutine.running() -- get reference to self
  set LAP_READY[ -- schedule the child coroutine
    coroutine.create(function()
      -- ...do some work...
      LAP_READY[cor] = 'self' -- reschedule parent when done
    end
  ] = 'child'
  yield(nil or false) -- tell scheduler to "forget" self for now
  -- ... do some more work after being re-scheduled

Obviously you wouldn't do precisely the above (the above is a less-efficient way to just yield(true)), but this way of doing things lets you implement zero cost channels (i.e. no scheduler is polling them) as well as near-zero cost all() (i.e. wait for multiple async functions) or Any() implementations, which are all demonstrated in lap.lua in that directory.

IMO don't alter the language for something that a library/protocol can already achieve.

Best,

Rett

--
You received this message because you are subscribed to a topic in the Google Groups "lua-l" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/lua-l/TmsDXBslnxk/unsubscribe.
To unsubscribe from this group and all its topics, send an email to lua-l+un...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/lua-l/29de2ce0-f47b-46dd-9522-ca3e6695f6f6%40app.fastmail.com.

[Roberto Ierusalimschy]

> Keep in mind it would also have to work with the C-API's *lua_yieldk*/
> *resumek*. Those are already fairly complex and I haven't fully wrapped my
> brain around them. Anything which *adds* complexity to that API would be a

> "no" from me (not that my vote counts).

No "vote" counts, but informed, non-repeated comments are always
welcome.

-- Roberto

[Thijs Schreijer]

On Mon, 29 Apr 2024, at 22:15, Roberto Ierusalimschy wrote:

If I may ask; what options were considered, and why were they dismissed or classified as "not a good fix"?

regards
Thijs

[Steven Johnson]

On Tuesday, April 30, 2024 at 6:46:38 AM UTC-6 Thijs Schreijer wrote:

I think the `coroutine.goto()` can work, though I'd probably call it `coroutine.yieldto()`, since `goto` implies to jump to just any coroutine, where `yieldto` implies the target coroutine must be up the stack somewhere.

Signature: `coroutine.yieldto(co, ...)

...

I have no clue though how this would work in the implementation.

 

Bit of a tangent, but this very recent article explored a similar idea, even using that very name: https://kyju.org/blog/piccolo-a-stackless-lua-interpreter/#symmetric-coroutines-and-coroutine-yieldto

The interpreter in question (https://github.com/kyren/piccolo) is built on some Rust machinery, so I don't know if any useful ideas can be carried over. The article also goes into some of the C-side difficulties.

 

[Michael Lenaghan]

That was a very interesting read, thank you!

--

You received this message because you are subscribed to the Google Groups "lua-l" group.

To unsubscribe from this group and stop receiving emails from it, send an email to lua-l+un...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/lua-l/2b6f06a4-8a82-4637-98cd-d2cc94549facn%40googlegroups.com.

[Roberto Ierusalimschy]

> If I may ask; what options were considered, and why were they dismissed or classified as "not a good fix"?

None. We didn't know a fix for that.

-- Roberto

[Thijs Schreijer]

a very interesting read indeed, thanks for sharing! Just wondering what the use-case would be for coroutine.goto(), jumping to any arbitrary coroutine? (as opposed to the coroutine.yieldto() which requires the target coroutine to be up the stack somewhere, for which there is the scheduler type use-case).

[bil til]

Not sure, whether this helps here in this discussion (I did not look
at the links given here in the posts, I must admit), from my
experience concerning coroutines in microcontrollers (I call them
"tasks" in my library):

It is straight forward to use them, if I I present a "Loop"
functionality to the user, and I require the Lua user to invoke a
"DoTasks" function in this Loop - so the task switching is done from a
function which is invoked by Lua.

So the multithreading runs somehow in a VERY cooparitive way -
cooperative not only "by Lua", but even more "by the Lua user
application" (if the user Lua does NOT invoike DoTasks, or not for
some time, the multitasking will freeze during this time).

[Renato Maia]

On Friday, April 26, 2024 at 6:05:18 AM UTC-3 Thijs Schreijer wrote:

> This works in the first test. In the second test the sleep is called

> from the fibonacci-producer. And this is where the coroutine stack

> comes into play. The sleep function now yields and passes the delay.

> But this doesn't end up in the main scheduler loop (2 levels up the stack),

> but instead ends up in the fibonacci-counter (1 level up the stack).

> ...

> [1] example code: https://gist.github.com/Tieske/8b119a80fffc0fda5f66216987289bab

I'm pretty late for this discussion, and I'm probably missing the general issue here, but for the particular problem in this example my considerations are:

- When someone resumes a coroutine passing or expecting some values they are defining a contract with the coroutine, much like when we call a function. Just like with functions, we should expect that changing the coroutine's contract will likely break the code it interacts with. When we add a call to a yielding function like `sleep` in the `fibonacciProducer` coroutine, we basically changed its "coroutine contract" since it now is resumed from clients expecting incompatible contracts (ex. the code printing numbers and the scheduler waking up coroutines).

- The best approach I found to provide such "flexibility" is to adopt the most minimal contract possibile. For instance, avoid passing or expecting values altogether when we want the coroutine be resumed and yield to multiple clients/threads. To illustrate this using your example, you can change the `sleep` function to avoid yielding values to the `run_scheduler` like:

```diff
 local function sleep(delay)  -- delay in ticks
   if type(delay) ~= "number" then
     error("bad argument #1 for 'sleep' expected number, got: " .. type(delay), 2)
   end
 
-  delay = math.max(0, math.floor(delay))
-  coroutine.yield(delay)
+  local coro = coroutine.running()
+  tasks[coro] = math.max(0, math.floor(delay))
+  coroutine.yield()
 end
```

And also change the scheduler to not expect an yielded value:

```diff
       else
         -- we're up!
-        success, new_delay = coroutine.resume(coro)
+        success = coroutine.resume(coro)
         if not success then
           print("error resuming coroutine: ", new_delay)
         end
-        if coroutine.status(coro) ~= "dead" then
-          tasks[coro] = new_delay
-        end
       end
     end
   end
```

Now we only need to find a way for the code that prints the numbers to communicate with the `fibonacciProducer` coroutine without passing values through `resume`&`yield` as well. For instance, we can use the `queue` object below:

```lua
local queue = { thread = nil, value = nil }
do
  local function resume(self, ...)
    local thread = self.thread
    self.thread = nil
    coroutine.resume(thread, ...)
  end

  local function suspend(self)
    self.thread = coroutine.running()
    return coroutine.yield()
  end

  function queue:push(value)
    if self.thread then
      resume(self, value)
    else
      self.value = value
      suspend(self)
    end
  end

  function queue:pop()
    if self.thread then
      local value = self.value
      resume(self)
      return value
    end
    return suspend(self)
  end
end
```

And then we change the code to use it:

```diff
@@ -71,7 +101,7 @@
     local function fibCoroutine()
       local a, b = 0, 1
       for i = 1, n do
-        coroutine.yield(a)  -- Yield the current Fibonacci number
+        queue:push(a)       -- Yield the current Fibonacci number
         a, b = b, a + b     -- Update to the next Fibonacci number
         sleep(number_ticks)  -- yield to allow other threads to run    <-- SLEEP WAS MOVED HERE
       end
@@ -83,9 +113,10 @@
   add_task(function()
       local i = 0
       local fibo = fibonacciProducer(100)
+      coroutine.resume(fibo)
       while i < 10 do
         i = i + 1
-        print("fibonacci:", coroutine.resume(fibo))    -- do work
+        print("fibonacci:", queue:pop())    -- do work
       end
     end, number_ticks)
```

Note that now we resume the `fibo` coroutine ignoring any values yielded. `fibo` could be on a `sleep`, `queue:push` or any other yielding operation that registers it to be resumed later.

I wrote the multi-threading library Coutil (https://github.com/renatomaia/coutil) following this basic approach. With Coutil your example could be rewritten as:

```lua
local channel = require "coutil.channel"
local system = require "coutil.system"

print("\nStarting second test using nested coroutines\n")
coroutine.resume(coroutine.create(function ()

  -- Fibonacci counter thread
  coroutine.resume(coroutine.create(function ()
      system.suspend(.1)  -- emulate the `add_task` initial "sleep"

      -- Fibonacci number generator thread
      coroutine.resume(coroutine.create(function ()
        local ch<close> = channel.create("fibonacci")
        local a, b = 0, 1
        for i = 1, 10 do
          system.awaitch(ch, "in", a)   -- Yield the current Fibonacci number
          a, b = b, a + b               -- Update to the next Fibonacci number
          system.suspend(.1)            -- yield to allow other threads to run    <-- SLEEP WAS MOVED HERE
        end
      end))

      local ch<close> = channel.create("fibonacci")
      for i = 1, 10 do
        print("fibonacci:", system.awaitch(ch, "out")) -- do work
      end
    end))

  -- character counter thread
  coroutine.resume(coroutine.create(function ()
    system.suspend(.2)  -- emulate the `add_task` initial "sleep"
    for i = 1, 3 do
      print("character:", string.char(64+i))  -- do work
      system.suspend(.2)                      -- wait till we're up again
    end
  end))

end))

system.run()
```

You can move all coroutines to the main chunk (thus avoiding nesting coroutines) and the script should behave the same.

I used the `coroutine.resume(coroutine.create(fun...end))` pattern to be clear on what's going on. But the ideal is to use something like `coutil.spawn.catch(print, fun...end)` that wraps the coroutine's function around an error handler that prints any errors regardless of how the coroutine is resumed.

Finally, the use of `coutil.channel` here is not ideal because it is designed for communication among system threads. In particular, if the `fibo` coroutine produces more values than are consumed, the coroutine will wait on the channel forever expecting that maybe someone from outside the Lua state to consume the values. To let `fibo` be collected when suspended, you can use the `queue` object written above instead of the values created by `coutil.channel`.

In summary, I fail to understand the actual issue a `coroutine.{goto,yieldto}` is trying to solve from this example.

> But if you write an application and compose it of multiple libraries, then
> the requirement is that all those libraries use the same mechanism, which
> is something users cannot rely on nor check. Hence the only way to properly
> solve this, is by providing a solution in Lua itself.

Coutil adopts a simple and probably sensible approach that could be shared by others to allow interoperability: if your coroutine wants to suspend from anywhere and be resumed from anywhere, make as minimal requirements from the caller/resumer as possible (ex. no values, no error handling, can be resumed from anywhere, anytime). We adapted the `sleep` function from the example to follow part of this approach and we could use it with the `queue` object defined above, and likely all Coutil functions.

One tricky part might be how to mix together multiple event loops like `run_scheduler` and `coutil.system.run` for instance. One possibility with Coutil is to run them in different threads and propagate events from the other to the `coutil.system.run` event loop using one of the Coutil's thread communication mechanisms, like in this example using "state coroutines": https://github.com/renatomaia/coutil/blob/master/demo/stateco.lua

Coutil exposes most, if not all, the features from https://libuv.org/, therefore you should be able to write code similar to these examples that not only wait for some time like with `sleep`, but can also wait on files, sockets, processes, threads, and more. And with some effort, you might even integrate other libraries with it when necessary.

--

Renato Maia