Qu'est-ce qu'une fonction trampoline?

Lors de récentes discussions au travail, quelqu'un a évoqué une fonction de trampoline.

J'ai lu la description sur Wikipedia . Il suffit de donner une idée générale de la fonctionnalité, mais j'aimerais quelque chose d'un peu plus concret.

Avez-vous un simple extrait de code qui illustrerait un trampoline?

Il y a aussi le sens LISP de `` trampoline '' tel que décrit sur Wikipedia:

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

Disons que nous utilisons Javascript et que nous voulons écrire la fonction naïve de Fibonacci en continuation-pass-style. La raison pour laquelle nous ferions cela n'est pas pertinente - pour porter Scheme sur JS par exemple, ou pour jouer avec 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, exécuter ceci avec n = 25dans Firefox donne une erreur «Trop de récursivité!». Maintenant, c'est exactement le problème (l'optimisation des appels de queue manquante en Javascript) que le trampoline résout. Au lieu de faire un appel (récursif) à une fonction, laissez-nous returnune 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]});
}

Permettez-moi d'ajouter quelques exemples de 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<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 implémentation 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-triche pour un jeu en ligne.

J'avais besoin de pouvoir analyser tous les fichiers chargés par le jeu pour les modifier. Donc, le moyen le plus robuste que j'ai trouvé pour le faire était d'utiliser un trampoline pour CreateFileA. Ainsi, lorsque le jeu était lancé, je trouvais l'adresse de CreateFileA en utilisant GetProcAddress, puis je modifierais les premiers octets de la fonction et j'insérerais le code d'assemblage qui passerait à ma propre fonction "trampoline", où je ferais certaines choses, et alors je reviendrais à l'emplacement suivant dans CreateFile après mon code jmp. Être capable de le faire de manière fiable est un peu plus délicat que cela, mais le concept de base consiste simplement à accrocher une fonction, à la forcer à la rediriger vers une autre fonction, puis à revenir à la fonction d'origine.

Edit: Microsoft a un cadre pour ce type de chose que vous pouvez regarder. Détours appelés

J'expérimente actuellement des moyens d'implémenter l'optimisation des appels de queue pour un interpréteur de schéma, et donc pour le moment j'essaie de déterminer si le trampoline serait faisable pour moi.

Si je comprends bien, il s'agit essentiellement d'une série d'appels de fonction exécutés par une fonction de trampoline. Chaque fonction est appelée un thunk et retourne l'étape suivante du calcul jusqu'à la fin du programme (suite vide).

Voici le premier morceau de code que j'ai écrit pour 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ésulte en:

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

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

comparne peut pas être une fonction externe, car elle utilise nbytes, qui n'existe que pendant l' sort_bytesappel. Sur certaines architectures, une petite fonction stub - le trampoline - est générée lors de l'exécution et contient l'emplacement de la pile de l' invocation actuelle de sort_bytes. Lorsqu'il est appelé, il saute au comparcode, en passant cette adresse.

Ce désordre n'est pas nécessaire sur les architectures comme PowerPC, où l'ABI spécifie qu'un pointeur de fonction est en fait un "gros pointeur", une structure contenant à la fois un pointeur vers le code exécutable et un autre pointeur vers des données. Cependant, sur x86, un pointeur de fonction n'est qu'un pointeur.

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

Maintenant que C # a des fonctions locales , le kata de codage du jeu de bowling peut être résolu avec élégance avec un trampoline:

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

La méthode Game.RollManyest appelée avec un certain nombre de rouleaux: généralement 20 rouleaux s'il n'y a pas de pièces de rechange ou de grèves.

La première ligne appelle immédiatement la fonction de trampoline: return Trampoline(1, 0, rs.ToList());. Cette fonction locale parcourt récursivement le tableau rolls. La fonction locale (le trampoline) permet au parcours de démarrer avec deux valeurs supplémentaires: commencer par frame1 et le rsf(résultat jusqu'ici) 0.

Dans la fonction locale, il existe un opérateur ternaire qui gère cinq cas:

• Le jeu se termine à l'image 11: retournez le résultat jusqu'à présent
• Le jeu se termine s'il n'y a plus de jets: retournez le résultat jusqu'à présent
• Strike: calculez le score d'image et continuez la traversée
• Spare: calculez le score d'image et continuez le parcours
• Score normal: calculez le score d'image et continuez le parcours

La poursuite de la traversée se fait en appelant à nouveau le trampoline, mais maintenant avec des valeurs mises à jour.

Pour plus d'informations, recherchez: " accumulateur de récursion de queue ". Gardez à l'esprit que le compilateur n'optimise pas la récursivité de queue. Aussi élégante que puisse être cette solution, ce ne sera probablement pas le jeûné.

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