<blockquote>
  <p>Is it possible to make a "smart" trampoline function that takes two forms of a function, a trampolined version and a non-trampolined version, and chooses (or predicts) the most efficient strategy?* </p>
</blockquote>

<p>Yes, it's possible to do things like this, but if you control the compiler, it's usually faster and easier to do something else. The main exception is when you are writing parallel code. </p>

<p>Trampolining style essentially does two things. </p>

<ol>
<li><p>First, you do a continuation-passing-style transformation to make the continuation explicit as a data structure. However, if you directly represent continuations as functions, the standard calling conventions mean that you will blow the stack. This is because programs in CPS never directly return -- they always pass control to their continuation. </p></li>
<li><p>So instead of representing continuations as functions, you represent continuations as <em>resumptions</em>. A resumption is a data structure representing a computation, which lets you evaluate a bit at a time until it is finished. That is, resumptions may be seen as a datatype declaration such as:</p>

<pre><code>type 'a resumption = Done of 'a | Wait of (unit -&gt; 'a resumption)
</code></pre>

<p>So a value of type <code>t resumption</code> is either a value <code>Done v</code> containing a value <code>v</code> of type <code>t</code>, representing a finished computation, or it is a value <code>Wait thunk</code>, where <code>thunk</code> is a function that will do some work and hand you back a new resumption representing a bit more progress towards the answer. </p></li>
<li><p>Once you represent continuations as resumptions, you can write a <em>scheduler</em> which runs in a while-loop, and incrementally forces the resumption. Since the scheduler runs in a loop, it won't automatically blow the stack. I call this loop a <em>scheduler</em> because precisely the same approach of using resumptions is used in implementations of green/lightweight threads. </p></li>
</ol>

<p>Implementing resumptions naively is slow, because the continuations in most programming languages are used in highly stylized ways. That is, in most languages you can implement continuations as a single imperatively-updated stack, and the overhead of trampolining simply arises from the fact that a linked list of thunks is a less efficient representation than a mutable stack. So compiler writers often use resumption-based intermediate forms, but implement them using better data structures. (And as a programmer, you can often use an optimized continuation representation "by hand".) </p>

<p>Papers you might want to look at:</p>

<ul>
<li><p>Ganz, Friedman and Wand's 1999 ICFP paper, <a href="http://www.cs.indiana.edu/~dfried/ts.ps" rel="nofollow"><em>Trampolined Style</em></a></p>

<p>This is probably the best survey paper on trampolining and how it works. </p></li>
<li><p>Wand's 1980 JACM paper, <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.83.8567&amp;rep=rep1&amp;type=pdf" rel="nofollow"><em>Continuation-Based Program Transformation Strategies</em></a></p>

<p>This is one of the fundamental papers on using custom data structures to represent continuations, and how it can make algorithms radically more efficient. The notation is kind of old-fashioned and clunky, but once you get past that, it's extremely accessible and mind-blowing. Highly recommended! </p></li>
<li><p>Hieb, Dybvig and Bruggeman's 1990 PLDI paper, <a href="http://www.cs.indiana.edu/~dyb/pubs/stack.pdf" rel="nofollow"><em>Representing Control in the Presence of First-Class Continuations</em></a></p>

<p>This paper gives a nice example of just how far compiler writers will go to implement continuations efficiently. </p></li>
<li><p>Appel's 1993 book, <a href="http://rads.stackoverflow.com/amzn/click/052103311X" rel="nofollow"><em>Compiling with Continuations</em></a> </p>

<p>EDIT: This is <em>not</em> out of print, and if you can afford it, it's a book-length explanation. </p></li>
<li><p>Abramsky's CONCUR 1996 paper, <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.46.7024" rel="nofollow"><em>Retracing Some Paths in Process Algebra</em></a></p>

<p>This paper gives a theoretical introduction to the application of resumptions to concurrency. </p></li>
<li><p>Acar, Charguéraud, and Rainey's 2011 OOPSLA paper, <a href="http://www.mpi-sws.org/~mrainey/oracle_scheduling.pdf" rel="nofollow"><em>Oracle scheduling: controlling granularity in implicitly parallel languages</em></a></p>

<p>This paper implements your suggestion of using two versions of the same function, in the context of parallelizing divide-and-conquer algorithms. Basically, the idea is that the optimal point to switch from spawning new tasks for subproblems to doing it sequentially depends a lot on details like the amount of parallelism in your hardware, the cost of thread spawning, and how much work each recursive call will do. So if you write a function to the scheduler can use to estimate how much work is left, it can automatically choose the best point to switch. </p></li>
</ul>

CC BY-SA 3.0
2013-07-03T10:57:40.653Z
_Compiling with Continuations_ is not out of print, at least according to Amazon.co.uk. BTW: Congrats on B'ham gig. Strong group to join!
Dave Clarke
CC BY-SA 3.0
2013-07-03T10:34:31.017Z
2013-07-04T15:13:59.787Z
2013-07-04T15:13:59.787Z
Neel Krishnaswami
<p>While working through Fogus' Functional Javascript, I came across the trampoline function, which can be used to make safe recursive functions that don't blow up the stack. In Fogus' words, "Of course there is no free lunch, even when using trampolines. While I’ve managed to avoid exploding the call stack, I’ve just transferred the problem to the heap."</p>

<p>On top of moving this problem to the heap, the trampolined version of the function is slower. </p>

<p>Is it possible to make a "smart" trampoline function that takes two forms of a function, a trampolined version and a non-trampolined version, and chooses (or predicts) the most efficient strategy?* </p>

<p>Ref: <a href="https://github.com/funjs/book-source/blob/master/chapter06.js#L195">https://github.com/funjs/book-source/blob/master/chapter06.js#L195</a></p>

<p>*(or better yet combines both strategies (is this possible?) that uses fewer trampoline "bounces", where each bounce is almost the maximum number of computations that can be performed recursively using the stack strategy)</p>

CC BY-SA 3.0
2013-07-03T07:13:29.363Z
I'd say you can't predict the depth of recursive calls - this would solve the halting problem. So the only chance is to measure the nesting level during computations and switch to the heap version, if necessary.
Petr
<functional-programming><recursion>
Trampoline that automatically balances heap and stack
Andrew De Andrade
# Trampoline that automatically balances heap and stack

(Asked by: username_0 on 2013-07-03)

While working through Fogus' Functional Javascript, I came across the trampoline function, which can be used to make safe recursive functions that don't blow up the stack. In Fogus' words, "Of course there is no free lunch, even when using trampolines. While I’ve managed to avoid exploding the call stack, I’ve just transferred the problem to the heap."

On top of moving this problem to the heap, the trampolined version of the function is slower.

Is it possible to make a "smart" trampoline function that takes two forms of a function, a trampolined version and a non-trampolined version, and chooses (or predicts) the most efficient strategy?\*

Ref: <https://github.com/funjs/book-source/blob/master/chapter06.js#L195>

\*(or better yet combines both strategies (is this possible?) that uses fewer trampoline "bounces", where each bounce is almost the maximum number of computations that can be performed recursively using the stack strategy)

**Tags:** functional-programming, recursion

> **Comments:**
> **username_1**: I'd say you can't predict the depth of recursive calls - this would solve the halting problem. So the only chance is to measure the nesting level during computations and switch to the heap version, if necessary.  

---

## 1 answers

### Answer by username_2 on 2013-07-03. Score: 12

Is it possible to make a "smart" trampoline function that takes two forms of a function, a trampolined version and a non-trampolined version, and chooses (or predicts) the most efficient strategy?* 

Yes, it's possible to do things like this, but if you control the compiler, it's usually faster and easier to do something else. The main exception is when you are writing parallel code. 
Trampolining style essentially does two things. 

First, you do a continuation-passing-style transformation to make the continuation explicit as a data structure. However, if you directly represent continuations as functions, the standard calling conventions mean that you will blow the stack. This is because programs in CPS never directly return -- they always pass control to their continuation. 
So instead of representing continuations as functions, you represent continuations as resumptions. A resumption is a data structure representing a computation, which lets you evaluate a bit at a time until it is finished. That is, resumptions may be seen as a datatype declaration such as:
type 'a resumption = Done of 'a | Wait of (unit -> 'a resumption)

So a value of type t resumption is either a value Done v containing a value v of type t, representing a finished computation, or it is a value Wait thunk, where thunk is a function that will do some work and hand you back a new resumption representing a bit more progress towards the answer. 
Once you represent continuations as resumptions, you can write a scheduler which runs in a while-loop, and incrementally forces the resumption. Since the scheduler runs in a loop, it won't automatically blow the stack. I call this loop a scheduler because precisely the same approach of using resumptions is used in implementations of green/lightweight threads. 

Implementing resumptions naively is slow, because the continuations in most programming languages are used in highly stylized ways. That is, in most languages you can implement continuations as a single imperatively-updated stack, and the overhead of trampolining simply arises from the fact that a linked list of thunks is a less efficient representation than a mutable stack. So compiler writers often use resumption-based intermediate forms, but implement them using better data structures. (And as a programmer, you can often use an optimized continuation representation "by hand".) 
Papers you might want to look at:

Ganz, Friedman and Wand's 1999 ICFP paper, Trampolined Style
This is probably the best survey paper on trampolining and how it works. 
Wand's 1980 JACM paper, Continuation-Based Program Transformation Strategies
This is one of the fundamental papers on using custom data structures to represent continuations, and how it can make algorithms radically more efficient. The notation is kind of old-fashioned and clunky, but once you get past that, it's extremely accessible and mind-blowing. Highly recommended! 
Hieb, Dybvig and Bruggeman's 1990 PLDI paper, Representing Control in the Presence of First-Class Continuations
This paper gives a nice example of just how far compiler writers will go to implement continuations efficiently. 
Appel's 1993 book, Compiling with Continuations 
EDIT: This is not out of print, and if you can afford it, it's a book-length explanation. 
Abramsky's CONCUR 1996 paper, Retracing Some Paths in Process Algebra
This paper gives a theoretical introduction to the application of resumptions to concurrency. 
Acar, Charguéraud, and Rainey's 2011 OOPSLA paper, Oracle scheduling: controlling granularity in implicitly parallel languages
This paper implements your suggestion of using two versions of the same function, in the context of parallelizing divide-and-conquer algorithms. Basically, the idea is that the optimal point to switch from spawning new tasks for subproblems to doing it sequentially depends a lot on details like the amount of parallelism in your hardware, the cost of thread spawning, and how much work each recursive call will do. So if you write a function to the scheduler can use to estimate how much work is left, it can automatically choose the best point to switch.

> **Comments:**
> **username_3**: _Compiling with Continuations_ is not out of print, at least according to Amazon.co.uk. BTW: Congrats on B'ham gig. Strong group to join!  

---

