Continuation is the abstraction of control context. It can transform a recursive function call into a tail-recursive call. Many concepts related to program control, like exception, multi-thread, also can be modeled using continuation.
Transform your code to a continuation-passing style can make your code take advantage of tail call. However, some languages (like java, python) do not do well in tail call optimization (they enlarge the stack even for the tail call). What can you do when we want to manually implement such a concept via those languages? The skill is called trampoline.
Several years ago I did not get the point of Section 5.2 of EOPL since I wrote in Erlang and Erlang does well in TCO. And I am surprised that some languages event do not have TCO.
So for those languages, even if you can transform the recursive code into CPS to have a tail call, how can you avoid unbound runtime stacks? To understand the skill here, we need first to understand why the stack grows. Invoke function (apply procedures) will transfer control and lead to stack growth. When it is to apply a procedure, stop, and wrap the procedure application into a thunk, and return the thunk (the thunk contains all the information to complete the job). Since we stop and return, the stack shrinks. We find it is a thunk, just invoke it to finish the computation.
Thus we introduce a trampolined procedure, it is a while loop or something that does not grow the stack, it invokes the code in CPS, if gets back a normal value, just return it; if gets back a thunk, invoke it. Using this skill we can have a bound runtime stack when computing recursive functions.
The above is what I suddenly understand when seeing trampoline recently. If you are interested in these kinds of topics, please refer to Dan Friedman’s great book or talk:
- Essentials of Programming Languages Third Edition
- The Role of the Study of Programming Languages in the Education of a Programmer
Or if you want to have a look at my implementation in Erlang: https://github.com/kainwen/eopl