Qu'est-ce qu'une fonction trampoline ?

Question

Lors de récentes discussions au travail, quelqu'un a fait référence à une fonction trampoline.

J'ai lu la description sur Wikipédia. Cela suffit pour se faire une idée générale de la fonctionnalité, mais j'aimerais quelque chose de plus concret.

Auriez-vous un petit extrait de code simple qui pourrait illustrer une trampoline?

Answer 1

Il existe également le sens de 'trampoline' en LISP tel que décrit sur Wikipedia :

Utilisé dans certaines implémentations de LISP, un trampoline est une boucle qui invoque de manière itérative des fonctions renvoyant un thunk. Un seul trampoline est suffisant pour exprimer tous les transferts de contrôle d'un programme ; un programme ainsi exprimé est trampoliné ou en "style trampoliné" ; convertir un programme en style trampoliné est du trampolinage. Les fonctions trampolinées peuvent être utilisées pour implémenter des appels de fonction récursive terminale dans des langages orientés sur la pile

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

Ainsi, la première tentative est la suivante :

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

Cependant, en exécutant ceci avec n = 25 dans Firefox, une erreur 'Trop de récursion !' se produit. C'est précisément le problème (optimisation des appels récursifs terminaux manquante en Javascript) que la trampolisation résout. Au lieu de faire un appel (récursif) à une fonction, retournons une instruction (thunk) pour appeler cette fonction, à interpréter dans une 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]});
}

Answer 2

Laissez-moi ajouter quelques exemples pour la fonction factorielle implémentée avec des trampolines, dans différentes langues :

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 
{
    public T get() { return null; }
    public Trampoline  run() { return null; }

    T execute() {
        Trampoline  trampoline = this;

        while (trampoline.get() == null) {
            trampoline = trampoline.run();
        }

        return trampoline.get();
    }
}

public class Factorial
{
    public static Trampoline factorial(final int n, final BigInteger product)
    {
        if(n <= 1) {
            return new Trampoline() { public BigInteger get() { return product; } };
        }   
        else {
            return new Trampoline() { 
                public Trampoline 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 (malheureusement sans implémentation de grands nombres) :

#include 

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

Answer 3

Je vais vous donner un exemple que j'ai utilisé dans un correctif anti-triche pour un jeu en ligne.

J'avais besoin de pouvoir analyser tous les fichiers qui étaient chargés par le jeu pour modification. La manière la plus robuste que j'ai trouvée pour le faire était d'utiliser un trampoline pour CreateFileA. Ainsi, lorsque le jeu était lancé, je devais trouver l'adresse de CreateFileA en utilisant GetProcAddress, puis je modifiais les premiers octets de la fonction et j'insérais du code assembleur qui sauterait vers ma propre fonction de "trampoline", où je ferais certaines choses, puis je sauterais de nouveau à l'emplacement suivant dans CreateFile après mon code jmp. Pour pouvoir le faire de manière fiable, c'est un peu plus délicat que cela, mais le concept de base est simplement de crocheter une fonction, de la forcer à rediriger vers une autre fonction, puis de sauter de nouveau vers la fonction originale.

Edit: Microsoft a un framework pour ce type de chose que vous pouvez consulter. Appelé Detours

Answer 4

Actuellement, j'expérimente des façons de mettre en œuvre l'optimisation des appels de queue pour un interprète Scheme, et donc en ce moment j'essaie de déterminer si le trampoline serait faisable pour moi.

D'après ce que je comprends, 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 dans le calcul jusqu'à ce que le programme se termine (continuation vide).

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

#include 

typedef void *(*CONTINUATION)(int);

void trampoline(CONTINUATION cont)
{
  int counter = 0;
  CONTINUATION currentCont = cont;
  while (currentCont != NULL) {
    currentCont = (CONTINUATION) currentCont(counter);
    counter++;
  }
  printf("sorti du trampoline - joyeux joyeux bonheur !\n");
}

void *thunk3(int param)
{
  printf("*boing* dernier 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ésultat :

meincompi $ ./trampoline 
*boing* thunk 1
*boing* thunk 2
*boing* dernier thunk
sorti du trampoline - joyeux joyeux bonheur !

Answer 5

Voici un exemple de fonctions imbriquées :

#include <stdlib.h>
#include <string.h>
/ * trier un tableau, en commençant à l'adresse `base`,
 * contenant `nmemb` membres, séparés par `size`,
 * en comparant uniquement les premiers `nbytes`. * /
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 pendant l'appel à sort_bytes. Sur certaines architectures, une petite fonction trampoline est générée à l'exécution et contient l'emplacement de pile de l'invocation actuelle de sort_bytes. Lorsqu'elle est appelée, elle saute au code de compar, en passant cette adresse.

Ce bazar n'est pas nécessaire sur des architectures comme PowerPC, où l'ABI spécifie qu'un pointeur de fonction est en réalité un "pointeur gras", 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 n'est qu'un simple pointeur.