c - 什么是蹦床功能？

Question

在最近的工作讨论中，有人提到了蹦床功能。

我已阅读 Wikipedia 的描述.大致了解一下功能就足够了，但我想要一些更具体的东西。

您是否有一段简单的代码来说明蹦床？

Answer 1

还有维基百科上描述的 LISP 意义上的“蹦床”:

Used in some LISP implementations, a trampoline is a loop that iteratively invokes thunk-returning functions. A single trampoline is sufficient to express all control transfers of a program; a program so expressed is trampolined or in "trampolined style"; converting a program to trampolined style is trampolining. Trampolined functions can be used to implement tail recursive function calls in stack-oriented languages

假设我们正在使用 Javascript 并希望以连续传递风格编写朴素的斐波那契函数。我们这样做的原因无关紧要 - 例如将 Scheme 移植到 JS，或者使用我们无论如何都必须使用的 CPS 来调用服务器端函数。

所以，第一次尝试是

function fibcps(n, c) {
    if (n <= 1) {
        c(n);
    } else {
        fibcps(n - 1, function (x) {
            fibcps(n - 2, function (y) {
                c(x + y)
            })
        });
    }
}

但是，在 Firefox 中使用 n = 25 运行它会出现错误“太多递归!”。现在这正是 trampolining 解决的问题(在 Javascript 中缺少尾调用优化)。让我们返回一条调用该函数的指令(thunk)，而不是对函数进行(递归)调用，并在循环中进行解释。

function fibt(n, c) {
    function trampoline(x) {
        while (x && x.func) {
            x = x.func.apply(null, x.args);
        }
    }

    function fibtramp(n, c) {
        if (n <= 1) {
            return {func: c, args: [n]};
        } else {
            return {
                func: fibtramp,
                args: [n - 1,
                    function (x) {
                        return {
                            func: fibtramp,
                            args: [n - 2, function (y) {
                                return {func: c, args: [x + y]}
                            }]
                        }
                    }
                ]
            }
        }
    }

    trampoline({func: fibtramp, args: [n, c]});
}