Was ist eine Trampolinfunktion?

Question

Während der letzten Diskussionen bei der Arbeit bezog sich jemand auf eine Trampolin-Funktion. Ich habe die Beschreibung unter Wikipedia gelesen. Es ist genug, um einen Überblick über die Funktionalität zu geben, aber ich möchte etwas konkreter.

Haben Sie ein einfaches Codeschnipsel, das ein Trampolin veranschaulichen würde?

Answer 1

Ich gebe Ihnen ein Beispiel, das ich in einem Anti-Cheat-Patch für ein Online-Spiel verwendet habe.

Ich musste in der Lage sein, alle Dateien zu scannen, die vom Spiel zur Modifikation geladen wurden. Die robusteste Methode, dies zu tun, war ein Trampolin für CreateFileA. Also, wenn das Spiel gestartet wurde, würde ich die Adresse für CreateFileA mit GetProcAddress finden, dann würde ich die ersten paar Bytes der Funktion ändern und Assembler-Code einfügen, der zu meiner eigenen "Trampolin" -Funktion springen würde, wo ich einige Dinge tun würde, und dann würde ich nach meinem JMP-Code zurück zum nächsten Ort in CreateFile springen. Zuverlässiger zu sein, ist ein wenig komplizierter als das, aber das Grundkonzept besteht darin, nur eine Funktion zu haken, sie zu einer anderen Funktion umzuleiten und dann zurück zur ursprünglichen Funktion zu springen.

Bearbeiten: Microsoft hat ein Framework für diese Art von Dingen, die Sie betrachten können. Genannt Detours

Answer 2

Hier ist ein Beispiel für verschachtelte Funktionen:

#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 kann nicht eine externe Funktion, weil es nbytes verwendet, die nur während der sort_bytes Anruf existiert. Auf einigen Architekturen wird zur Laufzeit eine kleine Stub-Funktion - das Trampolin - erzeugt, die den Stack-Ort des aktuellen Aufrufs von sort_bytes enthält. Wenn sie aufgerufen wird, springt sie zu dem Code compar und gibt diese Adresse weiter.

Diese Unordnung ist auf Architekturen wie PowerPC nicht erforderlich, wo der ABI angibt, dass ein Funktionszeiger tatsächlich ein "dicker Zeiger" ist, eine Struktur, die sowohl einen Zeiger auf den ausführbaren Code als auch einen anderen Zeiger auf Daten enthält. Ein Funktionszeiger ist jedoch nur ein Zeiger auf x86.

Answer 3

Es gibt auch den LISP Sinn von ‚Trampolin‘, wie auf Wikipedia beschrieben:

in einigen LISP-Implementierungen, ein Trampolin ist eine Schleife, die iterativ aufrufen thunk-Rückkehr Funktionen. Ein einzelnes Trampolin reicht aus, um alle Steuerübertragungen eines Programms auszudrücken; ein so ausgedrücktes Programm ist Trampolin oder im "Trampolin-Stil"; Umwandlung eines Programms in Trampolin Stil ist Trampolinspringen. Trampolined Funktionen können verwendet werden, Schwanz rekursive Funktion ruft in stapelorientierten Sprachen

uns zu implementieren Lassen Sie sagen, wir Javascript verwenden und wollen die naive Fibonacci-Funktion in Weiter-passing-Stil schreiben. Der Grund, warum wir das tun würden, ist nicht relevant - beispielsweise, um Scheme nach JS zu portieren oder um mit CPS zu spielen, das wir sowieso verwenden müssen, um serverseitige Funktionen aufzurufen.

So, der erste Versuch ist

function fibcps(n, c) { 
    if (n <= 1) { 
     c(n); 
    } else { 
     fibcps(n - 1, function (x) { 
      fibcps(n - 2, function (y) { 
       c(x + y) 
      }) 
     }); 
    } 
} 

Aber läuft dies mit n = 25 in Firefox einen Fehler gibt 'Rekursion zu viel!'. Nun ist das genau das Problem (fehlende Tail-Call-Optimierung in Javascript) das Trampolining löst. Anstatt einen (rekursiven) Aufruf an eine Funktion zu machen, lassen Sie uns return eine Anweisung (Thunk), um diese Funktion aufzurufen, in einer Schleife zu interpretieren.

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 4

Für C, ein Trampolin ein Funktionszeiger sein würde:

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

Edit: Mehr esoterischen Trampoline würde implizit durch den Compiler erzeugt werden. Eine solche Verwendung wäre ein Sprungtisch. (Obwohl es deutlich kompliziertere gibt, desto weiter unten beginnen Sie, komplizierten Code zu generieren.)

Answer 5

Ich experimentiere gerade mit Möglichkeiten, die Tail-Call-Optimierung für einen Scheme-Interpreter zu implementieren, und im Moment versuche ich herauszufinden ob das Trampolin für mich machbar wäre.

Wie ich es verstehe, ist es im Grunde nur eine Reihe von Funktionsaufrufen von einer Trampolin-Funktion durchgeführt. Jede Funktion wird als Thunk bezeichnet und gibt den nächsten Schritt in der Berechnung zurück, bis das Programm beendet ist (leere Fortsetzung). Hier

ist das erste Stück Code, das ich geschrieben habe mein Verständnis des Trampolins zu verbessern:

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

Ergebnisse in:

meincompi $ ./trampoline 
*boing* thunk 1 
*boing* thunk 2 
*boing* last thunk 
got off the trampoline - happy happy joy joy ! 

Answer 6

Lassen Sie mich einige Beispiele für Fakultäts-Funktion hinzufügen, mit Trampolinen umgesetzt , in verschiedenen Sprachen:

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

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

    public static void main(String [ ] args) 
    { 
     System.out.println(factorial(100000, BigInteger.ONE).execute()); 
    } 
} 

C (Pech ohne große Zahlen Implementierung):

#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 sum; 
} factorialParameters; 

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

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

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

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

    return 0; 
} 

Answer 7

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