An Extensible Iteration Facility

2025-06-17

1. Introduction

One of my favorite things about Python is its approach to iteration: Because the for-loop relies on a protocol, rather than elaborate syntax supporting a limited set of types, one can use a single construct to step over anything for which an iterator can be created. As a simple example, consider

>>> for i in [1,2,3]: print(i)
... 
1
2
3

The for loop is equivalent to

>>> xs = iter([1,2,3])
>>> while True:
...     try:
...         i = next(xs)
...         print(i)
...     except StopIteration:
...         break
... 
1
2
3

When an object has a __next__ method that either returns values or raises a StopIteration exception to signal exhaustion, we say that that object is an iterator. Among other uses, any iterator may be used in a for-loop or a comprehension, regardless of the source of the values (which may be infinite). Additionally, the looping syntax itself stays the same; this is in contrast to Common Lisp's loop, which requires different keywords to signal the type of sequence being iterated over.

2. Iterators

How can we bring this sensibility to our CL REPL? We can start by defining an iterator as a function of no arguments (called a thunk) that, when called, either returns a value or signals that there are no more values to be had.

(define-condition stop-iteration () ())

(defgeneric iter (seq))

We then define a handful of useful iterators:

(defmethod iter ((seq list))
  (lambda ()
    (guard seq)
    (pop seq)))

(defmethod iter ((seq vector))
  (let ((i 0))
    (lambda ()
      (guard (< i (length seq)))
      (let ((val (aref seq i)))
	(incf i)
	val))))

(defmethod iter ((seq stream))
  (lambda ()
    (handler-case
	(read-line seq)
      (end-of-file ()
	(guard nil)))))

where

(defun guard (pred &optional (condition 'stop-iteration))
  (unless pred
    (error condition)))

If we wildly assume that any thunk is suitable for use as an iterator,

(defmethod iter ((seq function)) seq)

then we can define

(defun range (left &optional (right nil right-supplied-p) (step 1))
  (let ((lo (if right-supplied-p left 0))
	(hi (if right-supplied-p right left)))
    (lambda ()
      (guard (or (not hi) (< lo hi)))
      (let ((x lo))
	(incf lo step)
	x))))

3. Loop `for` Great Justice

Finally, we extend the syntax just a bit:

(defmacro for ((var seq) &body body)
  (let ((iter-var (gensym)))
    `(let ((,iter-var (iter ,seq)))
       (handler-case
	   (loop for ,var = (funcall ,iter-var)
		 do ,@body)
	 (stop-iteration ())))))

We now have a looping facility that automatically does "the right thing" in a variety of circumstances:

CL-USER> (with-open-file (out "foo" :direction :output)
	   (for (i (range 10))
	     (for (j (range i))
	       (format out "* "))
	     (format out "~%")))
NIL
CL-USER> (for (line (open "foo"))
	   (format t "~a~%" line))

* 
* * 
* * * 
* * * * 
* * * * * 
* * * * * * 
* * * * * * * 
* * * * * * * * 
* * * * * * * * * 
NIL

4. Some Utilities

Now let's define some utilities. The first thing we might want is the ability to do mapping and filtering:

(defun mapiter (fn &rest seqs)
  (let ((iters (mapcar #'iter seqs)))
    (lambda ()
      (apply fn (mapcar #'funcall iters)))))

(defun filter (pred seq)
  (let ((iter (iter seq)))
    (lambda ()
      (loop for x = (funcall iter)
	    when (funcall pred x)
	      return x))))

Next up is the ability to concatenate multiple sequences:

(defun cat (&rest seqs)
  (infinicat seqs))

(defun infinicat (seqs)
  (let ((iters (mapiter #'iter seqs))
	(curr (iter nil)))
    (lambda ()
      (block next
	(loop do
	      (handler-case
		  (return-from next (funcall curr))
		(stop-iteration ()
		  (setf curr (funcall iters)))))
	(guard nil)))))

And occasionally we might want to interleave several sequences:

(defun mux (&rest seqs)
  (mapiter #'funcall (circular (mapcar #'iter seqs))))

where

(defun circular (xs)
  (nconc xs xs))

CL-USER> (for (x (mux (range 10)
		      "this is a test"
		      '(but this is not)))
	   (print x))

0 
#\t 
BUT 
1 
#\h 
THIS 
2 
#\i 
IS 
3 
#\s 
NOT 
4 
#\  
NIL

5. Generators and Ease of Expression

Consider a stream that has been partially run length encoded (RLE), such that

a sequence of characters ('~', '\0') becomes a single tilde
a sequence of characters ('~', N, D) becomes a run of D characters of length ord(N)
other characters are passed through without modification

So, "abc~\0def" expands to "abc~def", while "abc~\x04/def" expands to "abc////def".

This problem is perfectly doable with the tools we already have on hand:

(defun rle-decode (src)
  (let ((src (iter src)))
    (infinicat
     (lambda ()
       (block next
	 (let ((c (funcall src)))
	   (unless (eq c #\~)
	     (return-from next (list c)))
	   (let ((n (char-code (funcall src))))
	     (when (zerop n)
	       (return-from next (list #\~)))
	     (let ((d (funcall src)))
	       (mapiter (lambda (i)
			  (declare (ignore i))
			  d)
			(range n)))))))))))

CL-USER> (let ((s (format nil "abc~~~a/def" (code-char 40))))
	   (for (c (rle-decode s)) (format t "~a" c))
	   (format t "~%"))
abc////////////////////////////////////////def
NIL

However, we could implement this in Python like so:

def rle_decode(src):
    src = iter(src)
    for c in src:
	if c != '~':
	    yield c
	elif not (n := ord(next(src))):
	    yield '~'
	else:
	    d = next(src)
	    for i in range(n + 1):
		yield d

>>> ''.join(rle_decode('acd~\x28/def'))
'acd/////////////////////////////////////////def'

Invoking rle_decode produces an iterator backed by a function that generates values. Every time we call next on that iterator, execution of the generating function picks up at the beginning (on the very first call) or just after the most recent yield (for every subsequent call), and it continues until either the next encountered yield (in which case it produces a value for the caller) or the end of the function (implicitly raising StopIteration). The generator may yield values from any number of places in its body, yielding us considerable flexibility in how we write it.

In the case of rle_decode, that flexibility allows us to express the process of RLE decoding much more clearly. Meanwhile, the Lisp version operates by creating a series of sub-sequences, each corresponding to either single characters or expanded runs, and then concatenating them. Where the Python version permitted a very direct style, the Lisp version uses an invented intermediate form. While that intermediate view might be interesting for some application, here it is just a means to the end of expanding a stream of compressed data. It was necessary, though, because the function generating values for the iterator always starts at the beginning on each call; we cannot directly use progress through that function to mark generator state.

Creating the flexibility of expression that generators provide will be a task for another day. Until then, here's a silly version of Fizz Buzz.

(defun fizzbuzz (&optional n)
  (mapiter (lambda (&rest xs)
	     (some #'identity xs))
	   (circular '(nil nil nil nil nil
		       nil nil nil nil nil
		       nil nil nil nil fizzbuzz))
	   (circular '(nil nil fizz))
	   (circular '(nil nil nil nil buzz))
	   (range 1 n)))