트램펄린 함수가 뭐죠?

트램펄린 함수가 뭐죠?

최근 직장에서의 논의에서 트램펄린 함수에 대한 언급이 있었습니다.

나는 위키피디아에서 그 설명을 읽었다.대략적인 기능에 대해서는 알 수 있습니다만, 조금 더 구체적인 것을 원합니다.

트램폴린을 설명할 수 있는 간단한 코드 조각이 있나요?

Wikipedia에서 설명한 바와 같이 '트램폴린'에 대한 LISP의 의미도 있습니다.

일부 LISP 구현에서 사용되는 트램펄린은 thunk-return 함수를 반복적으로 호출하는 루프입니다.하나의 트램펄린으로 프로그램의 모든 제어 전달을 표현하기에 충분합니다; 그렇게 표현된 프로그램은 트램펄린 또는 "트램펄린 스타일"로 표현됩니다; 프로그램을 트램펄린 스타일로 변환하는 것은 트램펄린 스타일입니다.trampoline 함수를 사용하여 스택 지향 언어로 테일 재귀 함수 호출을 구현할 수 있습니다.

예를 들어 Javascript를 사용하고 있으며 순진한 Fibonacci 함수를 continuation-passing 스타일로 쓰고 싶다고 합시다.이것을 실시하는 이유는, 예를 들면, 스킴을 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파이어폭스 "Too much recursion!" (너무 많은 재귀!)이것이 바로 트램펄라이닝이 해결하는 문제(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, &params};

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

  return 0;
}

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

수정하기 위해 게임에서 로드하는 모든 파일을 스캔할 수 있어야 했습니다.가장 확실한 방법은 Create FileA에 트램펄린을 사용하는 것이었습니다.게임이 시작되면 GetProcAddress를 사용하여 CreateFileA의 주소를 찾은 후 함수의 처음 몇 바이트를 수정하고 어셈블리 코드를 삽입하여 자신의 "트램폴린" 함수로 점프한 후 jmp 코드 뒤에 CreateFile의 다음 위치로 점프합니다.신뢰성 있게 실행할 수 있는 것은 그것보다 조금 더 까다롭지만, 기본적인 개념은 한 기능을 후크하여 다른 기능으로 강제로 리다이렉트한 후 원래 기능으로 되돌리는 것입니다.

편집: Microsoft 에는, 이러한 종류의 정보를 참조할 수 있는 프레임워크가 있습니다.착신 우회

저는 현재 Scheme 인터프리터의 테일콜 최적화를 실시하는 방법을 실험하고 있기 때문에 현재 트램펄린이 실현 가능한지 여부를 검토하고 있습니다.

기본적으로는 트램펄린 함수에 의해 실행되는 일련의 함수 호출인 것으로 알고 있습니다.각 함수는 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 !

다음은 중첩된 함수의 예입니다.

#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일부 아키텍처에서는 trampoline이라는 작은 stub 함수가 런타임에 생성되며 현재 호출의 스택 위치를 포함합니다.sort_bytes '...'로합니다.compar아, 아, 아, 아, 아, 아.

ABI가 함수 포인터가 실제로 실행 가능한 코드에 대한 포인터와 데이터에 대한 포인터를 모두 포함하는 구조인 "팻 포인터"라고 지정하는 PowerPC와 같은 아키텍처에서는 이 혼란이 필요하지 않습니다.그러나 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());이 로컬 함수는 롤 배열을 재귀적으로 통과합니다. 함수 2개의할 수 은 '트램펄린'(trampoline)으로 시작합니다.frame과 1의 1rsf) (0.

로컬 함수에는 5가지 경우를 처리하는 3진 연산자가 있습니다.

• 프레임 11에서 게임 종료: 지금까지의 결과를 반환합니다.
• 더 이상 롤이 없으면 게임 종료: 지금까지의 결과를 반환합니다.
• Strike: 프레임 점수를 계산하고 횡단을 계속합니다.
• 스페어: 프레임 스코어를 계산하고 통과를 계속합니다.
• 정상 점수: 프레임 점수를 계산하고 횡단을 계속합니다.

트래버설을 계속하려면 트램펄린을 다시 호출해야 하지만 업데이트된 값을 사용합니다.

자세한 내용은 "테일 재귀 누적기"를 검색하십시오.컴파일러는 테일 재귀를 최적화하지 않습니다.따라서 이 솔루션은 우아하지만 빠른 솔루션이 아닐 수 있습니다.

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