Equality of Recursive Structures [Was: Closure Compiler in 3.9 ?]

Colin Putney cputney at wiresong.ca
Tue May 15 05:21:13 UTC 2007


On May 14, 2007, at 8:19 AM, Tony Garnock-Jones wrote:


>   UltimateCaller >> entryPoint
>   TailCaller >> doSomething "hovering over a return-to-sender  
> bytecode"
>   SomeClass >> someMessage
>
> Since all the middle frame will *ever* do when control is returned  
> to it
> is in turn return the accumulator to its caller, it can *always*  
> safely
> be elided without affecting the object-level meaning of a program  
> at all.
>

Ok, sure. So what are you proposing?

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.

Is this what you mean by frames being elided?


> The improved safe-for-space behaviour enables the construction of a  
> new
> class of programs that are not directly representable without  
> elision of
> redundant stack frames.
>

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.

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

Colin




More information about the Squeak-dev mailing list