Comparing LOOP and ITERATE

Published October 19th, 2008

Looping is the most common non-trivial construct in imperative programming, so having a domain language for generating iteration code is unquestionably useful. I’ll explore two options within Common Lisp:

  1. LOOP is a standard macro with an expressive syntax and built-in support for several iterative patterns. It’s acclaimed and criticized in equal portion.
  2. ITERATE is a second looping macro created outside of the standard as an answer to the problems and limitations of LOOP.

Superficially, the differences between them are few:

(loop for i from 0
      for el in '(a b c d e f)
      collect (cons i el))
=> ((0 . A) (1 . B) (2 . C) (3 . D) (4 . E) (5 . F)) 
 
(iter (for i from 0)
      (for el in '(a b c d e f))
      (collect (cons i el)))
=> ((0 . A) (1 . B) (2 . C) (3 . D) (4 . E) (5 . F))

The Common Lisp standard also includes the looping macros DO and DO*. They’re widely used but can be terse and obscure; in any case, I’m leaving them out of the comparison.

1. Views on LOOP

The following are the three most frequent criticisms of LOOP:

  1. It doesn’t look like Lisp. The pathological case is hash table iteration. I need to look this up every time:

    (loop for key being the hash-keys in *some-table*
              using (hash-value val)
          collect (list key val))

    As a general compromise, some developers use keyword syntax for LOOP forms, though it’s not a definite improvement:

    (loop :for counter :downfrom 20 :downto 0 :by 2
          :when (zerop (mod counter 3))
          :collect counter)
    => (18 12 6 0)
  2. Editors auto-indent LOOP poorly. I work for the preeminent employer of Lisp hackers, yet no one I know has an Emacs configuration which indents all corners of LOOP correctly. (That is, for my definition of correct; there’s no standard.)
  3. LOOP can behave unpredictably when for clauses interact in a certain way. However, in my experience this behaviour only presents itself in examples contrived to show it.

For these reasons and others, Paul Graham doesn’t recommend LOOP, and Peter Seibel remains neutral about it. But it has its place.

See also these articles:

2. The purpose of ITERATE

The ITERATE website makes two main claims:

  1. It’s extensible
  2. It helps editors auto-indent by having a more Lisp-like syntax

Both are true. ITERATE is as much a mini-language as LOOP, but its clauses look like, and frequently are, regular Lisp forms.

;; A LOOP example
(loop for i upto 20
      if (oddp i)
        collect i into odds
      else
        collect i into evens
      finally (return (values evens odds))) 
=> (0 2 4 6 8 10 12 14 16 18 20)
   (1 3 5 7 9 11 13 15 17 19)
 
;; The equivalent in ITERATE
(iter (for i from 0 to 20)
      (if (oddp i)
          (collect i into odds)
          (collect i into evens))
      (finally (return (values evens odds))))
=> (0 2 4 6 8 10 12 14 16 18 20)
   (1 3 5 7 9 11 13 15 17 19)

The IF above is not an ITERATE construct — it’s the normal Common Lisp operator. The LOOP if clause will be too, but only after a couple layers of macroexpansion.

Another example, harder to reproduce in LOOP:

(macrolet ((divisorp (n m)
             `(zerop (mod ,n ,m))))
  (iter (for i from 0 to 30)
        (cond ((divisorp i 2)
               (collect i into twos))
              ((divisorp i 3)
               (collect i into threes))
              ((divisorp i 5)
               (collect i into fives)))
        (finally (return (values twos threes fives)))))
=> (0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30)
   (3 9 15 21 27)
   (5 25)

It’s true that distinguishing an ITERATE form from a regular form is less straightforward than it is with LOOP, but in practice the distinction is rarely important. A benefit of the intermixing is that ITERATE clauses such as collect may appear arbitrarily deep in the body, in contrast to LOOP where they must fall within the mini-language portion.

Also: for comparison with LOOP’s egregious hash table iteration syntax in (1), here is the cleaner equivalent in ITERATE:

(iter (for (key val) in-hashtable *some-table*)
      (collecting (list key val)))

ITERATE’s extensibility is discussed in-depth in a second article. Through some means, LOOP can apparently be extended, but it’s not done often or easily. SBCL, at least, provides LOOP extension hooks, but using them ties you to that compiler.

3. Comparing looping clauses

In most cases, ITERATE is a superset of functionality.

*Accumulation*

LOOP offers collecting, nconcing, and appending. ITERATE has these and also adjoining, unioning, nunioning, and accumulating.

(iter (for el in '(a b c a d b))
      (adjoining el))
=> (A B C D)
 
(iter (for lst in '((a b c) (d b a) (g d h)))
      (unioning lst))
=> (A B C D G H)

accumulating is an accumulator builder. Here’s how to implement unioning:

(iter (for lst in '((a b c) (d b a) (g d h)))
      (accumulating lst by #'union))
=> (A B C G D H)
*Reduction*

LOOP has summing, counting, maximizing, and minimizing. ITERATE also includes multiplying and reducing. reducing is the generalized reduction builder:

(iter (with dividend = 100)
      (for divisor in '(10 5 2))
      (reducing divisor by #'/ initial-value dividend))
=> 1

A simple macro to lessen code noise:

(defmacro dividing (num &keys (initial-value 0))
  `(reducing ,num by #'/ initial-value ,initial-value))
 
(iter (for i in '(10 5 2))
      (dividing i :initial-value 100))
=> 1

(Obviously the above is better stated (/ 100 10 5 2), but imagine leveraging this clause in a more complicated loop.)

The ITERATE package provides a macro, DEFMACRO-CLAUSE, to create new clauses more idiomatically; read more about it in the follow up article.

For comparison, this article describes one way of writing new reduction constructs for LOOP.

*Boolean aggregation*

These are the same in both: always, never, thereis, corresponding to the functions EVERY, NOTANY, and SOME. ITERATE can specify both always and never in the same loop, but not to much purpose.

*Finding*

There is no analogue for finding in LOOP. The ITERATE website provides a good use case:

(iter (for lst in '((a) (b c d) (e f)))
      (finding lst maximizing (length lst)))
=> (B C D) 
 
;; The rough equivalent in LOOP:
(loop with max-lst = nil
      with max-key = 0
      for lst in '((a) (b c d) (e f))
      for key = (length lst)
      do
      (when (> key max-key)
        (setf max-lst lst
              max-key key))
      finally (return max-lst))
=> (B C D)

finding is a pattern for operating on the result of one expression based on the result of another.

*Control flow*

ITERATE has next-iteration, which is like continue in C or next in Perl. It’s a major inconvenience of LOOP that it doesn’t have this construct. ITERATE also offers the (if-first-time then else) form and the first-iteration-p var for conditioning on the initial iteration in cases which aren’t covered by patterns.

*Destructuring*

In a for clause, ITERATE and LOOP have the same syntax and same destructuring capabilities. However, ITERATE can also “destructure” multiple-value returns:

(for (values (a . b) c d) = (three-valued-function ...))

The consing equivalent in LOOP:

for ((a . b) c d) = (multiple-value-list
                     (three-valued-function ...))

LOOP can destructure within a with clause, but ITERATE cannot. The manual cites implementation difficulty.

*Parallel binding*

This is what DO does and DO* doesn’t, and it’s strictly unsupported in ITERATE. LOOP includes this optionally with an and clause:

(loop for el in '(a b c d e)
      and prev-el = nil then el
      collect (list el prev-el))
=> ((A NIL) (B A) (C B) (D C) (E D))

The ITERATE documentation states:

“My view is that if you are depending on the serial/parallel distinction, you are doing something obscure”

I have to agree. Also, the useful case of parallel binding in the LOOP example above can be accomplished with another ITERATE concept, variable backtracking:

(iter (for el in '(a b c d e))
      (for prev-el previous el)
      (collect (list el prev-el)))
=> ((A NIL) (B A) (C B) (D C) (E D))

4. Documentation

There are many resources out there for learning to use LOOP. The LOOP for Black Belts chapter of Practical Common Lisp is my favourite. The Common Lisp Quick Reference is also excellent in its treatment of LOOP.

For ITERATE, there really is only the manual, but it’s thorough. It includes another comparison of LOOP and ITERATE. There’s also a DISPLAY-ITERATE-CLAUSES function which comes with the package and can provide dynamic assistance:

(display-iterate-clauses)
INITIALLY    Lisp forms to execute before loop starts
AFTER-EACH   Lisp forms to execute after each iteration
ELSE         Lisp forms to execute if loop is not entered
FINALLY      Lisp forms to execute after loop ends
;; ...
 
(display-iterate-clauses 'multiply)
MULTIPLY &OPTIONAL INTO   Multiply into a variable

It’d be great to see this integrated into SLIME.

5. Obtaining ITERATE

It’s easiest to do this with ASDF-Install. To get ITERATE working in a repl or scratch buffer:

;; (Example below in SBCL.)
CL-USER> (asdf:oos 'asdf:load-op :ASDF-INSTALL)
;; stuff
 
CL-USER> (asdf-install:install "ITERATE")
;; lots of stuff
;; (only needs to be done once.)
 
CL-USER> (defpackage "MY-PACKAGE" (:use "CL" "ITERATE"))
 
#<PACKAGE "MY-PACKAGE">
CL-USER> (in-package "MY-PACKAGE")
 
#<PACKAGE "MY-PACKAGE">
MY-PACKAGE> (iter ...)  ;; etc.

6. Conclusion

In almost every case, ITERATE is more convenient to use and more powerful than LOOP. If you’re in control of your own project and aren’t religiously partial to DO (or functional programming), ITERATE is worth a try.

Thanks to Richard Kreuter, Alec Berryman, and John O’Laughlin for their comments and suggestions.

Further discussion on the programming reddit


8 Responses to “Comparing LOOP and ITERATE”

  1. Sam Says:

    Arguably, the “does not look like Lisp”-ness of loop is a feature, not a bug. Issues of style aside, rewriting a standard feature makes me a bit nervous. The new functionality seems like good stuff, though.

  2. Stephen Bach Says:

    Certainly a case could be made. To continue the point, compare these two simple list comprehensions:

    (loop for i upto 5 collect i)
    
    (iter (for i from 0 to 5) (collect i))
    

    The LOOP example is obviously clearer for lack of parentheses.

  3. Olivier Drolet Says:

    Stephen, I have never found the abundance of parentheses to impede clarity. On the contrary, in the example you give, I find the parens help me see the structure when glancing, and do not detract when I need to read the code attentively. YMMV.

  4. Daniel Radetsky Says:

    Stephen: I don’t think your example of the simple loops (I’m not sure they are properly called “List Comprehensions”, but whatever) is a very good one for a number of reasons:

    1. I’ve never seen anyone write an iter-loop on one line like that. It’s always written with the accumulator directly below the driver. In this case, the extra parentheses are beside the point: it’s easier (for humans) to parse the code because the what-are-we-iterating-over and the what-are-we-doing parts are separate.
    2. Comparing simple loops is uninformative. Both of those loops are so simple that you don’t need loop or iter. dotimes is plenty. The only proper test of an iteration construct is whether it can be used to write complicated loops effectively. After all, you don’t need any iteration constructs in scheme, as recursion is fine for relatively simple loops.

    Your point that “clauses may appear arbitrarily deep in the body” is a good reason to prefer iterate for complex loops, but it is only for complex loops that you care about powerful iteration constructs.

  5. Stephen Bach Says:

    Olivier: past a certain point, I agree. I would only prefer loop if the whole form could fit comfortably on a single line.

    Daniel, re: your second reason, I’d argue that a DOTIMES loop would be less clear, as that list would probably be collected using the longer push-nreverse idiom:

    (let (lst)
      (dotimes (i 5)
        (push i lst))
      (nreverse lst))
    

    Otherwise, I agree with you.

  6. Hagen Ladwig Says:

    Thanks for the parallel binding comment. I never use DO. Sometimes I tried and always had to change it to a DO*; I thought I was missing some point and kept trying from time to time, waiting for enlightenment.

  7. Stephen Bach Says:

    Hagen, happy to help. 🙂

  8. items.sjbach.com » Extending the ITERATE macro Says:

    […] a previous article I gave an overview of ITERATE but punted on showing its best feature, the ability to extend it to support new iteration […]