local buffers and tail-call optimization

If a Forth system supports local buffers (or another locals extension
that produces addresses of local memory, e.g., Gforth's
variable-flavoured locals), then it has to define the lifetime of the
memory the address points to. Typically the lifetime will be until
the end of the definition that the buffer was defined in.

This inhibits tail-call optimization; consider:

: bar ( addr -- )
... ;

: foo { | [ 1 ] x } x bar ;

in the syntax proposed by Stephen Pelc or

: foo 1 lbuffer bar ;

in a syntax suggested by others. The allocated buffer must stay alive
across the call to BAR, because it is used in BAR, so the deallocation
of the buffer must happen after the call to BAR, and BAR is no longer
a tail-call and can therefore not be optimized.

Consider the contrast to ordinary (value-flavoured locals):

: flip { a } a bar ;

Here the local can be deallocated right after its last use, before the
call to BAR, and therefore that call is a tail-call. More generally,
as long as there are only value-flavoured locals in the definition,
the rules for tail-call optimization are the same as without locals.

So it's a good idea to define local buffers in a way that does not
make it too hard for the compiler to know whether a definition
contains a local buffer definition or not. Stephen Pelc's proposal
has this property. As for LBUFFER, if we want it, we should specify it
as a compile-only word.

- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: http://www.forth200x.org/forth200x.html
EuroForth 2008: http://www.euroforth.org/ef08.html

On Fri, 29 Aug 2008 12:20:25 GMT, anton@mips.complang.tuwien.ac.at
(Anton Ertl) wrote:

>If a Forth system supports local buffers (or another locals extension
>that produces addresses of local memory, e.g., Gforth's
>variable-flavoured locals), then it has to define the lifetime of the
>memory the address points to. Typically the lifetime will be until
>the end of the definition that the buffer was defined in.
>
>This inhibits tail-call optimization; consider:
>
>: bar ( addr -- )
> ... ;
>
>: foo { | [ 1 ] x } x bar ;
>
>in the syntax proposed by Stephen Pelc or
>
>: foo 1 lbuffer bar ;

In practice this not very important, as (especially with
buffers as opposed to values) bar will manipulate the buffer
from which a result will be extracted.

: foo { | [ /struct ] x }
x bar x manipulate x .bField @
;

is a more realistic set of operations, which would inhibit
tail call optimisation anyway, but does not inhibit VFX's
source inliner, iForth's tokeniser, or binary inliners.

Given the ingenuity of programmers, and widespread recognition
that return addresses are on the return stack (despite what
any standard may say), determining the routines that are safe
for tail optimisation is a non-trivial exercise, as any return
stack manipulation propagates in the call tree. Practical use
trumps any standard IMHO.

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

stephenXXX@mpeforth.com (Stephen Pelc) writes:
>On Fri, 29 Aug 2008 12:20:25 GMT, anton@mips.complang.tuwien.ac.at
>(Anton Ertl) wrote:
>
>>If a Forth system supports local buffers (or another locals extension
>>that produces addresses of local memory, e.g., Gforth's
>>variable-flavoured locals), then it has to define the lifetime of the
>>memory the address points to. Typically the lifetime will be until
>>the end of the definition that the buffer was defined in.
>>
>>This inhibits tail-call optimization; consider:
>>
>>: bar ( addr -- )
>> ... ;
>>
>>: foo { | [ 1 ] x } x bar ;
>>
>>in the syntax proposed by Stephen Pelc or
>>
>>: foo 1 lbuffer bar ;
>
>In practice this not very important, as (especially with
>buffers as opposed to values) bar will manipulate the buffer
>from which a result will be extracted.
>
>: foo { | [ /struct ] x }
> x bar x manipulate x .bField @
>;

Another practical use would be to put something in the buffer that is
then read by the callee, e.g.:

: emit ( c -- )
1 lbuffer tuck c!
1 type ;

Here the call to TYPE looks like a tail-call, but it isn't.

