Во время недавних обсуждений на работе кто-то упомянул функцию батута.
Я прочитал описание в Википедии . Достаточно дать общее представление о функционале, но хотелось бы более конкретного.
У вас есть простой фрагмент кода, иллюстрирующий батут?
Во время недавних обсуждений на работе кто-то упомянул функцию батута.
Я прочитал описание в Википедии . Достаточно дать общее представление о функционале, но хотелось бы более конкретного.
У вас есть простой фрагмент кода, иллюстрирующий батут?
Ответы:
Есть также смысл LISP «батут», описанный в Википедии:
Допустим, мы используем Javascript и хотим написать наивную функцию Фибоначчи в стиле продолжения. Причина, по которой мы бы это сделали, не имеет значения - например, для переноса Scheme на JS или для игры с CPS, который мы все равно должны использовать для вызова серверных функций.
Итак, первая попытка
function fibcps(n, c) { if (n <= 1) { c(n); } else { fibcps(n - 1, function (x) { fibcps(n - 2, function (y) { c(x + y) }) }); } }
Но запуск этого
n = 25
в Firefox дает ошибку «Слишком много рекурсии!». Теперь это как раз та проблема (отсутствие оптимизации хвостового вызова в Javascript), которую решает трамплин. Вместо того, чтобы делать (рекурсивный) вызов функции, позвольте намreturn
инструкцию (преобразователь) для вызова этой функции, которая будет интерпретироваться в цикле.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]}); }
источник
Позвольте мне добавить несколько примеров факториальной функции, реализованной с помощью батутов, на разных языках:
Скала:
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))) }
Ява:
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 (не повезло без реализации больших чисел):
#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, ¶ms}; trampoline(&t); printf("\n%d\n", params.product); return 0; }
источник
if (n < 2) Done(product)
, SO не разрешил мне редактировать 1 символ ...Приведу пример, который я использовал в античит-патче для онлайн-игры.
Мне нужно было иметь возможность сканировать все файлы, загружаемые игрой, на предмет модификации. Итак, самый надежный способ, который я нашел, - использовать батут для CreateFileA. Поэтому, когда игра запускалась, я находил адрес CreateFileA с помощью GetProcAddress, затем я изменял первые несколько байтов функции и вставлял ассемблерный код, который переходил бы к моей собственной функции «трамплина», где я делал бы кое-что, и тогда я бы вернулся к следующему месту в CreateFile после моего jmp-кода. Надежно сделать это немного сложнее, но основная концепция состоит в том, чтобы просто перехватить одну функцию, заставить ее перенаправить на другую функцию, а затем вернуться к исходной функции.
Изменить: у Microsoft есть структура для этого типа вещей, на которую вы можете взглянуть. Называется обход
источник
В настоящее время я экспериментирую со способами реализации оптимизации хвостового вызова для интерпретатора схемы, и поэтому в настоящий момент я пытаюсь выяснить, подойдет ли мне батут.
Насколько я понимаю, это в основном просто серия вызовов функций, выполняемых функцией трамплина. Каждая функция называется преобразователем и возвращает следующий шаг в вычислении, пока программа не завершится (пустое продолжение).
Вот первый фрагмент кода, который я написал для лучшего понимания батута:
#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); }
приводит к:
meincompi $ ./trampoline *boing* thunk 1 *boing* thunk 2 *boing* last thunk got off the trampoline - happy happy joy joy !
источник
Вот пример вложенных функций:
#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
не может быть внешней функцией, потому что она используетnbytes
, которая существует только во времяsort_bytes
вызова. На некоторых архитектурах небольшая функция-заглушка - трамплин - создается во время выполнения и содержит местоположение в стеке текущего вызоваsort_bytes
. При вызове он переходит кcompar
коду, передавая этот адрес.Такой беспорядок не требуется в архитектурах, подобных PowerPC, где ABI указывает, что указатель функции на самом деле является «жирным указателем», структурой, содержащей как указатель на исполняемый код, так и другой указатель на данные. Однако на x86 указатель на функцию - это просто указатель.
источник
Для C батут был бы указателем на функцию:
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");
Изменить: более эзотерические трамплины будут неявно генерироваться компилятором. Одним из таких применений может быть таблица переходов. (Хотя явно есть более сложные, чем дальше вы начинаете пытаться сгенерировать сложный код.)
источник
Теперь, когда C # имеет локальные функции , ката кодирования игры в боулинг можно элегантно решить с помощью батута:
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)); } }
Метод
Game.RollMany
вызывается с количеством бросков: обычно 20 бросков, если нет запасных частей или ударов.Первая строка сразу вызывает функцию батута:
return Trampoline(1, 0, rs.ToList());
. Эта локальная функция рекурсивно просматривает массив rolls. Локальная функция (батут) позволяет обходу начинать с двух дополнительных значений: начало сframe
1 иrsf
(пока результат) 0.Внутри локальной функции есть тернарный оператор, который обрабатывает пять случаев:
Чтобы продолжить обход, снова вызовите батут, но теперь с обновленными значениями.
Для получения дополнительной информации выполните поиск по запросу " аккумулятор хвостовой рекурсии ". Имейте в виду, что компилятор не оптимизирует хвостовую рекурсию. Каким бы элегантным ни было это решение, оно, скорее всего, не будет голодным.
источник
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(); } // ...
источник