Go-style coroutines in the FN language
My toy Lisp fn is an inherently single-threaded language, but with its built-in stack-inspection capabilities, it’s easy to build coroutines on top.
only has about 20 lines of code, including comments. This article
contains a simplified implementation in-line. In only rewrote some
comments to make more sense in context, and removed confusing
fn's custom method call syntax, the use of
dynamic-wind and remarks about tail calls.
In most programming languages, the call stack is a chain of stack frames which ends in the program’s entry point.
In the case of C, this call stack is a contiguous memory area, but in fn, the stack frames are actually allocated objects on the heap which have pointers to each other. Each stack frame also stores the information required to resume it.
Additionally, fn has a natively implemented helper called
$get-frame returns the caller’s own stack frame as Lisp
object which can be manipulated. You can access it from an interactive
fn session as well:
fn> ($get-frame) #<Frame () @1ff4437b5780> fn> (frame-caller ($get-frame)) #<Frame () @1ff4437b97c4>
A queue of suspended coroutines
For Go-style coroutine behaviour, we keep track of a queue of call stacks of currently suspended coroutines. A coroutine which yields execution queues itself last, and returns into the first call stack from that queue.
A new coroutine is started with
its caller and itself becomes the entry point for the new coroutine
which immediately executes. The helper function
unschedules the current thread from execution by scheduling another
coroutine without adding itself back to the queue.
(defn thread-new! (thunk) ;; Suspend current call stack. (queue-push! *thread-queue* (frame-caller ($get-frame))) ;; Make sure we don't accidentally (set-frame-caller! ($get-frame) '*should-never-be-used*) ;; Call thunk, then call thread-die!. (thunk) (thread-die!)) (defn thread-die! () (set-frame-caller! ($get-frame) (queue-pop! *thread-queue*)) nil)
Switching between coroutines
To switch between coroutines, all you need to do is to have multiple
call stacks and switch between them. In fn, this is done in the
next-thread!, when called, will swizzle out
the calling stack frame stored in its own stack frame. That way, the
function can return into a different call stack than the one it was
next-thread! is implemented as follows:
(defn next-thread! () ;; Push our own frame's caller onto the queue. (queue-push! *thread-queue* (frame-caller ($get-frame))) ;; Remove a suspended stack frame from the queue, ;; and set it as our own caller, so we'll return to it. (set-frame-caller! ($get-frame) (queue-pop! *thread-queue*)) nil)
Caveats about tail calls
Manipulating your own stack frame leads to a simple and short implementation, but the devil is in the details.
In particular, in languages with implicit and automatic tail calls, an
invocation such as
(set-frame-caller! ($get-frame) ...) cannot be
put at the end of a function, of you would manipulate the caller of a
function that won’t ever return again. To work around this problem,
explicitly at the end, so that
set-frame-caller! does not get
invoked with a tail call.
The full coroutine implementation is in the
fn repository in