python - 在 Common Lisp 中延迟生成质数

Question

我正在尝试以 pythonic 方式生成素数，即使用生成器。

python 代码大致如下

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

我是 Lisp 的新手，所以我想知道惯用的等价物是什么。根据我到目前为止的研究，我有以下代码

(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 :(
      )
    )
  )

但是，这段代码有一个问题，它吐出的第一个值是 3。不幸的是，我一直无法弄清楚如何优雅地修改它以产生 2 作为第一个值。

我绝对可以在 lambda 中结合一个 if 语句和一个额外的变量来检查该方法是否是第一次被调用，但这看起来很难看。什么是更好的方法？

Answer 1

在 Common Lisp 中没有直接等同于 yield 的东西。人们可能会使用一些函数式方法或使用某种提供惰性计算的库。

完成你的方法的一种方法是这样的，我们有一个变量 f 来保存当前的延续。

(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

如果雄心勃勃，可以将上面的内容隐藏在一个宏之后，该宏将定义所有代码部分并管理转换。

进一步探索

我们可以通过引入局部函数 init、exit 和 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)))

现在这将是另一个稍微高级的任务:编写一个宏 gen-run，它允许我们删除样板文件并使代码更具声明性。可以这样使用:

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