什么是蹦床function？
在最近的工作讨论中，有人提到了蹦床的function。
我已阅读维基百科的描述。 给出一个function的总体思路就足够了，但是我想要一些更具体的东西。
你有一个简单的代码片段，可以说明一个蹦床吗？
还有LISP在维基百科中所描述的“蹦床”意义：
在一些LISP实现中使用，蹦床是迭代调用返回函数的循环。 一个蹦床足以expression一个程序的所有控制转移; 这样expression的节目就是蹦床或“蹦床式”的; 把一个程序转换成蹦床风格就是蹦蹦跳跳的。 可以使用蹦床函数来实现堆栈导向语言中的尾recursion函数调用
让我们说，我们正在使用JavaScript，并希望写出延续传球风格的天真的斐波那契函数。 我们这样做的原因是无关紧要的，比如将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会产生一个错误“太多的recursion！”。 现在，这正是问题（缺lessJavaScript中的尾部调用优化），蹦床解决了。 让我们return一个指令（thunk）来调用该函数，而不是对函数进行（recursion）调用，以循环方式解释。
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]}); }
让我来添加一些用蹦床来实现阶乘函数的例子，用不同的语言：
斯卡拉：
sealed trait Bounce[A] case class Done[A](result: A) extends Bounce[A] case class Call[A](thunk: () => Bounce[A]) extends Bounce[A] def trampoline[A](bounce: Bounce[A]): A = bounce match { case Call(thunk) => trampoline(thunk()) case Done(x) => x } def factorial(n: Int, sum: BigInt): Bounce[BigInt] = { if (n <= 2) Done(sum) else Call(() => factorial(n - 1, n * sum)) } object Factorial extends Application { println(trampoline(factorial(100000, 1))) }
Java的：
import java.math.BigInteger; class Trampoline<T> { public T get() { return null; } public Trampoline<T> run() { return null; } T execute() { Trampoline<T> trampoline = this; while (trampoline.get() == null) { trampoline = trampoline.run(); } return trampoline.get(); } } public class Factorial { public static Trampoline<BigInteger> factorial(final int n, final BigInteger sum) { if(n <= 1) { return new Trampoline<BigInteger>() { public BigInteger get() { return sum; } }; } else { return new Trampoline<BigInteger>() { public Trampoline<BigInteger> run() { return factorial(n - 1, sum.multiply(BigInteger.valueOf(n))); } }; } } public static void main( String [ ] args ) { System.out.println(factorial(100000, BigInteger.ONE).execute()); } }
C（不幸的是没有大数字的实现）：
#include <stdio.h> typedef struct _trampoline_data { void(*callback)(struct _trampoline_data*); void* parameters; } trampoline_data; void trampoline(trampoline_data* data) { while(data->callback != NULL) data->callback(data); } //----------------------------------------- typedef struct _factorialParameters { int n; int sum; } factorialParameters; void factorial(trampoline_data* data) { factorialParameters* parameters = (factorialParameters*) data->parameters; if (parameters->n <= 1) { data->callback = NULL; } else { parameters->sum *= parameters->n; parameters->n--; } } int main() { factorialParameters params = {5, 1}; trampoline_data t = {&factorial, ¶ms}; trampoline(&t); printf("\n%d\n", params.sum); return 0; }
我给你举个例子，我在一个反作弊补丁中用于在线游戏。
我需要能够扫描游戏加载的所有文件进行修改。 所以我发现最强大的方法就是使用一个蹦床来做CreateFileA。 所以当游戏启动时，我会使用GetProcAddressfindCreateFileA的地址，然后修改函数的前几个字节，然后插入汇编代码，跳到我自己的“蹦床”函数中，在那里做一些事情，那么我会跳回到我的jmp代码后的CreateFile中的下一个位置。 为了能够可靠地做到这一点有点棘手，但基本的概念是钩住一个function，强迫它redirect到另一个function，然后跳回原来的function。
编辑：微软有这样的事情，你可以看看的框架。 叫Detours
这是一个嵌套函数的例子：
#include <stdlib.h> #include <string.h> /* sort an array, starting at address `base`, * containing `nmemb` members, separated by `size`, * comparing on the first `nbytes` only. */ void sort_bytes(void *base, size_t nmemb, size_t size, size_t nbytes) { int compar(const void *a, const void *b) { return memcmp(a, b, nbytes); } qsort(base, nmemb, size, compar); }
compar不能是外部函数，因为它使用nbytes ，它只在sort_bytes调用期间存在。 在一些体系结构中，一个小的stub函数 – 蹦床 – 在运行时生成，并且包含当前调用sort_bytes的堆栈位置。 当被调用时，它跳转到compar代码，传递该地址。
在PowerPC这样的体系结构中，这种混乱并不是必须的，ABI指定函数指针实际上是一个“胖指针”，一个包含指向可执行代码的指针和另一个指向数据的指针的结构体。 但是，在x86上，函数指针只是一个指针。
目前我正在试验如何为Scheme解释器实现尾部呼叫优化，所以目前我正试图弄清楚蹦床对我是否可行。
据我所知，它基本上只是一系列由蹦床function执行的函数调用。 每个函数被称为thunk，并返回计算中的下一个步骤，直到程序终止（空的继续）。
这里是我写的第一个代码，以提高我对蹦床的理解：
#include <stdio.h> typedef void *(*CONTINUATION)(int); void trampoline(CONTINUATION cont) { int counter = 0; CONTINUATION currentCont = cont; while (currentCont != NULL) { currentCont = (CONTINUATION) currentCont(counter); counter++; } printf("got off the trampoline - happy happy joy joy !\n"); } void *thunk3(int param) { printf("*boing* last thunk\n"); return NULL; } void *thunk2(int param) { printf("*boing* thunk 2\n"); return thunk3; } void *thunk1(int param) { printf("*boing* thunk 1\n"); return thunk2; } int main(int argc, char **argv) { trampoline(thunk1); }
结果是：
meincompi $ ./trampoline *boing* thunk 1 *boing* thunk 2 *boing* last thunk got off the trampoline - happy happy joy joy !
对于C来说，蹦床就是一个函数指针：
size_t (*trampoline_example)(const char *, const char *); trampoline_example= strcspn; size_t result_1= trampoline_example("xyzbxz", "abc"); trampoline_example= strspn; size_t result_2= trampoline_example("xyzbxz", "abc");
编辑：更深奥的蹦床将由编译器隐式生成。 其中一个用途就是跳转表。 （尽pipe显然有更复杂的代码，但是你开始尝试生成复杂的代码。
typedef void* (*state_type)(void); void* state1(); void* state2(); void* state1() { return state2; } void* state2() { return state1; } // ... state_type state = state1; while (1) { state = state(); } // ...
