Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #44628 > unrolled thread

tail call elimination

Back to article view | Back to comp.lang.forth

Contents

  tail call elimination Johan Kotlinski <kotlinski@gmail.com> - 2016-01-06 05:19 -0800
    Re: tail call elimination Raimond Dragomir <raimond.dragomir@gmail.com> - 2016-01-06 05:59 -0800
      Re: tail call elimination Johan Kotlinski <kotlinski@gmail.com> - 2016-01-06 06:18 -0800
        Re: tail call elimination Raimond Dragomir <raimond.dragomir@gmail.com> - 2016-01-06 06:47 -0800
          Re: tail call elimination Johan Kotlinski <kotlinski@gmail.com> - 2016-01-06 08:57 -0800
          Re: tail call elimination Johan Kotlinski <kotlinski@gmail.com> - 2016-01-08 00:40 -0800
            Re: tail call elimination Raimond Dragomir <raimond.dragomir@gmail.com> - 2016-01-08 01:21 -0800
              Re: tail call elimination Raimond Dragomir <raimond.dragomir@gmail.com> - 2016-01-08 01:23 -0800
    Re: tail call elimination stephen@mpeforth.com (Stephen Pelc) - 2016-01-06 14:42 +0000
      Re: tail call elimination Raimond Dragomir <raimond.dragomir@gmail.com> - 2016-01-06 07:07 -0800
        Re: tail call elimination stephen@mpeforth.com (Stephen Pelc) - 2016-01-07 01:02 +0000
        Re: tail call elimination hughaguilar96@gmail.com - 2016-01-06 22:26 -0800
        Re: tail call elimination Bernd Paysan <bernd.paysan@gmx.de> - 2016-01-08 03:18 +0100
          Re: tail call elimination hughaguilar96@gmail.com - 2016-01-07 21:11 -0800
          Re: tail call elimination Andrew Haley <andrew29@littlepinkcloud.invalid> - 2016-01-08 04:16 -0600
    Re: tail call elimination rickman <gnuarm@gmail.com> - 2016-01-06 12:24 -0500
      Re: tail call elimination "Elizabeth D. Rather" <erather@forth.com> - 2016-01-06 08:50 -1000
    Re: tail call elimination Pablo Hugo Reda <pabloreda@gmail.com> - 2016-01-06 17:29 -0800
    Re: tail call elimination Matthias Koch <matthias.koch@hot.uni-hannover.de> - 2016-01-07 10:56 +0100
      Re: tail call elimination Coos Haak <chforth@hccnet.nl> - 2016-01-07 12:41 +0100
        Re: tail call elimination Mux <Yvo.Zoer@gmail.com> - 2016-01-07 16:44 -0800
    Re: tail call elimination Rod Pemberton <NoHaveNotOne@bcczxcfre.cmm> - 2016-01-07 05:33 -0500

Page 1 of 2  [1] 2  Next page →

#44628 — tail call elimination

Hi, I would like to bring up the problem of tail call elimination. I have it working in my STC Forth, but I am not too happy about my implementation and thought I should check if anyone has better ideas.

The basic idea is of course very simple: If the generated machine code ends with

  jsr XT ; jump to subroutine
  rts

replace with

  jmp XT

The problem is words like r>, which copies from the return stack to the parameter stack. If it is jmp'd instead of jsr'd to, a crash will happen, because the return address was never pushed and r> addressing will be off.

The way I worked around this is to manually tag words like r> with a special flag, no-tail-call-elimination. Obviously this manual tagging is very error prone, it is easy to forget, and errors can go unnoticed for a long time.

Surely others must have run into this problem before, are there better ways to do it?

Thanks,
Johan

[toc] | [next] | [standalone]

#44629

miercuri, 6 ianuarie 2016, 15:19:58 UTC+2, Johan Kotlinski a scris:
> Hi, I would like to bring up the problem of tail call elimination. I have it working in my STC Forth, but I am not too happy about my implementation and thought I should check if anyone has better ideas.
> 
> The basic idea is of course very simple: If the generated machine code ends with
> 
>   jsr XT ; jump to subroutine
>   rts
> 
> replace with
> 
>   jmp XT
> 
> The problem is words like r>, which copies from the return stack to the parameter stack. If it is jmp'd instead of jsr'd to, a crash will happen, because the return address was never pushed and r> addressing will be off.
> 
> The way I worked around this is to manually tag words like r> with a special flag, no-tail-call-elimination. Obviously this manual tagging is very error prone, it is easy to forget, and errors can go unnoticed for a long time.
> 
> Surely others must have run into this problem before, are there better ways to do it?
> 
> Thanks,
> Johan

