Now, we’re ready to put together the more complex version of the original macro with the generalized n-iterator macro-generating macro.  That’s fairly simple, certainly compared to the magic that goes into building the looping construct.  We’ve already got the desired template, we just fold them in.  Here’s the result:
   

(defmacro create-n-iter-loop (n name)
  (assert (and (integerp n) (> n 0)))
  (let (symbols first-sym last-sym)
    (dotimes (i n)
      (push (intern (format nil "ITER~D" i)) symbols))
    (setf last-sym (first symbols))
    (setf symbols (reverse symbols))
    (setf first-sym (first symbols))
    `(defmacro ,name ((dl-list ,@symbols 
                               &key start end circular reverse)
                      &body body)
       (let ((dl-cap (gensym))
             (start-cap (gensym))
             (end-cap (gensym))
             (circ-cap (gensym))
             (rev-cap (gensym))
             (inc-fcn (gensym))
             (early-exit (gensym)))
         `(let ((,dl-cap ,dl-list)
                (,start-cap ,start)
                (,end-cap ,end)
                (,circ-cap ,circular)
                (,inc-fcn 'iter-next)
                (,rev-cap ,reverse)
                ,early-exit)
            (cond
              ((and ,circ-cap ,rev-cap)
               (setf ,inc-fcn 
                     #'(lambda (dl it)
                         (let ((rv (iter-prev dl it)))
                           (or rv (iter-back dl))))))

              ((and ,circ-cap (not ,rev-cap))
               (setf ,inc-fcn 
                     #'(lambda (dl it)
                         (let ((rv (iter-next dl it)))
                           (or rv (iter-front dl))))))

              ((and (not ,circ-cap) ,rev-cap)
               (setf ,inc-fcn 'iter-prev)))

            (unless ,start-cap
              (if ,rev-cap
                  (setf ,start-cap (iter-back ,dl-cap))
                  (setf ,start-cap (iter-front ,dl-cap))))
            (when ,end-cap
              (setf ,early-exit #'(lambda (x) 
                                    (eq x ,end-cap))))

            (do* ((,,first-sym 
                   ,start-cap 
                   (funcall ,inc-fcn ,dl-cap ,,first-sym))
                  ,,@(mapcar #'(lambda (x y) 
                                 ``(,,x 
                                    (and ,,y 
                                         (funcall ,,'inc-fcn 
                                                  ,,'dl-cap 
                                                  ,,y))
                                    (and ,,y 
                                         (funcall ,,'inc-fcn 
                                                  ,,'dl-cap 
                                                  ,,y))))
                             (cdr symbols) symbols))
                 ((not ,,last-sym))
              ,@body
              (when (and ,early-exit
                         (funcall ,early-exit ,,first-sym))
                (return))))))))

While there might be some minor adjustments to be made, this macro does what I need for iteration over a dl-list object.

Continuing from part 6, we’re now getting into some macro magic.  We noticed a pattern between the basic iter-loop, 2-iter-loop, and 3-iter-loop.  We create a number of iterator names as placeholders.  The first one, we initialize from the beginning of the dl-list.  The second one we assign and update to the iter-next of the first iterator.  The third iterator we assign and update to the iter-next of the second iterator, and so on.  The exit condition is when the last iterator is nil.  Can we automate this?  Can we make a macro that produces macros of any number of iterators?  Yes.  Here’s the basic version of that macro:
 

