How to translate a LOOP into a DO inside a macro (common lisp)?

Question

I'm currently reading through Seibel's "Practical common lisp" and found this example macro:

(defmacro check (&rest forms)
 `(progn
     ,@(loop for f in forms collect `(do-stuff ,f ',f))

(defun test ()
    (check ( (= (+ 1 2 ) 3) (= (+ 1 2 ) 4 )))
 )

do-stuff simply then format the two args in a certain way allowing for 'testing' the truth of a form, but that's not important for my question.

What I was interested in was to translate the loop into a DO, unfortunately, I'm totally lacking in the necessary skill to do so:

(defmacro check (&rest forms)
`(progn
    ,@(do ((index 0 (list-length forms))
            (accumulator nil))
        ((= index (list-length forms)) accumulator)
         (push `(do-stuff ,(nth index forms) ',(nth index forms)) accumulator)
         ))

This does the job, I can also do this (put every form into a variable inside the do):

(defmacro check (&rest forms)
`(progn
    ,@(do* ((index 0 (list-length forms))
            (accumulator nil)
            (f (nth index forms) (nth index forms)))
        ((= index (list-length forms)) accumulator)
         (push `(do-stuff ,f ',f) accumulator)
         ))

My problem is the following :

Is there a more efficient way to write this do loop ? Is this a good way to implement it ?

Something in the LOOP version is making me wonder if there is not a simple way to extract an element of a list without the need to define an index variable, or to regroup the COLLECTED elements without the need to define an accumulator list...

Answer 1

If you use do you shouldn't use nth. Just iterate over the list, not the indexes.

(do ((l forms (cdr l))
     (accumulator nil))
    ((null l) (nreverse accumulator))
  (let ((f (car l)))
    (push `(do-stuff ,f ',f) accumulator)))

You can also use the built-in dolist:

(let ((accumulator nil))
  (dolist (f forms (nreverse accumulator))
    (push `(do-stuff ,f ',f) accumulator)))

Finally there's mapcar:

(mapcar (lambda (f) `(do-stuff ,f ',f)) forms)

Answer 2

Firstly, anything of the form

(loop for v in <list> collect (f v ...))

Can be easily expressed as mapcar:

(mapcar (lambda (v)
          (f v ...))
        <list>)

The interesting case is when the loop only collects a value sometimes, or when the iteration is over some more complicated thing.

In that case one nice approach is to factor out the iteration bit and the 'collecting values' bit, using do or whatever to perform the iteration and some other mechanism to collect values.

One such is collecting. So, for instance, you could use dolist to iterate over the list and collecting to collect values. And perhaps we might only want to collect non-nil values or something to make it more interesting:

(collecting
  (dolist (v <list>)
    (when v
      (collect (f v ...)))))

All of these are more verbose than the simple loop case, but for instance collecting can do things which are painful to express with loop.

Answer 3

Is there a more efficient way to write this do loop ? Is this a good way to implement it ?

The complexity of your code is quadratic to the size N of the list, since for each item you call nth to access an element inside, resulting in a O(N*N) execution time. There is a more efficient way to do it (the original LOOP version is an example of a linear algorithm).

Here is a different version where instead of calling push followed by nreverse, the items are queued at the end of the list during traversal. I added comments to explain what each part does.

_{By the way I don't claim that this is more efficient that using nreverse, I think we can't know without testing. Note however that there are as many operations in both cases (cons a new item, and eventually mutate the cdr slot), they are just done either in two passes or one pass.}

In fact the code below is very not far from being an implementation of MAPCAR where there is only one list to traverse (not the variadic version in the standard).

First, define a helper function that transforms one form:

(defun expand-check (form)
  `(do-stuff ,form ',form))

Recall that you could just (mapcar #'expand-check checks) to have the desired result.

Anyway, here is a DO version:

(defun expand-checks (checks)
  ;; LIST-HOLDER is just a temporary cons-cell that allows us to treat
  ;; the rest of the queue operations without having to worry about
  ;; the corner case of the first item (the invariant is that LAST is
  ;; always a cons-cell, never NIL). Here LIST-HOLDER is initially
  ;; (:HANDLE), the first value being discarded later.
  (let ((list-holder (list :handle)))
    ;; DO is sufficient because the iterator values are independant
    ;; from each other (no need to use DO*).
    (do (;; descend the input list
         (list checks (cdr list))
         ;; update LAST so that it is always the last cons cell, this
         ;; is how we can QUEUE items at the end of the list without
         ;; traversing it. This queue implementation was first
         ;; described by Peter Norvig as far as I known.
         (last list-holder (cdr last)))
        
        ;; End iteration when LIST is empty
         ((null list) 
          ;; In which case, return the rest of the LIST-HOLDER, which
          ;; is the start of the list that was built.
          (rest list-holder))
      
      ;; BODY of the DO, create a new cons-cell at the end of the
      ;; queue by mutating the LAST const cell.
      (setf (cdr last) 
            (list (expand-check
                   (first list)))))))