Sunday, January 15, 2017

coroutine iters in Common Lisp


This post describes an implementation of iterators in Common Lisp that uses coroutines based on conditions and restarts. Going through the motions one more time brought up memories and pain from past iterative experiences in various languages, it's clearly something we are still in the process of figuring out. The worst anti pattern I've been forced to deal with so far is Java's Iterables/Iterators/Streams mess; where each API got some parts right and completely forgot about the others. At least having no extensible protocol for iteration is better than having three, we're off to a good start.


First of all, extension and use of iterators has to be trivial; otherwise we'll find more convenient ways around. This is the reason you'll find most Common Lisp libraries consing lists and/or writing custom DO-macros, even though it's clearly the opposite of bottom up. It's with iterating as with testing; they are stepping stones to the point where real problem solving begins; and they need to be trivial or they will get jumped over.


Ideally, extending the iterator protocol shouldn't take more than calling into the library on iteration; the less ceremony, coupling and restrictions, the better. And iterators are not allowed to randomly fail above a certain number of items, like consing lists inevitably does.


Besides support for, wait for it, iterating; I prefer as few mentions of iterators as possible in user code. It's low level plumbing; a platform that allows building more interesting algorithms on top, and I want user code to be about those algorithms.

the holy grail

The holy grail is an extensible iterator with above properties that doesn't require cutting algorithms into small pieces and spoon feeding it. Unfortunately; implementing simple, fast and portable coroutines is often tricky business; and Common Lisp is no exception. I briefly entertained the idea of using cl-cont as a foundation, but it lacks the performance and simplicity I'm looking for. Which is when I remembered that Common Lisp supports conditions and restarts; a few macros on top to create the illusion of iterating and that might actually work. And it does. It's still not quite as fast as I would like, around 10x slower than consing lists; but since conditions are first class citizens in Common Lisp, their performance is on enough tables already. (Update 21/1 - I managed to triple performance by adding user specified batch size to reduce the number of call stack traversals, the details are in the repo). Above all, the implementation is both trivial and portable compared to available options.



The following examples are from cl4l's table and index packages, both are included to better illustrate the amount of ceremony involved in hooking into the iterator protocol. Notice how iterators are completely independent from library code except for calls to '(iter-yield ...)'. The main reason DO-macros are provided is to help with unpacking items returned from the iterator, the rest is delegated to the extension helper macro '(do-iter ...)'. Either macro could deal with unpacking any iterator with the same item encoding.


Really, that's it; once you're able to cut to the core of any problem, that's about as complex as it will look. It's all equations in the end.

A full implementation of these ideas and more may be found here.
peace, out