Qu'est ce qu'un trampoline?

il y a aussi le sens de "trampoline" tel que décrit sur Wikipedia:

utilisé dans certaines implémentations du LISP, trampoline est une boucle qui itérativement invoque les fonctions de retour de thunk. Un un seul trampoline suffit pour exprimer tous les transferts de contrôle d'un programme; un programme d'expression est trampolined ou dans "trampolined style"; conversion d'un programme en trampoline le style est trampolining. Trampoliné les fonctions peuvent être utilisées pour mettre appel de fonction récursive de queue pile langages orientés

disons que nous utilisons Javascript et que nous voulons écrire la fonction naïve Fibonacci dans le style continuation-passing. La raison pour laquelle nous ferions cela n'est pas pertinente - par exemple pour le portage vers JS, ou pour jouer avec des CPS que nous devons utiliser de toute façon pour appeler des fonctions côté serveur.

donc, la première tentative est

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

mais, en cours d'exécution de ce avec n = 25 dans Firefox donne une erreur' trop de récursion!'. Maintenant, c'est exactement le problème (absence d'optimisation de l'appel de queue dans Javascript) que trampolining résout. Au lieu de faire un appel (récursif) à une fonction, return une instruction (thunk) pour appeler cette fonction, à interpréter en boucle.

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

Permettez-moi d'ajouter quelques exemples pour la fonction factorielle mise en œuvre avec des trampolines, dans des langues différentes:

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 (malchanceux sans mise en œuvre de grands nombres):

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

je vais vous donner un exemple que j'ai utilisé dans un patch anti-cheat pour un jeu en ligne.

j'avais besoin de pouvoir scanner tous les fichiers qui étaient chargés par le jeu pour modification. Donc la façon la plus robuste que j'ai trouvé pour faire cela était d'utiliser un trampoline pour CreateFileA. Ainsi quand le jeu a été lancé je trouverais L'adresse pour CreateFileA en utilisant Getrocaddress, alors je modifierais les premiers octets de la fonction et insérerais le code d'assemblage qui sauterait à mon propre fonction "trampoline", où je ferais certaines choses, puis je retournerais à L'endroit suivant dans CreateFile après mon code jmp. Pour être en mesure de le faire de manière fiable est un peu plus compliqué que cela, mais le concept de base est juste de crocheter une fonction, la forcer à rediriger vers une autre fonction, puis de sauter de nouveau à la fonction originale.

éditer: Microsoft a un cadre pour ce type de chose que vous pouvez regarder. Appelé Détours

voici un exemple de fonctions imbriquées:

#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 ne peut pas être une fonction externe, car elle utilise nbytes , qui n'existe que lors de l'appel sort_bytes . Sur certaines architectures, une petite fonction de BUB -- le trampoline -- est générée à l'exécution, et contient l'emplacement de la pile du courant invocation de sort_bytes . Quand il est appelé, il saute au code compar , passant cette adresse.

ce mess n'est pas requis sur les architectures comme PowerPC, où L'ABI spécifie qu'un pointeur de fonction est en fait un" pointeur fat", une structure contenant à la fois un pointeur vers le code exécutable et un autre pointeur vers les données. Cependant, sur x86, un pointeur de fonction est un pointeur.

je suis en train d'expérimenter des façons de mettre en œuvre l'optimisation des appels de queue pour un interpréteur de schéma, et donc en ce moment j'essaye de comprendre si le trampoline serait faisable pour moi.

d'après ce que j'ai compris, il s'agit essentiellement d'une série d'appels de fonction effectués par une fonction trampoline. Chaque fonction est appelée un thunk et renvoie l'étape suivante du calcul jusqu'à ce que le programme se termine (suite vide).

Voici le premier morceau de code que j'ai écrit à améliorer ma compréhension du trampoline:

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

résultats dans:

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

pour C, un trampoline serait un pointeur de fonction:

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: Plus de trampolines ésotériques seraient générées implicitement par le compilateur. Une telle utilisation serait une table de saut. (Bien qu'il y en ait clairement plus compliquées plus loin, vous commencez à essayer de générer du code compliqué.)

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