Tail-optimized recursion 
Author Message
 Tail-optimized recursion

For a long time I'd implicitly thought that tail-optimized recursion,
recursion that's optimized into a BRANCH instead of an EXECUTE, is
simple to do.  I thought that I'd have to modify the inner interpreter
or the outer interpreter or such thing.  I'm happy to say that it's
much easier than that =)  A few days ago, with my greater knowledge
of control structures and Forth in general, I decided to sit down at
a Forth (gforth) at give it tail-optimized recursion.  This took a
few minutes.

In Gforth I found through experimentation that a  : FOO  changed HERE
in constant and simple fashion, so I just calculated the destination
of the BRANCH, and I used knowledge of Gforth's control structures
through SEE.

Here's something almost portable.

  variable r-pad
  : r: : here r-pad ! ;

Of course in the Gforth implementation you wouldn't need the variable.
Assuming a word :ADDR that would return the address of the start of a
definition,

  : recur; :ADDR postpone again ; immediate

And some quick code:

  : star [char] * emit ;
  : stars dup if star 1- recur; then drop ;
  : gcd dup if tuck mod recur; then drop ;



Sun, 25 Jan 2004 02:35:50 GMT  
 Tail-optimized recursion

Quote:

> For a long time I'd implicitly thought that tail-optimized recursion,
> recursion that's optimized into a BRANCH instead of an EXECUTE, is
> simple to do.  I thought that I'd have to modify the inner interpreter
> or the outer interpreter or such thing.  I'm happy to say that it's
> much easier than that =)  

I first picked up the technique about a decade ago from
Chuck Moore's code.  He used tail-recursion to convert
a called word to a jump if ; was compiled after it, or
he would explicitly direct this with a -; word.  This
used the same amount of source (or one extra character
for -; ) but compiled one less word, used one less
cell on the return stack at runtime, and saved the
time of one return at runtime.

Chuck also went to using self-recursion in
conjunction with the tail-recusion.  That is he
would not smudge a name while being defined so that
the use of the name of the word being compiled within
that word would compile a call (or jump with
the tail recursion) back to the start of that word.
For a while this was the only form of looping that
Chuck used.

Later he added a BEGIN NEXT to his colorForth.  But
he still has tail recursion and self recursion as
part of the design.  This also eliminated some words
like SMUDGE from the list but complicate the task
of redefining a word and using the old definition
in a new word with the same name.  It isn't a
big problem, you just have to get the address of
the old name before you redefine it, but Chuck
says that he usually just uses a new name rather
than redefine with the same name.

Chuck is doing something similar to what you did
in Gforth but doesn't have to define a special
word ( recur; ) although his -; or modified ;
for tail recursion is a complication and his
removal of smudge is a departure from tradition.



Sun, 25 Jan 2004 01:48:31 GMT  
 Tail-optimized recursion


Quote:
>Assuming a word :ADDR that would return the address of the start of a
>definition,

>  : recur; :ADDR postpone again ; immediate

Getting the address of the start of the definition is easy in Gforth:

lastxt >body

But AGAIN in Gforth takes more than just the address, so you would
have to define :ADDR like this:

: :ADDR 0 lastxt >body dest ;

And this does not work if the definition uses locals.

- anton
--
M. Anton Ertl                    Some things have to be seen to be believed

http://www.complang.tuwien.ac.at/anton/home.html



Sun, 25 Jan 2004 16:50:13 GMT  
 Tail-optimized recursion

Quote:


> > For a long time I'd implicitly thought that tail-optimized recursion,
> > recursion that's optimized into a BRANCH instead of an EXECUTE, is
> > simple to do.  I thought that I'd have to modify the inner interpreter
> > or the outer interpreter or such thing.  I'm happy to say that it's
> > much easier than that =)

> I first picked up the technique about a decade ago from
> Chuck Moore's code.  He used tail-recursion to convert
> a called word to a jump if ; was compiled after it, or
> he would explicitly direct this with a -; word.  This
> used the same amount of source (or one extra character
> for -; ) but compiled one less word, used one less
> cell on the return stack at runtime, and saved the
> time of one return at runtime.

On my Atari I had created a word called TAIL which looked
at the instruction before the last RTS. If it was a JSR,
it would change it in a JMP. It's not so sofisticated as a
self thinking    ;     but it sufficed. Needless to say the
Forth used is a jsr/native-code system.
I didn't had so much tail-recursion in mind as the speed
improvement of avoiding an unnecesary RTS for whatever
last JSR instruction. But it came in handy for tail-recursion
i.e. alternative looping as well.

Quote:

> Chuck also went to using self-recursion in
> conjunction with the tail-recusion.  That is he
> would not smudge a name while being defined so that
> the use of the name of the word being compiled within
> that word would compile a call (or jump with
> the tail recursion) back to the start of that word.
> For a while this was the only form of looping that
> Chuck used.

On Forth systems using the RECURSIVE method, the users
can do self-recursion as well. The RECURSIVE directive
could be misleading in its name though. Sometimes you need
the xt from the word being defined without recursion in mind.
In which case the word REVEAL would be more appropriate.
Anyway, I allways found the smudge stuff unnecessary com-
plicated. The name of the word being defined is the perfect
indication what you had in mind in these 'recursive' cases,
rather than words like RECURSE or MYSELF which deal with
a system implementation instead of the 'problem' at hand.

Quote:

> Later he added a BEGIN NEXT to his colorForth.  But
> he still has tail recursion and self recursion as
> part of the design.  This also eliminated some words
> like SMUDGE from the list but complicate the task
> of redefining a word and using the old definition
> in a new word with the same name.  It isn't a
> big problem, you just have to get the address of
> the old name before you redefine it, but Chuck
> says that he usually just uses a new name rather
> than redefine with the same name.

There is only one(1) case in all my code where I use
the old definition in a redefinition and where I can't
use a new name. But that could easily be solved with
the way mentioned here, indeed.

Quote:

> Chuck is doing something similar to what you did
> in Gforth but doesn't have to define a special
> word ( recur; ) although his -; or modified ;
> for tail recursion is a complication and his
> removal of smudge is a departure from tradition.

Now I wonder, I'm very curious. What is the reason for
this tradition? Who putted smudge in and what was the
argumentation, apart from redefining with the use of
the old def? If there was a real pressing reason to have
the smudge stuff, I would have suggested in having it
working the other way round (but IMHO FWIW smudge is out).

-Roelf



Sun, 25 Jan 2004 17:16:37 GMT  
 Tail-optimized recursion


Quote:


>>  : recur; :ADDR postpone again ; immediate
...
>: :ADDR 0 lastxt >body dest ;

>And this does not work if the definition uses locals.

I just tested this, and actually, it does work in the presence of
locals.  Ain't Forth great?

- anton
--
M. Anton Ertl                    Some things have to be seen to be believed

http://www.complang.tuwien.ac.at/anton/home.html



Sun, 25 Jan 2004 17:22:54 GMT  
 
 [ 5 post ] 

 Relevant Pages 

1. How is tail-recursion optimized in Smalltalk?

2. Tail recursion and complete recursion?

3. Optimizing tail-recursive operations using jumps

4. OO, lexical scope, closure, tail-recursion, continuation

5. Lisp type list, recursion and tail call optimisation

6. Tail recursion ???

7. Tail recursion

8. Thanks for the tail recursion

9. Any Smalltalk supporting tail recursion optimization ?

10. tail recursion analysis

11. tail recursion -- what's a good name

12. Recognising tail recursion

 

 
Powered by phpBB® Forum Software