What is wrong with the following Common Lisp macro using gensym?

Question

Learning Common Lisp (using GNU CLISP 2.43) .. so might be a noob mistake. Example is the 'print prime numbers between x and y'

(defun is-prime (n)
  (if (< n 2) (return-from is-prime NIL))

  (do ((i 2 (1+ i)))
      ((= i n) T)
    (if (= (mod n i) 0) 
        (return NIL))))

(defun next-prime-after (n)
  (do ((i (1+ n) (1+ i)))
      ((is-prime i) i)))

(defmacro do-primes-v2 ((var start end) &body body)
  `(do ((,var (if (is-prime ,start)
                  ,start
                  (next-prime-after ,start))
              (next-prime-after ,var)))
       ((> ,var ,end))
     ,@body))

(defmacro do-primes-v3 ((var start end) &body body)
  (let ((loop-start (gensym))
        (loop-end (gensym))) 
    `(do ((,loop-start ,start)
          (,loop-end ,end)
          (,var (if (is-prime ,loop-start)
                    ,loop-start
                    (next-prime-after ,loop-start))
                (next-prime-after ,var)))
         ((> ,var ,loop-end))
       ,@body )))

do-primes-v2 works perfectly.

[13]> (do-primes-v2 (p 10 25) (format t "~d " p))
11 13 17 19 23

Next I tried using gensym to avoid naming clashes in macro expansion - do-primes-v3. However I'm stuck with a

*** - EVAL: variable #:G3498 has no value

Tried using macro-expand to see if i could spot the mistake but I can't.

[16]> (macroexpand-1 `(do-primes-v3 (p 10 25) (format t "~d " p)))
(DO
 ((#:G3502 10) (#:G3503 25)
  (P (IF (IS-PRIME #:G3502) #:G3502 (NEXT-PRIME-AFTER #:G3502))
     (NEXT-PRIME-AFTER P)))
 ((> P #:G3503)) (FORMAT T "~d " P)) ;

Answer 1

You don't actually need the gensym here for avoiding variable capture, because you do not introduce any variables that would be "local to the macro". When you macroexpand your do-primes-v2, you will see that no variable is introduced that didn't exist outside of the macro.

You do need it for a different thing, though: avoiding multiple evaluation.

If you call the macro like this:

(do-primes-v2 (p (* x 2) (* y 3))
  (format "~a~%" p))

it expands to

(do ((p (if (is-prime (* x 2))
            (* x 2)
            (next-prime-after (* x 2))
        (next-prime-after p)))
    ((> p (* y 3))
  (format "~a~%" p))

At best, this is inefficient, because those multiplications are done multiple times. However, if you use a function with side effects as inputs, like setf or incf, this can be a big problem.

Answer 2

Use DO* instead of DO.

DO Initializes the bindings in a scope where they are not yet visible. DO* initializes the bindings in a scope where they are visible.

In this particular case var needs to reference the other binding loop-start.

Answer 3

Either move the binding of your loop-start and loop-end to an enclosing LET block or use DO*. The reason is that all loop variables in DO are bound "in parallel", so for the first binding, the (expanded) loop-start variable does not yet have a binding.

Answer 4

I suggest avoiding DO/DO* and macros altogether and instead going for Series (an implementation of which can be found on series.sourceforge.net).

If that's too complex then consider just generating a list of primes with recursion or a generator (for on-demand generation).

Answer 5

I know this doesn't really answer your question, but I do think it is relevant. In my experience, the type of macro you are attempting to write is a very common one. One problem I have with the way you have approached the problem is that it doesn't handle another common use case: functional composition.

I don't have the time to highlight some of the difficulties you will probably encounter using your macro, I will however highlight that, had you built your prime iterator geared towards functional composition, your macro turns out to be extremely simple, avoiding your question altogether.

Note: I have slightly modified some of your functions.

(defun is-prime (n)
  (cond
    ((< n 2)
     nil)
    ((= n 2)
     t)
    ((evenp n)
     nil)
    (t
     (do ((i 2 (1+ i)))
     ((= i n) t)
       (when (or (= (mod n i) 0))
         (return nil))))))

(defun next-prime (n)
  (do ((i n (1+ i)))
      ((is-prime i) i)))

(defun prime-iterator (start-at)
  (let ((current start-at))
    (lambda ()
      (let ((next-prime (next-prime current)))
         (setf current (1+ next-prime))
         next-prime))))

(defun map-primes/iterator (fn iterator end)
  (do ((i (funcall iterator) (funcall iterator)))
      ((>= i end) nil)
    (funcall fn i)))

(defun map-primes (fn start end)
  (let ((iterator (prime-iterator start)))
    (map-primes/iterator fn iterator end)))

(defmacro do-primes ((var start end) &body body)
  `(map-primes #'(lambda (,var)
                ,@body)
               ,start ,end))

I too recommend that you look at Series. The generator pattern is also a very common occurrence in lisp programs. You may also want to look at Alexandria, in particular the function ALEXANDRIA:COMPOSE to see what cool stuff you can do with functional composition.