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

language-agnostic programming-languages

Question

Durante las 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 fragmento de código simple que ilustraría un trampolín?

Answer 1

Actualmente estoy experimentando con formas de implementar la optimización de llamadas 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 lo entiendo, es básicamente una serie de llamadas a funciones realizadas por una función de trampolín. Cada función se denomina procesador y devuelve el siguiente paso en el cálculo hasta que el programa finaliza (continuación vacía).

Esta es la primera pieza 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);
}

resultados en:

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

Answer 2

Aquí hay 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);
}

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

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

Answer 3

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: Trampolines más esotéricos serían generados implícitamente por el compilador. Uno de esos usos sería una mesa de saltos. (Aunque hay claramente más complicados, cuanto más abajo empiezas a intentar generar código complicado).

Answer 4

Permítanme agregar algunos ejemplos para la 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, sum: BigInt): Bounce[BigInt] = {
    if (n <= 2) Done(sum)
    else Call(() => factorial(n - 1, n * sum))
}

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 sum)
    {
        if(n <= 1) {
            return new Trampoline<BigInteger>() { public BigInteger get() { return sum; } };
        }   
        else {
            return new Trampoline<BigInteger>() { 
                public Trampoline<BigInteger> run() { 
                    return factorial(n - 1, sum.multiply(BigInteger.valueOf(n)));
                } 
            };
        }
    }

    public static void main( String [ ] args )
    {
        System.out.println(factorial(100000, BigInteger.ONE).execute());
    }
}

C (desafortunada sin 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 sum;
} factorialParameters;

void factorial(trampoline_data* data) {
  factorialParameters* parameters = (factorialParameters*) data->parameters;

  if (parameters->n <= 1) {
    data->callback = NULL;
  }
  else {
    parameters->sum *= parameters->n;
    parameters->n--;
  }
}

int main() {
  factorialParameters params = {5, 1};
  trampoline_data t = {&factorial, &params};

  trampoline(&t);
  printf("/n%d/n", params.sum);

  return 0;
}

Answer 5

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 iterativamente funciones de devolución de datos. Un solo trampolín es suficiente para expresar todas las transferencias de control de un programa; un programa así expresado es trampolín o en "estilo trampolín"; la conversión de un programa al estilo trampolín es trampolín. Las funciones trampolinadas se pueden usar para implementar llamadas a funciones recursivas de cola en lenguajes orientados a la pila

Digamos que estamos usando Javascript y queremos escribir la función ingenua de Fibonacci en el estilo de continuación de paso. La razón por la que haríamos esto no es relevante: portar Scheme a JS, por ejemplo, o jugar con CPS, que debemos 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 al ejecutar esto con n = 25 en Firefox aparece un error ''¡Demasiada recursión!''. Este es exactamente el problema (falta de optimización de la llamada de la cola en Javascript) que soluciona el trampolín. En lugar de realizar una llamada (recursiva) a una función, permítanos return una instrucción (thunk) para llamar a esa función, para que se interprete 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]});
}

Answer 6

Te 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 estaba cargando para modificarlos. Así que la forma más sólida que encontré para hacer esto fue usar un trampolín para CreateFileA. Entonces, cuando se lanzara el juego, encontraría la dirección de CreateFileA usando GetProcAddress, luego modificaría los primeros bytes de la función e insertaría el código ensamblador que saltaría a mi propia función "trampolín", donde haría algunas cosas, y luego volvería a la siguiente ubicación en CreateFile después de mi código de jmp. Poder hacerlo de manera confiable es un poco más complicado que eso, pero el concepto básico es simplemente enganchar una función, forzarla a redirigir a otra función y luego volver a la función original.

Editar: Microsoft tiene un marco para este tipo de cosas que puedes mirar. Llamado Detours

Answer 7

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