Hi Colin,

Colin Putney wrote:
> Lex suggested that the stack could be constructed such that the
> invocation of #someMessage constructs an activation context whose sender
> slot points directly to the context for #entryPoint. We'd then have a
> tree rather than a stack, and barring a reference escaping via
> thisContext, the context for #doSomething is now garbage. Returning from
> #someMessage to #entryPoint will now take one bytecode instead of two.

That'd be ideal. (I still see it as a stack - just not a dense
representation!) I've looked at the VM before to see if it would be
difficult to introduce tail-call frame elision at that level, and it
was. I'm sorry to say I haven't got a patch to submit :-(

I'd like the compiler to be able to choose which send variant to use:
there'd be a new bytecode "tailsend" that combined both a "send" and an
implicit following "return". That way, existing code continues to have
the same behaviour it's always had, but new code can be built using
proper tail calls.

This gives the first half of the story: reclaiming garbage that is
otherwise unreclaimable. The other half involves building a
continuation-mark-like system to beef up the reflection side of things
again.

> This is where I get confused. Above you're talking about how frames can
> be elided because (barring reflection) that elision can have no effect
> on the semantics of the program. Now you're suggesting that elision of
> frames *does* have an effect on semantics, because it allows a new class
> of programs that wouldn't otherwise be possible to express.

I've chosen my words poorly. I meant "... not possible to express
without triggering a bug in the GC."

As Lex pointed out, I'm free to use recursion in any way I like in
Squeak already. The lack of tail-call frame elision can be seen then as
a bug in Squeak's *garbage collector*: I can write valid code in such a
way that garbage frames are generated but never reclaimed.

This is one of those hairy cases where the metalevel environment
impinges on the objectlevel environment by signalling out-of-memory
conditions to the interpreted program.

In a "perfect computer" (infinite memory), tail-call frame elision makes
no difference at all to the observable properties of the program. Once
we simulate a perfect computer in an imperfect (finite) one, we rely on
the GC to reclaim unused space, and so if we allocate and retain memory
excessively, either stack frames via recursion or regular heap objects,
the problems of representing the ideal computer in a finite environment
start to encroach upon our semantics...

Another choice (a poor one, IMO) would be to not let the objectlevel
program know it was running in emulation. Then, on an out-of-memory
condition, execution would be paused and the runtime would have to reach
*outward*, rather than inward, to receive instructions on how to
proceed. From the objectlevel program's point of view, it's still
running on a perfect computer... this touches upon the distinction
between Turing machines and more holistic approaches to what a computer
might be. If you forbade a machine from finding out it was running in
emulation, you'd probably want to be very careful in how you structured
your primitive operations, too...

> Are you talking about something other than tail-call-elimination?

I've been trying to avoid the phrase "tail-call optimisation" in
particular, since it has a specific meaning in the compiler community
that's only loosely related to the sense I'm interested in.

Will Clinger's paper http://citeseer.ist.psu.edu/clinger98proper.html
has a rigorous definition of various kinds of stack-related space leaks
and explores a lot of the detail.

Regards,
  Tony