pipsqueaker117 pipsqueaker117 - 3 years ago 136
Python Question

Lazily generating prime in Common Lisp

I'm trying to generate prime numbers in a pythonic way- that is, using generators.

The python code would be more or less the following

def divisor_in_list(n, d):
""" Returns true if a divisor of n is in d, false otherwise"

def primes():
yield 2
primelist = [2]
i = 3

while True:
while divisor_in_list(i, primelist):
i += 2
yield i

I'm very new to Lisp, so I was wondering what the idiomatic equivalent would be. Based on my research up to this point, I have the following code

(defun primes ()
(let* ((p (list 2)) (n 3))
(lambda ()
(loop while (divisor-in-slist n p)
do (incf n 2))
(nconc p (list n))
(+ n 0) ;; Not actually sure how to return N directly :(

However, there's a problem with this code, which is that the first value it spits out is 3. Unfortunately, I haven't been able to figure out how to elegantly modify it to produce 2 as the first value.

I could definitely combine an
statement in the lambda and an extra variable to check whether the method is being called for the first time, but that seems ugly. What's the better way to do it?

Answer Source

There is no direct equivalent of yield in Common Lisp. One might use some functional approach or use some kind of library which provides lazy computation.

One way to complete your approach would be something like this, where we have a variable f which holds the current continuation.

(defun make-prime-generator (&aux (p (list 2)) (n 2) f)
  (labels ((f2 ()            ; a function for the first iteration
             (incf n)
             (setf f #'fn)   ; setting f to the next function
           (fn ()            ; a function for all other iterations
             (loop while (divisor-in-list n p)
                   do (incf n 2))
             (push n p)
    (setf f #'f2)            ; setting f to the first function
    (lambda ()               ; returning a closure
      (funcall f))))         ;   which calls the current f

CL-USER 28 > (let ((p (make-prime-generator)))
               (flet ((p () (funcall p)))
                 (loop repeat 10 do (print (p)))))


If one would be ambitious, one could hide above behind a macro, which would define all the code parts and which would manage the transition.

Further Exploration

We can make the state changes a bit more explicit by introducing the local functions init, exit and step.

(defun make-prime-generator (&aux (p (list 2)) (n 2) f)
  (flet ((init (function)
           (setf f function))
         (exit (result function)
           (setf f function)
         (step ()
           (funcall f)))
    (labels ((f2 ()
               (incf n)
               (exit 2 #'fn))
             (fn ()
               (loop while (divisor-in-list n p)
                     do (incf n 2))
               (push n p)
               (exit n #'fn)))
      (init #'f2)

Now that would be another, slightly more advanced, task: write a macro gen-run which allows us to remove the boilerplate and make the code more declarative. It might be used like this:

(defmacro gen-run (f-descriptions &key start)
  (let ((§f    (gensym "F"))
        (§init (gensym "INIT"))
        (§exit (gensym "EXIT"))
        (§step (gensym "STEP")))
    `(let (,§f)
       (flet ((,§init (function)
                (setf ,§f function))
              (,§exit (result function)
                (setf ,§f function)
              (,§step ()
                (funcall ,§f)))
         (labels (,@(loop for fd in f-descriptions
                      collect (destructuring-bind (name -> next &body body)
                                (declare (ignore ->))
                                `(,name ()
                                    (,§exit ((lambda () ,@body))
                                            (function ,(if next next name)))))))
           (,§init (function ,start))
           (function ,§step))))))

(defun make-prime-generator (&aux (p (list 2)) (n 2))
  (gen-run ((f2 -> fn
              (incf n)
            (fn -> fn
              (loop while (divisor-in-list n p)
                    do (incf n 2))
              (push n p)
      :start f2))
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download