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

html5 • • 问答

序幕

在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 中实现这样的无限列表？

回答

一个很好的教学方法是定义有时称为“流”的事物。我所知道的最好的介绍是在计算机程序的结构和解释中。流在第 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，但这里太长了。

以上是在Lisp中实现连续整数的无限列表以进行惰性求值的全部内容。
THE END
分享
二维码
< <上一篇
下一篇>>