dmitry_vk's notes

Making iterators in Lisp

I've been curious about making iterators in Lisp. Python and C# have convenient ways to make a user-defined iterator. Python implements this with the generators and the C# uses the iterator blocks.

An example in Python:

def make_range(a,b):
    for x in xrange(a,b):
        yield x

for x in make_range(10,20):
    print x

And the sample example in C#:

static IEnumerable<int> make_range(int a, int b)
{
    for (i = a; i < b; ++i)
        yield return i;
}

foreach (int x in make_range(10,20))
    Console.WriteLine(x);

In both cases, the compiler takes care to save the state of the generator function and to restore this state upon the return to the iterator. There are some caveats related to exception handling and other non-local exits. For example, C# does not allow to place yield inside the try-block.

Lisp does not have language-level generators. Generators can be implemented using continuations, but Common Lisp lacks them either – although Scheme has. With the help of macros, they can be added to the language. That's what the cl-cont library does. Actually, these continuations have the same caveat that non-local control flow is not supported such as catch, throw, unwind-protect, or progv.

Also, Lisp has the iterate library which adds the iter which is a powerful and extensible construct to make various loops. iterate extensions are macros that generate the code necessary to enumerate elements of something. But that's less convenient than having generators (like in Python) due to the necessity to store state and suspend and resume the iteration.

Therefore we will try to augment the iterate package so that it is possible to use generators and we will write the macro to create said generators.

Here's what the end result will look like:

(defiterator range-iterator (a b)
  (iter (for i from a below b)
	(yield-return i)))

(iter (for i iterating (range-iterator 10 20))
      (format t "~A~%" i))

And this is the implementation to make this possible:

(defmacro defiterator (name (&rest args) (&body body))
  `(defun ,name (,@args)
    (macrolet ((yield-return (v) `(let/cc k (values ,v k)))
      (yield-break () '(let/cc k (declare (ignore k)) nil)))
        (lambda ()
          (with-call/cc
            ,body)))))

(defmacro-driver (FOR var ITERATING iterator)
  (let ((iterator-name (gensym "ITERATOR-"))
    (th (gensym))
    (nx (gensym))
    (kwd (if generate 'generate 'for)))
    `(progn
      (with ,iterator-name = ,iterator)
      (,kwd ,var next (multiple-value-bind (,th ,nx) (funcall ,iterator-name)
        (unless ,nx (terminate))
        (setf ,iterator-name ,nx)
        ,th)))))

Such implementation is not the most optimal or the best but just a proof of concept.

Iterator that is defined like this works as follows. The function defined by defiterator returns an iterator. An iterator is a function that either returns the current value and the function to call next or NIL which signals that the iteration is finished.

References: