什么是蹦床功能？

Question

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

我已阅读维基百科上的描述。 给出功能的一般概念就足够了，但我想要更具体的东西。

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

Answer 1

还有 LISP 意义上的“蹦床”，如 Wikipedia 上所述：

在一些 LISP 实现中使用，
蹦床是一个迭代循环
调用 thunk 返回函数。 A
单个蹦床就足够了
表达a的所有控制转移
程序; 这样表达的程序是
蹦床式或“蹦床式”；
将程序转换为蹦床程序
风格是蹦床。 蹦床
可以使用函数来实现
尾递归函数调用
面向堆栈的语言

假设我们正在使用 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)
            })
        });
    }
}

但是，在 Firefox 中使用 n = 25 运行此命令会出现错误“递归过多！”。 现在这正是蹦床解决的问题（Javascript 中缺少尾部调用优化）。 让我们返回一条指令（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

让我添加一些用不同语言使用蹦床实现的阶乘函数的示例：

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, ¶ms};

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

  return 0;
}

Answer 3

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

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

编辑：微软有一个针对此类事物的框架，您可以查看。 称为绕道

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解释器实现尾部调用优化的方法，因此目前我正在尝试弄清楚蹦床对我来说是否可行。

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

现在 C# 具有 本地函数，保龄球游戏编码型可以用蹦床优雅地解决：

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 次掷骰。

第一行立即调用trampoline函数：return Trampoline(1, 0, rs.ToList());。 该局部函数递归遍历 rolls 数组。 本地函数（trampoline）允许遍历从两个附加值开始：从 frame 1 和 rsf （到目前为止的结果）0 开始。

在本地函数中是三元运算符，处理五种情况：

• 游戏在第 11 帧结束：返回目前为止的结果
• 如果没有更多的掷骰，则游戏结束：返回目前为止的结果
• Strike：计算帧分数并继续遍历
• Spare：计算帧分数并继续遍历
• 正常分数：计算帧分数并继续遍历

继续遍历是通过再次调用蹦床来完成的，但现在使用更新的值。

有关更多信息，请搜索：“尾递归累加器”。 请记住，编译器不会优化尾递归。 因此，尽管这个解决方案可能很优雅，但它可能不会是禁食的。

Answer 7

对于 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 8

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