Skip to content

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.

3 Comments

  1. Ishmael Yavitz wrote:

    BTW, viewing your blog, if JavaScript is off, the code isn’t visible and one gets no warning that anything is amiss.

    Probably not the kind of feedback you’re looking for, but this post was way over my head. ;)

    Sunday, November 21, 2010 at 8:17 am | Permalink
  2. dasuxullebt wrote:

    Have you considered using cl-cont?

    Sunday, November 21, 2010 at 12:41 pm | Permalink
  3. Faré wrote:

    In philip-jose, I implemented co-routines and threads on top of arnesi’s call/cc library. Could easily be ported to delico, cl-cont, etc.

    Sunday, November 21, 2010 at 7:13 pm | Permalink

One Trackback/Pingback

  1. [...] easier without beer and after a good nights sleep.  Following up on last night’s defeat (see coroutines in common lisp), I re-read the documentation this morning and got my locks sorted [...]