트램폴린 기능은 무엇입니까?

트램폴린 기능은 무엇입니까?

---

최근 직장에서 토론하는 동안 누군가는 트램폴린 기능을 언급했습니다.

Wikipedia 에서 설명을 읽었습니다 . 기능에 대한 일반적인 아이디어를 제공하는 것으로 충분하지만 좀 더 구체적인 것을 원합니다.

트램폴린을 설명하는 간단한 코드 스 니펫이 있습니까?

---

Wikipedia에 설명 된대로 '트램폴린'의 LISP 감각도 있습니다.

일부 LISP 구현에서 사용되는 트램폴린은 썽크 반환 함수를 반복적으로 호출하는 루프입니다. 하나의 트램폴린으로 프로그램의 모든 제어 이전을 표현하기에 충분합니다. 이렇게 표현 된 프로그램은 트램폴린 또는 "트램폴린 스타일"입니다. 프로그램을 trampolined 스타일로 변환하는 것은 trampolining입니다. Trampolined 함수는 스택 지향 언어에서 꼬리 재귀 함수 호출을 구현하는 데 사용할 수 있습니다.

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 = 25Firefox 에서 이것을 실행하면 '너무 많은 재귀!'라는 오류가 발생합니다. 이제 이것은 트램폴린이 해결하는 문제 (자바 스크립트에서 꼬리 호출 최적화 누락)입니다. 함수를 (재귀 적) 호출하는 대신 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]});
}

---

여러 언어로 트램폴린으로 구현 된 팩토리얼 함수에 대한 몇 가지 예를 추가하겠습니다.

스칼라 :

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, &params};

  trampoline(&t);
  printf("\n%d\n", params.product);

  return 0;
}

---

온라인 게임의 치트 방지 패치에서 사용한 예를 들어 보겠습니다.

I needed to be able to scan all files that were being loaded by the game for modification. So the most robust way I found to do this was to use a trampoline for CreateFileA. So when the game was launched I would find the address for CreateFileA using GetProcAddress, then I would modify the first few bytes of the function and insert assembly code that would jump to my own "trampoline" function, where I would do some things, and then I would jump back to the next location in CreateFile after my jmp code. To be able to do it reliably is a little trickier than that, but the basic concept is just to hook one function, force it to redirect to another function, and then jump back to the original function.

Edit: Microsoft has a framework for this type of thing that you can look at. Called Detours

---

Here's an example of nested functions:

#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 can't be an external function, because it uses nbytes, which only exists during the sort_bytes call. On some architectures, a small stub function -- the trampoline -- is generated at runtime, and contains the stack location of the current invocation of sort_bytes. When called, it jumps to the compar code, passing that address.

This mess isn't required on architectures like PowerPC, where the ABI specifies that a function pointer is actually a "fat pointer", a structure containing both a pointer to the executable code and another pointer to data. However, on x86, a function pointer is just a pointer.

---

I am currently experimenting with ways to implement tail call optimization for a Scheme interpreter, and so at the moment I am trying to figure out whether the trampoline would be feasible for me.

As I understand it, it is basically just a series of function calls performed by a trampoline function. Each function is called a thunk and returns the next step in the computation until the program terminates (empty continuation).

Here is the first piece of code that I wrote to improve my understanding of the trampoline:

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

results in:

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

---

For C, a trampoline would be a function pointer:

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

Edit: More esoteric trampolines would be implicitly generated by the compiler. One such use would be a jump table. (Although there are clearly more complicated ones the farther down you start attempting to generate complicated code.)

---

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

참고URL : https://stackoverflow.com/questions/189725/what-is-a-trampoline-function