RE: A plea for a new old language

["Bayley, Alistair" <address@hidden>]

> You can fake tail calls as well, using a method known as trampolining.

I'm not sure what trampolining is (but I can guess), so I googled and come
across this explanation:

( from http://www.cs.indiana.edu/classes/c311-hils/exams/exam3-prac-ans.html
)

"In our interpreters, trampolining involves intercepting the application of
a continuation so that instead of directly applying the continuation, it
builds a thunk of the application and returns it. Then some driver loop can
apply the continuation. It shows that all programs can be expressed with a
single loop. It both allows us to express what happens when we may have more
than one of these thunks lying around (concurrency), and it allows us to
guarantee there will be no stack growth, even in languages that don't
optimize tail calls."


It sounds to me like the following technique, described well in
http://research.microsoft.com/users/simonpj/papers/spineless-tagless-gmachin
e.ps.gz (page 43, section 6.2.2), and quoted here (they're describing a
Haskell compiler targeting C):

"Each parameterless function, representing a code block, returns the code
pointer to which it would like to jump, rather than calling it. The
execution of the entire program is controlled by the following one-line
"interpreter":

	while (1) { cont = (*cont)(); }

That is, cont is the address of the code block (that is, C function) to be
executed next)."


Apparently this was first used in Steele's Rabbit compiler for Scheme, and
he called it the "UUO handler".


Is this trampolining, or am I wide of the mark?


-----Original Message-----
From: Michael Vanier [mailto:mvanier@cs.caltech.edu]
Sent: 12 May 2003 05:22
To: steven_shaw@iprimus.com.au
Cc: ll1-discuss@ai.mit.edu
Subject: Re: A plea for a new old language



You can fake tail calls as well, using a method known as trampolining.

Mike

> From: "Steven Shaw" <steven_shaw@iprimus.com.au>
> Date: Mon, 12 May 2003 12:49:29 +1000
> 
> > After talking to one of my compiler-guru friends, I found out that,
> > amazingly enough, you *can* do CPS in C, even without first-class
> > functions.  You have to lift the internal lambda expressions to the top
> > level and name them, and have an extra argument representing the state
> > captured by the lambda, yadda yadda, but it's doable.  I guess Real
> > Programmers can write scheme in any language ;-)
> 
> It wouldn't be efficient without tail call optimisation though, would it?
> 


*****************************************************************
The information in this email and in any attachments is 
confidential and intended solely for the attention and use 
of the named addressee(s). This information may be 
subject to legal professional or other privilege or may 
otherwise be protected by work product immunity or other 
legal rules.  It must not be disclosed to any person without 
our authority.

If you are not the intended recipient, or a person 
responsible for delivering it to the intended recipient, you 
are not authorised to and must not disclose, copy, 
distribute, or retain this message or any part of it.
*****************************************************************