Tail recursion.
Scott A Crosby
crosby at qwes.math.cmu.edu
Thu Jan 31 21:37:03 UTC 2002
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
More information about the Squeak-dev
mailing list
|