通过宏继续使用常见的lisp - 关于OnLisp中的实现

Question

在On Lisp,p.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-node用(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).根据格雷厄姆的说法,随后的调用restart应该产生(a 2),等等(a 5),然后是后续的调用应该产生(b 1),(b 2)等等,直到最后(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？这里发生了什么？

Answer 1

在Lisp上稍微早于Common Lisp,因此存在一些不兼容性

在Lisp实际上已经固化为语言之前编写了Lisp,因此在On Lisp和Common Lisp 中出现的代码之间存在一些不兼容性.On Lisp上的CLiki条目指出,这些继续传递宏实际上是不兼容的地方之一(强调添加):

在定义连续传递宏(p.267)时,Paul Graham似乎假设cont全局变量具有词法范围.这与Common Lisp标准相矛盾.使用当前的Common Lisp实现,前面提到的宏不起作用.此外,这个问题对于新手来说可能非常混乱.修复宏的建议解决方案是(注意使用#'值代替#'身份 - 根据Paul Graham的勘误表):

• 使用符号宏来模拟词法范围的全局变量cont,可以通过let或lambda阴影:(
  defvar actual-cont#'values)
  (define-symbol-macro*cont**actual-cont*)
• 只是省略(setq*cont*#'identity)并将"top-level"继续传递函数称为(= somefunc#'values ...)
• ...

这是对问题的简短描述,值得进一步研究,以帮助任何未来遇到它的新手.查看同一问题的其他讨论也可能有所帮助,包括:

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

实际发生了什么？

因为(= bind ...)扩展为(let((*cont*...))...),你完全正确,如果*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*是全局的,#'身份,因为我们现在在= bind表单之外.这就是为什么我们得到2,3,......作为结果.此时*saved*中的第二个函数是将继续遍历B处的字母树的函数.

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

通过操纵*cont*我们将获得延续的效果.虽然*cont*具有全局值,但这很少会使用:*cont*将几乎总是一个参数,由所捕获 =values的宏和由其定义的宏 =defun.add1例如,在体内*cont*是参数而不是全局变量.这种区别很重要,因为如果*cont*不是局部变量,这些宏将无法工作.这就是为什么 *cont*在a setq而不是a中给出它的初始值defvar:后者也会宣称它是特殊的.

在Lisp上略微早于Common Lisp,所以在编写本文时这并不一定是错误的,但是Common Lisp实际上并没有全局词汇变量,所以在顶部使用(setq*cont*...)不是这样的情况.级别必然会创建一个全局词汇变量.在Common Lisp中,确切的结果未指定.有些实现会将它视为全局词法,其他实现会认为你的意思是defparameter或defvar,而你最终会得到一个全局特殊变量.正如格雷厄姆所说,这是行不通的.听起来你有一个实现后者,所以事情不起作用.

有些实现实际上会抱怨他的代码.例如,SBCL正确地抱怨(setq *cont* …),打印"警告:未定义变量:CONTINUATIONS ::*CONT*",并在使用*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*的引用改变含义.

在我看来,一个更好的实现只是使用一个正常的词法变量来存储延续(有点像上面的k,但可能是由gensym产生的名字),并且只需要"对继续传递函数的调用必须最终是包含在= bind中,它定义了最外层的延续.