tail recursion analysis 
Author Message
 tail recursion analysis

: a .... b ;

How can you tell if it is ok to replace the
call to b with a jump to b?  It seems like there
are cases where you can do this even where no
recursion is involved.  I am not looking for a
conceptual explanation, I really just want an
algorithm.  Nachos gracious.

B.



Sun, 07 Dec 2003 13:40:32 GMT  
 tail recursion analysis
You can always replace the call to b with a jump, as long as there is
no branch destination that lands after b, as in;

: a .. IF ... b THEN ;

I hope this helps,

Tom Zimmer

Quote:

> : a .... b ;

> How can you tell if it is ok to replace the
> call to b with a jump to b?  It seems like there
> are cases where you can do this even where no
> recursion is involved.  I am not looking for a
> conceptual explanation, I really just want an
> algorithm.  Nachos gracious.

> B.



Sun, 07 Dec 2003 22:20:53 GMT  
 tail recursion analysis

Quote:

> You can always replace the call to b with a jump, as long as there is
> no branch destination that lands after b, as in;

> : a .. IF ... b THEN ;

> I hope this helps,

Um, that's not quite true.  In the particular case above b can still
be a tail call.  It only ceases to be a tail call if there is
something after THEN for example ...

 : a .. IF ... b THEN x ;

I tried adding full tail call optimisation to my Forth but in the end
decided that having the compiler do it was not the Forth way -- it
added quite a lot of bloat to a system that without it is under 4K.
Instead  I use a ";" which is like that in Chuck's latest Forths so
that your original example can be written as :-

  : a .. IF ... b ; THEN ;

So now the simple rule that :-

  x ;

can be replaced by a tail-call to x is true except when x has been
inlined and supporting that doesn't take much code at all.



Sun, 07 Dec 2003 22:41:19 GMT  
 tail recursion analysis

Quote:

> : a .... b ;

> How can you tell if it is ok to replace the
> call to b with a jump to b?  It seems like there
> are cases where you can do this even where no
> recursion is involved.  I am not looking for a
> conceptual explanation, I really just want an
> algorithm.  Nachos gracious.

I don't know why they have such a fancy name for such a mundane thing.

My Forths do it unless:

1. B operates on the return stack (like R>). B expects a return
address on the stack. I set a flag with CALL-ONLY, which works like
the IMMEDIATE or COMPILE-ONLY flag-setting words.

2. A branch has been resolved after B, so you need a return
instruction.

; and EXIT can do tail recursion. They look at B's CALL-ONLY flag
before deciding to convert the last call to a jump.

You can download Firmware Studio from www.tinyboot.com, install it and
FLOAD DEMO51.F1 which is for 8051 processors. Or, you can load
DEMOCF.FF or DEMOAVR.FF if you're more comfortable with 68000 or AVR
code. Then SEE to your heart's content. VIEW any word's source, or F9
in the editor hyperlinks you around the source.

BTW, does anyone know of a free, file-compressing installation program
other than WinZip?



Mon, 08 Dec 2003 00:11:22 GMT  
 tail recursion analysis


Quote:

> > You can always replace the call to b with a jump, as long as there is
> > no branch destination that lands after b, as in;

> > : a .. IF ... b THEN ;

> > I hope this helps,

> Um, that's not quite true.  In the particular case above b can still
> be a tail call.  It only ceases to be a tail call if there is
> something after THEN for example ...

>  : a .. IF ... b THEN x ;

I assume this was his intent although the wording is ambiguous
as to which side his example is for.

Quote:

> I tried adding full tail call optimisation to my Forth but in the end
> decided that having the compiler do it was not the Forth way -- it
> added quite a lot of bloat to a system that without it is under 4K.
> Instead  I use a ";" which is like that in Chuck's latest Forths so
> that your original example can be written as :-

>   : a .. IF ... b ; THEN ;

> So now the simple rule that :-

>   x ;

> can be replaced by a tail-call to x is true except when x has been
> inlined and supporting that doesn't take much code at all.

