함수형 프로그래밍 - 트램폴린(Trampoline)

 트램폴린(Trampoline)

트램폴린이란?

보통의 재귀 함수는 꼬리 재귀 최적화로 스택 오버플로우를 방지할 수 있다.

하지만 각 함수가 서로를 참조하는 상호 재귀 함수는 꼬리 재귀 최적화가 불가능하다.

트램폴린은 함수의 지연 처리를 이용해 상호 재귀 함수에 꼬리 재귀 최적화를 적용시킬 수 있다.

thunk: () => Bounce[A] 는 함수를 바로 실행하지 않고 지연 처리시킨다.

trampoline(evenWithTrampoline(5)) 의 동작을 살펴보자.

n 이 5 → 4 → 3 → 2 → 1 → 0 이 되면 oddWithTrampoline(0) 에서 Done(false) 를 리턴한다.

그러면 다시 반대로

evenWithTrampoline(1) 에선 More(() ⇒ Done(false)) 를 리턴한다.
oddWithTrampoline(2) 에선 More(() ⇒ More(() ⇒ Done(false))) 를 리턴한다.

이렇게 More 이 중첩되서 쌓이고, n 개 중첩된 More 를 trampoline 에서 인자로 받게 된다.

trampoline(More(() ⇒ More(() ⇒ More(…))))

trampoline 함수는 꼬리 재귀 함수다.
More 인 경우 thunk 의 결과값을 인자로 넘기기 때문에(acc 값) 콜스택이 쌓이지 않는다.
결국 콜스택을 쌓지 않고 More 을 모두 깐 뒤, 최종 Done 의 값을 얻어올 수 있다.