Common Lisp 中的宏延续——关于 OnLisp 中的实现

2023-12-12

In 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 with (cdr tree)再次。 但是这个电话已经打了outside最外层的范围=bind, and =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)

After (a 1),绑定*cont*建立者let不应再就位。后续调用如何restart这些值?范围是否为let仍然适用于单独的调用restart?这里发生了什么?


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

On Lisp是在 Common Lisp 实际上被固化为一种语言之前编写的,因此出现在中的代码之间存在一些不兼容性On Lisp和 Common Lisp。这CLIki 条目On Lisp请注意,这些连续传递宏实际上是不兼容的地方之一(添加了强调):

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

  • 模拟词法作用域的全局变量cont使用可以被 let 或 lambda 遮蔽的符号宏:
    (定义变量实际续#'值)
    (定义符号宏*续* *实际续*)
  • 只需省略 (setq *cont* #'identity) 并将“顶级”连续传递函数调用为 (=somefunc #'values ...)

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

  • 第268页...2006 年的 comp.lang.lisp 线程,其中用户询问以下两者之间的区别(设置*继续*...) and (defvar*续*...)。在这个帖子中,人们注意到On Lisp早于 ANSI Common Lisp。

到底发生了什么?

Since (=绑定...)扩展到(让((*续* …))…),你是绝对正确的,如果*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) 后,*saved*包含两个函数。第一个是在下一个分支上继续遍历数字树,并且*cont*这将被称为全局的,#'身份,因为我们现在在=bind形式。这就是为什么我们得到 2、3……结果。第二个函数在*saved*此时将继续遍历 B 处的字母树。

上面我们没有得到一堆列表 (a 1), (a 2), …, (b 1) 等的原因是我们(合理地)假设*cont*是特殊的,即动态绑定的。事实证明,格雷厄姆的目的是*cont* not变得特别;他希望它成为一个全球词汇。从On Lisp,第 268 页:

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

On Lisp稍微早于 Common Lisp,所以在撰写本文时这不一定是错误的,但 Common Lisp 实际上没有全局词法变量,所以情况并非如此(setq *继续* …)在顶层必然会创建一个全局词法变量。在 Common Lisp 中,确切的结果未指定。有些实现会将其视为全局词汇,其他实现会假设您的意思是定义参数 or defvar,你最终会得到一个全局的special多变的。正如格雷厄姆指出的那样,这是行不通的。听起来您已经有了执行后者的实现,所以事情不起作用。

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

应该发生什么?

要了解这是怎么回事supposed为了工作,查看一个更简单的实现可能更容易,该实现没有所有的管道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)))))

这里我们不隐藏任何连续传递机制或*重新启动*列表。这样,我们得到了这样的行为:

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

这里的区别在于没有引用*cont*一旦我们离开范围,意义就会改变let这限制了我们的继续。

在我看来,更好的实现只需使用普通的词法 a 变量来存储延续(有点像k上面,但可能有一个由gensym),并且只要求“对连续传递函数的调用最终必须包装在=bind定义了最外层的延续。

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

