¿Qué es una función de trampolín?

Durante discusiones recientes en el trabajo, alguien se refirió a una función de trampolín.

He leído la descripción en Wikipedia . Es suficiente para dar una idea general de la funcionalidad, pero me gustaría algo un poco más concreto.

¿Tiene un simple fragmento de código que ilustraría un trampolín?

También existe el sentido LISP de 'trampolín' como se describe en Wikipedia:

Utilizado en algunas implementaciones de LISP, un trampolín es un bucle que invoca de forma iterativa funciones de retorno de procesador. Un solo trampolín es suficiente para expresar todas las transferencias de control de un programa; un programa así expresado está en trampolín o en "estilo trampolín"; convertir un programa al estilo trampolín es trampolín. Las funciones de trampolín se pueden usar para implementar llamadas de función recursivas de cola en lenguajes orientados a pilas

Digamos que estamos usando Javascript y queremos escribir la función de Fibonacci ingenua en estilo de continuación-paso. La razón por la que haríamos esto no es relevante: para portar Scheme a JS, por ejemplo, o para jugar con CPS, que tenemos que usar de todos modos para llamar a las funciones del lado del servidor.

Entonces, el primer intento es

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

Pero, ejecutar esto con n = 25en Firefox da un error '¡Demasiada recursividad!'. Ahora bien, este es exactamente el problema (falta la optimización de la llamada de cola en Javascript) que resuelve el trampolín. En lugar de hacer una llamada (recursiva) a una función, permítanos returnuna instrucción (thunk) para llamar a esa función, para ser interpretada en un bucle.

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

Permítanme agregar algunos ejemplos de función factorial implementada con trampolines, en diferentes idiomas:

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 (mala suerte sin la implementación de grandes números):

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

Les daré un ejemplo que utilicé en un parche anti-trampas para un juego en línea.

Necesitaba poder escanear todos los archivos que el juego cargaba para modificarlos. Entonces, la forma más sólida que encontré para hacer esto fue usar un trampolín para CreateFileA. Entonces, cuando se lanzaba el juego, encontraba la dirección para CreateFileA usando GetProcAddress, luego modificaba los primeros bytes de la función e insertaba el código ensamblador que saltaba a mi propia función de "trampolín", donde haría algunas cosas, y luego volvería a la siguiente ubicación en CreateFile después de mi código jmp. Poder hacerlo de manera confiable es un poco más complicado que eso, pero el concepto básico es simplemente conectar una función, forzarla a redirigirla a otra función y luego volver a la función original.

Editar: Microsoft tiene un marco para este tipo de cosas que puedes ver. Desvíos llamados

Actualmente estoy experimentando formas de implementar la optimización de la llamada de cola para un intérprete de Scheme, por lo que en este momento estoy tratando de averiguar si el trampolín sería factible para mí.

Según tengo entendido, es básicamente una serie de llamadas de función realizadas por una función de trampolín. Cada función se llama procesador y devuelve el siguiente paso en el cálculo hasta que el programa termina (continuación vacía).

Aquí está el primer fragmento de código que escribí para mejorar mi comprensión del trampolín:

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

resulta en:

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

Aquí tienes un ejemplo de funciones anidadas:

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

comparno puede ser una función externa, porque usa nbytes, que solo existe durante la sort_bytesllamada. En algunas arquitecturas, una pequeña función de código auxiliar, el trampolín, se genera en tiempo de ejecución y contiene la ubicación de la pila de la invocación actual de sort_bytes. Cuando se llama, salta al comparcódigo y pasa esa dirección.

Este desorden no es necesario en arquitecturas como PowerPC, donde la ABI especifica que un puntero de función es en realidad un "puntero gordo", una estructura que contiene tanto un puntero al código ejecutable como otro puntero a los datos. Sin embargo, en x86, un puntero de función es solo un puntero.

Para C, un trampolín sería un puntero de función:

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

Editar: El compilador generaría implícitamente trampolines más esotéricos. Uno de esos usos sería una mesa de salto. (Aunque claramente hay otros más complicados cuanto más abajo empiece a intentar generar código complicado).

Ahora que C # tiene funciones locales , el kata de codificación del juego de bolos se puede resolver elegantemente con un trampolín:

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

El método Game.RollManyse llama con una serie de rollos: normalmente 20 rollos si no hay repuestos o golpes.

La primera línea inmediatamente llama a la función de trampolín: return Trampoline(1, 0, rs.ToList());. Esta función local atraviesa de forma recursiva la matriz rolls. La función local (el trampolín) permite que el recorrido comience con dos valores adicionales: comenzar con frame1 y el rsf(resultado hasta ahora) 0.

Dentro de la función local existe un operador ternario que maneja cinco casos:

• El juego termina en el cuadro 11: devuelve el resultado hasta ahora
• El juego termina si no hay más tiradas: devuelve el resultado hasta ahora
• Strike: calcula la puntuación del cuadro y continúa el recorrido
• Repuesto: calcula la puntuación del cuadro y continúa el recorrido
• Puntuación normal: calcula la puntuación del cuadro y continúa el recorrido

La continuación del recorrido se realiza volviendo a llamar al trampolín, pero ahora con valores actualizados.

Para obtener más información, busque: " acumulador de recursividad de cola ". Tenga en cuenta que el compilador no optimiza la recursividad de cola. Por muy elegante que sea esta solución, es probable que no sea el ayuno.

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