Some Lisp musings, part 6

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)
         ((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))
         (when (and ,early-exit
                    (funcall ,early-exit ,iter))

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))

(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))

(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))

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

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


反垃圾邮件 / Anti-spam question * Time limit is exhausted. Please reload CAPTCHA.