>Given the ingenuity of programmers, and widespread recognition
>that return addresses are on the return stack (despite what
>any standard may say), determining the routines that are safe
>for tail optimisation is a non-trivial exercise, as any return
>stack manipulation propagates in the call tree.

It's non-trivial, but doable to analyse it if you want to go for that.
The other option is to make it the programmers' responsibility to turn
off tail-call optimization and inliners if they do return-address
manipulation stuff.

> Practical use
>trumps any standard IMHO.

Sure, but I don't think that return-address manipulation is used
widely enough to justify any more effort than to provide a switch for
turning off optimizations that don't agree with them.

- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: http://www.forth200x.org/forth200x.html
EuroForth 2008: http://www.euroforth.org/ef08.html

On Aug 30, 10:02*am, an...@mips.complang.tuwien.ac.at (Anton Ertl)
wrote:
> stephen...@mpeforth.com (Stephen Pelc) writes:
> >On Fri, 29 Aug 2008 12:20:25 GMT, an...@mips.complang.tuwien.ac.at
> >(Anton Ertl) wrote:
>
> >>If a Forth system supports local buffers (or another locals extension
> >>that produces addresses of local memory, e.g., Gforth's
> >>variable-flavoured locals), then it has to define the lifetime of the
> >>memory the address points to. *Typically the lifetime will be until
> >>the end of the definition that the buffer was defined in.
>
> >>This inhibits tail-call optimization; consider:
>
> >>: bar ( addr -- )
> >> *... ;
>
> >>: foo { | [ 1 ] x } x bar ;
>
> >>in the syntax proposed by Stephen Pelc or
>
> >>: foo 1 lbuffer bar ;
>
> >In practice this not very important, as (especially with
> >buffers as opposed to values) bar will manipulate the buffer
> >from which a result will be extracted.
>
> >: foo { | [ /struct ] x }
> > *x bar *x manipulate *x .bField @
> >;
>
> Another practical use would be to put something in the buffer that is
> then read by the callee, e.g.:
>
> : emit ( c -- )
> *1 lbuffer tuck c!
> *1 type ;
>
> Here the call to TYPE looks like a tail-call, but it isn't.

In my syntax this becomes

: emit2 ( c -- )
1 lbuffer: tmp
tmp c!
tmp 1 type ;

The code generated is

see emit2
A490FC 40787F 33 C80000 5 normal EMIT2

40787F 8D6424FC lea esp , [esp-4h]
407883 8D0424 lea eax , [esp]
407886 8818 mov [eax] , bl
407888 8D1C24 lea ebx , [esp]
40788B 895DFC mov [ebp-4h] , ebx
40788E BB01000000 mov ebx , # 1h
407893 8D6DFC lea ebp , [ebp-4h]
407896 E89198FFFF call TYPE
40789B 8D642404 lea esp , [esp+4h]
40789F C3 ret near
ok

The local buffer prevents a tail jmp as the buffer needs to be
released

>
> >Given the ingenuity of programmers, and widespread recognition
> >that return addresses are on the return stack (despite what
> >any standard may say), determining the routines that are safe
> >for tail optimisation is a non-trivial exercise, as any return
> >stack manipulation propagates in the call tree.
>
> It's non-trivial, but doable to analyse it if you want to go for that.
> The other option is to make it the programmers' responsibility to turn
> off tail-call optimization and inliners if they do return-address
> manipulation stuff.

This is what I do with the word NO-TAIL-JMP

: t1 r> r@ 32 dump >r ; no-tail-jmp

: t2 t1 ;
see t2
A49128 4078D0 6 C80000 5 normal T2

4078D0 E8CBFFFFFF call T1
4078D5 C3 ret near
ok

but it don't propagate up the chain

: t3 t2 ; ok
see t3
A4913C 4078D6 5 C80000 5 normal T3

4078D6 E9F5FFFFFF jmp T2
ok

