scheme - 哪个最简单的评估模型可以解释 call/cc？

Question

TL;DR: call/cc 做什么，（半）正式地说？

长版：我对延续和 call/cc 隐约熟悉，但对形式的理解并不强。我想要一个。

在SICP 视频讲座中，我们看到了替代模型和元循环解释器。在 Shriram Krishnamurti 的编程语言课程中，我们看到了一种环境和商店传递风格。在我参加 uni 的编译器课程中，我通过操作堆栈来评估 Java 表达式。

最简单的可以表达 call/cc 的评估模型是什么，如何在其中表达 call/cc？

Answer 1

TL;DRcall/cc允许您利用 Schemes 内部代码，以便您可以使用延续，而无需以延续传递样式编写代码。最好的评估模型是替代模型，因为您不使用set并从 CPS 代码中查看它

想象一下这个小程序。

(define (sum-list lst)
  (cond ((null? lst) 0)
        ((number? (car lst)) (+ (car lst) (sum-list (cdr lsr))))
        (else (sum-list (cdr lsr)))))

(display (sum-list '(1 2 3 4))) ; displays 10

1337想象一下，如果你达到这个else词，你希望结果是这样的。如果不重写整个事情，你会怎么做？你不能。然而，大多数 Scheme 实现都会将 CPS 转换为您的代码，而更改它是微不足道的：

(define (sum-list& lst k)
  (null?& lst
          (lambda (nlst?)
            (if& nlst?
                 (lambda ()
                   (k 0))
                 (lambda ()
                   (car& lst
                         (lambda (car-lst)
                           (number?& car-lst
                                     (lambda (ncl?)
                                       (if& ncl?
                                            (lambda ()
                                              (cdr& lst
                                                    (lambda (clst)
                                                      (sum-list& clst
                                                                 (lambda (sclst)
                                                                   (+& car-lst sclst k))))))
                                            (lambda ()
                                              (cdr& lst
                                                    (lambda (clst)
                                                      (sum-list& clst k))))))))))))))
(sum-list& '(1 2 3 4)
           (lambda (sum)
             (display& sum halt)))

cond是一个宏，所以它是if&你看到的调用。我知道你在想什么。为什么不首先告诉程序员这样做呢？只是在开玩笑！

如果您将第二个延续中的第二个更改if&为(lambda () (k 1337))您就完成了。和 CPS 一样漂亮，它的读写是可怕的，但是既然编译器这样做了，就不能有一种方法能够以第一种方式编写代码并仍然获得代码控制流吗？两全其美是启用的call/cc。call/cc这是在 CPS 中：

(define (call/cc& f& continuation)
  (define (exit& value actual-continuation)
    (continuation value))
  (f& exit& continuation))

它根本没有多大作用。它通过exit&了，它在调用时忽略程序的真正延续，并使用调用的原始延续来call/cc&调用值。使用该列表'(1 2 3 #f)，您将有 3 个嵌套的延续等待添加结果，但所有这些都需要取消。如果您在计算之前选择延续的值，它会自动取消。就是这样。当你用它编写代码时，你不需要做完整的 CPS，只需要call/cc像这样想的延续：

(define (sum-list lst)
  (call/cc
   (lambda (k)
     (define (helper lst)
       (cond ((null? lst) 0)
             ((number? (car lst))
              (+ (car lst) (helper (cdr lst))))
             (else (k 1337))))
     (helper lst))))

这在 CPS 中被转换为：

(define (sum-list& lst k)
  (call/cc&
   (lambda (k& real-k)
     (define (helper& lst k)
       (null?& lst
               (lambda (nlst?)
                 (if& nlst?
                      (lambda ()
                        (k 0))
                      (lambda ()
                        (car& lst
                              (lambda (car-lst)
                                (number?& car-lst
                                          (lambda (ncl?)
                                            (if& ncl?
                                                 (lambda ()
                                                   (cdr& lst
                                                         (lambda (clst)
                                                           (helper& clst
                                                                    (lambda (sclst)
                                                                      (+& car-lst sclst k))))))
                                                 (lambda ()
                                                   (k& 1337 real-k))))))))))))
     (helper& lst real-k))
     k))


(sum-list& '(1 2 3 4)
           (lambda (sum)
             (display& sum halt)))

call/cc总是可以避免的。我们的示例可以重写为返回 1337，如下所示：

(define (sum-list lst)
  (define (helper lst sum)
    (cond ((null? lst) sum)
          ((number? (car lst)) (helper (cdr lst) (+ sum (car lst))))
          (else 1337)))
  (helper lst 0))

这是尾递归，而不是创建延续它累积。为了完整起见，这里是它的 CPS 版本：

(define (helper& lst sum k)
  (null?& lst
          (lambda (nlst)
            (if& nlst
                 (lambda () (k sum))
                 (lambda ()
                   (car& lst
                       (lambda (cl)
                         (number?& cl
                                 (lambda (ncl?)
                                   (if& ncl?
                                        (lambda ()
                                          (cdr& lst
                                                (lambda (cdrl)
                                                  (+& sum
                                                      cl
                                                      (lambda (scl)
                                                        (helper& cdrl
                                                                 scl
                                                                 k))))))
                                        (lambda () (k 1337))))))))))))


(define (sum-list& lst k)
  (helper& lst 0 k))

Answer 2

我找到了这个出色的演示文稿（德语），它回答了我的问题：https ://www.youtube.com/watch?v=iuaM9-PX1ls

要使用 call/CC 评估 lambda 演算，您需要传递一个评估上下文，该上下文由一个环境（像往常一样）和一个调用堆栈组成。调用call/cc创建一个特殊的类似函数的延续对象，该对象存储评估上下文。将特殊对象应用于表达式的结果是在延续对象中捕获的评估上下文expr中解释的结果。expr

TL；DR：您可以call/cc使用环境和调用堆栈传递解释器来实现。

如果您还想围绕可变存储进行线程处理，则延续对象不应捕获它。相反，在调用延续时，您将存储作为参数传递给恢复的评估上下文中的解释。（商店可以是线性类型。）

这是 Haskell 中的一个这样的实现。这是您可能要评估的示例表达式：interpret 0 (Application (Lambda (1, (CallCC (Lambda (2, (Application (Variable 2) (Lambda (3, (Variable 4))))))))) (Lambda (4, (Variable 5)))).

（这些数字只是简单的旧名称，而不是（例如）De Bruijn 索引。如果您想使用字符或字符串，请更改type Name = Integer为type Name = Char。）

注意特别interp适用于CallCC和InvokeContinuation以及continue适用于ContinuationArgument。

import qualified Data.Map as Map

type Name = Integer
type NameAndBody = (Name, LambdaCallCC)
data LambdaCallCC
  = Lambda NameAndBody
  | Variable Name
  | InvokeContinuation EvaluationContext LambdaCallCC
  | CallCC LambdaCallCC
  | Application LambdaCallCC LambdaCallCC
  deriving Show

type Environment = Map.Map Name NameAndBody

type EvaluationContext = (CallStack, Environment)
type CallStack = [Frame]

data Frame
  = FunctionPosition LambdaCallCC
  | ArgumentPosition NameAndBody
  | ContinuationArgument EvaluationContext
  deriving Show

type Fail = (Name, EvaluationContext)
interpret :: Name -> LambdaCallCC -> Either Fail NameAndBody
interpret thunkVarName expression = interp [] Map.empty expression
  where interp stk env (Lambda nameAndBody)
          = continue stk env nameAndBody
        interp stk env (Variable name)
          = case Map.lookup name env of
              Nothing -> Left (name, (stk, env))
              Just e -> continue stk env e
        interp stk env (Application e1 e2)
          = interp (FunctionPosition e2 : stk) env e1
        interp stk env (CallCC expr)
          = interp stk env (Application expr
                              (Lambda (thunkVarName,
                                        (InvokeContinuation
                                          (stk, env)
                                          (Variable thunkVarName)))))
        interp stk env (InvokeContinuation capturedContext expr)
          = interp [ContinuationArgument capturedContext] env expr

        continue [] env value
          = Right value
        continue ((FunctionPosition expr) : frames) env value
          = interp ((ArgumentPosition value) : frames) env expr
        continue ((ArgumentPosition (name, body)) : frames) env value
          = interp frames (Map.insert name value env) body
        continue ((ContinuationArgument (stk, env)) : nil) _ value
          = interp stk env (Lambda value)