113

職場での最近の議論の中で、誰かがトランポリン機能について言及しました。

ウィキペディアの説明を読みました。機能の一般的なアイデアを示すだけで十分ですが、もう少し具体的なものが欲しいです。

トランポリンを説明する簡単なコード スニペットはありますか?

4

8 に答える 8

78

ウィキペディアで説明されているように、「トランポリン」の LISP の意味もあります。

一部の LISP 実装で使用されるトランポリンは、サンクを返す関数を繰り返し呼び出すループです。プログラムのすべてのコントロール転送を表現するには、1 つのトランポリンで十分です。そのように表現されたプログラムは、トランポリンまたは「トランポリン スタイル」です。プログラムをトランポリン スタイルに変換するのがトランポリンです。トランポリン関数を使用して、スタック指向言語で末尾再帰関数呼び出しを実装できます

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 = 25Firefox で実行すると、「再帰が多すぎます!」というエラーが発生します。これはまさに、トランポリンが解決する問題 (Javascript で末尾呼び出しの最適化が欠落している) です。関数を (再帰的に) 呼び出す代わりにreturn、ループで解釈されるように、その関数を呼び出す命令 (サンク) を作成します。

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]});
}
于 2009-01-28T23:20:01.010 に答える
44

さまざまな言語で、トランポリンで実装された階乗関数の例をいくつか追加しましょう。

スカラ:

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

ジャワ:

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;
}
于 2012-08-12T10:29:49.510 に答える
23

オンライン ゲームのチート対策パッチで使用した例を紹介します。

ゲームによってロードされたすべてのファイルをスキャンして変更できるようにする必要がありました。そのため、これを行うための最も確実な方法は、CreateFileA にトランポリンを使用することでした。そのため、ゲームが起動されると、GetProcAddress を使用して CreateFileA のアドレスを見つけ、関数の最初の数バイトを変更して、独自の「トランポリン」関数にジャンプするアセンブリ コードを挿入し、そこでいくつかのことを行います。次に、jmp コードの後で CreateFile の次の場所に戻ります。確実に実行できるようにすることは、それよりも少しトリッキーですが、基本的な概念は、1 つの関数をフックし、強制的に別の関数にリダイレクトさせてから、元の関数にジャンプすることです。

編集: Microsoft には、この種のフレームワークがあります。迂回路と呼ばれる

于 2008-10-10T00:50:32.420 に答える
8

ネストされた関数の例を次に示します。

#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 では、関数ポインターは単なるポインターです。

于 2008-10-10T01:22:22.777 に答える
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");

編集:より難解なトランポリンは、コンパイラによって暗黙的に生成されます。そのような用途の 1 つにジャンプ テーブルがあります。(複雑なコードを生成しようとすると、下に行くほど明らかに複雑なものがあります。)

于 2009-01-28T23:31:08.150 に答える