One common question I get about coding in Fennel is about how to effectively use coroutines. Fennel runs on the Lua runtime, and Lua is famous for having very few features, but having carefully selected just the right features to include, and coroutines are one of those features that give a remarkable bang for their buck. But because most languages don't have them, they're often seen as an advanced or confusing feature, but they're not difficult, just different. Once you get a grasp on them, they provide a great deal of flexibility and in many cases mitigate the problem of not having OS threads on the Lua runtime.

What even is a coroutine?

In order to create a coroutine, you need a function to put inside it. Here's an example in Fennel¹:

(local c (coroutine.create (fn [] 5)))
c ; -> #<thread: 0x56546f8fba88>

Lua calls them "threads" which is confusing, but they're not OS threads. Coroutines are a form of cooperative multitasking while OS threads are a form of preemptive multitasking. That means that there's a scheduler which decides when to run or pause an OS thread. With coroutines, it's up to you to schedule and pause them. Despite some similarity to OS threads, you really don't use them in the same way, so I'd hesitate to lean on that analogy too hard.

In order to run a coroutine, you use coroutine.resume:

(coroutine.resume c) ; -> true 5

In the trivial case, it behaves like a function. However, if it were a function, we could call it again, but:

(coroutine.resume c) ; -> false "cannot resume dead coroutine"

That's because each coroutine represents a single run of a function. So far it just sounds worse; a function you can only call once. Great. In order for it to be interesting, we need a function that yields:

(fn f []
  (coroutine.yield 1)
  (coroutine.yield 2)
  :done)

(local c (coroutine.create f))

(coroutine.resume c) ; -> true 1
(coroutine.resume c) ; -> true 2
(coroutine.resume c) ; -> true "done"
(coroutine.resume c) ; -> false "cannot resume dead coroutine"

Yielding is like returning, but resuming starts you back where you were. That's it! That's the whole thing. You now understand coroutines; thanks for reading!

Just kidding; there is one more thing. You can pass values into the coroutine when resuming, and they will be returned by the call to coroutine.yield. To show this, let's make a recursive function that uses that return value:

(fn f [x] (f (+ x (coroutine.yield x))))
(local c (coroutine.create f))

(coroutine.resume c 1) ; -> true    1
(coroutine.resume c 1) ; -> true    2
(coroutine.resume c 6) ; -> true    8

You'll notice the function never actually needs to return. It can loop forever and that's fine as long as it yields.

OK, that's it now for real this time; that's the whole thing. Deceptively simple, but what can you do with it?

Workers working together

Coroutines allow you to write non-blocking code that still looks linear. Without coroutines, writing non-blocking code means leaning on callbacks. Here's a simplified example from a game I made with Matthew Lyon called Tower Institute of Linguistics. You can see the whole example here, but let's start by looking at one function:

(fn move [self target]
  (if (= self.y target.y)
      (set self.x (+ self.x (if (< self.x target.x) 1 -1)))
      (= :stairs (state.map:tile-type self.x self.y))
      (set self.y (+ self.y (if (< self.y target.y) 1 -1)))
      (move self (state.map:find-on-level self.x self.y :stairs)))
  (coroutine.yield)
  (when (not (self:at? target))
    (move self target)))

Workers move with this move function which A) figures out which direction to go, B) takes a single step in that direction, C) yields, and then D) recurses if it's not done. This looks like a pretty normal recursive loop; the only difference is it's got a yield in the middle of it.

So move on its own could be done not too badly with callbacks. Our approach really shines as part of a more complex flow. For context, this is from a game you give orders that get picked up by the workers in the game. Orders require two workers to work together to accomplish them. Without blocking the main loop, workers need to decide what to do next and coordinate on their work. Let's look down at the start function that kicks off a worker's logic:

(fn start [self]
  ;; first check the queue of incoming orders to take
  (case (table.remove state.order-queue 1)
    order (take-order self order))
  ;; next see if any other workers need help
  (case (table.remove state.help-queue 1)
    other-worker (give-help self other-worker))
  ;; if you're too frustrated, leave
  (when (< state.threshold self.frustration)
    (self:leave ["no one understands me.\nI'm tired of this."]))
  (coroutine.yield)
  (start self))

What does it mean to take an order?

(fn take-order [self order]
  ;; add yourself to the help queue and set yourself to waiting
  (table.insert state.help-queue self)
  (set (self.order self.waiting?) (values order true))
  (move self order) ; remember, move yields every step of the way
  (while self.waiting?
    (set self.frustration (+ self.frustration 1))
    (coroutine.yield))
  ;; once we have someone helping us, we can build
  (build-order self order false))

