Was ist eine Trampolinfunktion?

Lesezeit: 8 Minuten

Benutzeravatar von Benoit
Benoit

Bei kürzlichen Diskussionen auf der Arbeit hat jemand von einer Trampolinfunktion gesprochen.

Ich habe die Beschreibung unter gelesen Wikipedia. Es reicht aus, um eine allgemeine Vorstellung von der Funktionalität zu geben, aber ich hätte gerne etwas Konkreteres.

Haben Sie ein einfaches Code-Snippet, das ein Trampolin veranschaulichen würde?

  • In der Microsoft-Welt werden Trampoline üblicherweise „Thunks“ genannt. [Here’s a page][1] aus Andrei Alexandrescus “Modern C++ Design” —- [1]:books.google.com/…

    – Michael Burr

    10. Oktober 2008 um 1:02 Uhr

  • Verwandt

    – bobobobo

    12. Oktober 2010 um 12:26 Uhr


  • Es ist im Grunde die verallgemeinerte Form einiger Funktionen, die Sie mit setjmp/lomgjmp implementieren könnten, nämlich um einen Stapelüberlauf zu vermeiden.

    – Ing

    11. Juli 2013 um 15:51 Uhr

  • Warum sollte jemand einen Stapelüberlauf vermeiden wollen?

    – Nikola

    19. Juni 2016 um 15:30 Uhr

Es gibt auch den LISP-Sinn von “Trampolin”, wie auf Wikipedia beschrieben:

Ein Trampolin, das in einigen LISP-Implementierungen verwendet wird, ist eine Schleife, die iterativ Thunk-Rückgabefunktionen aufruft. Ein einziges Trampolin reicht aus, um alle Steuerübertragungen eines Programms auszudrücken; ein so ausgedrücktes Programm ist Trampolin oder im “Trampolin-Stil”; Das Umwandeln eines Programms in den Trampolinstil ist Trampolinspringen. Mit Trampolinen versehene Funktionen können verwendet werden, um rekursive Funktionsaufrufe in Stack-orientierten Sprachen zu implementieren

Nehmen wir an, wir verwenden Javascript und möchten die naive Fibonacci-Funktion im Continuation-Passing-Stil schreiben. Der Grund, warum wir dies tun würden, ist nicht relevant – zum Beispiel, um Scheme auf JS zu portieren oder mit CPS zu spielen, das wir sowieso verwenden müssen, um serverseitige Funktionen aufzurufen.

Also, 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 das läuft mit n = 25 in Firefox gibt einen Fehler ‘Too much recursion!’. Genau dieses Problem (fehlende Tail-Call-Optimierung in Javascript) löst Trampolining. Anstatt eine Funktion (rekursiv) aufzurufen, lassen Sie uns return eine Anweisung (Thunk) zum Aufrufen dieser Funktion, die in einer Schleife interpretiert werden soll.

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

Benutzeravatar von Piotr Kukielka
Piotr Kukielka

Lassen Sie mich einige Beispiele für mit Trampolinen implementierte Fakultätsfunktionen in verschiedenen Sprachen hinzufügen:

Skala:

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 (unglücklich ohne Implementierung großer Zahlen):

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

  • Ihre Erklärung, insbesondere das C-Beispiel, sowie die Antwort von ephemient unten zu verschachtelten Funktionen haben mich endlich dazu gebracht, Trampoline zu verstehen. Eine Art Hilfsfunktion, die verwendet werden kann, um den Status ähnlich wie eine Schließung zu aktualisieren.

    –Byte

    10. September 2018 um 23:55 Uhr

  • Scala-Code sollte korrigiert werden if (n < 2) Done(product)SO hat mir nicht erlaubt, 1 Symbol zu bearbeiten…

    – max

    29. September 2019 um 6:50 Uhr

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, die vom Spiel geladen wurden, auf Modifikation zu scannen. Der robusteste Weg, den ich dafür gefunden habe, war die Verwendung eines Trampolins für CreateFileA. Wenn das Spiel also 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. Dies zuverlässig zu tun, ist etwas kniffliger, aber das Grundkonzept besteht darin, nur eine Funktion zu verknüpfen, sie zu zwingen, auf eine andere Funktion umzuleiten, und dann zur ursprünglichen Funktion zurückzukehren.

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

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

So wie ich es verstehe, handelt es sich im Grunde nur um eine Reihe von Funktionsaufrufen, die von einer Trampolinfunktion ausgeführt werden. Jede Funktion wird als Thunk bezeichnet und gibt den nächsten Schritt in der Berechnung zurück, bis das Programm beendet wird (leere Fortsetzung).

Hier ist das erste Stück Code, das ich geschrieben habe, um 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);
}

ergibt:

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

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 keine externe Funktion sein, weil sie verwendet nbytesdie nur während der existiert sort_bytes Anruf. Auf einigen Architekturen wird zur Laufzeit eine kleine Stub-Funktion – das Trampolin – generiert, die den Stapelspeicherort der enthält aktuell Aufruf von sort_bytes. Beim Aufruf springt es auf die compar Code, der diese Adresse übergibt.

Dieses Durcheinander ist auf Architekturen wie PowerPC nicht erforderlich, wo die ABI angibt, dass ein Funktionszeiger tatsächlich ein “fetter Zeiger” ist, eine Struktur, die sowohl einen Zeiger auf den ausführbaren Code als auch einen anderen Zeiger auf Daten enthält. Auf x86 ist ein Funktionszeiger jedoch nur ein Zeiger.

Jetzt, wo C# hat Lokale Funktionendas Bowling-Spiel, das Kata kodiert lassen sich mit einem Trampolin elegant lösen:

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

Die Methode Game.RollMany wird mit einer Anzahl von Würfen angesagt: normalerweise 20 Würfe, wenn es keine Spares oder Strikes gibt.

Die erste Zeile ruft sofort die Trampolinfunktion auf: return Trampoline(1, 0, rs.ToList());. Diese lokale Funktion durchläuft rekursiv das Rolls-Array. Die lokale Funktion (das Trampolin) ermöglicht es, die Traversierung mit zwei zusätzlichen Werten zu beginnen: start with frame 1 und die rsf (Ergebnis bisher) 0.

Innerhalb der lokalen Funktion gibt es einen ternären Operator, der fünf Fälle behandelt:

  • Das Spiel endet bei Frame 11: Gib das bisherige Ergebnis zurück
  • Das Spiel endet, wenn es keine weiteren Würfe gibt: Gib das bisherige Ergebnis zurück
  • Strike: Berechnen Sie den Frame-Score und setzen Sie die Traversierung fort
  • Spare: Berechnen Sie den Frame-Score und setzen Sie die Traversierung fort
  • Normaler Score: Berechnen Sie den Frame-Score und fahren Sie mit der Traversierung fort

Das Fortsetzen der Traversierung erfolgt durch erneutes Aufrufen des Trampolins, jetzt jedoch mit aktualisierten Werten.

Für weitere Informationen suchen Sie nach: “Schwanzrekursionsakkumulator“. Denken Sie daran, dass der Compiler die Schwanzrekursion nicht optimiert. So elegant diese Lösung auch sein mag, sie wird wahrscheinlich nicht die schnellste sein.

Benutzeravatar von MSN
MSN

Für C wäre ein Trampolin ein Funktionszeiger:

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

Bearbeiten: Weitere esoterische Trampoline würden implizit vom Compiler generiert. Eine solche Verwendung wäre ein Sprungtisch. (Obwohl es deutlich kompliziertere gibt, je weiter unten Sie versuchen, komplizierten Code zu generieren.)

1422280cookie-checkWas ist eine Trampolinfunktion?

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy