List comprehension (Lisp)

From LiteratePrograms

List comprehensions are a very concise way to express functions that build lists out of generators. Haskell and Python, for example, have list comprehension support built in; here we will implement a list comprehension syntax for sequence types in Common Lisp using macros.

A list comprehension consists of an expression, a set of identifier-sequence pairs, and a set of guard expressions expressed in terms of the identifiers.

For example, in Haskell syntax, a list comprehension returning the list of all (x, y) pairs where x and y are in the range [0, 3] and x < y:

[ (x, y) | x<-[0,1,2,3], y <- [0,1,2,3], x < y]

And in python:

[(x, y) for x in [0,1,2,3] for y in [0,1,2,3] if x < y]

Now, the notation we'll use for our lisp list comprehensions is the following:

(comprehension expr 
	       ((var1 list1) (var2 list2) ... )
	       (predicate1 predicate2 ...))

So we could write the example comprehension above like this:

(comprehension (cons x y) 
	       ((x '(0 1 2 3)) (y '(0 1 2 3))) 
	       ((< x y)))

Now, we'll want to write a macro called comprehension. To do this we'll first see how we might translate a list comprehension into lisp by hand.

We have to iterate through the sequences in the order in which they are passed to the comprehension macro, binding each element in each sequence to its associated identifier: if these bindings satisfy the predicates, we evaluate expression and cons it into an accumulator. When we've iterated through all sequences, we reverse the accumulator and return it.

We'll use the feared loop macro to do this in a very straightforward manner. So our example list comprehension, translated into vanilla lisp by hand, might look like this:

(let ((accum (list)))
  (progn 
    (loop for x in '(0 1 2 3)
	  do (loop for y in '(0 1 2 3)
		   do (if (< x y) (push (cons x y) accum))))
    (nreverse accum)))

So we notice a pattern: we can translate a comprehension into lisp like this:

(comprehension expr 
	       ((var1 list1) (var2 list2) ... )
	       (predicate1 predicate2 ...))

rewrites to

(let ((accum (list)))
  (progn 
    (loop for var1 in list1
	  do (loop for var2 in list2 
		...
		   do (if (and predicate1 predicate2 ...)
			(push expr accum))))
    (nreverse accum)))

So, first we write a function that takes a list of (var list) forms and an expression and turns them into nested loops whose final do clause is the passed expression:

<<comprehension.lisp>>=
(defun make-loops (var-list-pairs last-loop-body)
  (if (endp var-list-pairs)
    last-loop-body
    (destructuring-bind ((var list) . therest) var-list-pairs
      `(loop for ,var in ,list do ,(make-loops therest last-loop-body)))))

Let's test it in the repl to see what it does:

[155]> (make-loops '((x '(1 2 3)) (y '(0 1 2 3))) 
		   '(if (< x y) (push (cons x y) accum)))
(LOOP FOR X IN '(1 2 3) DO
      (LOOP FOR Y IN '(0 1 2 3) DO (IF (< X Y) 
				       (PUSH (CONS X Y) ACCUM))))

Writing the macro is now trivial: we only have to create the context and then call our make-loops inside it. Of course, we use a gensym instead of the symbol accum to avoid unwanted variable capture:

<<comprehension.lisp>>=
(defmacro make-comprehension (expr vars-in-lists guards)
  (let ((accum (gensym)))
    `(let ((,accum (list)))
       (progn 
	 ,(make-loops vars-in-lists
		      `(if (and ,@guards)
			 (push ,expr ,accum)))
	 (nreverse ,accum)))))

And that's it. We have defined a simple macro that lets us conveniently write list comprehensions in common lisp. Let's test it with our example list comprehension:

[158]>(macroexpand-1 '(make-comprehension (cons x y) 
					  ((x '(0 1 2 3)) (y '(0 1 2 3))) 
					  ((< x y)))
(LET ((#:G3460 (LIST)))
 (PROGN
  (LOOP FOR X IN '(0 1 2 3) DO
   (LOOP FOR Y IN '(0 1 2 3) DO (IF (AND (< X Y)) (PUSH (CONS X Y) #:G3460))))
  (NREVERSE #:G3460))) ;
T
[159]>

It looks correct. Let's actually run it:

[159]>(make-comprehension (cons x y) 
			  ((x '(0 1 2 3)) (y '(0 1 2 3))) 
			  ((< x y))
((0 . 1) (0 . 2) (0 . 3) (1 . 2) (1 . 3) (2 . 3))

So we've added a simple list comprehension construct to Common Lisp.

But there is one glaring way this could be improved upon: instead of evaluating all the predicates in the innermost loop, we could evaluate them as soon as their arguments are bound. This might make enormous efficiency differences in some cases by obviating a lot of pointless looping. Let's use macros to gain clarity and efficiency at the same time. This requires a little more work (coming soon).

Download code