(fn build-order [self order helper?]
  (each [tx ty (order.tiles helper?)]
    (move self {:x tx :y ty})
    (self:build (. order.blueprint ty tx))))

And how about helping?

(fn give-help [self other-worker]
  ;; go to the worker you're helping (yielding the whole way)
  (move self other-worker)
  ;; unblock them
  (set other-worker.waiting? false)
  ;; get to building!
  (build-order self other-worker.order true))

There's a little hand-waving here, like what self.build does. But the point is the overall flow is very clear. Now try to imagine what this would look like using callbacks. You would have to turn the whole thing inside out. No recursion, no loops allowed. It would not read smoothly because you'd constantly be distracted by trivialities.

The Importance of Being Stackful

Other languages have similar constructs: Python and JavaScript have "generator functions" which can also yield. However, generator functions can only yield directly from their body. Other normal functions that they call normally can't yield². They can call other generator functions to let them do a nested yield.

Generators are a bit of a lower-level construct from coroutines. However, they can serve as building blocks to implement "stackless coroutines". Using macro-like tricks, you can implement stackless coroutines by splitting functions into generators at their yield boundaries. The advantage of this approach is that it can be done at compile-time without needing any support from the underlying virtual machine.

But going stackless has one critical limitation: you can only yield from a generator function. This would be fine for the worker example above; we wrote all code that yielded, so we could change it to use generators. If we wanted to yield from existing code that was not yield-aware, on the other hand...

You may now resume REPLing

Imagine you are creating a program with a GUI toolkit and the GUI library provides you with an event loop. You can't block the event loop, but you want to integrate a REPL so the user can run code from within the program. But when you call fennel.repl it makes a blocking call to read from standard in. That's no good—you're writing a GUI program! You can't do a blocking read, and you're not using console input anyway.

You can indicate for Fennel's repl to get its input from another source without too much trouble, since it accepts an options table. Let's put some canned input lines into a table and give it a function that pops those lines. Once the table is empty, we'll return nil which will get treated like an EOF, ending the REPL session.

(local lines ["(+ 54 " " 50 " ")"])

(fn next-line [] (table.remove lines 1))

(fennel.repl {:readChunk next-line}) ; -> 104

But how would we wire this into a GUI? Here's an example that uses LÖVE, a game framework. It starts out by defining one table each for input and output, then declaring a drawing function, which you can just skim because isn't that important for our purposes.

(local [lines input] [[] []])

(fn love.draw []
  (let [(w h) (love.window.getMode)
        fh (+ (: (love.graphics.getFont) :getHeight) 12)]
    (each [i line (ipairs lines)]
      (love.graphics.print line 2 (* i (+ fh 2))))
    (love.graphics.line 0 (- h fh 4) w (- h fh 4)) ; draw input
    (love.graphics.print (table.concat input) 9 (- h fh))))

Output puts things into the lines table; input gets handled by tossing text into input, plus we've got a little helper function to clear out input once we're ready to use it:

(fn out [xs] (icollect [_ x (ipairs xs) :into lines] x))

(fn love.textinput [text] (table.insert input text))

(fn pop-input []
  (let [text (table.concat input)]
    (while (table.remove input) nil) ; clear input
    (.. text "\n")))

Finally we wire it all together with a coroutine that runs our repl function; we override the output function to put things in the table, but instead of creating an input function to read from our GUI elements, we just pass in coroutine.resume directly! Finally the love.keypressed handler responds to the user pressing enter by resuming the repl coroutine with the string from the input table! The repl coroutine runs until it needs input, at which point it yields until the user indicates the input is ready by pressing enter, resuming the coroutine with the input.

(local options {:onValues out :readChunk coroutine.yield})
(local repl (coroutine.create (partial fennel.repl options)))

(fn love.keypressed [key]
  (case key
    :return (coroutine.resume repl (pop-input))
    :backspace (table.remove input)))

So what makes this different from the previous example? Well, in some senses it's simpler; it's just one loop instead of a whole series of actions. But the important thing is: fennel.repl doesn't know it's running in a coroutine! All it has to do is accept whatever function we want as the "read input" function³ replacing reading from standard in. For the rest of the repl code, it's completely irrelevant that it's going to yield waiting for input.

This technique is not possible with stackless coroutines. So it wouldn't work in Python or JavaScript, but it works great in Lua and Fennel! You can turn any code into non-blocking code regardless of whether it was originally written with that in mind or not. It's a really powerful technique⁴ whenever you need some flow control that goes a little outside the usual. Give it a try some time!

---

« older | 2024-12-31T19:28:41Z | newer »

๛