The problem with inlining is even simpler to solve. My system does not
do automatic inlining! You have to declare it manually with :m

:m t4 t3 ; ok
see t4
A49150 C885DA 0 A49164 5 macro T4
t3
ok
: t5 t4 ; ok
see t5
A4916C 4078DB 5 C80000 5 normal T5

4078DB E9F6FFFFFF jmp T3
ok

Peter

> > Practical use
> >trumps any standard IMHO.
>
> Sure, but I don't think that return-address manipulation is used
> widely enough to justify any more effort than to provide a switch for
> turning off optimizations that don't agree with them.
>
> - anton
> --
> M. Anton Ertl *http://www.complang.tuwien.ac.at/anton/home.html
> comp.lang.forth FAQs:http://www.complang.tuwien.ac.at/forth/faq/toc.html
> * * *New standard:http://www.forth200x.org/forth200x.html
> * *EuroForth 2008:http://www.euroforth.org/ef08.html

Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
> If a Forth system supports local buffers (or another locals extension
> that produces addresses of local memory, e.g., Gforth's
> variable-flavoured locals), then it has to define the lifetime of the
> memory the address points to. Typically the lifetime will be until
> the end of the definition that the buffer was defined in.

> This inhibits tail-call optimization; consider:

> : bar ( addr -- )
> ... ;

> : foo { | [ 1 ] x } x bar ;

> in the syntax proposed by Stephen Pelc or

> : foo 1 lbuffer bar ;

> in a syntax suggested by others. The allocated buffer must stay
> alive across the call to BAR, because it is used in BAR, so the
> deallocation of the buffer must happen after the call to BAR, and
> BAR is no longer a tail-call and can therefore not be optimized.

Sure it can. With one fairly obvious implementation of local buffers,
you push onto the return stack the address of a thunk that will
deallocate the buffer. At the end of the definition you can jump to
bar; when bar exits it returns to the thunk, which does the
deallocation.

Andrew.

In article <evWdnRDf97RBSCPVnZ2dnUVZ8qLinZ2d@supernews.com> ,
Andrew Haley <andrew29@littlepinkcloud.invalid> wrote:
>Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>> If a Forth system supports local buffers (or another locals extension
>> that produces addresses of local memory, e.g., Gforth's
>> variable-flavoured locals), then it has to define the lifetime of the
>> memory the address points to. Typically the lifetime will be until
>> the end of the definition that the buffer was defined in.
>
>> This inhibits tail-call optimization; consider:
>
>> : bar ( addr -- )
>> ... ;
>
>> : foo { | [ 1 ] x } x bar ;
>
>> in the syntax proposed by Stephen Pelc or
>
>> : foo 1 lbuffer bar ;
>
>> in a syntax suggested by others. The allocated buffer must stay
>> alive across the call to BAR, because it is used in BAR, so the
>> deallocation of the buffer must happen after the call to BAR, and
>> BAR is no longer a tail-call and can therefore not be optimized.
>
>Sure it can. With one fairly obvious implementation of local buffers,
>you push onto the return stack the address of a thunk that will
>deallocate the buffer. At the end of the definition you can jump to
>bar; when bar exits it returns to the thunk, which does the
>deallocation.

This is automatical with coroutine calls

: R-ALLOT R> SWAP (R-ALLOT) >R CO (R-DALLOT) ;

Where (R-ALLOT) is a code word that adds to the return stack pointer.

The buffer is to be found in the calling word at a cell offset
from the return stack pointer, typical I.
This is intended for systems with a true return stack.

With an S-stack ala tforth/iforth (or a fake return stack) it is even
easier:

: R-ALLOT (S-ALLOT) CO (S-DALLOT) ;

>
>Andrew.

P.S. I'm opposed to allocating space on a 64 k return stack if there
is a 2 Gbyte data stack, but that is an other story.

Groetjes Albert

--
--
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- like all pyramid schemes -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst