什么是蹦床功能？

Question

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

我已阅读说明Wikipedia。对功能进行总体概括就足够了，但我希望更具体一些。

你有简单的代码片段可以说明蹦床吗？

Answer 1

我给你举个例子，我在网上游戏的反作弊补丁中使用。

我需要能够扫描游戏加载的所有文件以进行修改。因此，我发现要做到这一点的最强有力的方法是为CreateFileA使用蹦床。所以当游戏启动时，我会使用GetProcAddress找到CreateFileA的地址，然后修改函数的前几个字节并插入汇编代码，这些代码会跳转到我自己的“蹦床”函数，我会做一些事情，并且那么在我的jmp代码之后，我会跳回到CreateFile中的下一个位置。为了能够可靠地做到这一点有点棘手，但基本概念是钩住一个函数，强制它重定向到另一个函数，然后跳回到原始函数。

编辑：微软有一个这种类型的东西，你可以看看的框架。所谓的Detours

Answer 2

这里的嵌套函数的例子：

#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通话过程中才存在。在某些体系结构中，一个小的存根函数 - 蹦床 - 在运行时生成，并且包含调用sort_bytes的当前的的堆栈位置。当被调用时，它跳转到compar代码，传递该地址。

像PowerPC这样的体系结构不需要这样的混乱，ABI指定函数指针实际上是一个“胖指针”，一个包含指向可执行代码的指针和另一个指向数据的指针的结构。但是，在x86上，函数指针只是一个指针。

Answer 3

还有如维基百科上描述的“蹦床”的LISP感：

用在一些LISP实现中， 蹦床是一个循环，反复地 所调用咚返回功能。 A 单蹦床足以让 表达一个 节目的所有控制转移;如此表达的节目是 蹦床或“蹦床式”; 转换程序为trampolined 风格是蹦床。 Trampolined 功能可以被用来实现 尾 面向堆栈的语言

递归函数调用让我们说，我们使用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) 
      }) 
     }); 
    } 
} 

但是，随着n = 25运行这个在Firefox提供了一个错误 '太多的递归调用！'。现在，这正是问题（缺少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]}); 
} 

Answer 4

对于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"); 

编辑：更深奥的蹦床将被隐式由编译器生成。其中一种用途就是跳转表。 （虽然显然有更复杂的，你开始尝试生成复杂的代码。）

Answer 5

我目前正在试验如何实现方案解释器的尾部呼叫优化，所以此刻我想图看看蹦床对我来说是否可行。

据我所知，它基本上只是一系列由蹦床功能执行的函数调用。每个函数都称为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 ! 

Answer 6

让我补充几个例子与蹦床实现的阶乘函数，用不同的语言：

斯卡拉：

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, &params}; 

    trampoline(&t); 
    printf("\n%d\n", params.sum); 

    return 0; 
} 

Answer 7

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(); 
} 
// ...