Common Lisp 中的宏延续——关于 OnLisp 中的实现 的相关文章

  • Lisp 内部引用工作

    口齿不清是如何做到的quote内部工作 例如 quote 1 1 2 似乎相当于 list 1 list 1 2 这意味着它是如何递归地象征 Head 值的 这个功能是内置的吗 Run equal quote 1 1 2 list 1 li
  • Scheme/Racket有枚举操作吗?

    Scheme Racket 是否有相当于 Haskell 中的 a b 表示法的枚举表示法 在 Haskell 中 1 5 计算结果为列表 1 2 3 4 5 for list i in range 1 6 i sequence gt li
  • 了解 LISP 中的绑定变量和自由变量

    我正在阅读SICP 又出现了绑定变量和自由变量的话题 然而 我对此感到困惑 术语 绑定变量 仅适用于形式参数变量吗 此外 文本还指出过程定义 绑定 其形式参数 这让我感到困惑 因为有些人说我们将值 绑定 到变量 显然 当我们谈论不同类型的变
  • Clozure Common Lisp - TCP 套接字编程 - 发送回复

    我有一个非常小的程序 它打开一个套接字并接受一个连接 然后它会获取远程 IP 和端口 我想向远程计算机 telnet 发送一条短信并关闭连接 我无法确定哪个函数用于向 telnet 客户端发送消息 The Clozure手册 http cc
  • 连续单子转变

    在尝试为 ContT monad 转换器建立一些直觉时 我 也许并不奇怪 发现自己很困惑 问题在于 shiftT 操作似乎没有做任何有用的事情 首先是一个如何使用它的简单示例 shiftT famr gt lift do a lt calc
  • 查找 lambda 表达式中的自由变量

    有谁知道如何找出 lambda 表达式中的自由变量 自由变量是不属于 lambda 参数的变量 我当前的方法 这对我毫无帮助 是简单地使用 car 和 cdr 来遍历表达式 我的主要问题是确定一个值是否是一个变量或者它是否是方案原语之一 有
  • 在 Parenscript 中使用 regex(正则表达式)

    我正在尝试 Parenscript 在尝试使用正则表达式函数时 我得到了意外的输出 例如 参考手册 https common lisp net project parenscript reference html shows regex f
  • 使用 MonadRef 实现 MonadCont

    有一个众所周知的问题我们不能使用forall类型在Cont返回类型 https stackoverflow com questions 7178919 how to make callcc more dynamic 7180154 7180
  • LISP 中的变量和符号有什么区别?

    从范围上来说 内存中的实际实现 语法 例如 if let a 1 a 是变量还是符号 约尔格的回答指出了正确的方向 让我补充一点 我将讨论与 Common Lisp 类似的 Lisp 作为数据结构的符号 符号是 Lisp 中真实的数据结构
  • 任意类型说明符上的 Defmethod?

    我想做的是 defgeneric fn x defmethod fn x integer 1 Positive integer defmethod fn x integer 1 Negative integer 我想要一个可以与任意类型说明
  • 宏扩展可以包含(声明...)表达式吗?

    Common Lisp Hyperspec 规定 宏形式不能扩展为声明 声明表达式必须显示为它们引用的形式的实际子表达式 我对 扩展到 的含义感到困惑 由于显而易见的原因 如下宏将不起作用 defmacro optimize fully d
  • 用通用函数替换普通函数

    我想将 elt nth 和 mapcar 等名称与我正在原型设计的新数据结构一起使用 但这些名称指定普通函数 因此我认为需要将其重新定义为通用函数 重新定义这些名称可能是一种不好的形式 有没有办法告诉 defgeneric 不要生成程序错误
  • 对于案例,这些表达案例的方法中哪种最好?

    这些都有效 defun testcaseexpr thecase case thecase foo format t matched foo bar format t matched bar funk format t matched fu
  • Common Lisp 鼠标位置与 ltk

    我正在 Common Lisp 中制作一个简单的小程序 我想使用鼠标移动来控制它 我用 LTK 作为窗口 我找不到任何可以检索鼠标位置的函数 例如 Emacs Lisp 有 鼠标像素位置 我发现这在罗塞塔代码上 https rosettac
  • Letrec 和可重入延续

    有人告诉我 以下表达式的计算结果为 0 但许多方案的实现将其计算为 1 let cont f letrec x call with current continuation lambda c set cont c 0 y call with
  • Common Lisp——为什么这个符号不是外部的?

    我正在尝试在 ASDF 中运行测试 如下所示 foo asd defsystem foo tests depends on foo fiveam components module tests components file main pe
  • 解决斐波那契数列的 Lisp 方法

    我想尝试学习 Lisp 但很快就放弃了 我想我会再试一次 我正在看 求 400 万以下所有偶数斐波那契数的总和 我写了下面的代码 它可以工作 但是很丑陋 其中最主要的是它太慢了 因为它一直在进行简单的递归 当我用 Python 编写这个程序
  • gensym 在 Lisp 中做什么?

    我听到一些同学谈论他们如何使用该功能gensym为此 我问他们它做了什么 甚至在网上查了一下 但我真的无法理解这个函数的作用是什么两者都不为什么或何时最好使用它 特别是 我对它在 Lisp 中的作用更感兴趣 谢谢你们 独特且未被拘禁的符号
  • 学习 Lisp 的资源 [关闭]

    就目前情况而言 这个问题不太适合我们的问答形式 我们希望答案得到事实 参考资料或专业知识的支持 但这个问题可能会引发辩论 争论 民意调查或扩展讨论 如果您觉得这个问题可以改进并可能重新开放 访问帮助中心 help reopen questi
  • 学习 LISP 的最佳方法是什么? [关闭]

    就目前情况而言 这个问题不太适合我们的问答形式 我们希望答案得到事实 参考资料或专业知识的支持 但这个问题可能会引发辩论 争论 民意调查或扩展讨论 如果您觉得这个问题可以改进并可能重新开放 访问帮助中心 help reopen questi

随机推荐