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

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

Answer 1

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

Necesitaba poder escanear todos los archivos que estaban siendo cargados por el juego para su modificación. 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 usted puede mirar. Llamado Detours

Answer 2

He aquí un ejemplo de las 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, ya que utiliza nbytes, que sólo 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 pila de la actual llamada 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 de función es en realidad un "puntero gordo", una estructura que contiene un puntero al código ejecutable y otro puntero a datos. Sin embargo, en x86, un puntero de función es solo un puntero.

Answer 3

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

Se utiliza en algunas implementaciones de LISP, un trampolín es un bucle que forma iterativa invoca thunk-volviendo funciones. 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"; convirtiendo un programa en trampolín estilo es trampolín. Trampolined funciones pueden utilizarse para aplicar la cola función recursiva se llama en lenguajes orientados a pila-

Digamos que estamos utilizando Javascript y queremos escribir la función de Fibonacci ingenua en que pasa al estilo de continuación. 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.

Así, 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) 
      }) 
     }); 
    } 
} 

embargo, la ejecución de este con n = 25 en Firefox da un error 'Demasiado recursividad!'. 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, déjenos 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 4

Para C, una cama elástica 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: camas elásticas más esotérico serían implícitamente generados por el compilador. Uno de esos usos sería una mesa de saltos. (Aunque hay claramente más complicados, más abajo se comienza a intentar generar código complicado.)

Answer 5

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

Según tengo entendido, se trata básicamente de 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).

Aquí es la primera pieza de código que escribí para mejorar mi comprensión de la cama elástica:

#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 6

permítanme añadir algunos ejemplos para la función factorial implementado con camas elásticas , 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 (mala suerte sin grandes números de aplicación):

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