My toy Lisp [fn](https://github.com/gnoack/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](https://github.com/gnoack/fn/blob/master/examples/threads.fn#L29)
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.

<figure>

```pikchr
fill = lightblue;
boxwid = 1cm;
boxht = 0.5cm;
lineht = 0.7cm;

up;
box "bar";
arrow "caller" aligned above small;
box "foo";
arrow "caller" aligned above small;
box "main";

right;
move from 3rd box.ne \
  right 3cm down 0.4cm;
SFC: [
    fill = bisque;
    boxwid = 3cm;
    down;
    box ht 2.5*boxht "information to" "resume execution of" "the calling function"
    box ht 2*boxht "values of local" "variables and arguments"
];
SF: box at SFC wid SFC.wid+0.5cm ht SFC.ht+0.5cm behind SFC;
text at SF.n "stack frame (simplified)" above;
line dotted from 1st box.se to SF.sw chop;
line dotted from 1nd box.ne to SF.nw chop;
```

<figcaption>A conventional call stack</figcaption>
</figure>

<div class="sidenote">
Stack frames are on the heap in fn.
</div>

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](https://github.com/gnoack/fn/blob/def2f2164f708df2980364f8f1495e94d0df8690/runtime/interpreter.c#L154).

<div class="sidenote">
Functions can get a handle on their own stack frame
</div>

Additionally, *fn* has a natively implemented helper called
[`$get-frame`](https://github.com/gnoack/fn/blob/def2f2164f708df2980364f8f1495e94d0df8690/runtime/primitives.c#L311).
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:

```scheme
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.

<figure>

```pikchr
fill = lightblue;
color = black;
boxwid = 0.8cm;
boxht = 0.5cm;
linewid = 0.6cm;
lineht = 0.5cm;

right;
"pop out" "(resume)";
arrow <-;
box;
up;
[
    arrow; B: box wid 0.6cm ht 0.4cm;
    arrow; box same;
    arrow; box same;
    line invis from 3rd last box.sw to last box.nw "next to be resumed" aligned above;
];
move to last box.e;
right;
box;
up;
[
    arrow; box wid 0.6cm ht 0.4cm;
    arrow; box same;
];
move to last box.e;
right;
box;
up;
[
    arrow; box wid 0.6cm ht 0.4cm;
    arrow; box same;
    arrow; box same;
];
move to last box.e;
right;
box;
up;
[
    arrow; box wid 0.6cm ht 0.4cm;
    arrow; box same;
];
move to last box.e;
right;
arrow <-;
"push in" "(suspend)";
```

<figcaption>A queue of suspended call stacks</figcaption>
</figure>

<div class="sidenote">
Starting new coroutines
</div>

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.

```scheme
(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

<div class="sidenote">
In some languages, <tt>next-thread!</tt> would be called <tt>yield</tt>
</div>

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.

<figure>

```pikchr
fill = lightblue
boxwid = 1cm
boxht = 0.5cm
lineht = 0.5cm

up
Y:  box "next-thread!" wid 1.6cm
OA: spline from 0.2cm left of Y.n \
      left 0.5cm up 0.3cm \
      then up 0.5cm \
      ->
S1: box; arrow; box; arrow; box
    line color red from 0.5cm left of OA to 0.2cm right of OA
    line color red from 0.2cm south of last line.start \
                   to 0.2cm north of last line.end
    text color red at last line.end " 1." ljust

NA: spline dashed color mediumseagreen \
      from 0.4cm right of Y.n \
      then right 1.1cm up 0.4cm \
      then up 0.4cm \
      -> "2." above
    box; arrow; box; arrow; box
```

<figcaption>next-thread! returns into a different call stack than it was called from</figcaption>
</figure>

`next-thread!` is implemented as follows:

```scheme
(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`](https://github.com/gnoack/fn/blob/master/examples/threads.fn).