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

Question

序幕

在Raku有一个概念叫infinite listAKAlazy 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

一个很好的教学方法是定义有时称为“流”的事物。我所知道的最好的介绍是在计算机程序的结构和解释中。流在第 3.5 节中介绍，但不要只是阅读：认真阅读本书：这是一本每个对编程感兴趣的人都应该阅读的书。

SICP使用Scheme，这种事情在Scheme中更加自然。但是它可以在 CL 中相当容易地完成。我在下面写的是 'Schemy' CL：特别是我只是假设尾调用是优化的。这在 CL 中不是一个安全的假设，但是如果您的语言有能力，那么了解如何将这些概念构建到尚未拥有它们的语言中就足够了。

首先，我们需要一个支持惰性求值的结构：我们需要能够“延迟”某些东西来创建一个“承诺”，它只会在需要时进行求值。好吧，函数的作用是仅在被要求时评估它们的主体，因此我们将使用它们：

(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有点繁琐，它希望确保承诺只被强制执行一次，并且还希望确保被延迟的表单不会被它用来执行此操作的状态所感染。您可以跟踪 的扩展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，但这里太长了。

Answer 2

出于实际目的，使用现有的库是明智的，但由于问题是如何实现惰性列表，我们将从头开始。

闭包

惰性迭代是指生成一个对象，该对象每次被要求时都可以生成惰性序列的新值。一个简单的方法是返回一个闭包，即一个关闭变量的函数，它在通过副作用更新其状态的同时生成值。

如果你评价：

(let ((a 0))
  (lambda () (incf a)))

您获得一个具有本地状态的函数对象，即此处名为 的变量a。这是到该函数独有的位置的词法绑定，如果您第二次计算相同的表达式，您将获得一个具有自己的本地状态的不同匿名函数。

当您调用闭包时，存储在a增量中的值将被返回。

让我们将此闭包绑定到名为 的变量counter，多次调用它并将连续结果存储在列表中：

(let ((counter (let ((a 0))
                 (lambda () (incf a)))))
  (list (funcall counter)
        (funcall counter)
        (funcall counter)
        (funcall counter)))

结果列表是：

(1 2 3 4)

简单迭代器

在您的例子中，您希望有一个在编写时从 5 开始计数的迭代器：

(inf 5)

这可以按如下方式实现：

(defun inf (n)
  (lambda ()
    (shiftf n (1+ n))))

这里不需要添加 a let，参数的词法绑定是n在调用函数时完成的。随着时间的推移，我们会n在体内分配不同的值。更准确地说，SHIFTF分配n给(1+ n)，但返回 的先前值n。例如：

(let ((it (inf 5)))
  (list (funcall it)
        (funcall it)
        (funcall it)
        (funcall it)))

这使：

(5 6 7 8)

通用迭代器

该标准dolist期望一个正确的列表作为输入，您无法放置另一种数据并期望它起作用（或者可能以特定于实现的方式）。我们需要一个类似的宏来迭代任意迭代器中的所有值。我们还需要指定迭代何时停止。这里有多种可能性，让我们定义一个基本的迭代协议如下：

1. 我们可以调用make-iterator任何对象以及任意参数来获取迭代器
2. 我们可以调用next迭代器来获取下一个值。
3. 更准确地说，如果有一个值，next则返回该值和 T 作为辅助值；否则，next返回 NIL。

让我们定义两个通用函数：

(defgeneric make-iterator (object &key)
  (:documentation "create an iterator for OBJECT and arguments ARGS"))

(defgeneric next (iterator)
  (:documentation "returns the next value and T as a secondary value, or NIL"))

使用泛型函数允许用户定义自定义迭代器，只要它们遵循上面指定的行为即可。

我们不使用dolist仅适用于急切序列的 ，而是定义自己的宏：for。它隐藏make-iterator与next用户之间的呼叫。换句话说，for获取一个对象并对其进行迭代。我们可以跳过迭代，(return v)因为for是用 实现的loop。

(defmacro for ((value object &rest args) &body body)
  (let ((it (gensym)) (exists (gensym)))
    `(let ((,it  (make-iterator ,object ,@args)))
       (loop
         (multiple-value-bind (,value ,exists) (next ,it)
           (unless ,exists
             (return))
           ,@body)))))

我们假设任何函数对象都可以充当迭代器，因此我们专门next针对fclass 的值function，以便f调用该函数：

(defmethod next ((f function))
  "A closure is an interator"
  (funcall f))

另外，我们还可以专门make-iterator让闭包成为它们自己的迭代器（我认为没有其他好的默认行为可以为闭包提供）：

(defmethod make-iterator ((function function) &key)
  function)

向量迭代器

例如，我们可以为向量构建一个迭代器，如下所示。我们专门研究class 的make-iterator值（此处名为） 。返回的迭代器是一个闭包，因此我们可以调用它。该方法接受默认为零的参数：vecvectornext:start

(defmethod make-iterator ((vec vector) &key (start 0))
  "Vector iterator"
  (let ((index start))
    (lambda ()
      (when (array-in-bounds-p vec index)
        (values (aref vec (shiftf index (1+ index))) t)))))

你现在可以写：

(for (v "abcdefg" :start 2)
  (print v))

这会打印以下字符：

#\c 
#\d 
#\e 
#\f 
#\g

列表迭代器

同样，我们可以构建一个列表迭代器。为了演示其他类型的迭代器，我们有一个自定义游标类型。

(defstruct list-cursor head)

游标是一个对象，它保留对正在访问的列表中当前 cons-cell 的引用，或 NIL。

(defmethod make-iterator ((list list) &key)
  "List iterator"
  (make-list-cursor :head list))

我们定义next如下，专门针对list-cursor：

(defmethod next ((cursor list-cursor))
  (when (list-cursor-head cursor)
    (values (pop (list-cursor-head cursor)) t)))

范围

Common Lisp 还允许使用 EQL 专用程序来专门化方法，这意味着我们给出的对象for可能是特定的关键字，例如:range。

(defmethod make-iterator ((_ (eql :range)) &key (from 0) (to :infinity) (by 1))
  (check-type from number)
  (check-type to (or number (eql :infinity)))
  (check-type by number)
  (let ((counter from))
    (case to
      (:infinity
       (lambda () (values (incf counter by) t)))
      (t
       (lambda ()
         (when (< counter to)
           (values (incf counter by) T)))))))

可能的要求make-iterator是：

(make-iterator :range :from 0 :to 10 :by 2)

这也返回一个闭包。例如，您可以按如下方式迭代一个范围：

(for (v :range :from 0 :to 10 :by 2)
  (print v))

上式展开为：

(let ((#:g1463 (make-iterator :range :from 0 :to 10 :by 2)))
  (loop
   (multiple-value-bind (v #:g1464)
       (next #:g1463)
     (unless #:g1464 (return))
     (print v))))

最后，如果我们添加一些小的修改inf（添加次要值）：

(defun inf (n)
  (lambda ()
    (values (shiftf n (1+ n)) T)))

我们可以写：

(for (v (inf 5))
  (print v)
  (when (= v 7)
    (return)))

哪个打印：

5 
6 
7