Loop v Iterate

Learning lisp, I learned loop. It looks a bit strange, but there are plenty of places on the internet to view examples because it is in the language. See, e.g.

http://www.ai.sri.com/pkarp/loop.html.

http://www.unixuser.org/~euske/doc/cl/loop.html,

http://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node235.html,

http://www.gigamonkeys.com/book/loop-for-black-belts.html,

http://sandbox.mc.edu/~bennet/cs231/examples/loops.html, etc.

Occasionally I would see complaints and suggestions to use iterate (sometimes shortened to iter) instead. See, e.g. http://items.sjbach.com/211/comparing-loop-and-iterate,

http://common-lisp.net/project/iterate/doc/Don_0027t-Loop-Iterate.html. Then I started running into libraries in quicklisp that actually used iter and, in order to understand the libraries, I needed to learn iter.

So, what do you do if you are me? Compare the two. So, I do.

Quick Summary

Loop is in the language. You do not have to add a library. It is also fractionally faster. On the other hand..... iter is better at everything else. And I mean everything else.

Basic Introduction

Let us start at the beginning. Take a very simple example and compare the two forms. (I am going to assume that we are using the iterate package so that I do not have to prefix the package name in front of the iter function in every example).

loop for i in '(0 2 4 555 6)

      do (format t " ~a " i))

 0  2  4  555  6

 (iter (for i in '(0 2 4 555 6))

      (format t " ~a " i))

0  2  4  555  6

We already know that loop and iter create locally scoped variables; i in the above case.

Looking at the code, Iter puts parens around the for clause and drops the "do". Looks more lispy and I often catch myself forgetting to type the "do" in loop. One person referred to loop in lisp as half lisp, half pascal.

In timing this basic loop, loop seemed to be 3% faster on my sbcl box than iter. Is iter worth it?

Local Variables

Both loop and iter create locally scoped variables. Iter throws parens around the creation of each, making it more like (let ((x 1)(y 2)(z 3)). See, for example, this next group which actually creates three local variables, looping through a list and assigning each member sequentially to the variable x, creating a local variable y which is calculated based on the value of x and finally local variable z which is counting where we are in the loop.

(loop for x in '(1 4 9 13)

      for y = (* x 2)

      counting x into z

      collect (list x y z))

((1 2 1) (4 8 2) (9 18 3) (13 26 4))

(iter (for x in '(1 4 9 13))

      (for y = (* x 2))

      (counting x into z)

      (collect (list x y z)))

((1 2 1) (4 8 2) (9 18 3) (13 26 4))

(loop for i

      in '(3 8 73 4 -5)

      minimize i into smallest

      maximize i into biggest

      finally

      (return

       (values smallest biggest)))

-5

(iter (for i in '(3 8 73 4 -5))

      (minimize i into smallest)

      (maximize i into biggest)

      (finally (return (values smallest biggest))))

Destructuring

Destructuring is the act of binding a set of variables to a set of

values. Loop and iter allow you to do this in parallel with each iteration.

(loop for (a b) on '(1 3 5 2 7 9)

      collect  (list a b))

((1 3) (3 5) (5 2) (2 7) (7 9) (9 NIL))

(iter (for (a b) on '(1 3 5 2 7 9))

      (collect  (list a b)))

((1 3) (3 5) (5 2) (2 7) (7 9) (9 NIL))

(loop for (a b) in '((1 3) (5 18) (9 -3))

      collect  (list b a))

((3 1) (18 5) (-3 9))

(iter (for (a b)  in '((1 3) (5 18) (9 -3)))

      (collect  (list b a)))

((3 1) (18 5) (-3 9))

(loop for (a b) on '(1 3 5 2 7 9) while b

      collect (+ a b))

(4 8 7 9 16)

(iter (for (a b) on '(1 3 5 2 7 9)) (while b)

      (collect (+ a b)))

(4 8 7 9 16)

(loop for (x . y) in '((1 . 1) (2 . 4) (3 . 9))

      collect y)

(1 4 9)

(iter (for (x . y) in '((1 . 1) (2 . 4) (3 . 9)))

      (collect y))

(1 4 9)

As

(loop as x from 5 to 10

      collect x)

(5 6 7 8 9 10)

(iter (as x from 5 to 10)

      (collect x))

(5 6 7 8 9 10)

With

(loop with x = (+ 1 2) repeat 5

      do (format t "~a " x))

3 3 3 3 3

(iter (with x = (+ 1 2))

      (repeat 5)

      (format t "~a " x))

3 3 3 3 3

Files and Streams

Iter can iterate over the contents of a file or stream using the "in-file" or "in-stream" clause.

Package-Symbols

Did you know that you can loop through package symbols?

(loop for x being the  external-symbols in :iter do (format t "~a " x))

MULTIPLY DISPLAY-ITERATE-CLAUSES LEAVE APPENDING THEREIS UNTIL COLLECT

IF-FIRST-TIME TERMINATE NEVER ACCUMULATE ACCUMULATING INITIALLY MULTIPLYING

DEFMACRO-DRIVER MAXIMIZE ELSE MINIMIZING REDUCING ITERATE AFTER-EACH FIRST-TIME-P

AS UNIONING FINALLY-PROTECTED NEXT FINISH DEFSYNONYM DSETQ NUNIONING COLLECTING

NEXT-ITERATION ITER GENERATE MAXIMIZING DEFCLAUSE-SEQUENCE FINALLY ADJOINING

NCONCING WHILE DECLARE-VARIABLES MINIMIZE COUNTING FIRST-ITERATION-P FINDING

SUM FOR REPEAT WITH SUMMING DEFMACRO-CLAUSE IN GENERATING ALWAYS

(iter (for x in-package :iter external-only t)

      (format t "~a " x))

MULTIPLY DISPLAY-ITERATE-CLAUSES LEAVE APPENDING THEREIS UNTIL COLLECT

IF-FIRST-TIME TERMINATE NEVER ACCUMULATE ACCUMULATING INITIALLY MULTIPLYING

DEFMACRO-DRIVER MAXIMIZE ELSE MINIMIZING REDUCING ITERATE AFTER-EACH FIRST-TIME-P

AS UNIONING FINALLY-PROTECTED NEXT FINISH DEFSYNONYM DSETQ NUNIONING COLLECTING

NEXT-ITERATION ITER GENERATE MAXIMIZING DEFCLAUSE-SEQUENCE FINALLY ADJOINING

NCONCING WHILE DECLARE-VARIABLES MINIMIZE COUNTING FIRST-ITERATION-P FINDING

SUM FOR REPEAT WITH SUMMING DEFMACRO-CLAUSE IN GENERATING ALWAYS

Iteration Control

Both loop and iter have all the normal iteration controls you might expect: while, until, when, if, etc.

While

(loop for i in '(0 2 4 555 6)

      while (evenp i)

      do (format t " ~a " i))

0 2 4

(iter (for i in '(0 2 4 555 6))

      (while (evenp i))

      (format t " ~a " i))

0 2 4

There really is not anything special here. Iter just looks more lispy.

Until (early termination)

(loop for i in '(1 2 4 555 6)

      until (evenp i)

      do (format t " ~a " i))

(iter (for i in '(1 2 4 555 6))

      (until (evenp i))

      (format t " ~a " i))

When

Look at one of the locally scoped variables and do something if the

when clause is true:

(loop for x in '(1 3 4 23 22 8)

                    when (evenp x)

                         do (format t "Even: ~a " x)

                    when (oddp x)

                         do (format t "Odd: ~a " x))

Odd: 1 Odd: 3 Even: 4 Odd: 23 Even: 22 Even: 8

(iter (for x in '(1 3 4 23 22 8))

                    (when (evenp x)

                          (format t "Even: ~a " x))

                    (when (oddp x)

                          (format t "Odd: ~a " x)))

Odd: 1 Odd: 3 Even: 4 Odd: 23 Even: 22 Even: 8

If - Else

Here we start to see some differences. "If" is not an issue - "Else" is where things start to get interesting.

(loop for x in '(1 3 4 23 22 8)

                    if (evenp x)

                    do (format t "Even: ~a " x)

                    else if (oddp x)

                    do (format t "Odd: ~a " x))

Odd: 1 Odd: 3 Even: 4 Odd: 23 Even: 22 Even: 8

(iter (for x in '(1 3 4 23 22 8))

                    (if (evenp x)

                        (format t "Even: ~a " x)

                        (if (oddp x)

                        (format t "Odd: ~a " x))))

Odd: 1 Odd: 3 Even: 4 Odd: 23 Even: 22 Even: 8

Ok. That works, but we did not use "else" in the iter version. What

happens if we use "else" in the iter version?

(iter (for x in '(1 3 4 23 22 8))

                    (if (evenp x)

                        (format t "Even: ~a " x)

                        (else (if (oddp x)

                                  (format t "Odd: ~a " x)))))

Even: 4 Even: 22 Even: 8

Ok. I did not expect that. What happened?

http://common-lisp.net/project/iterate/doc/Problems-with-Code-Movement.html#Problems-with-Code-Movement

explains that "else" and a few other terms are subject to code movement resulting in variable shadowing problems. Let's try something. These are macros, so ...

(macroexpand-1 '(iter (for x in '(1 3 4 23 22 8))

                      (if (evenp x) (format t "Even: ~a " x)

                          (else (format t "In Else: ~a " x)))))

(LET* ((#:LIST344 NIL) (X NIL) (#:ELSE345 T))

  (BLOCK NIL (TAGBODY (PROGN (SETQ #:LIST344 (QUOTE (1 3 4 23 22 8))))

                      LOOP-TOP-NIL

                      (PROGN (IF (ENDP #:LIST344) (GO LOOP-END-NIL))

                             (SETQ X (CAR #:LIST344))

                             (SETQ #:LIST344 (CDR #:LIST344))

                             (IF (EVENP X) (FORMAT T "Even: ~a " X)

                                           (SETQ #:ELSE345 NIL)))

                      (PROGN) (GO LOOP-TOP-NIL)

                              LOOP-END-NIL

                              (PROGN (WHEN #:ELSE345 (FORMAT T "In Else: ~a " X))))

         NIL))

Even though it initially looked like the else clause was within the if clause, it really was not, the evenp test set else to nil and the else function did not get called. Consider the following from the

iterate test suite:

(iter (for i below -3)

(else (return 2)))

According to the documentation, the &rest forms following else are placed in the epilogue section of the loop where they are executed if this else clause is never met during execution of the loop and the loop terminates normally. Basically, in iter, do no think that the else clause has anything to do with an explicit if clause earlier in the function. It really has a different meaning.

(iter (for x in '(1 3 4 23 22 8))

                    (if (evenp x) (format t "Even: ~a " x)

                        (format t "Odd: ~a " x)))

Odd: 1 Odd: 3 Even: 4 Odd: 23 Even: 22 Even: 8

We now get the expected result.

In

This was actually where we came in.

(loop for i in '(100 20 3) sum i)

(iter (for i in '(100 20 3))

      (sum i))

By

(loop for i from 6 to 8 by 2

      sum i)

(iter (for i from 6 to 8 by 2)

      (sum i))

Remember, you do not need to increment or decrement by whole integers

(loop for i from 3.0 downto 1.0 by 0.5

      do (print i))

(iter (for i from 3.0 downto 1.0 by 0.5)

      (print i))

Note that loop can also use the term "upto" here, but iter does not have that synonym.

Below

(loop for i from 1 below 5 by 2

      do (print i))

(iter (for i from 1 below 5 by 2)

      (print i))

Above

(loop for i from 3 above 1

      do (print i))

(iter (for i from 3 above 1)

      (print i))

Then

We have a bit more of a difference in how to use the term "then". Loop can use an equal sign as the initial assignment, but iter uses the term "initially" instead.

(loop repeat 5 for x = 10.0 then (/ x 2)

      collect x)

(10.0 5.0 2.5 1.25 0.625)

(iter (repeat 5)

      (for x initially 10.0 then (/ x 2))

      (collect x))

(10.0 5.0 2.5 1.25 0.625)

Are you bored yet? Have you picked up the basic pattern difference?

On

It took me an example to understand the use of the term on in this context. Essentially, the new variable created is set to successive sublists of the list provided.

(loop for i on '(1 2 3)

      do (print i))

(1 2 3)

(2 3)

(3)

(iter (for i on '(1 2 3))

      (print i))

From

(loop as x from 5 to 10 collect x)

(5 6 7 8 9 10)

(iter (as x from 5 to 10)

      (collect x))

(5 6 7 8 9 10)

Downfrom and Upfrom

Important: iter's use of downfrom and upfrom does not allow an explicit end, so you must use a return clause. E.g.

(loop for i downfrom 10 to 8

      do (print i))

(iter (for i downfrom 10)

      (print i)

      (when (= 8 i) (return "i")))

(loop for i upfrom 10 to 12

      do (print i))

(iter (for i upfrom 10)

      (print i)

      (when (= 12 i)

        (return "i")))

Downto and Upto

Loop uses "downto" and "upto" but while iter uses "downto" because of the directionality, iter just uses "to" for normal iteration.

(loop for i from 10 downto 8

      do (print i))

(iter (for i from 10 downto 8)

      (print i))

(loop for i from 10 upto 12

      do (print i))

(iter (for i from 10 to 12)

      (print i))

Both can control the increments by the term "by".

Across

Loop uses the term "across" to iterate through arrays. Iter uses "in-vector".

(loop for i across #(100 20 3)

      sum i)

(iter (for i in-vector #(100 20 3))

      (sum i))

Collect

(loop for x in '( 1 3 5 )

      collect (+ 1 x))

(2 4 6)

(iter (for x in '( 1 3 5 ))

      (collect (+ 1 x)))

(2 4 6)

From x to y

(loop for i from 0 to 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)

loop could also do: for i upto 20

iter is explicit: for i from 0 to 20

Initially

(loop initially

      (format t "~a " 'loop-begin)

      for x below 3

      do (format t "~a " x))

LOOP-BEGIN 0 1 2

(iter (initially (format t "~a " 'loop-begin))

      (for x below 3)

      (format t "~a " x))

LOOP-BEGIN 0 1 2

Always

(loop for x in '(foo 2)

      always (numberp x))

NIL

(iter (for x in '(foo 2))

      (always (numberp x)))

Never

(loop for x in '(foo 2)

      never (numberp x))

NIL

(iter (for x in '(foo 2))

      (never (numberp x)))

Thereis

(loop for x in '(foo 2)

      thereis (numberp x))

(iter (for x in '(foo 2))

      (thereis (numberp x)))

Named

(loop named outer for i below 10

      do (progn (format t "~a" "outer")

             (loop named inner for x below i

                   do (format t " ~a ~%" " **inner ~%")

                   when (= x 2) do

                   (return-from outer 'kicked-out-all-the-way))))

outerouter  **inner ~%

outer  **inner ~%

  **inner ~%

outer  **inner ~%

  **inner ~%

  **inner ~%

KICKED-OUT-ALL-THE-WAY

(iter outer (for i below 10)

      (progn (format t "~a" "outer")

             (iter inner (for x below i)

                   (format t " ~a ~%" " **inner ~%")

                   (when (= x 2)

                     (return-from outer 'kicked-out-all-the-way)))))

outerouter  **inner ~%

outer  **inner ~%

  **inner ~%

outer  **inner ~%

  **inner ~%

  **inner ~%

KICKED-OUT-ALL-THE-WAY

I have to admit after using lisp for awhile, that naked "when" without parentheses in the loop version makes me uncomfortable.

Different Kinds of Sequences

Strings

Here is some iter can do that loop cannot. Note the use of the term "in-string" to indicate what kind of sequence iter needs to be dealing with.

(iter (for i in-string "forsooth the years break" )

      (format t "~a " i))

f o r s o o t h   t h e   y e a r s   b r e a k

Sequences

Now think about generic sequences. Both of the following examples are from iter, not loop. Iter will use the control term "in-sequence".

(iter (for i in-sequence "forsooth the years break" )

      (format t "~a " i))

f o r s o o t h   t h e   y e a r s   b r e a k

NIL

(iter (for i in-sequence '(2 5 89)) (format t "~a " i))

2 5 89

Vectors

Both loop and iter deal with vectors (or one-dimensional arrays), but they use different control terms. Loop uses "across" and iter uses "in-vector".

(loop for i across #(1 2 3) do

      (print i))

(iter (for i in-vector  #(1 2 3))

      (format t "~a " i))

But here we discover iter has a little more to offer in the sense that you can directly assign the index of the vector to a variable

(iter (for i index-of-vector  #(1 2 3))

      (format t "~a " i))

0 1 2

Hash Tables

Ah, hash tables - Hash tables are where everyone gets disgusted by loop. Assume the following example:

(defparameter *currencies* (make-hash-table))

(setf (gethash 'Italy *currencies*) 'Euro)

(setf (gethash 'Sweden *currencies*) 'Krona)

Hash-key

(loop for x being each hash-key of *currencies*

      do (format t "~a " x))

ITALY SWEDEN

(iter (for (x y) in-hashtable *currencies*)

      (format t "~a " x))

ITALY SWEDEN

Hash-value

(loop for v being the hash-value of *currencies* do (print v))

EURO

KRONA

(iter (for (x y) in-hashtable *currencies*)

      (print y))

EURO

KRONA

You can immediate see that the call for hash-key and hash-value is the same in iter but it is different in loop

Key-Value Pair

(loop for k being the hash-key using (hash-value v) of *currencies*

      do (format t "~a ~a~%" k v))

ITALY EURO

SWEDEN KRONA

(iter (for (x y) in-hashtable *currencies*)

      (format t "~a ~a~%" x y))

ITALY EURO

SWEDEN KRONA

Hash-keys - Using

(loop for key being the hash-keys in *currencies*

          using (hash-value val)

      do (format t "~a ~a ~%" key val))

ITALY EURO

SWEDEN KRONA

(iter (for (x y) in-hashtable *currencies*)

      (format t "~a ~a~%" x y))

ITALY EURO

SWEDEN KRONA

Conclusion: At the end of the day, in hashtable situations, iterate looks more rational.

Declaring Variable Types

You can declare the local variables to be of specific types in order to ensure that the variable is correctly typed.

(loop for i of-type fixnum in '(1 3.1 4) counting (oddp i) into x

        do (print x))

;;Throws an error because 3.1 is not a fixnum

(iter (for el in '(1 3 4))

      (declare (fixnum el))

      (counting (oddp el)))

Return Value Structuring

Append/Appending

Here there is a difference in that loop works with either "append" or "appending" but iter works only with "appending".

(loop for i from 1 to 3

        appending (list i i))

(1 1 2 2 3 3)

(iter (for i from 1 to 3)

       (appending (list i i)))

(1 1 2 2 3 3)

(iter (for l on '(1 2 3))

      (appending l :at #:end)

      (collect (first l)))

(1 2 3 1 2 3 2 3 3)

(iter (for l on '(1 2 3))

       (appending l into x))

NIL

But

(loop for i from 1 to 3

        append (list i i))

(1 1 2 2 3 3)

(iter (for i from 1 to 3)

       (append (list i i)))

NIL

Unioning

(iter (for l on '(a b c))

(unioning l)

(collect (first l)))

(A B C A B C)

(iter (for l on '(a b c))

(collecting (first l))

(unioning l :test #'eql))

(A B C B C)

(iter (for l in-vector '#("a" "A" "aB" "ab" "AB"))

(unioning (list l) :test #'string-equal))

("a" "aB")

(iter (for l in-vector '#("a" "A" "aB" "ab" "AB"))

(nunioning (list l) :test #'string-equal :at :start))

("aB" "a")

Nconcing

(iter (for l on (list 1 2 3))

(collect (first l))

(nconcing (copy-list l) at end))

(1 1 2 3 2 2 3 3 3)

Finally

Finally sets the return value calls

(loop for x below 3

      do (format t "~a " x)

      finally

      (format t "~a " 'loop-end))

0 1 2 LOOP-END

(iter (for x below 3)

      (format t "~a " x)

      (finally

       (format t "~a " 'loop-end)))

0 1 2 LOOP-END

New and Wonderful

Previous Values

You can get to previous values in the loop? Well, in iter, yes, using the term "previous". Consider the following:

(iter (for el in '(1 2 3 4))

             (for pp-el previous el back 2 initially 0)

             (collect pp-el))

(0 0 1 2)

You do need to set the previous-element (in this case pp-el) to an initial setting and the argument to back must be a constant positive integer and defaults to 1.

Generators

Generators are a feature of iterate and have no analogue in loop. As described in http://items.sjbach.com/280/extending-the-iterate-macro, a generator is a lazy evaluated variable. It will only change when directed to do so by a next clause. If you forget the next clause, it will never change (and you are looking for a specific change to get you out of the iteration, you will be waiting forever).

Here is an example:

(iter (for i in '(1 2 3 4 5))

      (generate c in-string "black")

      (if (oddp i) (next c))

      (format t "~a " c))

b b l l a

New Drivers

Would you like to iterate over the leaves of a tree? You can write a new driver for iterate that will do that. Again, thank you Stephen Bach for the example.

(iter:defmacro-driver (FOR leaf IN-TREE tree)

  "Iterate over the leaves in a tree"

  (let ((gtree (gensym))

        (stack (gensym))

        (kwd (if generate 'generate 'for)))

    `(progn

       (with ,gtree = ,tree)

       (with ,stack = (list ,gtree))

       (,kwd ,leaf next

             (let ((next-leaf

                    (iter (while ,stack)

                          (for node = (pop ,stack))

                          (if (consp node)

                              (destructuring-bind (l . r)

                                  node

                                (unless (endp r)

                                  (push r ,stack))

                                (push l ,stack))

                              (return node)))))

               (or next-leaf (terminate)))))))

(iter (for leaf in-tree '(((2 3) (5) 1) 8 (4 (1 (2)) 2) 3))

      (collect leaf into leaves)

      (multiply leaf into product)

      (finally (return (values leaves product))))

(2 3 5 1 8 4 1 2 2 3)

Can you do that in loop? Ok. Maybe not.

Page updated

Google Sites

Report abuse