宏在通用lisp中的延续-关于OnLisp的实现 [英] continuation in common lisp by macros -- regarding an implemetation in OnLisp
问题描述
在 在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))
以下为树t1的每个叶子遍历一棵树t2的代码使用此实现，我想知道调用restart时会发生什么，尤其是当t1的叶子更改后从A(第一个元素)到B(第二个元素).调用restart时，它只是从*saved*中弹出一个lambda函数，然后该lambda函数再次使用(cdr tree)调用dft-node.
但是，此调用在最外面的=bind的范围内 进行，并且=bind负责绑定*cont*.那么，外部=bind引入的*cont*绑定如何仍在范围内?
(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)，依此类推，直到最终成为(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)之后，let建立的*cont*绑定应不再存在.随后调用restart这些值如何? let的范围是否仍适用于对restart的单独调用?这是怎么回事?
在Lisp上早于Common Lisp，因此存在一些不兼容之处
On Lisp 是在Common Lisp实际被巩固为一种语言之前编写的，因此 On Lisp 中出现的代码与Common Lisp之间存在一些不兼容性. 在Lisp上 上的 CLiki条目指出，这些连续传递宏实际上是不兼容(加重)的地方之一:
在定义连续传递宏时(第267页)，保罗·格雷厄姆(Paul Graham)似乎 假设 cont 全局变量具有词法范围.这 与Common Lisp标准相矛盾. 与今天共同Lisp 实现中，前面提到的宏根本不起作用.还有这个 对于新来者来说，这个问题可能会非常令人困惑.建议的解决方案 固定宏是(请注意，使用#'values代替 #'身份-根据Paul Graham的勘误表:
- 使用可以被let或lambda遮盖的符号宏模拟词法范围内的全局变量 cont :
(defvar actual-cont #'值)
(定义符号宏* cont * * actual-cont *)- 仅省略(setq * cont *#'identity)并以(= somefunc#'values ...)形式调用顶级"连续传递函数
- …
这是对该问题的简短描述，值得进一步研究，以帮助将来遇到此问题的任何新来者.看到有关同一问题的其他讨论也可能会有所帮助，包括:
- < On Lisp>的第268页... 2006年以来的comp.lang.lisp线程，其中用户询问(setq * cont * ...)和(defvar * cont * ...)之间的区别.在该线程中，人们注意到在Lisp上早于ANSI Common Lisp.
实际上发生了什么?
由于(= bind…)扩展为(let((** cont *…))…)，如果 * cont * 是一个特殊变量(即，具有动态范围)，一旦您离开该 let ，则 * cont * 的原始绑定，即 identity (身份)是调用重新启动功能的位置.如果 * 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)后， *保存* 包含两个功能.第一个是将继续遍历下一个分支上的数字树的树，而被称为 * cont * 的是全局树，即#'identity ，因为我们现在位于 = bind 表单之外.这就是为什么我们得到2，3，...作为结果的原因.此时 * saved * 中的第二个功能是将继续遍历B处的字母树的功能.
我们上面没有一堆列表(a 1)，(a 2)，...，(b 1)等的原因是，我们(合理地)假设 * cont * 是特殊的，即动态绑定.事实证明，格雷厄姆(Graham)打算 * cont * not 特殊.他希望它成为全球词汇.从 在Lisp上 ，第268页:
通过操纵
*cont*，我们将获得以下效果: 延续.尽管*cont*具有全局值，但这很少 使用的那个:*cont*几乎总是一个参数，由=values和由定义的宏=defun.例如，在add1的正文中，*cont*是一个参数，而不是全局变量.这种区别很重要，因为这些 如果*cont*不是本地变量，则宏将不起作用.这就是为什么 在setq中给*cont*赋予了其初始值，而不是defvar:后者也会宣称它是特殊的.
在Lisp上早于Common Lisp，因此在撰写本文时并不一定正确，但是Common Lisp实际上没有全局词汇变量，因此使用<顶层的strong>(setq * cont *…)必须会创建一个全局词法变量.在Common Lisp中，未指定确切结果.有些实现将其视为全局词汇，而其他实现则假定您是指 defparameter 或 defvar ，最后会得到全局 special 变量.正如格雷厄姆所说，那是行不通的.听起来好像您有一个实现可以实现后者的实现，所以一切都无法正常进行.
某些实现实际上会抱怨他的代码.例如，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 中.
In On Lisp, p. 267, Paul Graham provides an implementation of continuation passing macros:
(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))
The following code to traverse a tree t2 for each leaf of a tree t1, uses this implementation, and I am wondering what happens when restart is called, especially after when the leaf of t1 changed from A (the first element) to B (the second element). When restart is called, it simply pops a lambda function from *saved*, and that lambda function calls dft-node with (cdr tree) again.
But this call is made outside the scope of the outermost =bind, and =bind was responsible for binding *cont*. How is the binding of *cont* introduced by the outer =bind still in scope, then?
(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))))
The last form expands to
(let ((*cont* (lambda (node1)
(if (eq node1 'done)
'done
(let ((*cont* (lambda (node2)
(list node1 node2))))
(dft-node t2))
(dft-node t1))))))
This produces (a 1). According to Graham, subsequent calls to restart should produce (a 2), and so on, up to (a 5), and then subsequent calls should produce (b 1), (b 2), and so on, until 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)
After (a 1), the binding of *cont* established by let should no longer be in place. How do subsequent calls to restart these values? Is the scope of let still applied to a separate call to restart? What is going on here?
On Lisp slightly predates Common Lisp, so there are some incompatibilities
On Lisp was written before Common Lisp had actually been solidified as a language, so there are some incompatibilities between the code that appears in On Lisp and Common Lisp. The CLiki entry on On Lisp notes that these continuation passing macros are actually one of the places where there's an incompatibility (emphasis added):
When defining continuation-passing macros (p. 267) Paul Graham seems to be assuming that cont global variable has lexical scope. This contradicts Common Lisp standard. With present day Common Lisp implementations, the aforementioned macros just don't work. Also, this issue can be very confusing for newcomers. Suggested solutions for fixing the macros are (note that #'values is used instead of #'identity - according to Paul Graham's Errata):
- emulate lexically scoped global variable cont using symbol-macro that can be shadowed by let or lambda:
(defvar actual-cont #'values)
(define-symbol-macro *cont* *actual-cont*)- just omit (setq *cont* #'identity) and call "top-level" continuation-passing function as (=somefunc #'values ...)
- …
That's a pretty short description of the problem, and it's worth looking into a bit more, to help any newcomers who come across it in the future. It may also be helpful to see other discussions of this same issue, including:
- Page 268 of <On Lisp>... A comp.lang.lisp thread from 2006 in which a user asks about the difference between (setq *cont* …) and (defvar *cont* …). In this thread, people note that On Lisp predates ANSI Common Lisp.
What's actually happening?
Since (=bind …) expands to (let ((*cont* …)) …), you're absolutely right in that, if *cont* is a special variable (i.e., with dynamic extent), then once you're outside of that let, the original binding of *cont*, which is identity is what should be in place for calls to restarts. If *cont* is declared special, then you get the following behavior:
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
This makes sense, because after getting (a 1), *saved* contains two functions. The first is one that will continue traversing the numeric tree on the next branch, and the *cont* that will be called is the global one, #'identity, since we're now outside of the =bind form. That's why we get 2, 3, … as results. The second function in *saved* at this point is the one that will continue traversing the alphabetic tree at B.
The reason that we don't get a bunch of lists (a 1), (a 2), …, (b 1), etc., above is that we (reasonably) assumed that *cont* is special, i.e., dynamically bound. It turns out that Graham intends for *cont* not to be special; he wants it to be a global lexical. From On Lisp, page 268:
It is by manipulating
*cont*that we will get the effect of continuations. Although*cont*has a global value, this will rarely be the one used:*cont*will nearly always be a parameter, captured by=valuesand the macros defined by=defun. Within the body ofadd1, for example,*cont*is a parameter and not the global variable. This distinction is important because these macros wouldn’t work if*cont*were not a local variable. That’s why*cont*is given its initial value in asetqinstead of adefvar: the latter would also proclaim it to be special.
On Lisp slightly predates Common Lisp, so this wasn't necessarily incorrect at the time of writing, but Common Lisp doesn't actually have global lexical variables, so it's not the case that using (setq *cont* …) at the top-level will necessarily create a global lexical variable. In Common Lisp, the exact results are unspecified. Some implementations will treat it like a global lexical, others will assume that you meant defparameter or defvar, and you'll end up with a global special variable. As Graham notes, that won't work. It sounds like you've got an implementation that does the latter, so things don't work.
Some implementations will actually complain about his code. SBCL, for instance, rightly complains at (setq *cont* …), printing "warning: undefined variable: CONTINUATIONS::*CONT*", and issues a style warning when *cont* is used that it is "using the lexical binding of the symbol (CONTINUATIONS::*CONT*), not the dynamic binding, even though the name follows the usual naming convention (names like *FOO*) for special variables."
What's supposed to happen?
To understand how this is supposed to work, it's probably easier to look at a simpler implementation that doesn't have all the plumbing that's in the On Lisp version:
(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)))))
Here we don't hide any of the continuation passing mechanism or the *restarts* list. With this, we get this behavior:
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
We can recreate the multiple-list traversal one, too, and I think we get the results that you were expecting:
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
The difference here is that there are no references to *cont* that change meaning once we leave the scope of the let that bound the continuation for us.
In my opinion, a better implementation would simply use a normal lexical a variable to store the continuation (sort of like k above, but probably with a name produced by gensym), and would just require that "calls to continuation passing functions must ultimately be wrapped in a =bind that defines the outermost continuation.
这篇关于宏在通用lisp中的延续-关于OnLisp的实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
