Lazily generating prime in Common Lisp

Question

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
        primelist.append(i)
        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 if 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?

FYI "lazy" keyword => a lazy library: [clazy](https://common-lisp.net/project/clazy/) — Ehvince, Sep 30 '17 at 09:50
Possible duplicate of [Is there a straightforward lisp equivalent of Python's generators?](https://stackoverflow.com/questions/32956033/is-there-a-straightforward-lisp-equivalent-of-pythons-generators) — coredump, Sep 30 '17 at 10:47
Ugly is in the eye of the beholder. I see a lot of it in the Python solution: the hard-coded initial yield of 2, the hard-coded initialization of knowns to [2], iterating from 3, and finally the "cheat" of incrementing by 2. The definition of prime number does not say "2 and then starting with 3 skipping every other integer etc etc". So the Python solution has all sorts trickery specific to what we know about primes baked into it. Try again from "a whole number greater than 1, whose only two whole-number factors are 1 and itself". Then you just need one ugly hack: skip by two if > 2. — kennytilton, Oct 01 '17 at 14:56

Rainer Joswig · Accepted Answer · 2017-09-29T23:04:03.440

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
             2)
           (fn ()            ; a function for all other iterations
             (loop while (divisor-in-list n p)
                   do (incf n 2))
             (push n p)
             n))
    (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)))))

2 
3 
5 
7 
11 
13 
17 
19 
23 
29 
NIL

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)
           result)
         (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)
      #'step)))

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)
                result)
              (,§step ()
                (funcall ,§f)))
         (labels (,@(loop for fd in f-descriptions
                      collect (destructuring-bind (name -> next &body body)
                                  fd
                                (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)
              2)
            (fn -> fn
              (loop while (divisor-in-list n p)
                    do (incf n 2))
              (push n p)
              n))
      :start f2))

Lazily generating prime in Common Lisp

1 Answers1