How's ; defined and what happens in the (pathological?, programmer error?) cases:-

: a .. IF ... b ; THEN y ;

: a .. IF ... b ; THEN RECURSE ;

I don't know, that extra ; gives me the willies.

Geoff



Mon, 08 Dec 2003 01:42:20 GMT  
 tail recursion analysis

Quote:

>> : a .... b ;

>> How can you tell if it is ok to replace the
>> call to b with a jump to b?  It seems like there
>> are cases where you can do this even where no
>> recursion is involved.  I am not looking for a
>> conceptual explanation, I really just want an
>> algorithm.  Nachos gracious.

>I don't know why they have such a fancy name for such a mundane thing.

>My Forths do it unless:

>1. B operates on the return stack (like R>). B expects a return
>address on the stack. I set a flag with CALL-ONLY, which works like
>the IMMEDIATE or COMPILE-ONLY flag-setting words.

>2. A branch has been resolved after B, so you need a return
>instruction.

>; and EXIT can do tail recursion. They look at B's CALL-ONLY flag
>before deciding to convert the last call to a jump.

>You can download Firmware Studio from www.tinyboot.com, install it and
>FLOAD DEMO51.F1 which is for 8051 processors. Or, you can load
>DEMOCF.FF or DEMOAVR.FF if you're more comfortable with 68000 or AVR
>code. Then SEE to your heart's content. VIEW any word's source, or F9
>in the editor hyperlinks you around the source.

>BTW, does anyone know of a free, file-compressing installation program
>other than WinZip?

The free stuff tends to be factored into TAR.EXE, GZIP.EXE and whatever
else "install" means. There's a GZIP.EXE somewhere. gzip.org maybe. And in
the DOS dirs of many Linux distribution sites.

Rick



Mon, 08 Dec 2003 10:30:34 GMT  
 tail recursion analysis

Quote:

> How's ; defined and what happens in the (pathological?, programmer
> error?) cases:-

> : a .. IF ... b ; THEN y ;

This is equivalent to the following Scheme code (I'm using Scheme
since it is one of the few languages that requires all standards
conforming implementations to perform tail-call optimisation) :-

  (define (a ...)
    (if ...
      (b ...)
      (y ...)))

and is not an error unless what you wanted was :-

  (define (a ...)
    (if ...
      (b ...))
    (y ...))

in which case then it should have been written as :-

  : a .. IF ... b THEN y ;

IMHO there is nothing pathalogical here, the programmer just has to
know whether they want y to always occur or not and add/remove the ";"
as appropriate.

Quote:
> : a .. IF ... b ; THEN RECURSE ;

