时间戳

首页 > 解决方案 > CPS转换时如何避免堆栈溢出？

f# - CPS转换时如何避免堆栈溢出？

问题描述

我正在编写从 Scheme 子集到 CPS 语言的转换。它在 F# 中实现。在大输入程序中，转换因堆栈溢出而失败。

我正在使用论文Compiling with Continuations中描述的某种算法。我试图将工作线程的最大堆栈大小增加到 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))

wherehalt是完成程序的最终延续。

标签： f#compiler-constructionlisp

解决方案

也许您的实际问题有简单的解决方案来避免大量堆栈消耗，所以请不要介意添加细节。但是，如果没有更多关于您的特定代码的知识，这里有一个通用的方法来减少递归程序中的堆栈消耗，基于蹦床和延续。

沃克

这是一个典型的递归函数，它不是普通的尾递归，用 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 单元组成的树：

  1. 如果表单是一个 cons-cell，递归地走上汽车（resp. cdr）并加入结果
  2. 否则，对值应用变换

例如：

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

代码遍历表单，仅保留数字，但保留（非空）嵌套。

使用上面的示例调用trace显示walk了 8 个嵌套调用的最大深度。

延续和蹦床

这是一个改编版本，称为 walk/then，它像以前一样遍历表单，当结果可用时，调用then它。这then是一个延续。

该函数还返回一个thunk，即无参数闭包。发生的情况是，当我们返回闭包时，堆栈被展开，当我们应用thunk时，它将从一个新的堆栈开始，但在计算中已经推进（我通常想象有人走上一个下降的自动扶梯）。我们返回一个 thunk 以减少堆栈帧数的事实是蹦床的一部分。

该then函数取一个值，即当前walk最终将返回的结果。结果因此被向下传递到堆栈中，并且在每一步返回的是一个 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) ...))读作如下：带着参数和走形式的汽车，并最终调用结果；即，沿着 cdr 走，然后加入两个结果；最终，在连接的结果上transformjoin(lambda (v) ...)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)，并且在追踪时追踪的深度永远不会超过2 walk/then。

请参阅Eli Bendersky 的文章以了解 Python 中的另一篇文章。

推荐阅读