Return stack and tail call optimizations

[massung]

Has anyone here ever worked with (or implemented) a Forth that prevents a tail call to a word?

I'm currently implementing my own little Forth modeled after the F18A. And while tail call optimization is quite simple, occasionally it should be illegal and I'm having a heluva time coming up with an algorithm to figure out when.

Consider this (contrived example) I've created using F18A to load a literal, counted string into the A register:

000 - @p push ex .
001 - 5
002 - 2
003 - 'H'
004 - 'i'
005 - pop a! @+ ;

When this code is done executing, the A register should point to 003 ('H') and 2 should be on the parameter stack (length).

But, let's say we have several literal strings in our code and so we decide to break out the instructions at address 005 into their own word, not because we're saving space, but because we don't want to accidentally mess it up or forget to do it:

( >string )
000 - pop a! @+ ;

Well, obviously this word doesn't work as-is, because since we'll be getting called, the top of the return stack will be a return address and not the address of the string. So, we swizzle the return stack a bit...

( >string )
000 - pop pop a! push
001 - @+ ;

So, now we go back to our original code and modify it to call our subroutine instead:

005 - call (>string)
006 - ;

But, now we perform tail call optimization...

005 - jump (>string)

And suddenly our definition for >string is broken. The return address we expected to be on the stack is no longer there.

Aside from a modifying word (like ANS Forth's IMMEDIATE) identifying a word as "cannot be tail called" I can't think of a solution to this.

Better still would be to somehow realize that the (unswizzled) definition of >string is a single cell and should just be inlined, but ignoring that, has anyone run into this ever with their Forth implementations or on the F18A?

Thanks!

[Immortalin]

Take a look at joy

[phreda4]

When I implement the show word, like colorforth, this problem come to me, when use the rstack in between words call the tail recurse is incorrect.

the word show is like:

::show |
       ....
    ( .exit 0? )( drop
        update 
        r exec
        redraw
               )
      ....
      ;

SHOW work like an iteration with update event and redraw screen.

:main
     0 'val ! | only in the start
     show      | from here iterate until esc is depressed, in the screen see a counter moving
         clrscr
         val "%d " print 
         1 'val +!
         'exit >esc< ;

The compiler translate WORD + ; like JMP (tail recursion), if I write SHOW ; ... this crash..but not have sense! is a infinite loop. I can test if a word have a r cell used in exec if need this check but not are very usefull for now.

[ruv]

Yet another example: : some-word ... 2>R ... 2R> ; — if 2R> is a regular word, tail call optimization will break its work. Also any use of the return stack for control flow (see BacForth for example) usually conflicts with tail call optimization. SP-Forth has tail-call optimization that is disabled by default and can be enabled by the user for the cases when it is known to be safe.

[mikaelpatel]

Looks like you need a method to temporary disable the peep-hole optimizer. This could be done by adding a noop before ; (EXIT). I use this technique in a run-time tail-call optimizing byte token threaded interpreter (writting in C++ for Arduino). Please see https://github.com/mikaelpatel/Arduino-FVM/blob/master/FVM.cpp#L179 and https://github.com/mikaelpatel/Arduino-FVM/blob/master/FVM.cpp#L501.

Below is an example; iter1 uses run-time tail-call optimization and iter2 uses a noop to disable the optimization. Please see the resulting dynamic trace.

: iter1 ( n -- n...1 ) ?dup if dup 1- iter1 then ;
3 iter1
task@537331992: execute:[2]: 3 384
task@537331992:  ?dup:[1]: 3
task@537331992:  (0branch):[2]: 3 3
task@537331992:  dup:[1]: 3
task@537331992:  1-:[2]: 3 3
task@537331992:  iter1:[2]: 3 2
task@537331992:  ?dup:[2]: 3 2
task@537331992:  (0branch):[3]: 3 2 2
task@537331992:  dup:[2]: 3 2
task@537331992:  1-:[3]: 3 2 2
task@537331992:  iter1:[3]: 3 2 1
task@537331992:  ?dup:[3]: 3 2 1
task@537331992:  (0branch):[4]: 3 2 1 1
task@537331992:  dup:[3]: 3 2 1
task@537331992:  1-:[4]: 3 2 1 1
task@537331992:  iter1:[4]: 3 2 1 0
task@537331992:  ?dup:[4]: 3 2 1 0
task@537331992:  (0branch):[4]: 3 2 1 0
task@537331992:  exit:[3]: 3 2 1
task@537331992: halt:[3]: 3 2 1

: iter2 ( n -- n...1 ) ?dup if dup 1- iter2 noop then ;
3 iter2
task@537331992: execute:[5]: 3 2 1 3 385
task@537331992:  ?dup:[4]: 3 2 1 3
task@537331992:  (0branch):[5]: 3 2 1 3 3
task@537331992:  dup:[4]: 3 2 1 3
task@537331992:  1-:[5]: 3 2 1 3 3
task@537331992:  iter2:[5]: 3 2 1 3 2
task@537331992:   ?dup:[5]: 3 2 1 3 2
task@537331992:   (0branch):[6]: 3 2 1 3 2 2
task@537331992:   dup:[5]: 3 2 1 3 2
task@537331992:   1-:[6]: 3 2 1 3 2 2
task@537331992:   iter2:[6]: 3 2 1 3 2 1
task@537331992:    ?dup:[6]: 3 2 1 3 2 1
task@537331992:    (0branch):[7]: 3 2 1 3 2 1 1
task@537331992:    dup:[6]: 3 2 1 3 2 1
task@537331992:    1-:[7]: 3 2 1 3 2 1 1
task@537331992:    iter2:[7]: 3 2 1 3 2 1 0
task@537331992:     ?dup:[7]: 3 2 1 3 2 1 0
task@537331992:     (0branch):[7]: 3 2 1 3 2 1 0
task@537331992:     exit:[6]: 3 2 1 3 2 1
task@537331992:    noop:[6]: 3 2 1 3 2 1
task@537331992:    exit:[6]: 3 2 1 3 2 1
task@537331992:   noop:[6]: 3 2 1 3 2 1
task@537331992:   exit:[6]: 3 2 1 3 2 1
task@537331992:  noop:[6]: 3 2 1 3 2 1
task@537331992:  exit:[6]: 3 2 1 3 2 1
task@537331992: halt:[6]: 3 2 1 3 2 1

[massung]

@mikaelpatel that's a good idea. I think what I'll end up doing is having a word like notail which is used after the declaration (much like immediate) which - whenever a call is assembled - automatically inserts a NOP as well. Thanks for the suggestion!

[AshleyF]

Would this work?

000 - @p push @p ex
001 - 5
002 - 2
003 - 'H'
004 - 'i'
005 - jump (>string)

Where (>string) is:

000 - pop drop a! @+
001 - ; . . .