我正在编写从Scheme子集到CPS语言的转换。它是在 F# 中实现的。在大输入程序上，由于堆栈溢出，转换失败。
我正在使用论文"编译与延续"中描述的某种算法。 我试图将工作线程的最大堆栈大小增加到 50 MB，然后它可以工作。
也许有某种方法可以修改算法，这样我就不需要调整堆栈大小了？
例如，算法转换
(foo (bar 1) (bar 2))
自
(let ((c1 (cont (r1)
(let ((c2 (cont (r2)
(foo halt r1 r2))))
(bar c2 2)))))
(bar c1 1))
其中halt是完成程序的最终延续。
也许您的实际问题有简单的解决方案来避免大量堆栈消耗，所以请不要介意添加详细信息。但是，在没有更多关于特定代码的知识的情况下，这里有一种基于蹦床和延续的递归程序中减少堆栈消耗的通用方法。
沃克
这是一个典型的递归函数，它不是简单的尾递归函数，用Common Lisp编写，因为我不知道F#：
(defun walk (form transform join)
(typecase form
(cons (funcall join
(walk (car form) transform join)
(walk (cdr form) transform join)))
(t (funcall transform form))))
然而，代码非常简单，希望，并且走一棵由缺点单元格组成的树：
- 如果表单是 cons-cell，则递归地走在汽车上(或 CDR(并连接结果
- 否则，对值应用转换
例如：
(walk '(a (b c d) 3 2 (a 2 1) 0)
(lambda (u) (and (numberp u) u))
(lambda (a b) (if a (cons a b) (or a b))))
=> (3 2 (2 1) 0)
代码遍历窗体，仅保留数字，但保留(非空(嵌套。
使用上述示例在walk上调用trace显示最大深度为 8 个嵌套调用。
延续和蹦床
这是一个改编的版本，称为walk/then，它像以前一样遍历表单，并且当结果 可用，调用then。这里then是一个延续。
该函数还返回一个thunk，即无参数闭包。 发生的情况是，当我们返回封盖时，堆栈被展开， 当我们应用thunk时，它将 从一个新的堆栈开始，但在计算方面已经取得了进步 (我通常想象有人走上自动扶梯，然后下降(。 我们返回一个thunk以减少堆栈帧数的事实是蹦床的一部分。
then函数取一个值，即 当前步行最终将返回的结果。 因此，结果会向下传递到堆栈中，以及什么是 每一步返回的是一个 thunk 函数。
嵌套延续允许捕获transform/join的复杂行为，方法是在嵌套延续中推动计算的其余部分。
(defun walk/then (form transform join then)
(typecase form
(cons (lambda ()
(walk/then (car form) transform join
(lambda (v)
(walk/then (cdr form) transform join
(lambda (w)
(funcall then (funcall join v w))))))))
(t (funcall then (funcall transform form)))))
例如，(walk/then (car form) transform join (lambda (v) ...))如下：走车的形式 论证transform和join，并最终对结果调用(lambda (v) ...);即，沿着 CDR 走下去，然后连接两个结果;最后，对联接的结果调用输入then。
缺少的是一种不断调用返回的thunk直到筋疲力尽的方法;这就是它 带有循环，但这很容易成为尾递归函数：
(loop for res =
(walk/then '(a (b c d) 3 2 (a 2 1) 0)
(lambda (u) (and (numberp u) u))
(lambda (a b) (if a (cons a b) (or a b)))
#'identity)
then (typecase res (function (funcall res)) (t res))
while (functionp res)
finally (return res))
上面返回(3 2 (2 1) 0)，跟踪时跟踪的深度永远不会超过 2walk/then。
参见 Eli Bendersky 的文章，了解 Python 中对此的另一种看法。
我已经将算法转换为蹦床形式。它看起来像密克罗尼西亚联邦。 有一个循环，它查看当前状态，进行一些操作，然后转到另一个状态。此外，它还使用两个堆栈进行不同类型的延续。
这是输入语言(它是我最初使用的语言的子集(：
// Input language consists of only variables and function applications
type Expr =
| Var of string
| App of Expr * Expr list
这是目标语言：
// CPS form - each function gets a continuation,
// added continuation definitions and continuation applications
type Norm =
| LetCont of name : string * args : string list * body : Norm * inner : Norm
| FuncCall of func : string * cont : string * args : string list
| ContCall of cont : string * args : string list
这是原始算法：
// Usual way to make CPS conversion.
let rec transform expr cont =
match expr with
| App(func, args) ->
transformMany (func :: args) (fun vars ->
let func' = List.head vars
let args' = List.tail vars
let c = fresh()
let r = fresh()
LetCont(c, [r], cont r, FuncCall(func', c, args')))
| Var(v) -> cont v
and transformMany exprs cont =
match exprs with
| e :: rest ->
transform e (fun e' ->
transformMany rest (fun rest' ->
cont (e' :: rest')))
| _ -> cont []
let transformTop expr =
transform expr (fun var -> ContCall("halt", [var]))
这是修改版本：
type Action =
| ContinuationVar of Expr * (string -> Action)
| ContinuationExpr of string * (Norm -> Action)
| TransformMany of string list * Expr list * (string list -> Action)
| Result of Norm
| Variable of string
// Make one action at time and return to top loop
let rec transform2 expr =
match expr with
| App(func, args) ->
TransformMany([], func :: args, (fun vars ->
let func' = List.head vars
let args' = List.tail vars
let c = fresh()
let r = fresh()
ContinuationExpr(r, fun expr ->
Result(LetCont(c, [r], expr, FuncCall(func', c, args'))))))
| Var(v) -> Variable(v)
// We have two stacks here:
// contsVar for continuations accepting variables
// contsExpr for continuations accepting expressions
let transformTop2 expr =
let rec loop contsVar contsExpr action =
match action with
| ContinuationVar(expr, cont) ->
loop (cont :: contsVar) contsExpr (transform2 expr)
| ContinuationExpr(var, contExpr) ->
let contVar = List.head contsVar
let contsVar' = List.tail contsVar
loop contsVar' (contExpr :: contsExpr) (contVar var)
| TransformMany(vars, e :: exprs, cont) ->
loop contsVar contsExpr (ContinuationVar(e, fun var ->
TransformMany(var :: vars, exprs, cont)))
| TransformMany(vars, [], cont) ->
loop contsVar contsExpr (cont (List.rev vars))
| Result(r) ->
match contsExpr with
| cont :: rest -> loop contsVar rest (cont r)
| _ -> r
| Variable(v) ->
match contsVar with
| cont :: rest -> loop rest contsExpr (cont v)
| _ -> failwith "must not be empty"
let initial = ContinuationVar(expr, fun var -> Result(ContCall("halt", [var])))
loop [] [] initial