在 Lisp 中实现连续整数的无限列表以进行惰性求值
Implementing infinite list of consecutive integers in Lisp for lazy evaluation
序曲
在 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中最实用地实现这样一个无限列表？
出于实际目的，使用现有库是明智的，但由于问题是关于如何实现惰性列表的，我们将从头开始。
闭包
惰性迭代是生成一个 object 的问题，它可以在每次被要求这样做时生成惰性序列的新值。
一个简单的方法是 return 闭包，即关闭变量的函数，它在通过 side-effect.
更新其状态时产生值
如果你评价：
(let ((a 0))
(lambda () (incf a)))
您获得了一个具有局部状态的函数 object，即此处名为 a 的变量。
这是一个词法绑定到这个函数独有的位置，如果你第二次计算同一个表达式，你将获得一个不同的匿名函数，它有自己的本地状态。
调用闭包时，存储在a中的值递增，其值为returned。
让我们将这个闭包绑定到一个名为 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))))
这里不需要加let，参数到n的词法绑定是在调用函数的时候完成的。
随着时间的推移，我们将 n 分配给 body 中的不同值。
更准确地说，SHIFTF 将 n 分配给 (1+ n)，但 return 是 n 的先前值。
例如：
(let ((it (inf 5)))
(list (funcall it)
(funcall it)
(funcall it)
(funcall it)))
给出：
(5 6 7 8)
通用迭代器
标准 dolist 需要一个适当的列表作为输入，您无法放置另一种数据并期望它起作用（或者可能以 implementation-specific 方式）。
我们需要一个类似的宏来迭代任意迭代器中的所有值。
我们还需要指定迭代何时停止。
这里有多种可能性，我们定义一个基本的迭代协议如下：
- 我们可以在任何 object 上调用
make-iterator 以及任意参数，以获得一个 iterator
- 我们可以在迭代器上调用
next来获取下一个值。
- 更准确地说，如果有一个值，
next returns 值和 T 作为次要值；否则，next returns 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"))
使用通用函数允许用户定义自定义迭代器，只要它们遵守上面指定的行为。
我们定义了自己的宏：for，而不是使用仅适用于急切序列的 dolist。
它向用户隐藏对 make-iterator 和 next 的调用。
换句话说，for 接受一个 object 并对其进行迭代。
我们可以跳过 (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)))))
我们假设任何函数 object 都可以充当迭代器，因此我们将 next 特化为 class function 的值 f，以便函数 f 被调用：
(defmethod next ((f function))
"A closure is an interator"
(funcall f))
此外，我们还可以专门化 make-iterator 使闭包成为它们自己的迭代器（我认为没有其他好的默认行为可以为闭包提供）：
(defmethod make-iterator ((function function) &key)
function)
向量迭代器
例如，我们可以为向量构建一个迭代器，如下所示。我们将 make-iterator 专门用于 class vector 的值（此处命名为 vec）。
returned 迭代器是一个闭包，因此我们可以在其上调用 next。
该方法接受默认为零的 :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)
游标是一个 object，它保留对正在访问的列表中当前 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 的 object 可能是一个特定的关键字，例如 :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)
这也是 return 一个闭包。
例如，在这里，您将按如下方式迭代一个范围：
(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
一个很好的教学方法是定义有时称为 'streams' 的事物。据我所知，有关执行此操作的最佳介绍在 Structure and Interpretation of Computer Programs 中。 3.5 节介绍了 Streams，但是 不要只读那个：认真读这本书：这是一本每个对编程感兴趣的人都应该读的书阅读。
SICP用的是Scheme，这种东西在Scheme里更自然。但它可以在 CL 中相当容易地完成。我在下面写的是 'Schemy' CL：特别是我只是假设尾调用是优化的。这在 CL 中不是一个安全的假设，但它足以让您了解如何将这些概念构建到一种尚不具备这些概念的语言中，如果您的语言是有能力的。
首先我们需要一个支持惰性求值的结构：我们需要能够'delay'创建一个'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
现在我们可以编写一个函数来枚举自然数中的区间，默认情况下将是 half-infinite 区间：
(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，但是这里太长了。
我会用一个库来展示它：
如何使用 GTWIWTG 生成器库创建和使用无限整数列表
这个名为“生成器以我想要的方式生成”的库允许做三件事：
- 创建生成器（迭代器）
- 合并它们
- 消耗它们（一次）。
与近乎经典的系列没有什么不同。
使用 (ql:quickload "gtwiwtg") 安装库。我将在它的包中工作：(in-package :gtwiwtg).
为无限整数列表创建生成器，从 0 开始：
GTWIWTG> (range)
#<RANGE-BACKED-GENERATOR! {10042B4D83}>
我们还可以指定它的:from、:to、:by和:inclusive参数。
将此生成器与其他生成器结合使用：此处不需要。
迭代并停止：
GTWIWTG> (for x *
(print x)
(when (= x 7)
(return)))
0
1
2
3
4
5
6
7
T
这个方案很实用:)
序曲
在 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中最实用地实现这样一个无限列表？
出于实际目的，使用现有库是明智的，但由于问题是关于如何实现惰性列表的，我们将从头开始。
闭包
惰性迭代是生成一个 object 的问题，它可以在每次被要求这样做时生成惰性序列的新值。 一个简单的方法是 return 闭包，即关闭变量的函数，它在通过 side-effect.
更新其状态时产生值如果你评价：
(let ((a 0))
(lambda () (incf a)))
您获得了一个具有局部状态的函数 object，即此处名为 a 的变量。
这是一个词法绑定到这个函数独有的位置，如果你第二次计算同一个表达式，你将获得一个不同的匿名函数，它有自己的本地状态。
调用闭包时，存储在a中的值递增，其值为returned。
让我们将这个闭包绑定到一个名为 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))))
这里不需要加let，参数到n的词法绑定是在调用函数的时候完成的。
随着时间的推移，我们将 n 分配给 body 中的不同值。
更准确地说，SHIFTF 将 n 分配给 (1+ n)，但 return 是 n 的先前值。
例如：
(let ((it (inf 5)))
(list (funcall it)
(funcall it)
(funcall it)
(funcall it)))
给出：
(5 6 7 8)
通用迭代器
标准 dolist 需要一个适当的列表作为输入，您无法放置另一种数据并期望它起作用（或者可能以 implementation-specific 方式）。
我们需要一个类似的宏来迭代任意迭代器中的所有值。
我们还需要指定迭代何时停止。
这里有多种可能性，我们定义一个基本的迭代协议如下：
- 我们可以在任何 object 上调用
make-iterator以及任意参数，以获得一个 iterator - 我们可以在迭代器上调用
next来获取下一个值。 - 更准确地说，如果有一个值，
nextreturns 值和 T 作为次要值；否则，nextreturns 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"))
使用通用函数允许用户定义自定义迭代器，只要它们遵守上面指定的行为。
我们定义了自己的宏：for，而不是使用仅适用于急切序列的 dolist。
它向用户隐藏对 make-iterator 和 next 的调用。
换句话说，for 接受一个 object 并对其进行迭代。
我们可以跳过 (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)))))
我们假设任何函数 object 都可以充当迭代器，因此我们将 next 特化为 class function 的值 f，以便函数 f 被调用：
(defmethod next ((f function))
"A closure is an interator"
(funcall f))
此外，我们还可以专门化 make-iterator 使闭包成为它们自己的迭代器（我认为没有其他好的默认行为可以为闭包提供）：
(defmethod make-iterator ((function function) &key)
function)
向量迭代器
例如，我们可以为向量构建一个迭代器，如下所示。我们将 make-iterator 专门用于 class vector 的值（此处命名为 vec）。
returned 迭代器是一个闭包，因此我们可以在其上调用 next。
该方法接受默认为零的 :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)
游标是一个 object，它保留对正在访问的列表中当前 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 的 object 可能是一个特定的关键字，例如 :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)
这也是 return 一个闭包。 例如，在这里，您将按如下方式迭代一个范围：
(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
一个很好的教学方法是定义有时称为 'streams' 的事物。据我所知，有关执行此操作的最佳介绍在 Structure and Interpretation of Computer Programs 中。 3.5 节介绍了 Streams，但是 不要只读那个：认真读这本书：这是一本每个对编程感兴趣的人都应该读的书阅读。
SICP用的是Scheme，这种东西在Scheme里更自然。但它可以在 CL 中相当容易地完成。我在下面写的是 'Schemy' CL：特别是我只是假设尾调用是优化的。这在 CL 中不是一个安全的假设，但它足以让您了解如何将这些概念构建到一种尚不具备这些概念的语言中，如果您的语言是有能力的。
首先我们需要一个支持惰性求值的结构：我们需要能够'delay'创建一个'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
现在我们可以编写一个函数来枚举自然数中的区间，默认情况下将是 half-infinite 区间：
(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，但是这里太长了。
我会用一个库来展示它：
如何使用 GTWIWTG 生成器库创建和使用无限整数列表
这个名为“生成器以我想要的方式生成”的库允许做三件事：
- 创建生成器（迭代器）
- 合并它们
- 消耗它们（一次）。
与近乎经典的系列没有什么不同。
使用 (ql:quickload "gtwiwtg") 安装库。我将在它的包中工作：(in-package :gtwiwtg).
为无限整数列表创建生成器，从 0 开始：
GTWIWTG> (range)
#<RANGE-BACKED-GENERATOR! {10042B4D83}>
我们还可以指定它的:from、:to、:by和:inclusive参数。
将此生成器与其他生成器结合使用：此处不需要。
迭代并停止：
GTWIWTG> (for x *
(print x)
(when (= x 7)
(return)))
0
1
2
3
4
5
6
7
T
这个方案很实用:)