哪个最简单的评估模型可以解释 call/cc？
Which simplest evaluation model explains call/cc?
TL;DR：call/cc 做什么，（半）正式地说？
长版：我对continuations 和call/cc 有点熟悉，但我对形式化的理解不深。我想要一个。
在 SICP video lectures we are presented with the substitution model and a metacircular interpreter. In Shriram Krishnamurti's programming language course 中，我们看到了环境和商店传递样式。在我学习 uni 的编译器课程中，我通过操纵堆栈评估了 Java 表达式。
最简单的可以表达call/cc的评价模型是什么，在其中怎么表达call/cc？
TL;DR call/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
想象一下，如果您点击 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 实现了两全其美。 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总是可以避免的。我们的示例可以重写为 return 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))
我找到了这个出色的演示文稿（德语），它回答了我的问题：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)
TL;DR：call/cc 做什么，（半）正式地说？
长版：我对continuations 和call/cc 有点熟悉，但我对形式化的理解不深。我想要一个。
在 SICP video lectures we are presented with the substitution model and a metacircular interpreter. In Shriram Krishnamurti's programming language course 中，我们看到了环境和商店传递样式。在我学习 uni 的编译器课程中，我通过操纵堆栈评估了 Java 表达式。
最简单的可以表达call/cc的评价模型是什么，在其中怎么表达call/cc？
TL;DR call/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
想象一下，如果您点击 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 实现了两全其美。 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总是可以避免的。我们的示例可以重写为 return 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))
我找到了这个出色的演示文稿（德语），它回答了我的问题：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)