计划延续假人

Question

对于我的生活,我无法理解延续.我认为这个问题源于我不明白它们的用途.我在书籍或网上找到的所有例子都非常简单.他们让我想知道,为什么有人甚至想要延续？

这是一个典型的不切实际的例子,来自TSPL,我认为这是一本非常公认的关于这个主题的书.在英语中,他们将继续描述为计算结果的"做什么".好的,这是可以理解的.

然后,第二个例子给出:

(call/cc
  (lambda (k)
    (* 5 (k 4)))) => 4 

这有什么用？k甚至没有定义!当(k 4)无法计算时,如何评估此代码？更何况,如何call/cc知道撕掉4最内层表达式的参数并返回它？会发生什么事(* 5 ..？如果这个最外层的表达式被丢弃,为什么要写呢？

然后,陈述的"较少"的简单示例是如何使用call/cc来提供递归的非本地退出.这听起来像流控制指令,即break/return在命令式语言中,而不是计算.

通过这些动议的目的是什么？如果有人需要计算结果,为什么不只是存储它并在以后根据需要调用.

Answer 1

忘call/cc了一会儿.在任何编程语言中,每个表达式/语句都有一个延续 - 也就是说,你对结果做了什么.以C为例,

x = (1 + (2 * 3)); 
printf ("Done");

继续进行数学作业printf(...); 继续(2 * 3)是'加1; 分配给x; 的printf(...)".从概念上讲,无论您是否有权访问它,都会继续存在.想一想继续所需的信息 - 信息是1)堆内存状态(一般),2)堆栈,3)任何寄存器和4)程序计数器.

因此存在延续,但通常它们只是隐含的,不能被访问.

在Scheme和其他一些语言中,您可以访问continuation.基本上,在您的背后,编译器+运行时捆绑了延续所需的所有信息,将其存储(通常在堆中)并为您提供句柄.你得到的手柄是函数'k' - 如果你调用该函数,你将在该call/cc点之后继续.重要的是,您可以多次调用该函数,并且您将始终在该call/cc点之后继续.

我们来看一些例子:

> (+ 2 (call/cc (lambda (cont) 3)))
5

在上面,结果call/cc是3的结果.lambda没有调用继续.

现在让我们调用延续:

> (+ 2 (call/cc (lambda (cont) (cont 10) 3)))
12

通过调用continuation,我们在调用之后跳过任何内容,并在该call/cc点继续.使用(cont 10)延续返回10,将12添加到2.

现在让我们保存延续.

> (define add-2 #f)
> (+ 2 (call/cc (lambda (cont) (set! add-2 cont) 3)))
5
> (add-2 10)
12
> (add-2 100)
102

通过保存延续,我们可以随意使用它来"跳回"任何计算call/cc点.

通常延续用于非本地退出.想想一个将返回列表的函数,除非在哪一点上'()会返回一些问题.

(define (hairy-list-function list)
  (call/cc
    (lambda (cont)
       ;; process the list ...

       (when (a-problem-arises? ...)
         (cont '()))

       ;; continue processing the list ...

       value-to-return)))

Answer 2

以下是我班级笔记中的文字:http://tmp.barzilay.org/cont.txt.它基于许多来源,并且得到了很大的扩展.它有动机,基本解释,对它如何完成的更高级的解释,以及从简单到高级的许多例子,甚至是对分隔延续的一些快速讨论.

(我尝试将整篇文章放在这里,但正如我所料,120k的文字并不能令人高兴.

Answer 3

TL;DR：延续只是捕获的 GOTO，带有或多或少的值。

你问的例子，

(call/cc
  (lambda (k)
    ;;;;;;;;;;;;;;;;
    (* 5 (k 4))                     ;; body of code
    ;;;;;;;;;;;;;;;;
    )) => 4 

可以近似翻译成例如 Common Lisp，如

(prog (k retval)
    (setq k (lambda (x)             ;; capture the current continuation:
                    (setq retval x) ;;   set! the return value
                    (go EXIT)))     ;;   and jump to exit point

    (setq retval                    ;; get the value of the last expression,
      (progn                        ;;   as usual, in the
         ;;;;;;;;;;;;;;;;
         (* 5 (funcall k 4))        ;; body of code
         ;;;;;;;;;;;;;;;;
         ))
  EXIT                              ;; the goto label
    (return retval))

这只是一个示例；在 Common Lisp 中，我们第一次退出后就无法跳回 PROG 标记体。但在Scheme中，通过真正的延续，我们可以。如果我们在Scheme中调用的函数体内设置一些全局变量call/cc，那么(setq qq k)我们可以在以后的任何时间，从任何地方调用它，重新进入相​​同的上下文（例如(qq 42)）。

要点是，call/cc形式的主体可以包含一个if或一个cond表达式。它只能在某些情况下调用延续，而在其他情况下则正常返回，像往常一样评估代码体中的所有表达式并返回最后一个的值。那里可能会发生深度递归。通过调用捕获的延续，可以实现立即退出。

所以我们在这里看到它的k 定义。它是由call/cc调用定义的。当(call/cc g)被调用时，它用当前的延续来调用它的参数：(g the-current-continuation)。the current-continuation是一个指向表单返回点的“转义过程”call/cc。调用它意味着提供一个值，就好像它是由call/cc表单本身返回的一样。

所以上面的结果是

((lambda(k) (* 5 (k 4))) the-current-continuation) ==>

(* 5 (the-current-continuation 4)) ==>

; to call the-current-continuation means to return the value from
; the call/cc form, so, jump to the return point, and return the value:

4