Tail call elimination always has to check if it is possible or not. 
You already implemented some checks for sure, because when you need to
compile the exit it's not always a previous CALL (JSR) compiled, maybe
it is something else, a literal, some inline code, whatever.
So in the same tail call elimination check procedure you have to 
check for >R and the stuff too. There is no workaround. The implementation
is up to you, a flag bit, direct address comparing, etc.

What I don't understand is your concern about being error prone. How many
>R words or the like are you having in the system? And what's easy to forget?

[toc] | [prev] | [next] | [standalone]

#44630

On Wednesday, January 6, 2016 at 2:59:45 PM UTC+1, Raimond Dragomir wrote:
> What I don't understand is your concern about being error prone. How many
> >R words or the like are you having in the system? And what's easy to forget?

By now I have 28 special words in the system, like >r, if, then, begin, until, do, loop, s" et.c. that I tagged (out of necessity) with no-tail-call-elimination. It's easy to forget adding this tag when creating new special words. It's also a bit annoying that a typical implementation of e.g. case..of..endcase will not work without adding this special tag. It makes porting harder.

Johan

[toc] | [prev] | [next] | [standalone]

#44632

miercuri, 6 ianuarie 2016, 16:18:23 UTC+2, Johan Kotlinski a scris:
> On Wednesday, January 6, 2016 at 2:59:45 PM UTC+1, Raimond Dragomir wrote:
> > What I don't understand is your concern about being error prone. How many
> > >R words or the like are you having in the system? And what's easy to forget?
> 
> By now I have 28 special words in the system, like >r, if, then, begin, until, do, loop, s" et.c. that I tagged (out of necessity) with no-tail-call-elimination. It's easy to forget adding this tag when creating new special words. It's also a bit annoying that a typical implementation of e.g. case..of..endcase will not work without adding this special tag. It makes porting harder.
> 
> Johan

You should not tag high level words like IF. All you need is a variable in which 
you should remember the size of the last compiled instruction. When you
are about to compile the EXIT (rts) you look back at the last instruction
compiled (you have the current pointer and the size of the next instruction).
If the instruction is a CALL (jsr) all you further need is to check the 
address to not be one of the >R R@ R> and possible LOOP primitives (those
primitives that deal with the return address explicitely).
Of course you need not forget to store the last instruction length in this 
variable, and it helps if your compiling is happening in a centralized place
(like COMPILE,)

[toc] | [prev] | [next] | [standalone]

#44635

On Wednesday, January 6, 2016 at 3:47:58 PM UTC+1, Raimond Dragomir wrote:
> You should not tag high level words like IF. All you need is a variable in which 

Thanks for the hints. I got stuck searching for a perfect solution when maybe there is none. I now made it so that tail call elimination is skipped iff the last found word is immediate, or one of : r@ r> >r unloop ]  -- works well for me!

Johan

[toc] | [prev] | [next] | [standalone]

#44678

On Wednesday, January 6, 2016 at 3:47:58 PM UTC+1, Raimond Dragomir wrote:
> You should not tag high level words like IF. All you need is a variable in which 
> you should remember the size of the last compiled instruction. When you
> are about to compile the EXIT (rts) you look back at the last instruction
> compiled (you have the current pointer and the size of the next instruction).
> If the instruction is a CALL (jsr) all you further need is to check the 
> address to not be one of the >R R@ R> and possible LOOP primitives (those
> primitives that deal with the return address explicitely).
> Of course you need not forget to store the last instruction length in this 
> variable, and it helps if your compiling is happening in a centralized place
> (like COMPILE,)

Oh yes, accidentally I remember why this approach alone doesn't work.

: x 0 if foo then ;

...would get compiled to...

   jsr ZERO
   jsr ZEROBRANCH
   +3  ; skip foo
   jmp foo