There is no RECURSE in my Forth (nor in Chuck's IIRC), instead you'd
write it as :-

  : a .. IF ... b ; THEN a ;

which is equivalent to the following Scheme :-

  (define (a ...)
    (if ...
      (b ...)
      (a ...)))

which is a perfectly valid (tail) recursive function.

Quote:
> I don't know, that extra ; gives me the willies.

I can understand that, since it just doesn't look like traditional
Forth.  All I can say is that the more code you write this way, the
more natural it becomes (pretty much true for anything I should think :-)


Mon, 08 Dec 2003 10:32:34 GMT  
 tail recursion analysis
On Wed, 20 Jun 2001 13:42:20 -0400, "Geoff Summerhayes"

Quote:

>How's ; defined and what happens in the (pathological?, programmer error?) cases:-

>: a .. IF ... b ; THEN y ;

>: a .. IF ... b ; THEN RECURSE ;

>I don't know, that extra ; gives me the willies.

The reference is to a ";" as in Color Forth, which does not switch the
interpreter from interpreter to compiler mode ... this is no worries
in Color Forth, since the "space" token in front of each word indicate
which mode it is in, rather than this being accomplished by compiler
words like "]" and ";", so ";", whether in the middle of a definition
or at the end, is just an "exit".

: a ... IF ... b EXIT THEN y ;
: a ... IF b EXIT THEN RECURSE ;

In the second example, recursion stops when you get inside the IF.

(
----------
Virtually,

Bruce McFarling, Newcastle,

)



Mon, 08 Dec 2003 11:09:53 GMT  
 tail recursion analysis

Quote:
>BTW, does anyone know of a free, file-compressing installation program
>other than WinZip?

I use PowerArchiver (www.powerarchiver.com) which looks like a perfect

WinZip clone. I only use its extraction capabilities, so i dont know
exactly about its archiving capabilities.

I also saw Winimp (www.winimp.com) claimed to be faster than PA.

There was a recent discussion about this on alt.comp.freeware.

Regards

Klaus



Mon, 08 Dec 2003 16:25:37 GMT  
 tail recursion analysis

Quote:


> > : a .... b ;

> > How can you tell if it is ok to replace the
> > call to b with a jump to b?  It seems like there
> > are cases where you can do this even where no
> > recursion is involved.  I am not looking for a
> > conceptual explanation, I really just want an
> > algorithm.  Nachos gracious.

> I don't know why they have such a fancy name for such a mundane thing.

> My Forths do it unless:

> 1. B operates on the return stack (like R>). B expects a return
> address on the stack. I set a flag with CALL-ONLY, which works like
> the IMMEDIATE or COMPILE-ONLY flag-setting words.

That's how it should be done right.
ANS Forth says that access to the return stack is
system-dependent and therefore such things are left beyond
the scope of the standard. A reason (one of probably many)
for that is that in 1990's many 8086..80286 Forths had
double-cell return addresses (as e.g. F-PC).

But if you plan to ever write programs that may not
need portability across all platforms from 8051 CamelForth
and outdated F-PC to Alpha, you should care about
return stack manipulations as well.

In principle, you can detect that the word is not
CALL-ONLY automatically.
If it invokes only NOT-CALL-ONLY words, and does not

If the words >R R> are balanced as it is required for
ANS Forth programs, and if it does not call CALL-ONLY words,
it is NOT-CALL-ONLY.

The algorithm for detecting r-stack use depends on what
result you want to get.
If you want your code to be correct, the above may be ok.
If you want more...

CALL-ONLY words usually expect a finite number of r-stack
values, so it is meaningful to attribute this number to
a word, rather than a flag.

So,

0 INVERT 1 RSHIFT CONSTANT MAX-INT
: ;I POSTPONE ; IMMEDIATE ; IMMEDIATE

\ Header format:
\ [^attrib-list] [^cfa] [flags] [link] [[len]name]
: n>attr 4 CELLS - ;
\ ^attrib-list -- reserved, so let's use it now
' EXIT ALIAS return     \ we are going to redefine this name

VARIABLE r-stack-state
VARIABLE r-stack-use
VARIABLE reachable
VARIABLE last-dest

: r-use ( n -- )

        r-stack-use ! ;
: r-change ( n -- )
        r-stack-state +!
        0 r-use
;
: cf-dest \ control flow destination
        HERE ( code-memory-pointer )
        last-dest !
;

: initially-in-:
        0 r-stack-state !
        0 r-stack-use !
        -1 reachable !
        cf-dest
;
: .r-st-items ( n -- )
        DUP . ." r-stack item" ABS 1 <> IF 's' EMIT THEN SPACE
;
: finally-in-;

        IF      CR LATEST .NAME ." uses " .r-st-items
        THEN

        IF
                CR LATEST .NAME
                DUP 0> IF ." takes " ELSE ." leaves " THEN ABS
                .r-st-items
        THEN
        NAMESPACE
                HERE LATEST n>attr !
                0 ,


        DATASPACE
;

: R> POSTPONE R>  1 r-change ;I
: >R POSTPONE >R -1 r-change ;I

\ how would you tick them now?
\ using a smart tick?

: 2R> POSTPONE 2R>   2 r-change ;I
: 2>R POSTPONE 2>R  -2 r-change ;I




;
: r-param-match ( x1 x2 -- )

        IF      MAX-INT r-stack-use !
                CR LATEST .NAME
                ."  unbalanced r-stack use "
        THEN
;
: unreachable!
        0 reachable !
        0 r-use
;
: reachable!
        -1 reachable !
;
] AHEAD [ 2CONSTANT quasi-orig

DEFER tailcalloptimization ' NOOP IS tailcalloptimization

        unreachable!
;I

        unreachable!
;I

: 4SWAP   4 0 DO 7 ROLL LOOP ;
: CS-SWAP 4SWAP ; ( was: 2SWAP )



: THEN  r-param-match POSTPONE THEN cf-dest reachable! ;I

: AGAIN r-param-match POSTPONE AGAIN unreachable! ;

: ELSE   POSTPONE AHEAD CS-SWAP POSTPONE THEN ;I
: WHILE  POSTPONE IF CS-SWAP ;I
: REPEAT POSTPONE AGAIN POSTPONE THEN ;I
HEX
\ these can interfere with tail-call optimization
: S" POSTPONE S" cf-dest ;I
: C" POSTPONE C" cf-dest ;I
: ." POSTPONE ." cf-dest ;I
: ABORT" POSTPONE ABORT" cf-dest ;I
: ['] POSTPONE ['] cf-dest ;I

\ DO ... LOOP --- not so beautiful

: : CREATE HIDE ] initially-in-: !CSP
        donest IT !     \ DOES> >R  ( we write to the code field)
