Apa itu fungsi trampolin?

Selama diskusi baru-baru ini di tempat kerja, seseorang merujuk pada fungsi trampolin.

Saya telah membaca deskripsinya di Wikipedia . Ini cukup untuk memberikan gambaran umum tentang fungsinya, tetapi saya ingin sesuatu yang sedikit lebih konkret.

Apakah Anda memiliki potongan kode sederhana yang akan menggambarkan trampolin?

Ada juga pengertian LISP dari 'trampolin' seperti yang dijelaskan di Wikipedia:

Digunakan dalam beberapa implementasi LISP, trampolin adalah loop yang secara berulang memanggil fungsi penghasil thunk. Sebuah trampolin tunggal cukup untuk mengekspresikan semua transfer kendali suatu program; sebuah program yang diekspresikan dengan cara diinjak-injak atau dalam "gaya trampolin"; mengubah program menjadi gaya trampolin adalah trampolin. Fungsi trampolin dapat digunakan untuk mengimplementasikan panggilan fungsi rekursif ekor dalam bahasa berorientasi stack

Misalkan kita menggunakan Javascript dan ingin menulis fungsi Fibonacci yang naif dalam gaya penerusan-lanjutan. Alasan kami melakukan ini tidak relevan - untuk mem-port Scheme ke JS misalnya, atau untuk bermain dengan CPS yang tetap harus kami gunakan untuk memanggil fungsi sisi server.

Jadi, upaya pertama adalah

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

Tapi, menjalankan ini dengan n = 25di Firefox memberikan kesalahan 'Rekursi terlalu banyak!'. Sekarang inilah sebenarnya masalah (tidak adanya optimasi panggilan-ekor dalam Javascript) yang dipecahkan oleh trampolin. Alih-alih membuat panggilan (rekursif) ke suatu fungsi, mari kita returngunakan instruksi (thunk) untuk memanggil fungsi itu, untuk diinterpretasikan dalam satu putaran.

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

Izinkan saya menambahkan beberapa contoh untuk fungsi faktorial yang diimplementasikan dengan trampolin, dalam berbagai bahasa:

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 (sial tanpa implementasi angka besar):

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

Saya akan memberi Anda contoh yang saya gunakan dalam patch anti-cheat untuk game online.

Saya harus bisa memindai semua file yang sedang dimuat oleh game untuk modifikasi. Jadi cara paling kuat yang saya temukan untuk melakukan ini adalah dengan menggunakan trampolin untuk CreateFileA. Jadi, ketika game diluncurkan, saya akan menemukan alamat untuk CreateFileA menggunakan GetProcAddress, lalu saya akan memodifikasi beberapa byte pertama dari fungsi tersebut dan menyisipkan kode assembly yang akan melompat ke fungsi "trampolin" saya sendiri, di mana saya akan melakukan beberapa hal, dan kemudian saya akan melompat kembali ke lokasi berikutnya di CreateFile setelah kode jmp saya. Untuk dapat melakukannya dengan andal sedikit lebih rumit dari itu, tetapi konsep dasarnya adalah hanya mengaitkan satu fungsi, memaksanya untuk mengalihkan ke fungsi lain, lalu melompat kembali ke fungsi aslinya.

Sunting: Microsoft memiliki kerangka kerja untuk hal semacam ini yang dapat Anda lihat. Disebut Memutar

Saat ini saya sedang bereksperimen dengan cara menerapkan pengoptimalan panggilan ekor untuk juru bahasa Skema, dan saat ini saya mencoba mencari tahu apakah trampolin akan layak untuk saya.

Seperti yang saya pahami, ini pada dasarnya hanyalah serangkaian panggilan fungsi yang dilakukan oleh fungsi trampolin. Setiap fungsi disebut thunk dan mengembalikan langkah berikutnya dalam komputasi hingga program berakhir (kelanjutan kosong).

Berikut adalah potongan kode pertama yang saya tulis untuk meningkatkan pemahaman saya tentang trampolin:

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

menghasilkan:

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

Berikut adalah contoh fungsi bertingkat:

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

compartidak bisa menjadi fungsi eksternal, karena menggunakan nbytes, yang hanya ada selama sort_bytespanggilan. Pada beberapa arsitektur, fungsi rintisan kecil - trampolin - dibuat pada waktu proses, dan berisi lokasi tumpukan pemanggilan saat inisort_bytes . Saat dipanggil, ia melompat ke comparkode, meneruskan alamat itu.

Kekacauan ini tidak diperlukan pada arsitektur seperti PowerPC, di mana ABI menentukan bahwa penunjuk fungsi sebenarnya adalah "penunjuk lemak", struktur yang berisi penunjuk ke kode yang dapat dieksekusi dan penunjuk lain ke data. Namun, pada x86, penunjuk fungsi hanyalah penunjuk.

Untuk C, trampolin akan menjadi penunjuk fungsi:

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

Sunting: Lebih banyak trampolin esoterik akan secara implisit dihasilkan oleh kompilator. Salah satu kegunaannya adalah meja lompat. (Meskipun ada yang jelas lebih rumit, semakin jauh Anda mulai mencoba membuat kode yang rumit.)

Sekarang C # memiliki Fungsi Lokal , pengkodean kata Game Bowling dapat diselesaikan dengan elegan dengan trampolin:

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

Metode Game.RollManyini disebut dengan sejumlah gulungan: biasanya 20 gulungan jika tidak ada suku cadang atau pukulan.

Baris pertama segera memanggil fungsi trampolin: return Trampoline(1, 0, rs.ToList());. Fungsi lokal ini secara rekursif melintasi larik gulungan. Fungsi lokal (trampolin) memungkinkan traversal untuk memulai dengan dua nilai tambahan: mulai dengan frame1 dan rsf(hasil sejauh ini) 0.

Di dalam fungsi lokal ada operator terner yang menangani lima kasus:

• Pertandingan berakhir di frame 11: sejauh ini kembalikan hasil
• Permainan berakhir jika tidak ada lagi lemparan: kembalikan hasil sejauh ini
• Strike: hitung skor frame dan lanjutkan traversal
• Cadangan: hitung skor bingkai dan lanjutkan traversal
• Skor normal: hitung skor frame dan lanjutkan traversal

Melanjutkan traversal dilakukan dengan memanggil trampolin lagi, tetapi sekarang dengan nilai yang diperbarui.

Untuk informasi lebih lanjut, cari: " tail rekursi akumulator ". Perlu diingat bahwa compiler tidak mengoptimalkan rekursi tail. Jadi, seindah solusi ini, kemungkinan besar tidak akan berpuasa.

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