c - 什么是蹦床功能？

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

我已阅读Wikipedia上的描述。给出功能的一般概念就足够了，但是我想更具体一些。

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

最佳答案

如Wikipedia所述，还有LISP对“蹦床”的感觉:



假设我们正在使用Javascript，并且想以延续传递样式编写朴素的Fibonacci函数。我们这样做的原因无关紧要-例如将Scheme移植到JS，或者使用CPS，无论如何我们都必须使用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运行它会产生错误“太多的递归!”。现在这正是蹦床解决的问题(在Javascript中缺少尾调用优化)。与其对函数进行(递归)调用，不如让我们return一条指令(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]});
}

关于c - 什么是蹦床功能？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/189725/