如果你有一个表达式(+ (* 2 3) (/ 10 2)),Scheme系统不会同时评估所有内容,而是部分评估.方案没有在Scheme中指定,但让我们想象它是从左到右(我认为Racket总是从左到右):
你(* 2 3),延续到这将是计算(/ 10 2),然后(+ result1 result2).Scheme系统可以这样做的方法是在执行之前将代码转换为Continuation传递样式.上面的表达式变成了这样的东西:
(lambda (k)
(*& 2
3
(lambda (result1)
(/& 10
2
(lambda (result2)
(+& result1 result2 k))))))
现在,最后的程序与&Scheme中的程序相同,除了它是最后一个参数的延续.其中一个例子:(define (+& a b k) (k (+ a b))).所有其他的都是这样完成的,被认为是原始的.
如果你申请并通过display或values它将显示或评估为11.但是,如果你使用,call/cc你可以覆盖它.想象一下这个变种:
(call/cc (lambda (k) (+ (* 2 3) (/ 10 (if (zero? a) (k +inf.0) a))
在Scheme中,如果除以零,则会出现错误,如果发生这种情况,您需要取消其余的计算,并说结果是无限的.上面的代码就是这样,如果a为零,它将不会对前两个计算的结果求和.它实际上充当GOTO.该代码的CPS版本看起来像这样:
(lambda (k)
(*& 2
3
(lambda (result1)
(zero?& a
(lambda (azero?)
(if azero?
(k +inf.0) ; continuation used here
(/& 10
a
(lambda (result2)
(+& result1 result2 k))))))))) ; and here
那怎么call/cc办？那么它可以让你按常规方式编码,而不是CPS就像计算机如何进行实际计算,但是通过掌握延续来获得最佳的两个世界,这样你就可以像在CPS中编写它一样.
现在,想象一下这个代码块:
(let* ((c 10)
(r (call/cc (lambda (exit) exit))))
(display "Hello\n")
(cond ((zero? c) 'done)
(else (set! c (- c 1))
(r r))))
在这里你看到我将继续作为r.继续是从设置开始的其余计算r,然后做display...这实际上显示"hello \n"11次,因为当你在底部调用延续时它再次执行相同的操作.
就像eval我尝试将其保持在绝对最小值时一样,当我这样做时,我通常会这样做以从正在进行的计算中获得中止.例如.
(define (lstadd1 lst)
(call/cc (lambda (exit)
(let loop ((lst lst))
(cond ((pair? lst) (cons (add1 (car lst)) (loop (cdr lst))))
((null? lst) '())
(else (exit #f))))))) ; not proper
(lstadd1 '(1 2 3)) ; ==> (2 3 4)
(lstadd1 '(1 2 . 3)) ; ==> #f
有关更多示例,我喜欢Matt Mights页面,其中包含有关如何使用continuation的大量示例.
并非所有的实现call/cc都完全相同,但希望这个答案可以适用于包括Racket在内的所有常见变体.这个故事实际上是基于Unlambda的c内置.
你是一位超级英雄的考古学家,在一个古老的玛雅遗址上挖掘.您将在优雅的拱门中挖掘出精美的,保存完好的石头门廊.但它只是一个门口,已经摆在它的一边; 它附近没有任何墙壁,它似乎也不是墙壁的一部分.您的员工会从中获取能量读数,因此您可以将其完整地运回实验室进行学习.
在你的实验室里,墙上挂着一个大钟,直接放在现在直立的拱门前面,你已放置在房间中间附近.在检查拱门时,你会走过它.
下午4:17
走过拱门之后,你现在惊讶地发现,你手里拿着一个立方体盒子,大到足以把书放进去,带盖子和一个发光的按钮.你不记得拿起这样的盒子,或者之前看过它.你打电话给你的助手,询问盒子的来源.助手不知道.如果放下盒子,按钮会停止发光.你再次拿起它,按钮再次发光.只有握住它才会发光; 如果助手拿起盒子就不会发光.在百灵鸟上,你将一个回形针放入盒子里,关上盖子,然后按下按钮.
下午4:23
走过拱门之后,你会惊讶地发现,你手里拿着一个回形针.你不记得捡起来了.你的助手在房间里,盯着你傻眼了.你不记得你的助手进入房间.你的时钟似乎快几分钟.
"刚刚发生了什么？" 问助手.
"我只是走过拱门,"你说,并没有真正理解这个问题.
"不,你没有!盒子里发生了什么？" 助手说.
"你在说什么？" 你说,越来越恼火.
...
一旦整个情况发生,你就会了解这个拱门的作用,你决定做一些大胆的事情.你大声朗读当前时间,然后走过拱门.
下午5:30
从拱门出现,你拿着一个空盒子.观察时间是您预期的下午5:30,您可以在标有的方框中附上便利贴#1.你把盒子放在桌子上,大声朗读当前时间,再次走过拱门.
下午5:31
从拱门出现,你拿着一个空盒子.观察到时间是您预期的下午5:31,您可以在标有的方框中附上便利贴#2 - use to forget.你将盒子#2 放在盒子#1 里面(它缩小到你的尺寸的一小部分;看起来盒子是为此设计的).
作为一名超级英雄考古学家,你可以适当地装备自己并闯入你最不喜欢的压迫政权的外国大使馆,破坏它的金库并窃取一些密切保存的国家机密的纸质副本.香港动作片的东西,子弹和拳头飞扬.你将自己设置在金库中,在他们的警卫可以找到你之前购买宝贵的秒钟.从你的包里制作#1盒子,你把纸张塞进里面(同时也不在里面的#2盒子里面),关闭盒子#1,就像金库门被打开一样,你微笑,拉别针,放下手榴弹,按下按钮.
晚上9:45
从拱门出现,你拿着一个空盒子,上面贴有标签#2 - use to forget,纸张上含有你最不喜欢的压迫政权的敏感国家秘密.您还注意到时间不是您预期的下午5:30,而是下午9:45,因此您不会继续执行预定的闯入计划.您坐下来将文档的内容提交到内存中,一旦您确定将它们完全记忆,就可以将文档刻录到垃圾箱中.现在你大声朗读当前的时间并走过拱门.
凌晨2点
从拱门出现,你拿着一个空盒子.观察当前时间是您预期的凌晨2:00,您可以立即标记新框#3 - use to remember.你给自己写了一个快速说明:Allow self to forget again. At exactly 7:15 PM call police and report suspicious persons at 14th and Maple. 放置#3框和#2框内的注释,然后点击#2框上的按钮.
凌晨2点01分
从拱门出来,你拿着一个空盒子,上面贴有标签#3 - use to remember,还有一个用自己手写的笔记.时间比预期的下午5:31晚得多,因此您不会继续执行预定的闯入计划.按照你自己的指示,再次走过拱门,获得一个你标记的新盒子#4 - use to forget.你按照你的笔记中的指示打电话给警察,不知道为什么,并且在新闻日之后再听到你家乡的国际间谍圈被打破了.
任务完成!(你假设.)从现在开始,你可以选择了解信息本身,但不知道你用它做了什么; 或者不知道这些信息,但要知道它是如何使用的.
最后,这个奇妙的工具是有代价的.当你继续在各种活动中依赖拱门时,你必须知道你永远会破坏你的生活,除非你在许多替代自我之间发送信息,否则碎片永远不会统一.单按一下按钮盒会导致许多珍贵记忆的无法恢复,这可能是一种策略,也可能是一种严重而悲惨的错误.
穿过拱门代表一个call/cc操作.这样做会导致创建一个新的按钮盒,它代表一个延续功能.将内容放入框中表示将参数传递给continuation函数.按下框上的按钮表示调用延续功能.
按下框上的按钮(调用延续函数)会使传说中的字符(带变量的调用堆栈)恢复到创建框(继续)时的确切状态,即call/cc最初完成的时刻.传递给continuation的参数成为call/cc堆栈恢复后原始的结果值; 这就是为什么按下按钮时,传说中的角色不是一个盒子而是盒子的内容.
框(继续)可以被封装(相互传递),允许使用call/cc作为基元来实现协同例程,状态机和其他高级构造.
也可以使用Continuations以方便的方式从代码分支中逃脱("丢弃手榴弹,按下按钮"),例如立即退出深层嵌套的条件和导致副作用的循环.
另请注意,拱门不是时间机器; 时间永远不会在故事中逆转自己,传说中的人物也不会穿过拱门.(通过调用延续函数,不会反转破坏性赋值,堆内存更改和其他副作用.)
练习:为要跟随的传奇字符编写伪代码,这将导致正确执行的间谍计划描述.
| 归档时间： |
|
| 查看次数： |
2904 次 |
| 最近记录： |