...when it should be:

   jsr ZERO
   jsr ZEROBRANCH
   +3  ; skip foo
   jsr foo
   rts

Johan

[toc] | [prev] | [next] | [standalone]

#44679

> Oh yes, accidentally I remember why this approach alone doesn't work.
> 
> : x 0 if foo then ;
> 
> ...would get compiled to...
> 
>    jsr ZERO
>    jsr ZEROBRANCH
>    +3  ; skip foo
>    jmp foo
> 
> ...when it should be:
> 
>    jsr ZERO
>    jsr ZEROBRANCH
>    +3  ; skip foo
>    jsr foo
>    rts
> 
> Johan

THEN should compile a 0 length "virtual" instruction :)
Then the ; will corectly compile rts.
THEN can also make a tail optimization against the last instruction it sees:

    jsr ZERO
    jsr ZEROBRANCH
    +3  ; skip foo
    jmp foo
    rts

[toc] | [prev] | [next] | [standalone]

#44680

vineri, 8 ianuarie 2016, 11:21:12 UTC+2, Raimond Dragomir a scris:
> > Oh yes, accidentally I remember why this approach alone doesn't work.
> > 
> > : x 0 if foo then ;
> > 
> > ...would get compiled to...
> > 
> >    jsr ZERO
> >    jsr ZEROBRANCH
> >    +3  ; skip foo
> >    jmp foo
> > 
> > ...when it should be:
> > 
> >    jsr ZERO
> >    jsr ZEROBRANCH
> >    +3  ; skip foo
> >    jsr foo
> >    rts
> > 
> > Johan
> 
> THEN should compile a 0 length "virtual" instruction :)
> Then the ; will corectly compile rts.
> THEN can also make a tail optimization against the last instruction it sees:
> 
>     jsr ZERO
>     jsr ZEROBRANCH
>     +3  ; skip foo
>     jmp foo
>     rts

Sorry, not THEN, the semicolon. When it sees a 0 length instruction
it should compile rts, but at the same time it can look 3 bytes
earlier and can also optimize a jsr.

[toc] | [prev] | [next] | [standalone]

#44631

On Wed, 6 Jan 2016 05:19:56 -0800 (PST), Johan Kotlinski
<kotlinski@gmail.com> wrote:

>The basic idea is of course very simple: If the generated machine code ends with
>
>  jsr XT ; jump to subroutine
>  rts
>
>replace with
>
>  jmp XT
>
>The problem is words like r>, which copies from the return stack to the parameter
>stack. If it is jmp'd instead of jsr'd to, a crash will happen, because the return
>address was never pushed and r> addressing will be off.

It's not as easy as it looks! In essence, you have to determine all
words that poison the return stack, determine how many levels are
poisoned, and then mark the word. For example:

