使用 elisp 实现流
Implementing streams with elisp
我正在阅读 SICP 书的第 3.5 节,我正在尝试实现
使用 Elisp 的流。书中使用Scheme语言实现流如下:
流的核心结构是一对,其car
是序列的当前值,其cdr
是评估下一项的承诺,这是通过以下构造实现的:
(define (cons-stream a b) (cons a (delay b)))
其中 (delay b)
等价于 (lambda () b)
.
当对这对cdr
求值时,会强制对流的延迟元素求值,这样我们就可以得到下一个元素,实现如下:
(define (stream-cdr stream) (force (cdr stream)))
其中(force delayed-object)
只是(delayed-object)
的执行。
通过这种构造,我们现在可以轻松地透明地构建带有流的递归过程,就好像它们是 map 中的常规列表一样:
(define (stream-map proc stream)
(if (stream-null? stream)
the-empty-stream
(cons-stream (proc (stream-car s))
(stream-map p (stream-cdr s)))))
我正在尝试使用 Elisp 编写类似的流实现,但我还没有找到实现 delay
的方法,因此它允许我以与 Scheme 类似的方式编写递归过程,目前我的解决方法是将延迟作为 lambda 表达式放在递归过程中,如下所示:
(defun stream-map (proc stream)
(lexical-let ((p proc)
(s stream))
(if (stream-null? stream)
the-empty-stream
(cons-stream (funcall p (stream-car s))
(lambda ()
(stream-map p (stream-cdr s)))))))
这显然不如 Scheme 实现好。
这些是我创建流的核心函数的 Elisp 版本:
(defun cons-stream (a b) (cons a b))
(defun stream-cdr (stream) (sicp-force (cdr stream)))
(defun sicp-force (exp) (funcall exp))
如何编写 delay
和其他流函数,这样我就不必将 lambda
放在递归过程中?
感谢@Gerstmann 的建议,我能够编写我正在寻找的结构。新的实现现在看起来像:
(setq the-empty-stream nil)
(defun stream-null? (s) (eq s the-empty-stream))
(defun my/sicp-delay (exp) `(lambda () ,exp))
(defun my/sicp-force (exp) (funcall exp))
(defmacro my/cons-stream (a b) (list 'cons a (my/sicp-delay b)))
(defun my/stream-car (stream) (car stream))
(defun my/stream-cdr (stream) (my/sicp-force (cdr stream)))
现在我可以编写看起来与 Scheme 实现一样干净的过程:
(defun my/stream-enumerate-interval (low high)
(lexical-let ((l low)
(h high))
(if (> l h)
the-empty-stream
(my/cons-stream low
(my/stream-enumerate-interval (1+ l) h)))))
; this returns 12
(my/stream-car (my/stream-cdr (my/stream-cdr (my/stream-enumerate-interval 10 20))))
我正在阅读 SICP 书的第 3.5 节,我正在尝试实现 使用 Elisp 的流。书中使用Scheme语言实现流如下:
流的核心结构是一对,其car
是序列的当前值,其cdr
是评估下一项的承诺,这是通过以下构造实现的:
(define (cons-stream a b) (cons a (delay b)))
其中 (delay b)
等价于 (lambda () b)
.
当对这对cdr
求值时,会强制对流的延迟元素求值,这样我们就可以得到下一个元素,实现如下:
(define (stream-cdr stream) (force (cdr stream)))
其中(force delayed-object)
只是(delayed-object)
的执行。
通过这种构造,我们现在可以轻松地透明地构建带有流的递归过程,就好像它们是 map 中的常规列表一样:
(define (stream-map proc stream)
(if (stream-null? stream)
the-empty-stream
(cons-stream (proc (stream-car s))
(stream-map p (stream-cdr s)))))
我正在尝试使用 Elisp 编写类似的流实现,但我还没有找到实现 delay
的方法,因此它允许我以与 Scheme 类似的方式编写递归过程,目前我的解决方法是将延迟作为 lambda 表达式放在递归过程中,如下所示:
(defun stream-map (proc stream)
(lexical-let ((p proc)
(s stream))
(if (stream-null? stream)
the-empty-stream
(cons-stream (funcall p (stream-car s))
(lambda ()
(stream-map p (stream-cdr s)))))))
这显然不如 Scheme 实现好。
这些是我创建流的核心函数的 Elisp 版本:
(defun cons-stream (a b) (cons a b))
(defun stream-cdr (stream) (sicp-force (cdr stream)))
(defun sicp-force (exp) (funcall exp))
如何编写 delay
和其他流函数,这样我就不必将 lambda
放在递归过程中?
感谢@Gerstmann 的建议,我能够编写我正在寻找的结构。新的实现现在看起来像:
(setq the-empty-stream nil)
(defun stream-null? (s) (eq s the-empty-stream))
(defun my/sicp-delay (exp) `(lambda () ,exp))
(defun my/sicp-force (exp) (funcall exp))
(defmacro my/cons-stream (a b) (list 'cons a (my/sicp-delay b)))
(defun my/stream-car (stream) (car stream))
(defun my/stream-cdr (stream) (my/sicp-force (cdr stream)))
现在我可以编写看起来与 Scheme 实现一样干净的过程:
(defun my/stream-enumerate-interval (low high)
(lexical-let ((l low)
(h high))
(if (> l h)
the-empty-stream
(my/cons-stream low
(my/stream-enumerate-interval (1+ l) h)))))
; this returns 12
(my/stream-car (my/stream-cdr (my/stream-cdr (my/stream-enumerate-interval 10 20))))