lisp - 在 Lisp 中实现无限连续整数列表以进行惰性求值

Question

前奏
在 Raku有一个概念叫做 infinite list又名 lazy list它的定义和使用如下:

my @inf = (1,2,3 ... Inf);
for @inf { say $_;
           exit if $_ == 7 }
# => OUTPUT
1
2
3
4
5
6
7

我想在 Common Lisp 中实现这种东西，特别是一个无限的连续整数列表，例如:

(defun inf (n)
  ("the implementation"))

这样

(inf 5)
=> (5 6 7 8 9 10 .... infinity)
;; hypothetical output just for the demo purposes. It won't be used in reality

然后我将使用它进行惰性评估，如下所示:

(defun try () ;; catch and dolist 
  (catch 'foo ;; are just for demo purposes
    (dolist (n (inf 1) 'done)
      (format t "~A~%" n)
      (when (= n 7)
    (throw 'foo x)))))

CL-USER> (try)
1
2
3
4
5
6
7
; Evaluation aborted.

如何以最实用的方式在 CL 中实现这样的无限列表？

Answer 1

一个好的教学方法是定义有时被称为“流”的事物。我所知道的关于这样做的最好的介绍是 Structure and Interpretation of Computer Programs .流在 3.5 节中介绍，但不要仅仅阅读:认真阅读这本书:这是一本每个对编程感兴趣的人都应该阅读的书。
SICP使用Scheme，这种东西在Scheme中更自然。但它可以在 CL 中相当容易地完成。我在下面写的是“Schemy”CL:特别是我只是假设尾调用是优化的。这在 CL 中不是一个安全的假设，但是如果您的语言能够胜任，那么看看如何将这些概念构建到一种还没有它们的语言中就足够了。
首先，我们需要一个支持惰性评估的构造:我们需要能够“延迟”某些东西以创建一个“ promise ”，该 promise 仅在需要时才被评估。好吧，函数的作用是只在被要求时才评估它们的 body ，所以我们将使用它们:

(defmacro delay (form)
  (let ((stashn (make-symbol "STASH"))
        (forcedn (make-symbol "FORCED")))
    `(let ((,stashn nil)
           (,forcedn nil))
       (lambda ()
         (if ,forcedn
             ,stashn
           (setf ,forcedn t
                 ,stashn ,form))))))

(defun force (thing)
  (funcall thing))

delay有点繁琐，它想确保一个 promise 只被强制执行一次，并且它还想确保被延迟的表单不会被它用来执行此操作的状态所感染。您可以追踪 delay 的扩展看看它是什么:

(delay (print 1))
 -> (let ((#:stash nil) (#:forced nil))
      (lambda ()
        (if #:forced #:stash (setf #:forced t #:stash (print 1)))))

这可以。
所以现在，我们将发明流:流就像 conses(它们是 conses!)但它们的 cdr 是延迟的:

(defmacro cons-stream (car cdr)
  `(cons ,car (delay ,cdr)))

(defun stream-car (s)
  (car s))

(defun stream-cdr (s)
  (force (cdr s)))

好的，让我们编写一个函数来获取流的第 n 个元素:

(defun stream-nth (n s)
  (cond ((null s)
         nil)
        ((= n 0) (stream-car s))
        (t
         (stream-nth (1- n) (stream-cdr s)))))

我们可以测试一下:

> (stream-nth 2
              (cons-stream 0 (cons-stream 1 (cons-stream 2 nil))))
2

现在我们可以编写一个函数来枚举自然数中的一个区间，默认情况下它将是一个半无限区间:

(defun stream-enumerate-interval (low &optional (high nil))
  (if (and high (> low high))
      nil
      (cons-stream
       low
       (stream-enumerate-interval (1+ low) high))))

现在:

> (stream-nth 1000 (stream-enumerate-interval 0))
1000

等等。
好吧，我们想要某种可以让我们遍历流的宏:类似于 dolist ，但对于流。好吧，我们可以通过首先编写一个函数来为流中的每个元素调用一个函数来做到这一点(这不是我在生产 CL 代码中这样做的方式，但在这里很好):

(defun call/stream-elements (f s)
  ;; Call f on the elements of s, returning NIL
  (if (null s)
      nil
    (progn
      (funcall f (stream-car s))
      (call/stream-elements f (stream-cdr s)))))

现在

(defmacro do-stream ((e s &optional (r 'nil)) &body forms)
  `(progn
     (call/stream-elements (lambda (,e)
                             ,@forms)
                           ,s)
     ,r))

现在，例如

(defun look-for (v s)
  ;; look for an element of S which is EQL to V
  (do-stream (e s (values nil nil))
    (when (eql e v)
      (return-from look-for (values e t)))))

然后我们可以说

> (look-for 100 (stream-enumerate-interval 0))
100
t

嗯，你需要更多的机制来让流真正有用:你需要能够组合它们，附加它们等等。 SICP有很多这样的功能，一般很容易转成CL，但是这里太长了。