coroutines in common lisp

After spending awhile in python land, I wanted to have “yield” in lisp.  After a month or so of stewing, I decided to dive in tonight.  My first stab uses threads, not continuations to accomplish this.  I made that choice partially because I find the arnesi library intimidating (arnesi has continuations in there somewhere), and partially because I wanted to more practice with threads.

I ended up futzing with bordeaux-threads for a few hours, and eventually punted and used a library that had already solved these problems.  My basic test function was:

In retrospect, this may have been a bit pathological.  Virtually no time was spent anywhere, and so everything was happening pretty much at once.

My basic threading approach was to make a reader/writer pair:

  1. run the coroutine (writer) in a thread, and lexically bind yield using a flet such that calling yield set shared memory (with the appropriate locks)
  2. build a lambda (reader) that, when funcalled, waits for the thread to have a value ready, pulls it from shared memory and returns it (with the appropriate locks)

The “with the appropriate locks” bit killed me.  I spent a lot of time in deadlock, and had race conditions everywhere.  I ran into these issues:

  • race condition during startup where the writer thread would start too slowly, missing the notify from the reader to give me a value, and then get stuck waiting for the reader to notify
  • race condition at the end of the coroutine, where the writer thread wouldn’t die fast enough, and the reader would get stuck waiting for the writer to notify
  • many cases where I wanted to CONDITION-WAIT in one thread before I CONDITION-NOTIFY in another, but kept getting it backward.  Adding more layers of locks/condition variables seemed to just defer the problem to another level.

My initial bordeaux-threads version worked great if I ran it from the REPL (with 1+ second pauses for me to run the commands), but the race conditions screwed me when I put it all together.

After a few hours (and a few beers) of debugging, I decided to look at how chanl did it, which rapidly degraded into a chanl-based implementation.  This, of course, took 10m to write and worked great:

For reference, my last broken bordeaux-threads version was:

Fun stuff! Good to know I suck at threads, maybe I’ll take another try with less beer later. At least now I can browse simpy source with less envy.