CODEWITHSUNDEEP
lispcommon-lisp
Gishu
Gishu

Reputation: 136673

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

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

Upvotes: 11

Views: 1210

Answers (5)

Mark Cox
Mark Cox

Reputation: 440

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.

Upvotes: 1

Leslie P. Polzer
Leslie P. Polzer

Reputation: 3028

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

Upvotes: 0

Svante
Svante

Reputation: 51551

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.

Upvotes: 4

Vatine
Vatine

Reputation: 21288

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.

Upvotes: 3

kmkaplan
kmkaplan

Reputation: 18970

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.

Upvotes: 5

Related Questions