Что такое функция батута?
Во время недавних обсуждений на работе кто-то ссылался на функцию батута.
Я прочитал описание в Wikipedia. Достаточно дать общее представление о функциональности, но мне хотелось бы что-то более конкретное.
У вас есть простой фрагмент кода, который иллюстрирует батут?
Ответы
Ответ 1
Существует также LISP смысл "батута", как описано в Википедии:
Используется в некоторых реализациях LISP, батут - это цикл, который итеративно вызывает функции возврата функции. одного батута достаточно для выражать все контрольные передачи программа; такая выраженная программа батут или в стиле "батут"; преобразование программы в батут стиль батут. Trampolined функции могут использоваться для реализации хвостовые рекурсивные вызовы функций Языки, ориентированные на стек
Предположим, мы используем Javascript и хотим написать наивную функцию Фибоначчи в стиле продолжения прохождения. Причина, по которой мы это сделаем, не имеет значения - например, для схемы портов для 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 инструкцию (thunk) вызвать эту функцию, которая будет интерпретироваться в цикле.
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]});
}
Ответ 2
Позвольте мне добавить несколько примеров факториальной функции, реализованной с батутами, на разных языках:
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 (несчастливая без реализации больших чисел):
#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, ¶ms};
trampoline(&t);
printf("\n%d\n", params.sum);
return 0;
}
Ответ 3
Я приведу вам пример, который я использовал в анти-чит-патче для онлайн-игры.
Мне нужно было проверить все файлы, которые были загружены игрой для модификации. Поэтому самым надежным способом, который я нашел для этого, было использование батута для CreateFileA. Поэтому, когда игра была запущена, я нашел бы адрес для CreateFileA с помощью GetProcAddress, затем я бы изменил первые несколько байтов функции и вставил код сборки, который бы переместился на мою собственную функцию "батут", где я бы сделал некоторые вещи и то я вернусь к следующему месту в CreateFile после моего кода jmp. Чтобы сделать это надежно, это немного сложнее, но базовая концепция - просто подключить одну функцию, заставить ее перенаправить на другую функцию, а затем вернуться к исходной функции.
Изменить: у Microsoft есть структура для такого типа вещей, на которую вы можете смотреть. Вызывается Detours
Ответ 4
Вот пример вложенных функций:
#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 указатель на функцию - это просто указатель.
Ответ 5
В настоящее время я экспериментирую с путями реализации оптимизации хвостового вызова для интерпретатора Схемы, и поэтому на данный момент я пытаюсь выяснить, может ли батут быть осуществимым для меня.
Как я понимаю, это всего лишь серия вызовов функций, выполняемых функцией батута. Каждая функция называется thunk и возвращает следующий шаг в вычислении до тех пор, пока программа не завершится (пустое продолжение).
Вот первый фрагмент кода, который я написал, чтобы улучшить мое понимание батута:
#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 !
Ответ 6
Для 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");
Изменить: более сложные эзотерические батуты будут неявно созданы компилятором. Одним из таких применений будет таблица перехода. (Хотя есть явно более сложные, тем дальше вы начинаете пытаться генерировать сложный код.)
Ответ 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();
}
// ...
