continuations and trampolining

In the process of working on the mechanics of my pet language design something just occurred to me: is "trampolining" as is normally done for tail-recursion, etc., just a poor-man's version of calling continuations?

Just a thought.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

for implementing in languages without TCO

jimdesu: "trampolining" [...] just a poor-man's version of calling continuations?

It's a way to implement a language with TCO (tail call optimization) in a language (like C) normally without TCO. By trampolining you can unwind the part of the C stack before going further, so you don't get the continuations of your own language snarled with the C stack wrapped around it like a maypole. I think this is a long way of saying yes to your question.

I hope other folks want to talk about this a lot, because it's something I never get to hear enough about when folks talk about their implementations. You want to use trampolining to get "stackless" versions for languages (like stackless Python), where the stack you've removed (to get less stack) is the C stack and not the call stack in the language you're implementing, which is the continuation you want saved as a first class value.

continuations and trampolines: Program transformations

It is about much more than that. It is about program transformations.

Programs with trampolines is a step when doing program transformations using continuation-passing-style (CPS). In particular it is used in some compilers/interpreters.

You may want to look into the writings of Daniel Friedman and Olivier Danvy.

For a ligth read, The Role of the Study of Programming Languages in the Education by Daniel Friedman contains a good example to put things in perspective:

If that paper catches your interest, you want to read Olivier Danvy's D.Sc. dissertation, An Analytical Approach to Programs as Data Objects, which you can find on http://www.daimi.au.dk/~danvy/DSc/ with many other papers of interest (see also http://www.daimi.au.dk/~danvy/DSc.html)

In particular, see http://www.daimi.au.dk/~danvy/ for more papers of interest in the same area.

It really is fascinating and exciting!

Read Friedman's paper first and go from there.

Update: I said earlier that Olivier Danvy was a
student of Daniel Friedman! He was not! Mea culpa!
See genealogy.

Broken Link

When I click on your link to Daniel Friedman's paper, I get a 403 Forbidden. ("You don't have permission to access /~dfried/dfried/mex.ps on this server.")

Edit: The link is indeed not broken (see below). There was a temporary problem, now fixed. -- Ehud

Broken link?

I am sorry for your inconvenience, but it is unbroken for me, so
I cannot help you!

I forgot to check the archives. The paper is already mentioned in
the LtU Classic Archives

By the way, there is also a version in PDF (s/ps$/pdf/) in the same place.
Daniel Friedman also gave a talk with the same title (at UNAM).

Reading the program as data objects paper...

I'm wondering about the different ways that programming languages have tried mixing CPS and direct styles.

I'm thinking that an alternative to something like call/cc would be just a way of defining a function that knows its continuation.

so something like (lambdacps (params, continuation) ...program) and then a special form to call a function providing a different continuation (call-with-continuation fun args continuation) . I'd think that it would be helpful to be able to pass in parameters at the same time as capturing a continuation?

Wouldn't something like this let the compiler do things more intelligently in a situation like:

(lambdacps (params, continuation)
(if (...) (continuation 0)
(~something more complicated~)))

?

(call-with-continuation fun

(call-with-continuation fun args continuation)

Wouldn't that just be the same as (continuation (fun args)) ?

And
(lambdacps (params, continuation)
(if (...) (continuation 0)
(~something more complicated~)))

would just be the same as

(lambda (params)
(if (...) 0
(~something more complicated~)))

or more generally, the extra continuation argument would just work as the return statment in languages like C (except perhaps that it could be captured as closure). And while that might be nice and all, its nowhere near as powerfull as call/cc.

hmm...

thanks, didn't quite figure that first part out, guess that would be useless.

my other example was pretty useless too I guess, I was thinking something more like this:

(lambdacps (params, continuation)
(cond ((...) (continuation 0))
((...) (~abort computation~))
((...) ~save continuation somewhere~ (~call a continuation passed in by params~) )
((...) ~save continuation somewhere~ (~call a different continuation passed in by params~) )
((...) (~call another continuation passed in by params~))
)

So instead of you having to put in the call/ccs in just the places that you need it, the compiler should be able to figure out what's happening.

Another thing is that if lambdacps is primitive then:

(define call/cc (lambdacps (function continuation)
(function continuation)))

With call/cc, you can do:

With call/cc, you can do:

(lambda (params) (call/cc (lambda (cont) ~function body~)))

Is that different than what you want?

It's the same thing

Mainly, I don't like the idea that call/cc "does" something, the continuation is already there in some sense, whether it needs to be converted into a first class value (terminology probably wrong) depends on how I use it.

So in my example, if I define it that way, a call/cc has to happen every time I call the function, even if all I'm doing is just a simple return, because I decide whether or not to do a simple return in the function. If I want to optimize it, I have to go through and push the call/ccs down to the right branches.

Though it's probably the case that it's really not that practical, it just seems like a nicer way to do things (though I'm not even a scheme novice, so I really don't know).

Well, either way I think I understand a little more about how call/cc is used now that I went through this whole thing, thanks for that definition, seems like you'd be able to macro it for something to play around with...

Continuation returning style

is "trampolining" as is normally done for tail-recursion, etc., just a poor-man's version of calling continuations?

I'd say not exactly (depending on what the question means), but trampolining does involve calling continuations, which are necessarily represented more explicitly than they would otherwise need to be. In a trampoline implementation, you have to package up the next evaluation step in such a way that it can be returned to the trampoline loop, where it will be dispatched. That packaged-up evaluation step is thus the continuation of your interpreter loop, and dispatching it is equivalent to calling that continuation. (Trampolining can be thought of as "continuation returning style", but that's not standard terminology.)

Depending on your implementation, this "continuation" may still be more of an implicit entity rather than a single, first-class value. For example, if you're maintaining a global call stack for the target language (i.e. for the language being implemented), then the state of that stack is implicitly part of the continuation (so you have a "poor man's", or partially implicit, continuation). In that case, if you want to do something with the continuation other than immediately apply it, you may need to take a copy of the call stack. So, for example, the ability to support first-class continuations in the target language doesn't automatically follow from having implemented a trampoline; it requires a suitable explicit representation for continuations, as well as support in the interpreter for dealing with them.

Continuations in JavaScript

If you are interested, I gave a talk about continuations in JavaScript at the recent Ajax experience conference, and included some material about TCO and trampolining. Here is the presentation if you want to look at it:
http://www.xucia.com/page/Continuations