;
: ; ?COMP ?CSP POSTPONE EXIT REVEAL POSTPONE [ finally-in-; ;I
\ DOES>

: >TCODE >BODY ; ( colon-xt -- threaded-code-addr ) \ ITC
: do-tail-call-optimization-with-threaded-code ( -- )


   IF

        IF

             donest =
             IF


                      ELSE DROP TRUE \ do optimize by default
                      THEN
                  IF

                      ['] BRANCH HERE 2 CELLS - !
   THEN THEN THEN THEN
;
IT IS tailcalloptimization

: __S$PROCESS-NAME
        0 TO LastFoundLFA
        [ ' S$PROCESS-NAME BEHAVIOR COMPILE, ]
        LastFoundLFA
        IF

                IF      CELL+


                THEN
        ELSE
                cf-dest \ it was a literal: LIT nn
        THEN
;
IT IS S$PROCESS-NAME

=====================================
The code sort of works:

HEX
 ok[Hex]
: foo ." hi!" ;
 ok[Hex]
: bar >R R> ;
 ok[Hex]
: baar R> >R ;

baar uses 1 r-stack item  ok[Hex]
: my-R> R> R> SWAP >R ;

my-R> uses 2 r-stack items
my-R> takes 1 r-stack item  ok[Hex]
: my->R R> SWAP >R >R ;

my->R uses 1 r-stack item
my->R leaves 1 r-stack item  ok[Hex]
: my-EXIT my-R> DROP ;

my-EXIT uses 1 r-stack item  ok[Hex]
: my-noop my-EXIT ;
 ok[Hex]
: my-test my-noop ;
 ok[Hex]
: my-test2 ['] my-noop ;
 ok[Hex]
see my-test

: my-test     BRANCH &my-noop  ok[Hex]
see my-noop

: my-noop     my-EXIT EXIT ( return )  ok[Hex]
see my-EXIT

: my-EXIT     my-R> DROP ( D>S ) EXIT ( return )  ok[Hex]
see my-test2

: my-test2     LIT my-noop EXIT ( return )  ok[Hex]

"sort of": I mean, I could forget about something.
Such as DO...LOOP LEAVE etc.
OTOH, do we really need such a complx compiler?

===============

Quote:

> 2. A branch has been resolved after B, so you need a return
> instruction.

['] myword EXIT also must not be touched.
And some others...
(see above)

Quote:

> ; and EXIT can do tail recursion. They look at B's CALL-ONLY flag
> before deciding to convert the last call to a jump.

> You can download Firmware Studio from www.tinyboot.com, install it and
> FLOAD DEMO51.F1 which is for 8051 processors. Or, you can load
> DEMOCF.FF or DEMOAVR.FF if you're more comfortable with 68000 or AVR
> code. Then SEE to your heart's content. VIEW any word's source, or F9
> in the editor hyperlinks you around the source.

> BTW, does anyone know of a free, file-compressing installation program
> other than WinZip?

Try RAR:
http://www.rarsoft.com
http://www.rarsoft.de

Not exactly free, shareware with a trial period, but
the unpacker (unrar) is free.

I also can remember the archivers:
ARJ, HA (harry hirvola ?), UC2 (ultra compressor), AIN.
I am not sure about the license.

--
do not do that -- universal advice



Mon, 08 Dec 2003 19:09:31 GMT  
 tail recursion analysis
one more improvement:

: finish DROP ." ." ;
 ok[Hex]
: actions DUP 0> IF DUP . 1- RECURSE EXIT ELSE finish THEN ;
 ok[Hex]
see finish

: finish     DROP ( D>S ) (.") [2e01"."] EXIT ( return )  ok[Hex]
see actions

: actions     DUP 0> ?BRANCH [18] DUP . 1- ( CHAR- ) jump &actions jump
&finish  ok[Hex]
5 actions
5 4 3 2 1 . ok[Hex]
: this ." this " ;
 ok[Hex]
: that ." that " ;
 ok[Hex]
: hmmm IF this EXIT ELSE that THEN ;
 ok[Hex]
1 hmmm
this  ok[Hex]
0 hmmm
that  ok[Hex]
see hmmm

: hmmm     ?BRANCH [c] jump &this jump &that  ok[Hex]

==================

and the code is:

0 INVERT 1 RSHIFT CONSTANT MAX-INT
: ;I POSTPONE ; IMMEDIATE ; IMMEDIATE

\ Header format:
\ [^attrib-list] [^cfa] [flags] [link] [[len]name]
: n>attr 4 CELLS - ;
\ ^attrib-list -- reserved, so let's use it now
' EXIT ALIAS return     \ we are going to redefine this name

VARIABLE r-stack-state
VARIABLE r-stack-use
VARIABLE reachable
VARIABLE last-dest

: r-use ( n -- )

        r-stack-use ! ;
: r-change ( n -- )
        r-stack-state +!
        0 r-use
;
: cf-dest \ control flow destination
        HERE ( code-memory-pointer )
        last-dest !
;

: initially-in-:
        0 r-stack-state !
        0 r-stack-use !
        -1 reachable !
        cf-dest
;
: .r-st-items ( n -- )
        DUP . ." r-stack item" ABS 1 <> IF 's' EMIT THEN SPACE
;
: finally-in-;

        IF      CR LATEST .NAME ." uses " .r-st-items
        THEN

        IF
                CR LATEST .NAME
                DUP 0> IF ." takes " ELSE ." leaves " THEN ABS
                .r-st-items
        THEN
        NAMESPACE
                HERE LATEST n>attr !
                0 ,


        DATASPACE
;

: R> POSTPONE R>  1 r-change ;I
: >R POSTPONE >R -1 r-change ;I

\ how would you tick them now?
\ using a smart tick?

: 2R> POSTPONE 2R>   2 r-change ;I
: 2>R POSTPONE 2>R  -2 r-change ;I




;
: r-param-match ( x1 x2 -- )

        IF      MAX-INT r-stack-use !
                CR LATEST .NAME
                ."  unbalanced r-stack use "
        THEN
;
: unreachable!
        0 reachable !
        0 r-use
;
: reachable!
        -1 reachable !
;
] AHEAD [ 2CONSTANT quasi-orig

DEFER tailcalloptimization ' NOOP IS tailcalloptimization

        unreachable!
;I

        unreachable!
;I
: THEN  2DUP quasi-orig D<> IF   POSTPONE THEN cf-dest reachable!
                            ELSE 2DROP THEN
;I

: 4SWAP   4 0 DO 7 ROLL LOOP ;
: CS-SWAP 4SWAP ; ( was: 2SWAP )



: THEN  r-param-match POSTPONE THEN ;I

: AGAIN r-param-match POSTPONE AGAIN unreachable! ;

: ELSE   POSTPONE AHEAD CS-SWAP POSTPONE THEN ;I
: WHILE  POSTPONE IF CS-SWAP ;I
: REPEAT POSTPONE AGAIN POSTPONE THEN ;I
HEX
\ these can interfere with tail-call optimization
: S" POSTPONE S" cf-dest ;I
: C" POSTPONE C" cf-dest ;I
: ." POSTPONE ." cf-dest ;I
: ABORT" POSTPONE ABORT" cf-dest ;I
: ['] POSTPONE ['] cf-dest ;I

\ DO ... LOOP --- not so beautiful

: : CREATE HIDE ] initially-in-: !CSP
        donest IT !     \ DOES> >R  ( we write to the code field)
;
: ; ?COMP ?CSP POSTPONE EXIT REVEAL POSTPONE [ finally-in-; ;I
\ DOES>

: >TCODE >BODY ; ( colon-xt -- threaded-code-addr ) \ ITC
: do-tail-call-optimization-with-threaded-code ( -- )


   IF

        IF

             donest =
             IF


                      ELSE DROP TRUE \ do optimize by default
                      THEN
                  IF

                      ['] jump HERE 2 CELLS - !
   THEN THEN THEN THEN
;
IT IS tailcalloptimization

: __S$PROCESS-NAME
        0 TO LastFoundLFA
        [ ' S$PROCESS-NAME BEHAVIOR COMPILE, ]
        LastFoundLFA
        IF

                IF      CELL+


                THEN
        ELSE
                cf-dest \ it was a literal: LIT nn
        THEN
;
IT IS S$PROCESS-NAME

--
do not do that -- universal advice

--
the fewer the navorots, the fewer the glitches
(navorot -- unnecessary functionality/feature/complexity/etc.)



Mon, 08 Dec 2003 19:32:47 GMT  
 tail recursion analysis

Quote:

>: a .... b ;

>How can you tell if it is ok to replace the
>call to b with a jump to b?

In ANS Forth it is always ok.  If a uses locals, you may have to think
about where you deallocate them (just before b would be an appropriate
point).

In other languages or Forth variants things are more complex.  For
Forth there are at least three issues that come to mind:

- If your Forth supports return-address manipulations, you cannot
perform this optimization if b wants to do anything with its return
address.

- If your Forth supports backtraces, tail-call optimization would
eliminate some calls from the backtrace.

- If your Forth supports taking the address of a local (e.g., Gforth's
variable-flavoured locals), and that address is passed to b, you have
to free the locals after the call, so, you may not be able to
tail-call b (depends on your locals implementation).

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

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



Mon, 08 Dec 2003 20:13:03 GMT  
 tail recursion analysis

Quote:

> : a .... b ;
> How can you tell if it is ok to replace the call to b with a jump to b?

If you write ; to convert the last call to a jump AND also to insert the
usual return code then you can write as normal without having to worry
about resolving THEN's etc and automatically have tail recursion replaced
with jumps. Optimisations should be obvious (don't bother with the return
if no branching was resolved after b and no locals in use) but are not
needed to get tail-recursion replaced with jumping.

Following ANS restrictions on what is allowed to be done with the return
stack should avoid any issues with >r and so on, and even the lousy ANS
locals should "work" since ; does its normal action in addition to
optimising the compiled last word call.

TW



Wed, 10 Dec 2003 20:02:42 GMT  
 
 [ 17 post ]  Go to page: [1] [2]

 Relevant Pages 

1. Tail recursion and complete recursion?

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

3. Lisp type list, recursion and tail call optimisation

4. Tail recursion ???

5. Tail recursion

6. Thanks for the tail recursion

7. How is tail-recursion optimized in Smalltalk?

8. Any Smalltalk supporting tail recursion optimization ?

9. Tail-optimized recursion

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

11. Recognising tail recursion

12. Tail recursion

 

 
Powered by phpBB® Forum Software