哪个最简单的评估模型可以解释呼叫/抄送?

Question

TL;DR：call/cc是做什么的，(半)正式地说？

长版本：我对延续和 call/cc 有点熟悉，但我没有很强的正式理解。我想要一个。

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

可以表达呼叫/抄送的最简单评估模型是什么，您如何在其中表达呼叫/抄送？

Answer 1

TL;DRcall/cc允许您利用 Scheme 内部代码，以便您可以使用延续，而无需以延续传递样式编写代码。最好的评估模型是替换模型，前提是您不使用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

想象一下，如果您希望达到else项，结果1337。在不重写整个事情的情况下，您将如何做到这一点？你不能。但是，大多数 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启用。 CPS中call/cc：

(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)