(defmacro create-n-iter-loop (n name)
  (assert (and (integerp n) (> n 0)))
  (let (symbols first-sym last-sym)
    (dotimes (i n)
      (push (intern (format nil "ITER~D" i)) symbols))
    (setf last-sym (first symbols))
    (setf symbols (reverse symbols))
    (setf first-sym (first symbols))
    `(defmacro ,name ((dl-list ,@symbols) &body body)
       (let ((dl-cap (gensym)))
         `(let ((,dl-cap ,dl-list))
            (do* ((,,first-sym (iter-front ,dl-cap) 
                               (iter-next ,dl-cap ,,first-sym))
                  ,,@(mapcar #'(lambda (x y) 
                                 ``(,,x 
                                    (and ,,y 
                                         (iter-next ,,'dl-cap ,,y))
                                    (and ,,y 
                                         (iter-next ,,'dl-cap ,,y))))
                             (cdr symbols) symbols))
                 ((not ,,last-sym))
              ,@body))))))

This macro would be invoked with an ‘n’, and the name of the looping macro to be created.  So, executing the command

(create-n-iter-loop 1 iter-loop)

produces the simple single-iterator macro.  We can observe this by executing the command

(macroexpand-1 '(create-n-iter-loop 1 iter-loop))

the output of which is:
 

(DEFMACRO ITER-LOOP ((DL-LIST::DL-LIST ITER0) &BODY DL-LIST::BODY)
  (LET ((DL-LIST::DL-CAP (GENSYM)))
    `(LET ((,DL-LIST::DL-CAP ,DL-LIST::DL-LIST))
       (DO* ((,ITER0 (DL-LIST:ITER-FRONT ,DL-LIST::DL-CAP)
                     (DL-LIST:ITER-NEXT ,DL-LIST::DL-CAP ,ITER0)))
            ((NOT ,ITER0))
         ,@DL-LIST::BODY))))

This code is the same as our original iter-loop.  Similarly, we can produce the 2-iter-loop:
 

(DEFMACRO 2-ITER-LOOP ((DL-LIST::DL-LIST ITER0 ITER1) &BODY DL-LIST::BODY)
  (LET ((DL-LIST::DL-CAP (GENSYM)))
    `(LET ((,DL-LIST::DL-CAP ,DL-LIST::DL-LIST))
       (DO* ((,ITER0 (DL-LIST:ITER-FRONT ,DL-LIST::DL-CAP)
                     (DL-LIST:ITER-NEXT ,DL-LIST::DL-CAP ,ITER0))
             (,ITER1 (AND ,ITER0 (DL-LIST:ITER-NEXT ,DL-LIST::DL-CAP ,ITER0))
                     (AND ,ITER0 (DL-LIST:ITER-NEXT ,DL-LIST::DL-CAP ,ITER0))))
            ((NOT ,ITER1))
         ,@DL-LIST::BODY))))

and the 3-iter-loop macro:
 

(DEFMACRO 3-ITER-LOOP
          ((DL-LIST::DL-LIST ITER0 ITER1 ITER2) &BODY DL-LIST::BODY)
  (LET ((DL-LIST::DL-CAP (GENSYM)))
    `(LET ((,DL-LIST::DL-CAP ,DL-LIST::DL-LIST))
       (DO* ((,ITER0 (DL-LIST:ITER-FRONT ,DL-LIST::DL-CAP)
                     (DL-LIST:ITER-NEXT ,DL-LIST::DL-CAP ,ITER0))
             (,ITER1 (AND ,ITER0 (DL-LIST:ITER-NEXT ,DL-LIST::DL-CAP ,ITER0))
                     (AND ,ITER0 (DL-LIST:ITER-NEXT ,DL-LIST::DL-CAP ,ITER0)))
             (,ITER2 (AND ,ITER1 (DL-LIST:ITER-NEXT ,DL-LIST::DL-CAP ,ITER1))
                     (AND ,ITER1 (DL-LIST:ITER-NEXT ,DL-LIST::DL-CAP ,ITER1))))
            ((NOT ,ITER2))
         ,@DL-LIST::BODY))))

So, why go to all that trouble of generalizing the macro?  Well, I need all three looping constructs.  iter-loop, 2-iter-loop, 3-iter-loop.  They’re very similar macros, but coding them three times raises the possibility that there will be typos that introduce subtle errors, or bugs might be fixed in two of the macros, but not in the third.  By making sure that they’re all created from a single block of code, I increase the reliability.  I can make sure that all of the macros have the same API, that they use the same keywords, and if one day I decide I need a 4-iter-loop, it’s no effort at all to create it and know that it’s running the same basic code as all the others.

So, now that we’ve written the generalized basic iterator macro-generating macro, it’s time to put back the bells and whistles.  Circular lists, start/end points, and backward traversal.  That’s for next time.

Now, we’re interested in maybe running the iterators backwards as well as forwards.  This is a fairly simple adjustment to the macro.  We create a new keyword parameter, :reverse.  Now, the iterator increment function has four possible values.  It can be the simple next-iter, it can be a next-iter with wrap-around, it can be prev-iter, or prev-iter with wrap-around.  These cases are handled in the macro here.  This is actually a very simple modification to the macro.  After this, we’ll start doing some more complicated/interesting things.
   

(defmacro iter-loop ((dl-list iter &key start end circular reverse) &body body)
  (let ((dl-cap (gensym))
        (start-cap (gensym))
        (end-cap (gensym))
        (circ-cap (gensym))
        (rev-cap (gensym))
        (inc-fcn (gensym))
        (early-exit (gensym)))
    `(let((,dl-cap ,dl-list)
          (,start-cap ,start)
          (,end-cap ,end)
          (,circ-cap ,circular)
          (,inc-fcn 'iter-next)
          (,rev-cap ,reverse)
          ,early-exit)
       (cond
         ((and ,circ-cap ,rev-cap)
          (setf ,inc-fcn #'(lambda (dl it)
                             (let ((rv (iter-prev dl it)))
                               (or rv (iter-back dl))))))
         ((and ,circ-cap (not ,rev-cap))
          (setf ,inc-fcn #'(lambda (dl it) 
                             (let ((rv (iter-next dl it))) 
                               (or rv (iter-front dl))))))
         ((and (not ,circ-cap) ,rev-cap)
          (setf ,inc-fcn 'iter-prev)))

       (unless ,start-cap
         (if ,rev-cap
             (setf ,start-cap (iter-back ,dl-cap))
             (setf ,start-cap (iter-front ,dl-cap))))
       (when ,end-cap
         (setf ,early-exit #'(lambda (x) (eq x ,end-cap))))
       (do ((,iter ,start-cap (funcall ,inc-fcn ,dl-list ,iter)))
           ((not ,iter))
         ,@body
         (when (and ,early-exit
                    (funcall ,early-exit ,iter))
           (return))))))

So, where are we going next?  Well, at the beginning of this series of articles, I mentioned that my real-world application involves looking at pairs and triplets of points in a doubly-linked list.  So, let’s go back in time a bit, to our basic single iterator macro.  What if we wanted a macro that did the same thing, but with two, or even three consecutive iterators, all incrementing together?  We’d need to be a bit careful about what happens at the end of the loop, but otherwise it’s very similar to what we had before.  For a non-circular list of N elements, we have N-1 pairs, or N-2 triplets.  Here are the macros that would perform these operations.  The single iterator version again, and the 2- and 3- iterator versions:
 

(defmacro iter-loop ((dl-list iter) &body body)
  (let ((dl-cap (gensym)))
    `(let ((,dl-cap ,dl-list))
       (do ((,iter (iter-front ,dl-cap) (iter-next ,dl-cap ,iter)))
           ((not ,iter))
         ,@body))))

(defmacro 2-iter-loop ((dl-list iter1 iter2) &body body)
  (let ((dl-cap (gensym)))
    `(let ((,dl-cap ,dl-list))
       (do* ((,iter1 (iter-front ,dl-cap) (iter-next ,dl-cap ,iter1))
             (,iter2 (and ,iter1 (iter-next ,dl-cap ,iter1))
                     (and ,iter1 (iter-next ,dl-cap ,iter1))))
           ((not ,iter2))
         ,@body))))

(defmacro 3-iter-loop ((dl-list iter1 iter2 iter3) &body body)
  (let ((dl-cap (gensym)))
    `(let ((,dl-cap ,dl-list))
       (do* ((,iter1 (iter-front ,dl-cap) 
                     (iter-next ,dl-cap ,iter1))
             (,iter2 (and ,iter1 (iter-next ,dl-cap ,iter1))
                     (and ,iter1 (iter-next ,dl-cap ,iter1)))
             (,iter3 (and ,iter2 (iter-next ,dl-cap ,iter2))
                     (and ,iter2 (iter-next ,dl-cap ,iter2))))
           ((not ,iter3))
         ,@body))))

There’s a pattern here, and we’re going to make use of that soon.

Continuing from part 4, it’s time to start beefing up the macro a bit.  Now, we might want our loop to start somewhere other than the beginning of the list, and end somewhere other than the end of the list.  And, a few articles back, I mentioned that these lists might sometimes be circular, so we’d like to be able to start at the fifth element of the list, loop forward to the end, continue at the beginning, and then loop up to, say, the second element of the list.

At this point, we come across another very helpful feature of Lisp, one that I frequently miss when programming in C++.  Named parameters.  A function that takes four or five parameters can be awkward to read where it appears in source code, because it might not be clear which parameters represent what behaviour.  It interferes with readability.  In Lisp, you can require certain parameters to be named, which helps to understand what is happening.  A nice consequence of this is that you can set defaults for any of the named parameters, in any order, whereas in C++ you are fairly tightly restricted in what default parameter values you may omit (you cannot choose to omit the second, fourth, and seventh parameters of the invocation, you must omit a contiguous set of trailing parameters with defaults).

So, now we’re going to set up our macro.  Once again, I use (gensym) to build capture variables to avoid multiple evaluations of the arguments.  I also define named parameters :start and :end, which take iterator values as arguments, and :circular, which is either nil or non-nil.  I’ve also created here two lambda functions.  These allow me to create a tiny function on the spot, where the programmer can see it because it’s in the screen with the implementation of its use.  One lambda function is the alternative iterator increment function, to be used when the :circular argument is non-nil, to force the iterator to loop back once it reaches the end of the list.  The other is an exit test that checks to see if the iterator matches the :end condition, if one was supplied.  If so, the (do…) loop is exited at that point.  Note that this condition is tested after the user-supplied body of the loop, before the iterator increment operation, so that the :end iterator is included in the loop.

Here is the next version of this macro:
macros.lisp  

(defmacro iter-loop ((dl-list iter &key start end circular) &body body)
  (let ((dl-cap (gensym))
        (start-cap (gensym))
        (end-cap (gensym))
        (circ-cap (gensym))
        (inc-fcn (gensym))
        (early-exit (gensym)))
    `(let((,dl-cap ,dl-list)
          (,start-cap ,start)
          (,end-cap ,end)
          (,circ-cap ,circular)
          (,inc-fcn 'iter-next)
          ,early-exit)
       (when ,circ-cap
         (setf ,inc-fcn #'(lambda (dl it) 
                            (let ((rv (iter-next dl it))) 
                              (or rv (iter-front dl))))))
       (unless ,start-cap
         (setf ,start-cap (iter-front ,dl-cap)))
       (when ,end-cap
         (setf ,early-exit #'(lambda (x) (eq x ,end-cap))))
       (do ((,iter ,start-cap (funcall ,inc-fcn ,dl-list ,iter)))
           ((not ,iter))
         ,@body
         (when (and ,early-exit
                    (funcall ,early-exit ,iter))
           (return))))))

Now, referring back to the code we showed in part 3, it’s time to step off into macros.  Macros have a bad reputation in C/C++.  Their limitations are significant, and their use is often discouraged except in fairly narrow cases where they are used only in a trivial fashion.

Multi-instruction macros in C/C++ can be made safely, as long as the programmer takes the time to learn how to do it.  The common construct is do { … } while (false), with no trailing semicolon.  That allows it to be used safely in things like the clause of an ‘if’ statement without parenthesis delimiters.  Designing a macro that creates its own named variables is dangerous because they may collide with names already in use in the context where the macro is applied, but not using temporary variables can be dangerous if the arguments are reused, because their side-effects are invoked every time the arguments appear.  Having a complex macro return a value is awkward, and variadic macro arguments are complicated.  The C-preprocessor macro language is very handy, but it does not give the macros the full power of the language.

Because of this, a C/C++ programmer coming to Lisp may hear “macro”, and think that this is a feature to be avoided, clunky and dangerous.  Lisp macros, however, are quite strongly different.  Lisp macros have access to the language features at compile-time, and emit Lisp code at expansion time.  They can implement new language structures, such as new looping constructs.  Often, they seem quite mundane at first, but there eventually comes an “aha!” moment, after which the power and utility becomes clear.  So, we’ve defined out doubly-linked lists and our iterators.  One common activity is to loop the iterator over all elements in the list.  In C++, you would typically do this with a for(;;) loop, or sometimes a while() loop if the conditions are a bit more unusual.  However, your C++ code is full of these for(;;) loops.  Looping over integers, looping over iterators of one kind or another, they’re expressed the same way, so interpreting them requires reading the context of the loop to understand what the variables are and what they represent.  It would be nice to have a loop construct whose name indicates immediately that it is looping an iterator over a doubly-linked list.With that introduction, here is our first (wrong) implementation of an iterator looping macro:

(defmacro iter-loop ((dl-list iter) &body body)
  `(do ((,iter (iter-front ,dl-list) (iter-next ,dl-list ,iter)))
       ((not ,iter))
     ,@body))))

This is wrong because of the danger of argument re-evaluation.  If one were to use it in a loop like this:
macros.lisp  

(dl-list:iter-loop ((expensive-dl-list-creation-function) my-iter)
  (perform-my-operation-on-iterator my-iter))

then the expensive-dl-list-creation-function would be called many times, each time creating a new object that would cause difficulties because of the way iterator incrementation is implemented.  Just as in C/C++ macros, the side-effects of the parameters can manifest too many times, in ways the programmer doesn’t expect.  In Lisp, however, there is a way to capture the argument exactly once, using a temporary variable that is guaranteed not to collide with variables in the program where the macro is expanded.

The (gensym) function, invoked at compile time during macro expansion, returns a variable guaranteed not to exist.  We use this to expand and capture the value of the dl-list, whatever it might be, and use it in the macro.

(defmacro iter-loop ((dl-list iter) &body body)
  (let ((dl-cap (gensym)))
    `(let ((,dl-cap ,dl-list))
       (do ((,iter (iter-front ,dl-cap) (iter-next ,dl-cap ,iter)))
           ((not ,iter))
         ,@body))))

Why didn’t I do the same thing for ‘iter’?  Well, as we see from the use case, ‘iter’ is a variable name that the user supplies, and which they can then operate on in the body of the macro expansion.  I don’t see a way the user could supply anything other than a bare name here and expect it to work.  If the user supplies a name for ‘iter’ that is the name of an existing variable, then this macro shadows that variable.

So, that’s the very basic, single iterator looping over the entire list from beginning to end, example.  But we can build on this, making it significantly more powerful.  That’s for later posts.