什么是蹦床功能？

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

我已经在 维基百科看过描述了。这足以给出功能的一般概念，但我希望看到一些更具体的东西。

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

51660 次浏览
小开

我会给你一个例子，我用在一个反作弊补丁的在线游戏。

我需要能够扫描所有的文件正在加载的游戏进行修改。所以我找到的最健壮的方法是为 CreateFileA 使用蹦床。所以当游戏启动时，我会使用 GetProcAddress 找到 CreateFileA 的地址，然后我会修改函数的前几个字节并插入汇编代码，这些代码会跳到我自己的“蹦床”函数中，在那里我会做一些事情，然后我会跳回到我的 jmp 代码后 CreateFile 的下一个位置。为了能够可靠地完成这个任务，要比这个复杂一些，但是基本的概念只是钩住一个函数，强制它重定向到另一个函数，然后跳回到原来的函数。

Edit: Microsoft has a framework for this type of thing that you can look at. Called 绕道

小开

下面是一个嵌套函数的例子:

#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，而 nbytes只存在于 sort_bytes调用期间。在某些体系结构中，在运行时生成一个小的存根函数(trampoline) ，它包含 sort_bytes的 目前调用的堆栈位置。当调用时，它跳转到 compar代码，传递该地址。

像 PowerPC 这样的架构并不需要这种混乱，在这种架构中，ABI 指定一个函数指针实际上是一个“胖指针”，一个既包含指向可执行代码的指针，又包含指向数据的指针的结构。然而，在 x86上，函数指针只是一个指针。

小开

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

在某些 LISP 实现中使用的 蹦床是一个循环 调用 Thunk-return 函数 单人蹦床足以 表示所有控制权的转移 程序; 如此表达的程序是 蹦床式或“蹦床式”; 将程序转换为蹦床 style is trampolining. Trampolined 函数可用于实现 尾递归函数调用 面向堆栈的语言

假设我们正在使用 Javascript，并且希望以延续传递的方式编写简单的 Fibonacci 函数。我们这样做的原因与此无关——例如，将 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运行这个命令会产生一个错误‘太多的递归！'.现在，这正是蹦床所要解决的问题(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 来说，蹦床就是一个函数指针:

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

编辑: 编译器将隐式生成更深奥的蹦床。一个这样的用途将是一个跳台。(尽管越往下开始尝试生成复杂的代码，显然就有越复杂的代码。)

小开

我目前正在尝试为 Scheme 解释器实现尾部调用优化的方法，因此目前我正试图弄清楚蹦床对我来说是否可行。

As I understand it, it is basically just a series of function calls performed by a trampoline function. Each function is called a thunk and returns the next step in the computation until the program terminates (empty continuation).

下面是我为提高对蹦床的理解而编写的第一段代码:

#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 !
小开

让我添加一些用蹦床实现的阶乘函数的例子，用不同的语言:

Scala:

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, product: BigInt): Bounce[BigInt] = {
if (n <= 2) Done(product)
else Call(() => factorial(n - 1, n * product))
}


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 product)
{
if(n <= 1) {
return new Trampoline<BigInteger>() { public BigInteger get() { return product; } };
}
else {
return new Trampoline<BigInteger>() {
public Trampoline<BigInteger> run() {
return factorial(n - 1, product.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 product;
} factorialParameters;


void factorial(trampoline_data* data) {
factorialParameters* parameters = (factorialParameters*) data->parameters;


if (parameters->n <= 1) {
data->callback = NULL;
}
else {
parameters->product *= parameters->n;
parameters->n--;
}
}


int main() {
factorialParameters params = {5, 1};
trampoline_data t = {&factorial, &params};


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


return 0;
}
小开 
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();
}
// ...
小开

Now that C# has 本地职能, the 保龄球游戏编码 can be elegantly solved with a trampoline:

using System.Collections.Generic;
using System.Linq;


class Game
{
internal static int RollMany(params int[] rs)
{
return Trampoline(1, 0, rs.ToList());


int Trampoline(int frame, int rsf, IEnumerable<int> rs) =>
frame == 11             ? rsf
: rs.Count() == 0         ? rsf
: rs.First() == 10        ? Trampoline(frame + 1, rsf + rs.Take(3).Sum(), rs.Skip(1))
: rs.Take(2).Sum() == 10  ? Trampoline(frame + 1, rsf + rs.Take(3).Sum(), rs.Skip(2))
:                           Trampoline(frame + 1, rsf + rs.Take(2).Sum(), rs.Skip(2));
}
}

方法 Game.RollMany被调用的辊数: 通常20辊，如果没有备件或罢工。

第一行立即调用蹦床函数: return Trampoline(1, 0, rs.ToList());。这个局部函数递归地遍历 Rolls 数组。本地函数(蹦床)允许遍历从两个附加值开始: 从 frame1和 rsf(到目前为止的结果)0开始。

在局部函数中，有一个三元运算符处理五种情况:

  • 游戏在第11帧结束: 返回到目前为止的结果
  • 游戏结束，如果没有更多的滚动: 返回的结果迄今为止
  • 点击: 计算帧得分并继续遍历
  • Spare: calculate the frame score and continue traversal
  • 正常分数: 计算帧分数并继续遍历

Continuing the traversal is done by calling the trampoline again, but now with updated values.

For more information, search for: "尾部递归累加器尾部递归累加器". Keep in mind that the compiler does not optimize tail recursion. So as elegant as this solution may be, it will likely not be the fasted.


提交答案