The joy of iterators

Since I've been taking so many pot-shots at Arc I thought I'd post one of my own ideas so that people can shoot at me for a change. (Well, it's not really my idea, but it's an idea that I advocate.) I'll motivate this with a multi-step puzzle: first, write a function that can accept either a (linked) list or a vector an print out its elements. Here's one solution in Common Lisp:

(defun print-elements (thing)
  (etypecase thing
    (list (loop for element in thing do (print element)))
    (vector (loop for element across thing do (print element))))

This is not particularly elegant. The amount of repetition between the two clauses in the etypecase is pretty annoying. We need to copy almost the entire LOOP clause just so we can change "in" to "across". How can we make this prettier?

The usual fix for repetitive code is to use a macro, e.g.:

(defmacro my-loop1 (var keyword thing &body body)
  `(loop for ,var ,keyword ,thing do ,@body))

But this hardly helps at all (and arguably makes the situation worse):

(defun print-elements (thing)
  (etypecase thing
    (list (my-loop1 element in thing (print element)))
    (vector (my-loop1 element across thing (print element))))

We could do this:

(defmacro my-loop2 (keyword)
  `(loop for element ,keyword thing do (print element)))

(defun print-elements (thing)
  (etypecase thing
    (list (my-loop2 in)
    (vector (my-loop2 across))))

But that's not a very good solution either. We're not likely to get much re-use out of my-loop2, the code overall is not much shorter, and it feels horribly contrived.

Here's another attempt, taking advantage of the fact that Common Lisp has a few functions built-in that are generic to sequences (which include lists and vectors):

(defun print-elements (thing)
  (loop for i from 0 below (length thing) do (print (elt thing i))))

That looks better, but it's O(n^2) when applied to a list, which is not so good. And in any case it completely falls apart when we suddenly get a new requirement:

Extend print-elements-in-order so that it can accept a hash table, and prints out the hash-table's keyword-value pairs.

Now the first solution is suddenly looking pretty good, because it's the easiest to extend to deal with this new requirement. We just have to add another line to the etypecase:

(defun print-elements (thing)
  (etypecase thing
    (list (loop for element in thing do (print element)))
    (vector (loop for element across thing do (print element)))
    (hash-table (loop for key being the hash-keys of thing do (print (list key (gethash key thing)))))))

Now we get yet another requirement:

Extend print-elements so that it can accept a file input stream, and print out the lines of the file.

I'll leave that one as an exercise.

Now, the situation seems more or less under control here, with one minor problem: every time we get a new requirement of this sort we need to change the print-elements function. That's not necessarily a problem, except that if we have more than one programmer working on implementing these requirements we have to be sure that they don't stomp on each other as they edit print-elements (but modern revision-control systems should be able to handle that).

But now we get this requirement:

Extend print-elements so that it takes as an optional argument an integer N and prints the elements N at a time.

Now all our hard work completely falls apart, because the assumption that the elements are to be printed one at a time is woven deeply into the fabric of our code.

Wouldn't it be nice if the LOOP macro just automatically did the Right Thing for us, so that we could just write, e.g.:

(defun print-elements (thing &optional (n 1))
  (loop for elements in (n-at-a-time thing n) do (print elements)))

and be done with it? Can we make that happen? Yes, we can. Here's how:

(defconstant +iterend+ (make-symbol "ITERATION_END"))

(defmacro for (var in thing &body body)
  (with-gensym itervar
    `(let ( (,itervar (iterator ,thing)) )
   (loop for ,var = (funcall ,itervar)
          until (eq ,var +iterend+)
      ,@body))))

(defmethod iterator ((l list))
  (fn () (if l (pop l) +iterend+)))

(defmethod iterator ((v vector))
  (let ( (len (length v)) (cnt 0) )
    (fn () (if (< cnt len)
             (prog1 (elt v cnt) (incf cnt))
             +iterend+))))

(defun print-elements (thing)
  (for element in thing do (print element)))

The overall code is much longer than our original solution, but I claim that it is nonetheless a huge win. Why? Because it is so much easier to extend. In order to make print-elements work on new data types all we have to do is define an iterator method on that data type which returns a closure that conforms to the iteration protocol that we have (implicitly for now) defined. So, for example, to handle streams all we have to do is:

(define-method (iterator (s stream)) (fn () (read-char s nil +iterend+)))

We don't have to change any existing code. And in particular, we don't need to redefine print-elements.

Furthermore, we can now do this neat trick:

(defmacro n-of (form n)
  `(loop for #.(gensym "I") from 1 to ,n collect ,form))

(defun n-at-a-time (n thing)
  (let ( (iter (iterator thing)) )
    (fn () (let ((l (n-of (funcall iter) n)))
             (if (eq (car l) +iterend+) +iterend+ l)))))

It actually works:

? (for l in (n-at-a-time 2 '(1 2 3 4)) do (print l))

(1 2)
(3 4)
NIL
? (for l in (n-at-a-time 2 #(1 2 3 4)) do (print l))

(1 2)
(3 4)
NIL

Furthermore, n-at-a-time works on ANY data type that has an iterator method defined for it.

There's a fly in the ointment though. Consider this requirement:


Write a function that takes either a list or a vector of integers and destructively increments all of its elements by 1.


We can't do that using the iteration protocol as it currently stands, because it only gives us access to values and not locations. Can we extend the protocol so that we get both? Of course we can, but it's a tricky design issue because there are a couple of different ways to do it. The way I chose was to take advantage of Common Lisp's ability to let functions return multiple values. I extended the FOR macro to accept multiple variables corresponding to those multiple values. By convention, iterators return two values (except for the N-AT-A-TIME meta-iterator): the value, and a key that refers back to the container being iterated over (assuming that makes sense -- some data types, like streams, don't have such keys). This makes the code for the FOR macro and the associated ITERATOR methods quite a bit more complicated:

(defmacro for (var in thing &body body)
  (unless (sym= in :in) (warn "expected keyword 'in', got ~A instead" in))
  (with-gensym itervar
    `(let ( (,itervar (iterator ,thing)) )
       ,(if (consp var)
   `(loop for ,var = (multiple-value-list (funcall ,itervar))
          until (eq ,(fst var) +iterend+)
      ,@body)
   `(loop for ,var = (funcall ,itervar)
          until (eq ,var +iterend+)
      ,@body)))))

(define-method (iterator (v vector))
  (let ( (len (length v)) (cnt 0) )
    (fn () (if (< cnt len)
             (multiple-value-prog1 (values (elt v cnt) cnt) (incf cnt))
             +iterend+))))

(define-method (iterator (h hash-table))
  (let ( (keys (loop for x being the hash-keys of h collect x)) )
    (fn ()
      (if keys (let ( (k (pop keys)) ) (values k (gethash k h))) +iterend+))))

(defun n-at-a-time (n thing)
  (let ( (iter (iterator thing)) )
    (fn ()  (apply 'values (n-of (funcall iter) n)))))

Note that N-AT-A-TIME has actually gotten simpler since we no longer need to check for +iterend+. When the underlying iterator returns +iterend+ it just gets passed through automatically.

All this works in combination with another generic function called REF which is like ELT except that, because it's a generic function, can be extended to work on data types other than lists and vectors. The solution to the last problem is now:

(for (elt key) in thing do (setf (ref thing key) (+ elt 1)))

So we've had to do a lot of typing, but the net result is a huge win in terms of maintainability and flexibility. We can apply this code to any data type for which we can define an iterator and reference method, which means we can swap those types in and out without having to change any code. We can define meta-iterators (like N-AT-A-TIME) to modify how our iterations happen. (By default, the iterator I use for streams iterates over characters, but I have a meta-iterator called LINES that iterates over lines instead. It's easy to define additional meta-iterators that would iterate over paragraphs, or forms, or other semantically meaningful chunks.)

All this code, include the support macros (like with-gensym) is available at http://www.flownet.com/ron/lisp in the file utilities.lisp and dictionary.lisp. (There's lots of other cool stuff in there too, but that will have to wait for another day.)

UPDATE: I mentioned that iterators are not my idea, but didn't provide any references. There are plenty of them, but here are two to get you started if you want to read what people who actually know what they are talking about have to say about this:

http://okmij.org/ftp/Scheme/enumerators-callcc.html

http://okmij.org/ftp/papers/LL3-collections-enumerators.txt

Thanks to sleepingsquirrel for pointing these out.

I also realized after reading these that I probably should have used catch/throw instead of +iterend+ to end iterations.

Finally, it's worth noting that Python has iterators built-in to the language. But if it didn't you couldn't add them yourself like you can in Common Lisp. It can be done in Arc, but it's harder (and IMO less elegant) because ARC does not have generic functions, so you have to essentially re-invent that functionality yourself.