: foo1 r> drop  ;              \ 1 level poisoned
: foo2 r> drop r> drop  ;      \ 2 levels poisoned
: foo3  r> drop  ['] bar >r  ; \ at least 1 level poisoned

If a word contains a word poisoned to level n, then that word is
itself poisoned to level n-1.

J have not yet convinced myself that I have a complete set of
rules for preventing tail optimisation. If anyone has such a set,
I would be really interested in seeing them. Never underestimate
the ingenuity of Forth programmers.

Stephen

-- 
Stephen Pelc, stephenXXX@mpeforth.com
MicroProcessor Engineering Ltd - More Real, Less Time
133 Hill Lane, Southampton SO15 5AF, England
tel: +44 (0)23 8063 1441, fax: +44 (0)23 8033 9691
web: http://www.mpeforth.com - free VFX Forth downloads

[toc] | [prev] | [next] | [standalone]

#44633

> : foo1 r> drop  ;              \ 1 level poisoned
> : foo2 r> drop r> drop  ;      \ 2 levels poisoned
> : foo3  r> drop  ['] bar >r  ; \ at least 1 level poisoned

Who says that this usage is suppose to work in a system?
Declare it undefined behaviour and you are done.
Or if you want that these examples should work as expected
(I can still ask: what's to be expected?) you may be better
off with tail recursion optimization...

These kinds of examples are exactly like those in BEGIN WHILE UNTIL THEN.
Very "clever" usage of an implementation defined behaviour
of some words (or exploiting side effects of words not designed for
that - like using "undocumented" instructions for a Z80 :)

[toc] | [prev] | [next] | [standalone]

#44643

On Wed, 6 Jan 2016 07:07:48 -0800 (PST), Raimond Dragomir
<raimond.dragomir@gmail.com> wrote:

>> : foo1 r> drop  ;              \ 1 level poisoned
>> : foo2 r> drop r> drop  ;      \ 2 levels poisoned
>> : foo3  r> drop  ['] bar >r  ; \ at least 1 level poisoned
>
>Who says that this usage is suppose to work in a system?
>Declare it undefined behaviour and you are done.
>Or if you want that these examples should work as expected
>(I can still ask: what's to be expected?) you may be better
>off with tail recursion optimization...

I have always believed that compilers should cope with
programmers actually do rather than what we might want
them to do.

Stephen

-- 
Stephen Pelc, stephenXXX@mpeforth.com
MicroProcessor Engineering Ltd - More Real, Less Time
133 Hill Lane, Southampton SO15 5AF, England
tel: +44 (0)23 8063 1441, fax: +44 (0)23 8033 9691
web: http://www.mpeforth.com - free VFX Forth downloads

[toc] | [prev] | [next] | [standalone]

#44649

On Wednesday, January 6, 2016 at 8:07:50 AM UTC-7, Raimond Dragomir wrote:
> > : foo1 r> drop  ;              \ 1 level poisoned
> > : foo2 r> drop r> drop  ;      \ 2 levels poisoned
> > : foo3  r> drop  ['] bar >r  ; \ at least 1 level poisoned
> 
> Who says that this usage is suppose to work in a system?
> Declare it undefined behaviour and you are done.

This usage is not going to work in ANS-Forth --- section 3.2.3.3 says: "A program shall not access values on the return stack (using R@, R>, 2R@ or 2R>) that it did not place there using >R or 2>R" --- if it does work, it is not portable.

In my FloatForth I won't allow this to work either. It shouldn't work! For example, on the AVR the return-stack is too small to be used for >R data, plus the code is very awkward due to a lack of appropriate instructions. The solution is to use the built-in return-stack for holding return addresses, but to use a separate stack for >R etc.. The separate stack would use one of the register pairs as the stack pointer, and >R etc. would temporarily move this to Z to do its operation, and then move it back again (I would leave Z free to be used as a temporary pointer like this, as the other register pairs can't be used as pointers). Of course, with this implementation, your code is not going to work because R> won't access the return-address which is actually on a different stack.

[toc] | [prev] | [next] | [standalone]

#44673

Raimond Dragomir wrote:

>> : foo1 r> drop  ;              \ 1 level poisoned
>> : foo2 r> drop r> drop  ;      \ 2 levels poisoned
>> : foo3  r> drop  ['] bar >r  ; \ at least 1 level poisoned
> 
> Who says that this usage is suppose to work in a system?

A number of systems say in their documentation that this works on them.

> Declare it undefined behaviour and you are done.

We rarely have UB in the Forth standard, we have IB.  And that means you 
have to document what happens if you claim to be standard.  Once it is 
documented, it is a feature, i.e. the user relies on it, and right so.

> Or if you want that these examples should work as expected
> (I can still ask: what's to be expected?)

A call pushes one cell return address onto the return stack, of course.  If 
you r> drop it, you won't return to that place.

> you may be better
> off with tail recursion optimization...

For sure it's easier that way.

> These kinds of examples are exactly like those in BEGIN WHILE UNTIL THEN.
> Very "clever" usage of an implementation defined behaviour
> of some words (or exploiting side effects of words not designed for
> that - like using "undocumented" instructions for a Z80 :)

BEGIN WHILE UNTIL THEN is standard.  It's not even just IB, it's supposed to 
work on every standard system.

It looks like you are stuck in the way C language lawyers think of the 
world: everything is undefined, and therefore, an implementer can be as 
sloppy as he likes.  We think that's making C a way more useless language 
than it used to be.

-- 
Bernd Paysan
"If you want it done right, you have to do it yourself"
net2o ID: kQusJzA;7*?t=uy@X}1GWr!+0qqp_Cn176t4(dQ*
http://bernd-paysan.de/

[toc] | [prev] | [next] | [standalone]

#44676

On Thursday, January 7, 2016 at 9:25:42 PM UTC-7, Bernd Paysan wrote:
> Raimond Dragomir wrote:
> 
> >> : foo1 r> drop  ;              \ 1 level poisoned
> >> : foo2 r> drop r> drop  ;      \ 2 levels poisoned
> >> : foo3  r> drop  ['] bar >r  ; \ at least 1 level poisoned
> > 
> > Who says that this usage is suppose to work in a system?
> 
> A number of systems say in their documentation that this works on them.
> 
> > Declare it undefined behaviour and you are done.
> 
> We rarely have UB in the Forth standard, we have IB.  And that means you 
> have to document what happens if you claim to be standard.  Once it is 
> documented, it is a feature, i.e. the user relies on it, and right so.

As Elizabeth Rather famously said: "Just declare a dependency and forge ahead!"

Of course, this is why ANS-Forth compliant programs can't be ported between compilers that are also ANS-Forth compliant. Everybody gets to declare themselves to be ANS-Forth compliant, but none of their stuff is compatible --- Elizabeth Rather is like the kindergarten teacher who says: "We can all be winners!"

The purpose of having a standard is portability --- if you don't understand this basic fact, then you don't deserve to be on the Forth-200x committee --- every member of the Forth-200x committee including yourself was appointed to that position by Elizabeth Rather, which is your only qualification.

[toc] | [prev] | [next] | [standalone]

#44681

Bernd Paysan <bernd.paysan@gmx.de> wrote:
> Raimond Dragomir wrote:
> 
>>> : foo1 r> drop  ;              \ 1 level poisoned
>>> : foo2 r> drop r> drop  ;      \ 2 levels poisoned
>>> : foo3  r> drop  ['] bar >r  ; \ at least 1 level poisoned
>> 
>> Who says that this usage is suppose to work in a system?
> 
> A number of systems say in their documentation that this works on them.
> 
>> Declare it undefined behaviour and you are done.
> 
> We rarely have UB in the Forth standard, we have IB.

We have "ambiguous conditions", which are "circumstances for which
this standard does not prescribe a specific behavior."  This is
remarkably similar to undefined behavior, which is "behavior for which
this standard imposes no requirements."

> And that means you have to document what happens if you claim to be
> standard.

In the cases of pushing junk onto the return stack and then returning,
or wild writes into memory, it's hard to say much beyond "shit
happens".

> Once it is documented, it is a feature, i.e. the user relies on it,
> and right so.

No: "The response to a particular ambiguous condition need not be the
same under all circumstances."

Andrew.

[toc] | [prev] | [next] | [standalone]

#44638

On 1/6/2016 8:19 AM, Johan Kotlinski wrote:
> Hi, I would like to bring up the problem of tail call elimination. I have it working in my STC Forth, but I am not too happy about my implementation and thought I should check if anyone has better ideas.
>
> The basic idea is of course very simple: If the generated machine code ends with
>
>    jsr XT ; jump to subroutine
>    rts
>
> replace with
>
>    jmp XT
>
> The problem is words like r>, which copies from the return stack to the parameter stack. If it is jmp'd instead of jsr'd to, a crash will happen, because the return address was never pushed and r> addressing will be off.
>
> The way I worked around this is to manually tag words like r> with a special flag, no-tail-call-elimination. Obviously this manual tagging is very error prone, it is easy to forget, and errors can go unnoticed for a long time.
>
> Surely others must have run into this problem before, are there better ways to do it?

Perhaps I'm a bit confused.  Never having written a Forth myself, I 
haven't given much thought to a problem like this.  Should I assume R> 
is written as a subroutine and in essence nips the second item on the 
return stack because the top item is the return address needed at the 
end of the R> word?  So when this code is jumped to rather than called, 
the wrong value is removed from the stack, no?

-- 

Rick

[toc] | [prev] | [next] | [standalone]

#44640

On 1/6/16 7:24 AM, rickman wrote:
> On 1/6/2016 8:19 AM, Johan Kotlinski wrote:
>> Hi, I would like to bring up the problem of tail call elimination. I
>> have it working in my STC Forth, but I am not too happy about my
>> implementation and thought I should check if anyone has better ideas.
>>
>> The basic idea is of course very simple: If the generated machine code
>> ends with
>>
>>    jsr XT ; jump to subroutine
>>    rts
>>
>> replace with
>>
>>    jmp XT
>>
>> The problem is words like r>, which copies from the return stack to
>> the parameter stack. If it is jmp'd instead of jsr'd to, a crash will
>> happen, because the return address was never pushed and r> addressing
>> will be off.
>>
>> The way I worked around this is to manually tag words like r> with a
>> special flag, no-tail-call-elimination. Obviously this manual tagging
>> is very error prone, it is easy to forget, and errors can go unnoticed
>> for a long time.
>>
>> Surely others must have run into this problem before, are there better
>> ways to do it?
>
> Perhaps I'm a bit confused.  Never having written a Forth myself, I
> haven't given much thought to a problem like this.  Should I assume R>
> is written as a subroutine and in essence nips the second item on the
> return stack because the top item is the return address needed at the
> end of the R> word?  So when this code is jumped to rather than called,
> the wrong value is removed from the stack, no?

It's dangerous to "assume" anything about how a Forth is written, unless 
you are using a Forth whose source you have and are willing to accept 
being dependent on that particular implementation, or are working in 
your own implementation that you control.

Working with tail-call elimination is something an implementor can do, 
not a user.

Cheers,
Elizabeth

-- 
==================================================
Elizabeth D. Rather   (US & Canada)   800-55-FORTH
FORTH Inc.                         +1 310.999.6784
5959 West Century Blvd. Suite 700
Los Angeles, CA 90045
http://www.forth.com

"Forth-based products and Services for real-time
applications since 1973."
==================================================

[toc] | [prev] | [next] | [standalone]

#44644

El miércoles, 6 de enero de 2016, 10:19:58 (UTC-3), Johan Kotlinski  escribió:
> Hi, I would like to bring up the problem of tail call elimination. I have it working in my STC Forth, but I am not too happy about my implementation and thought I should check if anyone has better ideas.
> 
> The basic idea is of course very simple: If the generated machine code ends with
> 
>   jsr XT ; jump to subroutine
>   rts
> 
> replace with
> 
>   jmp XT
> 
> The problem is words like r>, which copies from the return stack to the parameter stack. If it is jmp'd instead of jsr'd to, a crash will happen, because the return address was never pushed and r> addressing will be off.
> 
> The way I worked around this is to manually tag words like r> with a special flag, no-tail-call-elimination. Obviously this manual tagging is very error prone, it is easy to forget, and errors can go unnoticed for a long time.
> 
> Surely others must have run into this problem before, are there better ways to do it?
> 
> Thanks,
> Johan

I only have this problem with one word, SHOW (like colorforth) this word make the rest of definition a loop por interation.
but "SHOW ;" not have sense then is not a problem.
My forth have flow control words in a diferent implementation then this not have problem too.

[toc] | [prev] | [next] | [standalone]

#44657

Dear Johan,

I have implemented Tail-Call in Mecrisp-Ice for J1a CPU, my solution is
to always inline problematic things like >r r@ r> and of course a lot
of normal, but very short instructions. It will improve execution speed,
and it is quite simple to add basic inlining to an STC-Forth.

The non-symmetric uses of the return stack will either crash, according
to ANS :-) - or simply require a bit of code-generator knowledge 
from the user.

Next step would be including constant folding, too.

Just see the English translation of my talk on 32C3:
https://www.youtube.com/watch?v=a8Dg08DkILo

Matthias

[toc] | [prev] | [next] | [standalone]

#44661

Op Thu, 07 Jan 2016 10:56:35 +0100 schreef Matthias Koch:

> Dear Johan,
> 
> I have implemented Tail-Call in Mecrisp-Ice for J1a CPU, my solution is
> to always inline problematic things like >r r@ r> and of course a lot
> of normal, but very short instructions. It will improve execution speed,
> and it is quite simple to add basic inlining to an STC-Forth.
> 
> The non-symmetric uses of the return stack will either crash, according
> to ANS :-) - or simply require a bit of code-generator knowledge 
> from the user.
ANS never mentions the word crash. It's just undefined  behavior.
Your _implementation_ may crash or much less likely run happily without
blinking an eye.

groet Coos

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.forth

csiph-web