什么是弹跳函数？
119
- Benoit
4
2在微软的世界中，跳板通常被称为“thunks”。这里有一篇来自Andrei Alexandrescu的《现代C++设计》的页面。 - Michael Burr
1Related - bobobobo
这基本上是一些功能的泛化形式，你可以使用setjmp/longjmp来实现，即避免堆栈溢出。 - Ingo
26为什么有人想要避免使用Stack Overflow？ - Nikole
8个回答
83
还有一种 LISP 中的“trampoline” 意义，如维基百科所述：
在某些 LISP 实现中，一个 trampoline 是一个循环，迭代地调用返回 thunk 函数。单个 trampoline 就足以表达程序的所有控制转移；这样表达的程序是被蹦床化的或者是“蹦床化风格”；将程序转换为蹦床化风格就是蹦床技术。可以使用蹦床函数来实现栈定向语言中的尾递归函数调用。
假设我们使用 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运行时会出现错误“递归太多！”。 现在，这正是trampolining解决的问题（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]});
}
- toyvo
48
让我举几个使用跳板实现阶乘函数的例子，涉及不同语言：
Scala:
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;
}
- Piotr Kukielka
2
1您的解释，特别是关于C语言示例以及ephemient在下面关于嵌套函数的回答最终使我理解了跳板功能。这是一种类似于闭包的辅助函数，可以用于更新状态。 - Byte
Scala代码应该更正为
if (n < 2) Done(product)，SO不允许我编辑1个符号... - Max23
我给你举一个网络游戏反作弊补丁中的例子。
我需要能够扫描游戏加载的所有文件是否被修改。所以我发现最稳健的方法是使用CreateFileA的“trampoline”（跳板）方式。当游戏启动时，我会使用GetProcAddress找到CreateFileA的地址，然后我会修改函数的前几个字节，并插入汇编代码来跳转到我的自己的“trampoline”函数，在那里我会做一些事情，然后再跳回CreateFile的下一个位置。为了可靠地执行这个过程比这要棘手一些，但基本概念就是挂钩一个函数，强制将其重定向到另一个函数，然后再跳回原始函数。
编辑：微软有一个名为Detours的框架，可以供您参考。
- Gerald
9
我目前正在尝试实现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 !
- boxofrats
9
以下是嵌套函数的示例：
#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调用期间存在。在某些体系结构上，会在运行时生成一个小的存根函数 - 跳板 - 它包含sort_bytes调用的当前调用堆栈位置。当被调用时，它跳转到compar代码，并传递该地址。
这种混乱在像PowerPC这样的体系结构上不是必需的，因为ABI规定函数指针实际上是一个“fat指针”，包含指向可执行代码和另一个指向数据的指针的结构。然而，在x86上，函数指针只是一个指针。
- ephemient
1
我想探索一下这个问题，并注意到它无法使用标准的C编译器进行编译。http://gcc.gnu.org/onlinedocs/gcc/Nested-Functions.html那个页面有相关的信息。嵌套函数在GCC中是作为一种扩展实现的。“GCC通过一种称为跳板的技术来实现获取嵌套函数地址的功能。这种技术在《Lexical Closures for C++》（Thomas M. Breuel, USENIX C++ Conference Proceedings, October 17-21, 1988）中有描述。” 这是在godbolt上的链接：https://godbolt.org/z/W9W9PdMPv - undefined
1
现在C#有了本地函数，使用一个trampoline就可以优雅地解决Bowling Game编程卡塔：
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());。 这个本地函数递归遍历投掷数组。 本地函数（trampoline）允许遍历从两个附加值开始：以frame 1和 rsf（迄今为止的结果）0 开始。在本地函数中，有一个三元运算符，处理以下五种情况：
- 比赛在第11轮结束：返回到目前为止的结果
- 如果没有更多的投掷，则游戏结束：返回到目前为止的结果
- 全中: 计算本轮得分并继续遍历
- 补中: 计算本轮得分并继续遍历
- 普通得分: 计算本轮得分并继续遍历
想要了解更多信息，请搜索: "尾递归累加器"。请记住，编译器不会优化尾递归。因此，尽管这种解决方案可能很优雅，但它可能不是最快的。
- RandomProgrammer
0
在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");
编辑：编译器将隐式生成更多奇特的跳板。其中一个用途是跳转表。（尽管在尝试生成复杂代码时，显然会有更复杂的跳板。）
- MSN
-2
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();
}
// ...
- thenry
2
3你能否添加任何评论或解释为什么这是一个蹦床？ - prasun
这是一个函数指针，根据它所调用的函数返回的内容，跳转到下一个函数。 - thenry
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接