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.

The implementation 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 technicalities like fn’s custom method call syntax, the use of dynamic-wind and remarks about tail calls.

Prerequisites

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. When 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>

Implementation

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 thread-new!. thread-new! suspends its caller and itself becomes the entry point for the new coroutine which immediately executes. The helper function thread-die! 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! function. 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 invoked from.

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, functions like next-thread! and thread-die! return nil 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 examples/threads.fn.

Comments