On Thu, 31 Jan 2002, Andrew C. Greenberg wrote:

>
> On Thursday, January 31, 2002, at 02:19 AM, Scott A Crosby wrote:
>
> >> How, exactly, can I safely and in straightforward manner optimize this
> >> for any Class, when the definitions of foo1 and foo2 may well depend
> >> upon definitions in subclasses, which in turn may change?  Moreover,
> >> since these kinds of expressions can be horribly complex, I would HATE
> >> if the debugger lost contexts when showing me the problem.
> >
> > Actually, its not all that bad to implement. Tail recursion can be done
> > by
> > replacing your own context with a new one..
> >
> > IE:
> >
> > foo
> >   blah blah
> >   ^self bar: 12
> >
> > --
> >
> > What happens is when foo sees the `^bar: 12' at the end, it replaces its
> > method context with the one for `^bar: 12'. (or, equivalently, it pops
> > its
> > stack frame. and pushes the new one for ^bar.)
>
> How, exactly, do you intend to do this, with optimization, without
> massively rewriting the compiler?  Assuming bar is inherited, we can't

One bytecode. call it a #tailSend:. Basically, it sets up the
methodcontext, then 'moves' it down to replace the current methodcontext.
As such, it doesn't care about the function being invoked, just the
invoker.

> optimize this code without recompiling foo everytime we change a bar,
> whether in this class or a superclass.

You don't need to change the function you're invoking. the function #bar:
that gets invoked doesn't need to change and can be written as normal.

IE:

Let slook at the stack, normally, it'd go:


PARENT >> foo
PARENT >> foo >> bar
PARENT >> foo >> bar >> (stuff in Bar)
   .....
PARENT >> foo >> bar >> (stuff in Bar)
PARENT >> foo >> bar
PARENT >> foo
PARENT

Here, we make the tailcall of bar instead:

PARENT >> foo
PARENT >> bar
PARENT >> bar >> (stuff in Bar)
    ....
PARENT >> bar >> (stuff in Bar)
PARENT >> bar
PARENT >> bar
PARENT

Which we do by replacing foo's methodcontext *completely* with bar's
methodcontext, thus, for all intents and purposes, bar will think that its
been invoked by PARENT, and return its result there.

This change only requires a new bytecode that replaces:
  send:
  returnTop

with a single one called
  tailSend:

which does the above optimization.

foo
	^self bar: self.
--
9 <70> self
10 <70> self
11 <E0> send: bar:
12 <7C> returnTop


In *either* case, the code for #bar: remains completely unchanged. What
changes is the last two bytecodes in #foo. Since I don't care about #bar
when doing this, it doesn't matter if its inherited or where it came from.
It can be a primitive, inherited, or even changed.


BTW, assume we have something like:

foo: n
  ^ self bar: 2*n
bar: n
  ^ self baz: n+1
baz: n
  ^ n

Then, using tailcall, the stack looks like:

PARENT
PARENT>>foo
PARENT>>foo>>*
PARENT>>foo
PARENT>>bar
PARENT>>bar>>+
PARENT>>bar
PARENT>>baz
PARENT


--

All in all, it should be an easy optimization. The only complexity there
might be would depend on exactly how it builds methodcontexts... I don't
know; I'm not planning on learning that till I see the new BC VM.

Scott