什么是蹦床功能？

Question

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

我已经阅读了维基百科的描述.这足以给出功能的一般概念,但我想要更具体的东西.

你有一个简单的代码片段来说明蹦床吗？

Answer 1

维基百科上也有LISP的"蹦床"感:

在一些LISP实现中使用,trampoline是一个循环,它迭代地调用thunk返回函数.单个蹦床足以表达节目的所有控制转移; 如此表达的节目是蹦床或"蹦床风格"; 将程序转换为蹦床风格是蹦床.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)
            })
        });
    }
}

但是,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 2

让我举几个使用trampolines实现的阶乘函数的例子,用不同的语言:

斯卡拉:

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;
}

Answer 3

我将举一个例子,我在一个反作弊补丁中用于在线游戏.

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

编辑:微软有一个框架,你可以看到这种类型的东西.叫Detours

Answer 4

以下是嵌套函数的示例:

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

在像PowerPC这样的体系结构中不需要这种混乱,其中ABI指定函数指针实际上是"胖指针",该结构包含指向可执行代码的指针和指向数据的另一指针.但是,在x86上,函数指针只是一个指针.

Answer 5

我目前正在尝试为Scheme解释器实现尾调用优化的方法,所以目前我正在试图弄清楚蹦床是否对我来说是可行的.

据我了解,它基本上只是一系列由trampoline函数执行的函数调用.每个函数都被称为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 !