5

在Lisp中，第 267，Paul Graham 提供了延续传递宏的实现：

(setq *cont* #'identity)

(defmacro =lambda (parms &body body)
  `#'(lambda (*cont* ,@parms) ,@body))

(defmacro =defun (name parms &body body)
  (let ((f (intern (concatenate 'string
                "=" (symbol-name name)))))
    `(progn
       (defmacro ,name ,parms
     `(,',f *cont* ,,@parms))
       (defun ,f (*cont* ,@parms) ,@body))))

(defmacro =bind (parms expr &body body)
  `(let ((*cont* #'(lambda ,parms ,@body))) ,expr))

(defmacro =values (&rest retvals)
  `(funcall *cont* ,@retvals))

下面的代码为一棵树t2的每个叶子遍历一棵树t1，使用这个实现，我想知道restart调用时会发生什么，特别是在叶子t1从A（第一个元素）更改为B（第二个元素）之后。当restart被调用时，它只是简单地从 中弹出一个 lambda 函数*saved*，然后该 lambda 函数再次调用dft-nodewith (cdr tree)。但是这个调用是在最外层范围之外=bind进行的，并且=bind是负责绑定的*cont*。*cont*那么，外部引入的绑定如何=bind仍在范围内呢？

(setq *saved* nil)

(=defun dft-node (tree)
    (cond ((null tree) (restart))
          ((atom tree) (=values tree))
          (t (push #'(lambda () (dft-node (cdr tree))) *saved*)
             (dft-node (car tree)))))

(=defun restart ()
    (if *saved*
        (funcall (pop *saved*))
      (=values 'done)))

(setq t1 '(a (b (d h)) (c e (f i) g))
      t2 '(1 (2 (3 6 7) 4 5)))

(=bind (node1) (dft-node t1)
  (if (eq node1 'done)
      'done
    (=bind (node2) (dft-node t2)
      (list node1 node2))))

最后一种形式展开为

(let ((*cont* (lambda (node1)
                (if (eq node1 'done)
                    'done
                    (let ((*cont* (lambda (node2)
                                    (list node1 node2))))
                      (dft-node t2))
  (dft-node t1))))))

这产生(a 1). 根据 Graham 的说法，后续调用restart应该产生(a 2)，等等，直到(a 5)，然后后续调用应该产生(b 1), (b 2)，等等，直到 finally (g 5)：

> (let ((node1 (dft-node t1)))
    (if (eq? node1 ’done)
        ’done
        (list node1 (dft-node t2))))
(A 1)
> (restart)
(A 2)
…
> (restart)
(B 1)

之后(a 1)，*cont*建立的绑定let应该不再存在。后续如何调用restart这些值？的范围是否let仍然适用于单独的调用restart？这里发生了什么？

4

1 回答 1

7

在 Lisp上略早于 Common Lisp，因此存在一些不兼容性

On Lisp是在 Common Lisp 真正固化为一种语言之前编写的，因此On Lisp和 Common Lisp中出现的代码之间存在一些不兼容性。On Lisp上的CLiki 条目指出，这些延续传递宏实际上是不兼容的地方之一（强调添加）：

在定义延续传递宏（第 267 页）时，Paul Graham 似乎假设cont全局变量具有词法范围。这与 Common Lisp 标准相矛盾。在当今的 Common Lisp 实现中，上述宏不起作用。此外，这个问题对于新手来说可能非常混乱。修复宏的建议解决方案是（请注意，使用 #'values 而不是 #'identity - 根据 Paul Graham 的勘误表）：

  • 使用可以被 let 或 lambda 遮蔽的符号宏模拟词法范围的全局变量cont
    ： (defvar actual-cont #'values)
    (define-symbol-macro *cont* *actual-cont*)
  • 只需省略 (setq *cont* #'identity) 并将“顶级”延续传递函数称为 (=somefunc #'values ...)
  • …</li>

这是对问题的简短描述，值得进一步研究，以帮助将来遇到它的任何新人。查看有关同一问题的其他讨论也可能会有所帮助，包括：

  • <On Lisp> 的第 268 页...一个来自 2006 年的 comp.lang.lisp 线程，其中用户询问(setq *cont* ...)和(defvar *cont* ...)之间的区别。在这个线程中，人们注意到On Lisp早于 ANSI Common Lisp。

究竟发生了什么？

由于(=bind ...)扩展为(let ((*cont* ...)) ...)，如果*cont*是一个特殊变量（即，具有动态范围），那么你是绝对正确的，那么一旦你在let之外，*cont*的原始绑定，即身份是应该为调用重新启动而设置的。如果*cont*被声明为特殊的，那么您会得到以下行为：

CONTINUATIONS> (=bind (node1) (dft-node '(a (b (d h)) (c e (f i) g)))
                 (if (eq node1 'done)
                     'done
                     (=bind (node2) (dft-node '(1 (2 (3 6 7) 4 5)))
                       (list node1 node2))))
(A 1)
CONTINUATIONS> (restart)
2
CONTINUATIONS> (restart)
3
CONTINUATIONS> (restart)
6
CONTINUATIONS> (restart)
7
CONTINUATIONS> (restart)
4
CONTINUATIONS> (restart)
5
CONTINUATIONS> (restart)
B
CONTINUATIONS> (restart)
D

这是有道理的，因为在得到 (a 1) 之后，*saved*包含两个函数。第一个是在下一个分支上继续遍历数字树的树，将被调用的*cont*是全局树#'identity，因为我们现在不在=bind形式之外。这就是为什么我们得到 2, 3, ... 作为结果。此时*saved*中的第二个函数将继续遍历 B 处的字母树。

我们没有得到一堆列表 (a 1), (a 2), ..., (b 1) 等的原因是我们（合理地）假设*cont*是特殊的，即动态的边界。事实证明，格雷厄姆打算让*cont* 不特别；他希望它成为一个全球词汇。从在 Lisp上，第 268 页：

正是通过操纵*cont*，我们将获得延续的效果。尽管*cont*有一个全局值，但它很少被使用：*cont*几乎总是一个参数，由 捕获并由 =values定义的宏 =defun。add1例如，在 的主体内*cont*是参数而不是全局变量。*cont*这种区别很重要，因为如果不是局部变量，这些宏将不起作用。这就是为什么 在 a而不是 a*cont*中给出它的初始值：后者也会宣称它是特殊的。setqdefvar

在 Lisp上略早于 Common Lisp，因此在撰写本文时这不一定是不正确的，但 Common Lisp 实际上并没有全局词法变量，因此在顶部使用(setq *cont* ...)并非如此- level 必然会创建一个全局词法变量。在 Common Lisp 中，未指定确切的结果。一些实现会将其视为全局词法，其他实现会假设您的意思是defparameter或defvar，您最终会得到一个全局特殊变量。正如格雷厄姆所说，那是行不通的。听起来你有一个实现后者的实现，所以事情不起作用。

一些实现实际上会抱怨他的代码。例如，SBCL 正确地抱怨，打印“警告：未定义变量：CONTINUATIONS::*CONT*”，并在使用*cont*(setq *cont* …)时发出样式警告，指出它“正在使用符号的词法绑定（CONTINUATIONS:: *CONT*)，而不是动态绑定，即使名称遵循特殊变量的通常命名约定（如 *FOO* 之类的名称）。”

应该发生什么？

要了解这应该如何工作，可能更容易查看一个没有On Lisp版本中所有管道的更简单的实现：

(defparameter *restarts* '())

(defun do-restart ()
  (if (endp *restarts*) nil
      (funcall (pop *restarts*))))

(defun traverse-tree (k tree)
  (cond
    ((null tree) (do-restart))
    ((atom tree) (funcall k tree))
    (t (push (lambda () (traverse-tree k (cdr tree))) *restarts*)
       (traverse-tree k (car tree)))))

在这里，我们不隐藏任何延续传递机制或*restarts*列表。有了这个，我们得到了这个行为：

CL-USER> (traverse-tree 'identity '((1 2) (3 4)))
1
CL-USER> (do-restart)
2
CL-USER> (do-restart)
3
CL-USER> (do-restart)
4
CL-USER> (do-restart)
NIL

我们也可以重新创建多列表遍历，我认为我们得到了您所期望的结果：

CL-USER> (let ((k (lambda (num)
                    (traverse-tree (lambda (alpha)
                                     (list num alpha))
                                   '(a (b) c)))))
           (traverse-tree k '((1 2) 3)))
(1 A)
CL-USER> (do-restart)
(1 B)
CL-USER> (do-restart)
(1 C)
CL-USER> (do-restart)
(2 A)
CL-USER> (do-restart)
(2 B)
CL-USER> (do-restart)
(2 C)
CL-USER> (do-restart)
(3 A)
CL-USER> (do-restart)
(3 B)
CL-USER> (do-restart)
(3 C)
CL-USER> (do-restart)
NIL

这里的不同之处在于，一旦我们离开为我们绑定延续的let范围，就没有对*cont*的引用会改变含义。

在我看来，一个更好的实现会简单地使用一个普通的词汇 a 变量来存储延续（有点像上面的k，但可能使用由gensym产生的名称），并且只需要“对延续传递函数的调用最终必须是包裹在定义最外层延续的=bind中。

于 2014-07-14T15:04:09.687 回答