Co to jest funkcja trampoliny?

Podczas ostatnich rozmów w pracy ktoś odniósł się do funkcji trampoliny.

Przeczytałem opis na Wikipedii . Wystarczy podać ogólne wyobrażenie o funkcjonalności, ale chciałbym czegoś bardziej konkretnego.

Czy masz prosty fragment kodu, który ilustruje trampolinę?

Istnieje również znaczenie LISP-a `` trampoliny '', jak opisano w Wikipedii:

Używana w niektórych implementacjach LISP, trampolina jest pętlą, która iteracyjnie wywołuje funkcje zwracające thunk. Jedna trampolina jest wystarczająca do wyrażenia wszystkich transferów kontrolnych programu; tak wyrażony program jest trampolinowy lub w stylu trampoliny; konwersja programu do stylu trampoliny to trampolina. Funkcje trampoliny mogą być używane do implementacji wywołań funkcji rekurencyjnych ogona w językach zorientowanych na stos

Powiedzmy, że używamy Javascript i chcemy napisać naiwną funkcję Fibonacciego w stylu kontynuacji-przekazywania. Powód, dla którego byśmy to zrobili, nie jest istotny - na przykład przeniesienie Scheme do JS lub granie z CPS, którego i tak musimy używać do wywoływania funkcji po stronie serwera.

Tak więc pierwsza próba jest

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

Ale uruchomienie tego n = 25w przeglądarce Firefox powoduje wyświetlenie błędu „Za dużo rekurencji!”. To jest dokładnie problem (brak optymalizacji wywołań ogonowych w JavaScript), który rozwiązuje trampolina. Zamiast wykonywać (rekurencyjne) wywołanie funkcji, returnużyjmy instrukcji (thunk), aby wywołać tę funkcję, aby została zinterpretowana w pętli.

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

Dodam kilka przykładów funkcji silni zaimplementowanej za pomocą trampolin w różnych językach:

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

Jawa:

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 (pech bez implementacji dużych liczb):

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

Podam ci przykład, którego użyłem w łatce przeciw oszustwom do gry online.

Musiałem mieć możliwość przeskanowania wszystkich plików ładowanych przez grę w celu modyfikacji. Więc najbardziej niezawodnym sposobem, jaki znalazłem, było użycie trampoliny do CreateFileA. Więc kiedy gra została uruchomiona, znajdowałem adres dla CreateFileA za pomocą GetProcAddress, potem modyfikowałem kilka pierwszych bajtów funkcji i wstawiałem kod asemblera, który przeskakiwałby do mojej własnej funkcji "trampoliny", w której robiłem kilka rzeczy i potem wróciłbym do następnej lokalizacji w CreateFile po moim kodzie jmp. Aby móc to zrobić niezawodnie, jest to trochę trudniejsze, ale podstawową koncepcją jest po prostu podpięcie jednej funkcji, wymuszenie na niej przekierowania do innej funkcji, a następnie powrót do pierwotnej funkcji.

Edycja: Microsoft ma ramy dla tego typu rzeczy, na które możesz spojrzeć. Nazywa się objazdami

Obecnie eksperymentuję ze sposobami implementacji optymalizacji wywołań ogonowych dla interpretera Schematu, więc w tej chwili próbuję dowiedzieć się, czy trampolina byłaby dla mnie wykonalna.

Jak rozumiem, jest to po prostu seria wywołań funkcji wykonywanych przez funkcję trampoliny. Każda funkcja nazywana jest thunk i zwraca następny krok w obliczeniach do momentu zakończenia programu (pusta kontynuacja).

Oto pierwszy fragment kodu, który napisałem, aby poprawić moje zrozumienie trampoliny:

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

prowadzi do:

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

Oto przykład funkcji zagnieżdżonych:

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

comparnie może być funkcją zewnętrzną, ponieważ używa nbytes, która istnieje tylko podczas sort_bytespołączenia. W przypadku niektórych architektur mała funkcja pośrednicząca - trampolina - jest generowana w czasie wykonywania i zawiera lokalizację stosu bieżącego wywołania sort_bytes. Po wywołaniu przeskakuje do comparkodu, przekazując ten adres.

Ten bałagan nie jest wymagany na architekturach takich jak PowerPC, gdzie ABI określa, że ​​wskaźnik funkcji jest w rzeczywistości „grubym wskaźnikiem”, strukturą zawierającą zarówno wskaźnik do kodu wykonywalnego, jak i inny wskaźnik do danych. Jednak na x86 wskaźnik funkcji jest tylko wskaźnikiem.

W przypadku C trampolina byłaby wskaźnikiem funkcji:

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

Edycja: bardziej ezoteryczne trampoliny byłyby domyślnie generowane przez kompilator. Jednym z takich zastosowań byłaby tabela skoków. (Chociaż są wyraźnie bardziej skomplikowane, im niżej zaczniesz próbować wygenerować skomplikowany kod).

Teraz, gdy C # ma funkcje lokalne , kata kodowania gry w kręgle można elegancko rozwiązać za pomocą trampoliny:

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

Metoda Game.RollManyjest wywoływana z liczbą rolek: zwykle 20 rolek, jeśli nie ma części zapasowych ani uderzeń.

Pierwsza linia natychmiast wywołuje funkcję trampoliny: return Trampoline(1, 0, rs.ToList());. Ta lokalna funkcja rekurencyjnie przechodzi przez tablicę rolek. Funkcja lokalna (trampolina) umożliwia rozpoczęcie przemierzania dwoma dodatkowymi wartościami: zacznij od frame1 i rsf(dotychczasowy wynik) 0.

W ramach funkcji lokalnej istnieje operator trójskładnikowy, który obsługuje pięć przypadków:

• Gra kończy się na klatce 11: zwróć dotychczasowy wynik
• Gra kończy się, jeśli nie ma więcej rzutów: zwróć dotychczasowy wynik
• Uderzenie: oblicz liczbę klatek i kontynuuj przemierzanie
• Zapasowe: oblicz liczbę klatek i kontynuuj przemierzanie
• Wynik normalny: oblicz liczbę klatek i kontynuuj przemierzanie

Kontynuowanie przemierzania odbywa się przez ponowne wywołanie trampoliny, ale teraz ze zaktualizowanymi wartościami.

Aby uzyskać więcej informacji, wyszukaj: „ akumulator rekurencji ogona ”. Pamiętaj, że kompilator nie optymalizuje rekurencji ogona. Tak eleganckie, jak może być to rozwiązanie, prawdopodobnie nie będzie to post.

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