6
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Petr Pudlák Jul 3 '13 at 7:13
12
$\begingroup$

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.

  1. 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.

  2. 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.

  3. 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.

$\endgroup$
  • 2
    $\begingroup$ 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! $\endgroup$ – Dave Clarke Jul 3 '13 at 10:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.