TAIL (optimised tail call)
m_l_g3
Anyway, I welcome anyone to use the proposed word.
PROPOSAL
========
TAIL ( "name" -- )
Skip leading space delimiters. Parse name delimited by a space.
Perform name's compilation semantics. Modify the run-time semantics
compiled for name (later referred to as "acion of name") in the
following way:
Run-time: ( r: nest-sys -- )
Remove nest-sys from the return stack, and invoke the action of name
so that nest-sys will be used as information about the calling
definition. Information about the current (actually calling)
definition will not be passed during this invocation. (In other words,
a jump to a function is performed instead of a call.)
An ambiguous condition exists if no single execution token for the
original run-time semantics of name exists in the system.
In particular, TAIL RECURSE is iteration rather than recursion, and
TAIL NOOP is equivalent to EXIT (where NOOP is a definition that does
nothing).
Example
=======
: DEFER CREATE ['] NOOP , DOES> @ TAIL EXECUTE ; \ no extra return
address
DISCUSSION
==========
This proposal introduces the notion of a tail call. A tail call is
iteration rather than recursion.
The proposed wording allows for such usages as
TAIL POSTPONE my-immediate-word
and
TAIL RECURSE
Other programming languages, such as Scheme, do distinguish tail calls
from calls with return.
REFERENCE IMPLEMENTATION
========================
\ reference implementation of TAIL
\ (p) M.L.Gassanenko, 28.10.2009
cr .( ==tail.f==) cr
0 CONSTANT _VFX
_VFX 0= CONSTANT _Win32Forth
_VFX [IF]
\ the version for VFX Forth, a highly optimized native code compiler
: tail
postpone [o/f] \ flush optimizer
[-opt \ disable optimizations
here >r
\ parse a name
bl word find dup 0= abort" ?"
\ perform its compilation semantics
1 = if execute else compile, then
\ verify there's a call (and don't care if there's more)
r@ c@ $e8 <> abort" cannot convert to tail call"
\ fetch call destination (which is xt)
r@ 1+ @ r@ 5 + +
\ remove the run-time semantics of parsed name
r> dp !
>r \ keep call destination
opt] \ restore the optimizer's mode
\ generate a jump to the call destination
r> postpone literal postpone >r postpone exit
; immediate
(( Note that this version conflicts with the VFX inliner
: tail
postpone [o/f]
[-opt
here >r
bl word find dup 0= abort" ?"
1 = if execute else compile, then
r@ c@ $e8 <> abort" cannot convert to tail call"
$e9 r> c!
opt]
; immediate
))
[ELSE]
\ the version for Win32Forth, a classical ITC model
anew ==tail==
0 [IF]
\ an excerpt from sources that explains how the interpreter works
EXEC is
jmp [eax]
NEXT is
mov eax, 0 [esi]
add esi, # 4
jmp [eax]
NCODE UNNEST ( -- ) \ exit the current Forth definition
mov esi, 0 [ebp]
add ebp, # 4
next c;
NCODE EXECUTE ( xt -- ) \ go perform the Forth function
\ whose address is "xt"
mov eax, ebx
pop ebx
exec c;
NCODE LIT ( -- n ) \ push the literal value
\ following LIT in the
\ dictionary onto the data stack
push ebx
mov eax, 4 [esi]
mov ebx, 0 [esi]
add esi, # 8
exec c;
[THEN]
0 [IF] \ this code works
NCODE EXIT&EXECUTE ( xt -- )
\ like in EXIT
mov esi, 0 [ebp]
add ebp, # 4
\ like in EXECUTE
mov eax, ebx
pop ebx
exec c;
: (TAIL) R> @ EXIT&EXECUTE ;
[ELSE] \ this code works too
NCODE (TAIL) ( xt -- )
\ like in next
mov eax, 0 [esi]
\ like in EXIT
mov esi, 0 [ebp]
add ebp, # 4
\ like in next
exec c;
[THEN]
: TAIL POSTPONE (TAIL) BL WORD FIND DUP 0= ABORT" ?" 1 = IF EXECUTE
ELSE COMPILE, THEN ; IMMEDIATE
\ Disable Win32Forth stack depth change warnigs
HERE ] DROP EXIT [ ' WARNMSG >BODY 8 CMOVE
[THEN]
\ === tests and examples of usage -- worth reading !!! ===
CR .( testing... )
: test1a rot * -rot * tail + ;
: test1b rot * -rot * + ;
: test1c rot * -rot * tail + 0 ; \ 0 is not executed
depth 0 ?pairs
2 3 4 5 test1a depth 1 ?pairs $17 ?pairs
2 3 4 5 test1b depth 1 ?pairs $17 ?pairs
2 3 4 5 test1c depth 1 ?pairs $17 ?pairs
.( test1_ok )
\ sum numbers from 0 to i the hard way.
\ A recursion would overflow the return stack.
: isum ( d-sum i -- d-sum' ) dup >r M+ r> 1- dup if tail recurse then
drop ;
: test-isum ( n -- ) >r 0 0 r@ isum r> dup 1+ m* d2/ 2dup d. d= 0=
abort" wrong result" ;
10 test-isum depth 0 ?pairs
1000000 test-isum depth 0 ?pairs
.( test2_ok )
\ we can define a DEFER that does not leave an extra address
\ on the return stack.
: mydefer create ['] noop , does> @ tail execute ;
: myis ' >body ! ;
mydefer myrp@
' rp@ myis myrp@
rp@ myrp@ ?pairs \ the same return stack depth
.( test3_ok )
\ and now, some mutually recursive functions
mydefer [MYELSE] immediate
mydefer skip-nested
: _skip-nested
bl word count
dup 0= if 2drop refill 0= abort" premature end of stream"
tail skip-nested
then
2dup S" [MYTHEN]" compare 0= if 2drop exit then
2dup S" [MYIF]" compare 0= if 2drop skip-nested tail skip-nested
then
2drop tail skip-nested
;
: _[else]
bl word count
dup 0= if 2drop refill 0= abort" premature end of stream"
tail postpone [MYELSE]
then
2dup S" [MYTHEN]" compare 0= if 2drop exit then
2dup S" [MYELSE]" compare 0= if 2drop exit then
2dup S" [MYIF]" compare 0= if 2drop skip-nested tail postpone
[MYELSE] then
2drop tail postpone [MYELSE]
;
' _[else] myis [MYELSE]
' _skip-nested myis skip-nested
: [MYIF] 0= if postpone [MYELSE] then ; immediate
: [MYTHEN] ; immediate
1 [MYIF] 1234 [MYELSE] 1 2 ?pairs [MYTHEN] 2345
2345 ?pairs 1234 ?pairs
.( test4_ok )
0 [MYIF] 1 2 ?pairs [MYELSE] 3456 [MYTHEN] 4567
4567 ?pairs 3456 ?pairs
.( test5_ok )
0 [MYIF]
1 2 ?pairs
0 [MYIF] 1 2 ?pairs [MYELSE] 3 4 ?pairs [MYTHEN]
4 5 ?pairs
[MYELSE]
0 [MYIF] 1 2 ?pairs [MYELSE] 3456 [MYTHEN] 4567
8901
[MYTHEN] 9012
9012 ?pairs 8901 ?pairs 4567 ?pairs 3456 ?pairs
.( test6_ok )
1 [MYIF]
0 [MYIF] 1 2 ?pairs [MYELSE] 3456 [MYTHEN] 4567
8901
[MYELSE]
1 2 ?pairs
0 [MYIF] 1 2 ?pairs [MYELSE] 3 4 ?pairs [MYTHEN]
4 5 ?pairs
[MYTHEN] 9012
9012 ?pairs 8901 ?pairs 4567 ?pairs 3456 ?pairs
.( test7_ok )
\ The unstandard but important technique of
\ return address manipulations also benefits from TAIL
\ we define two branching words
: myskip r> cell+ >r ;
: mybranch r> @ >r ;
\ and a third word in terms of the above two!
\ one cannot do that without TAIL
: my?branch if tail myskip else tail mybranch then ;
\ let us demonstrate that the above stuff works
: myif postpone my?branch here 0 , 22 ; immediate
: myahead postpone mybranch here 0 , 22 ; immediate
_VFX [IF]
\ need to tell the compiler it's time to flush cache
: mythen 22 ?pairs 0 , postpone [o/f] here swap ! ; immediate
[ELSE]
: mythen 22 ?pairs here swap ! ; immediate
[THEN]
: myelse postpone myahead 2swap postpone mythen ; immediate
: mymax 2dup < myif nip myelse drop mythen ;
: test8a myif 123 myelse 456 mythen 789 ;
\ what is interesting is that this works on both Win32Forth and VFX
1 2 mymax 2 ?pairs
2 1 mymax 2 ?pairs
0 test8a 789 ?pairs 456 ?pairs
1 test8a 789 ?pairs 123 ?pairs
.( test8_ok )
Aleksej Saushev
> I do not know if I should make a formal proposal for the Forth200x...
> Anyway, I welcome anyone to use the proposed word.
>
> PROPOSAL
> ========
>
> TAIL ( "name" -- )
Very bad name. It has closer connections to list processing
than to recursion.
> Skip leading space delimiters. Parse name delimited by a space.
> Perform name's compilation semantics. Modify the run-time semantics
> compiled for name (later referred to as "acion of name") in the
> following way:
>
> Run-time: ( r: nest-sys -- )
> Remove nest-sys from the return stack, and invoke the action of name
> so that nest-sys will be used as information about the calling
> definition. Information about the current (actually calling)
> definition will not be passed during this invocation. (In other words,
> a jump to a function is performed instead of a call.)
If it is "jump", global "goto", why do you call it "tail"?
--
HE CE3OH...
m_l_g3
Because it is "tail call" and "tail recursion". And the key word
"call"
is not used in programming languages.
Aleksej Saushev
> Aleksej Saushev 写锟斤拷:
>> m_l_g3 <m_l...@yahoo.com> writes:
>>
>> If it is "jump", global "goto", why do you call it "tail"?
>
> Because it is "tail call" and "tail recursion".
You write yourself that it isn't neither "tail call" nor "tail recursion":
1. "In other words, a jump to a function is performed instead of a call."
2. "TAIL NOOP is equivalent to EXIT"
> And the key word "call" is not used in programming languages.
You've heard about wikipedia, haven't you?
http://en.wikipedia.org/wiki/Fortran#FORTRAN_II
Three different Common Lisp implementations describe it this way:
1. :CALL is the symbol :CALL, lies in #<PACKAGE KEYWORD>, is accessible
in 19 packages CHARSET, CLOS, COMMON-LISP, COMMON-LISP-USER,
CS-COMMON-LISP, CS-COMMON-LISP-USER, CUSTOM, EXPORTING, EXT, FFI, GRAY,
GSTREAM, I18N, KEYWORD, POSIX, REGEXP, SCREEN, SOCKET, SYSTEM,
is a keyword, a constant, value: :CALL.
2. :CALL - keyword
3. CALL names a constant variable.
Various assemblers use "call" to express a subroutine call rather than
unconditional jump.
Rather than inventing your own terms, you'd better learn what it is in
other languages. There "tail call" is a regular function call, where it
is immediatly followed by return and thus may be optimized away. When
you mark tail calls explicitly, effectively you write "goto". That's all.
Lack of understanding leads to further confusion.
--
HE CE3OH...
Jerry Avins
...
> Various assemblers use "call" to express a subroutine call rather than
> unconditional jump.
Do any use an unconditional jump? How do they return?
...
Jerry
--
Engineering is the art of making what you want from things you can get.
???????????????????????????????????????????????????????????????????????
Aleksej Saushev
> Aleksej Saushev wrote:
>
> ...
>
>> Various assemblers use "call" to express a subroutine call rather than
>> unconditional jump.
>
> Do any use an unconditional jump? How do they return?
Sarcasm? Irony?
By jump into the opposite side! (Same way as AGAIN/REPEAT/UNTIL do.)
If no irony meant, then wikipedia explains you what the whole stuff is about:
http://en.wikipedia.org/wiki/Tail_call
--
HE CE3OH...
Jerry Avins
No irony. I wasn't referring to tail calls., but to subroutine calls,
following what you wrote. I'm familiar with both CALL and JSR (Jump to
SubRoutine) ass assembler instructions. Both leave a return address
somewhere (on the return stack in modern architectures).
�����������������������������������������������������������������������
Aleksej Saushev
> Aleksej Saushev wrote:
>> Jerry Avins <j...@ieee.org> writes:
>>
>>> Aleksej Saushev wrote:
>>>
>>> ...
>>>
>>>> Various assemblers use "call" to express a subroutine call rather than
>>>> unconditional jump.
>>> Do any use an unconditional jump? How do they return?
>>
>> Sarcasm? Irony?
>>
>> By jump into the opposite side! (Same way as AGAIN/REPEAT/UNTIL do.)
>>
>> If no irony meant, then wikipedia explains you what the whole stuff is about:
>> http://en.wikipedia.org/wiki/Tail_call
>
> No irony. I wasn't referring to tail calls., but to subroutine
> calls, following what you wrote. I'm familiar with both CALL and
> JSR (Jump to SubRoutine) ass assembler instructions. Both leave
> a return address somewhere (on the return stack in modern
> architectures).
Does ARM count as modern? 'Cause it uses link register.
To my knowledge, other not-so-archaic architectures (SPARC?) do the same.
If you move away from discussing tail calls, then I don't understand
your questions. How do they relate? Processors support jumps and calls,
tail calls can be optimized away by using jump instead of call+return.
That's all.
--
HE CE3OH...
Jerry Avins
> Jerry Avins <j...@ieee.org> writes:
>
>> Aleksej Saushev wrote:
>>> Jerry Avins <j...@ieee.org> writes:
>>>
>>>> Aleksej Saushev wrote:
>>>>
>>>> ...
>>>>
>>>>> Various assemblers use "call" to express a subroutine call rather than
>>>>> unconditional jump.
>>>> Do any use an unconditional jump? How do they return?
>>> Sarcasm? Irony?
>>>
>>> By jump into the opposite side! (Same way as AGAIN/REPEAT/UNTIL do.)
>>>
>>> If no irony meant, then wikipedia explains you what the whole stuff is about:
>>> http://en.wikipedia.org/wiki/Tail_call
>> No irony. I wasn't referring to tail calls., but to subroutine
>> calls, following what you wrote. I'm familiar with both CALL and
>> JSR (Jump to SubRoutine) ass assembler instructions. Both leave
>> a return address somewhere (on the return stack in modern
>> architectures).
>
> Does ARM count as modern? 'Cause it uses link register.
> To my knowledge, other not-so-archaic architectures (SPARC?) do the same.
Well, a link register is a place to put a return address. The Nova 1200
makes that familiar.
> If you move away from discussing tail calls, then I don't understand
> your questions. How do they relate? Processors support jumps and calls,
> tail calls can be optimized away by using jump instead of call+return.
> That's all.
We had a slight language problem. Conversation cleared it up.
m_l_g3
> Aleksej Saushev wrote:
> > Jerry Avins <j...@ieee.org> writes:
> >> Aleksej Saushev wrote:
> >>> Jerry Avins <j...@ieee.org> writes:
> >>>> Aleksej Saushev wrote:
Folks, a discussion whether or not PL/I was the last high-level
language that used the word CALL for procedure invocation, as well as
psychological aspects of the FORTRAN programming of 60-es (at that
time writing a SUBROUTINE apparently was a great event in programmer's
life, so punching in this long word was probably meant as a kind of
celebration rite), IS COMPLETELY OFF-TOPIC IN THIS THREAD.
Criticism, please. (And a constructive one is more welcome than non-
constructive.)
Aleksej Saushev
> On Oct 29, 4:11О©╫am, Jerry Avins <j...@ieee.org> wrote:
>> Aleksej Saushev wrote:
>> > Jerry Avins <j...@ieee.org> writes:
>> >> Aleksej Saushev wrote:
>> >>> Jerry Avins <j...@ieee.org> writes:
>> >>>> Aleksej Saushev wrote:
> [snipped as irrelevant]
>
> Folks, a discussion whether or not PL/I was the last high-level
> language that used the word CALL for procedure invocation, as well as
> psychological aspects of the FORTRAN programming of 60-es (at that
> time writing a SUBROUTINE apparently was a great event in programmer's
> life, so punching in this long word was probably meant as a kind of
> celebration rite), IS COMPLETELY OFF-TOPIC IN THIS THREAD.
It was you, who brought that as an argument, now you cry aloud this is
off-topic.
> Criticism, please. (And a constructive one is more welcome than non-
> constructive.)
You don't seem to be ready for criticism of any kind. When I show you
two strong reasons why this shouldn't be called "tail", you claim it
irrelevant.
--
HE CE3OH...
Andrew Haley
> Criticism, please. (And a constructive one is more welcome than non-
> constructive.)
With any proposed extension, the questions always are:
1. Is this thing useful?
2. Can it already be done in Standard Forth?
3. Is this the best way to do it?
As for 1, I'm not entirely sure. In Scheme, it's idiomatic to use
tail recursion to express iteration, but that's not true of Forth. I
suppose there are cases where using tail calls rather than more
conventional iteration make for a more elegant result. It'd be
interesting to see some examples.
As for 2, no, it can't.
As for 3, maybe it makes sense to define FOO EXIT as a tail call [*],
and let the compiler do the work. It won't break any existing
standard Forth programs and it provides a new facility, but it
complicates the compiler. Doing this is well-established practice,
going back at least to Novix in 1983.
Andrew.
[*] With a few obvious exceptions for FOO such as >R, immediate words,
etc.
Albert van der Horst
Andrew Haley <andr...@littlepinkcloud.invalid> wrote:
>m_l_g3 <m_l...@yahoo.com> wrote:
>
>> Criticism, please. (And a constructive one is more welcome than non-
>> constructive.)
>
>With any proposed extension, the questions always are:
>
>1. Is this thing useful?
>2. Can it already be done in Standard Forth?
>3. Is this the best way to do it?
>
>As for 1, I'm not entirely sure. In Scheme, it's idiomatic to use
>tail recursion to express iteration, but that's not true of Forth. I
Your questions are good.
For colorforth it is very idiomatic, useful because other loop
constructs are missing, and totally automatic. An extra keyword
is superfluous, because the compiler can sort it out.
Insofar it is useful for ISO Forth's the compiler can sort it out.
>
>Andrew.
>
Groetjes Albert
--
--
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst
m_l_g3
> m_l_g3 <m_l...@yahoo.com> wrote:
>
> > Criticism, please. (And a constructive one is more welcome than non-
> > constructive.)
>
> With any proposed extension, the questions always are:
>
> 1. Is this thing useful?
> 2. Can it already be done in Standard Forth?
> 3. Is this the best way to do it?
Indeed, very good questions. But if I comment on all of them in the
same post, it will be long and unreadable. So:
>maybe it makes sense to define FOO EXIT as a tail call [*],
[snip]
>[*] With a few obvious exceptions for FOO such as >R, immediate words,
etc.
The exceptions are NOT obvious.
Let t denote a code fragment, N denote a single-cell value, and ==
will denote functional equivalence.
Definition.
R1( t ) is such code fragment that
ForAll N:
N >R R1( t ) == t N >R
Examples:
R1( DUP ) == DUP
R1( >R ) == R> SWAP >R >R
R1( EXIT ) == RDROP EXIT
For the latter one, indeed, N >R RDROP EXIT == EXIT N >R
Let us introduce a notation for calls:
y == nest[ t EXIT ] if y is defined as : y t ;
There's a theorem about code fragment call equivalence:
ForAll t:
t == nest[ R1( t ) EXIT ]
In particular,
t == nest[ t EXIT ] if t == R1( t )
(The latter condition, by the way, is what the standard requires for
code definition bodies.)
So the exceptions are not obvious and not few.
> As for 3, maybe it makes sense to define FOO EXIT as a tail call [*],
> and let the compiler do the work. It won't break any existing
> standard Forth programs
In fact, I am interested in techniques beyond the standard such as
return address manipulations, control transfers, and backtracking.
These methods are not explicitly supported by the current standard,
but on the other hand there is no conflict. The standard is compatible
with such practices. If we define FOO EXIT as a tail call, this will
break a lot of valuable code with environmental dependencies.
m_l_g3
> m_l_g3 <m_l...@yahoo.com> wrote:
>
> > Criticism, please. (And a constructive one is more welcome than non-
> > constructive.)
>
> With any proposed extension, the questions always are:
>
> 1. Is this thing useful?
> 2. Can it already be done in Standard Forth?
> 3. Is this the best way to do it?
>
> As for 1, I'm not entirely sure. In Scheme, it's idiomatic to use
> tail recursion to express iteration, but that's not true of Forth. I
> suppose there are cases where using tail calls rather than more
> conventional iteration make for a more elegant result. It'd be
> interesting to see some examples.
\ a hash: maps a string onto a cell
\ The purpose of this code is to compare
\ iteration via tail recursion and iteration via loops.
\ The code uses a linked list of siblings where an array
\ would be more appropriate.
: sfield create dup , does> @ + ;
: sfield@ sfield does> @ + @ ;
: sfield! sfield does> @ + ! ;
: pluck 2 pick ;
0
sfield@ sibling sfield! sibling! CELL+
sfield@ descendant sfield! descendant! CELL+
constant /tree-elem
/tree-elem
sfield@ hkey sfield! hkey! CELL+
sfield@ hval sfield! hval! CELL+
constant /elem
\ ------------------------------------------
\ find an item in the tree, tail recursion
\ words: 34
\ lines_of_code: 16
: hfind ( addr len ptr -- val )
pluck c@ swap
begin ( addr len c ptr )
dup
while
2dup hkey =
if nip -rot 1 /string rot ( a' l' ptr )
over
if descendant TAIL RECURSE
else hval nip nip EXIT
then
then
sibling
repeat ( addr len 0 )
nip nip nip
;
\ ------------------------------------------
\ find an item in the tree, loops
\ words: 40
\ lines _of_code: 21
: find-sibling ( c ptr -- ptr' )
begin
dup
while
2dup hkey <>
while
sibling
repeat then
nip
;
: h-find ( addr len ptr -- val )
begin
pluck c@ swap find-sibling
-rot 1 /string rot
dup
while
over 0= if nip nip hval exit then
descendant
repeat
nip nip
;
\ ------------------------------------------
\ test data
here 0 , 0 , char p , 111 , \ cop
here swap , 0 , char b , 112 , \ cob
here swap , 0 , char d , 113 , \ cod
( descendant)
here swap 0 , , char o , 11 , \ co
here 0 , 0 , char t , 121 , \ cat
here swap , 0 , char r , 122 , \ car
here swap , 0 , char n , 123 , \ can
( sibling descendant)
here -rot swap , , char a , 12 , \ ca
( descendant)
here swap 0 , , char c , 1 , \ c
here 0 , 0 , char t , 211 , \ bat
here swap , 0 , char r , 212 , \ bar
here swap , 0 , char n , 213 , \ ban
( descendant)
here swap 0 , , char a , 21 , \ ba
( sibling descendant)
here -rot swap , , char b , 2 , \ b
constant t-root
\ ------------------------------------------
\ test code
cr
S" cop" t-root hfind .
S" cob" t-root hfind .
S" cod" t-root hfind .
S" cat" t-root hfind .
S" car" t-root hfind .
S" can" t-root hfind .
S" bat" t-root hfind .
S" bar" t-root hfind .
S" ban" t-root hfind .
S" co" t-root hfind .
S" ca" t-root hfind .
S" ba" t-root hfind .
S" c" t-root hfind .
S" b" t-root hfind .
cr
S" cop" t-root h-find .
S" cob" t-root h-find .
S" cod" t-root h-find .
S" cat" t-root h-find .
S" car" t-root h-find .
S" can" t-root h-find .
S" bat" t-root h-find .
S" bar" t-root h-find .
S" ban" t-root h-find .
S" co" t-root h-find .
S" ca" t-root h-find .
S" ba" t-root h-find .
S" c" t-root h-find .
S" b" t-root h-find .
( eof)
Andrew Haley
This seems to be assuming that
: MYEXIT R> DROP ;
is equivalent to EXIT.
> So the exceptions are not obvious and not few.
I think they mostly are, actually, at least in the context of Standard
Forth.
> > As for 3, maybe it makes sense to define FOO EXIT as a tail call [*],
> > and let the compiler do the work. It won't break any existing
> > standard Forth programs
> In fact, I am interested in techniques beyond the standard such as
> return address manipulations, control transfers, and backtracking.
> These methods are not explicitly supported by the current standard,
> but on the other hand there is no conflict. The standard is compatible
> with such practices. If we define FOO EXIT as a tail call, this will
> break a lot of valuable code with environmental dependencies.
Far enough. With a few exceptions, code that messes with the reurn
stack fails Test 1 and/or Test 3: there are almost always better ways
to do the job, IMO.
Andrew.
Hugh Aguilar
> I do not know if I should make a formal proposal for the Forth200x...
> Anyway, I welcome anyone to use the proposed word.
>
> PROPOSAL
> ========
>
> TAIL ( "name" -- )
If you're only purpose is to support tail recursion (following TAIL
with RECURSE), then TAIL is unnecessary as most optimizing compilers
do this internally. I wrote a compiler for the 65c02 a long time ago
and it converted any JSR (call) preceding an RTS (return from
subroutine) into a JMP (unconditional jump). This provided tail
recursion, and also sped up a lot of Forth words that just happened to
end in a call to another Forth word.
Your TAIL can be used in the middle of Forth words and can be followed
by a Forth word other than RECURSE. This is effectively a GOTO that
Forth word. I can't think of any reason why you would want to do this.
If you can show examples in which this would be useful, that would
help your proposal.
Andrew Haley
> > As for 3, maybe it makes sense to define FOO EXIT as a tail call
> > [*], and let the compiler do the work. It won't break any
> > existing standard Forth programs
> In fact, I am interested in techniques beyond the standard such as
> return address manipulations, control transfers, and backtracking.
> These methods are not explicitly supported by the current standard,
Novix, by the way, had an immediate word (I think it might have been
\\) which broke the peeophole optimizer's pipeline. So, if FOO was a
call to a word that did return stack manipulation, you'd write
FOO \\ EXIT . This has the additional benefit of warning the reader
that FOO is going to do something odd.
Andrew.
Andrew Haley
> This seems to be assuming that
> : MYEXIT R> DROP ;
> is equivalent to EXIT.
It doesn't. Sorry, I misread the notation.
Andrew.
Brad
> I do not know if I should make a formal proposal for the Forth200x...
> Anyway, I welcome anyone to use the proposed word.
>
> PROPOSAL
> ========
>
> TAIL ( "name" -- )
>
compilers that would remove the need for what you're proposing. Tail
call generation is really a compiler optimization. It's not too hard
for a compiler to recognize "FOO ;" and compile a jump instead of a
call.
Some programmers don't want tail call optimization because it would
break their non-ans-compliant code that manipulates the return stack.
What's needed is a standard way to turn off tail call optimization
when it's not wanted. The default mode could be "off" so that hidden
return stack dependencies don't bite the user. I think some Forths may
already have such a switch, and this should be standardized.
-Brad
Dennis
Why is a standard needed to do non-standard things?
Not that I don't see some benefit to being able to turn off compiler
optimizations, from time to time. I have needed that frequently,
since I have been guilty of doing these non-standard things. I could
even agree that it would be nice if all the vendors used the same
words/concepts. However, all of this puts us outside the standard.
Until we can agree that we do have a return stack model, which carries
some entitlement, we have no need for these concepts.
DaR
m_l_g3
> On Oct 31, 8:51 am, Brad <hwfw...@gmail.com> wrote:
> > On Oct 28, 7:18 am, m_l_g3 <m_l...@yahoo.com> wrote:> I do not know if I should make a formal proposal for the Forth200x...
> > > Anyway, I welcome anyone to use the proposed word.
> >
> > > PROPOSAL
> > > ========
> >
> > > TAIL ( "name" -- )
> >
> > The point of the ANS standard was to enable the construction of
> > compilers that would remove the need for what you're proposing. Tail
> > call generation is really a compiler optimization. It's not too hard
> > for a compiler to recognize "FOO ;" and compile a jump instead of a
> > call.
> >
> > Some programmers don't want tail call optimization because it would
> > break their non-ans-compliant code that manipulates the return stack.
> > What's needed is a standard way to turn off tail call optimization
> > when it's not wanted. The default mode could be "off" so that hidden
> > return stack dependencies don't bite the user. I think some Forths may
> > already have such a switch, and this should be standardized.
> >
> > -Brad
>
> Why is a standard needed to do non-standard things?
Because it was expected from the very beginning that many useful
programs will be unstandard, and therefore the TC introduced the
notion of "a program with environmental dependencies".
>
> Not that I don't see some benefit to being able to turn off compiler
> optimizations, from time to time. I have needed that frequently,
> since I have been guilty of doing these non-standard things. I could
> even agree that it would be nice if all the vendors used the same
> words/concepts. However, all of this puts us outside the standard.
> Until we can agree that we do have a return stack model, which carries
> some entitlement, we have no need for these concepts.
>
> DaR
Well, the trick is that with tail recursion one can find out whether
tail call elimination (TCE) was performed. At second, demanding that
TCE is performed is not acceptable because it would:
1) make systems that don't do TCE non-compliant
2) break existing valuable packages written for such systems
And, finally, if you define FOO EXIT to be a tail call, what will EXIT
EXIT be?
TAIL EXIT is RDROP EXIT.
m_l_g3
Yes it does.
: myexit r> drop ; ok
: foo ." foo1 " myexit ." foo2" ; ok
: bar ." bar1 " foo ." bar2 " ; ok
bar bar1 foo1 bar2 ok
Elizabeth D Rather
That works only on systems where the actual return address is on the
Return Stack. That isn't required on Standard Systems, and on some it
isn't.
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."
==================================================
Brad
> Why is a standard needed to do non-standard things?
>
> Not that I don't see some benefit to being able to turn off compiler
> optimizations, from time to time. I have needed that frequently,
> since I have been guilty of doing these non-standard things. I could
> even agree that it would be nice if all the vendors used the same
> words/concepts. However, all of this puts us outside the standard.
> Until we can agree that we do have a return stack model, which carries
> some entitlement, we have no need for these concepts.
>
The next step would be to make the 200x standard less restrictive.
That means making tail call optimization smart enough to recognize
words that manipulate the return stack. Is that so hard? Some vendors
have Forths that don't have cell-wide return addresses, but even those
would not be broken by such a change. It would just create a future
restriction (that already exists) on users of the looser standard.
Floating point in the 1994 standard could keep floats on the stack,
but the practice of using a separate floating point stack is so
widespread that support of a unified stack might as well be retired
for simplicity's sake. A similar argument could be made for loosening
return stack restrictions. That puts the onus on vendors to make their
tools smarter, but the change doesn't affect users that are already
1994 compliant. It just puts a valuable tool back in the mainstream.
-Brad
Andrew Haley
> Floating point in the 1994 standard could keep floats on the stack,
> but the practice of using a separate floating point stack is so
> widespread that support of a unified stack might as well be retired
> for simplicity's sake. A similar argument could be made for
> loosening return stack restrictions.
I don't see how this follows. On some hardware, Forth's return stack
is not a good place to put return addresses. On some
microcontrollers, for example, the JSR instruction uses a dedicated
area of memory. If you're going to have subroutine-threaded Forth,
therefore, you have to use that memory. This fact won't change as a
result of standardization.
> That puts the onus on vendors to make their tools smarter, but the
> change doesn't affect users that are already 1994 compliant. It just
> puts a valuable tool back in the mainstream.
You're rather presuming that return stack manipulation is a useful
tool. From my point of view it's an evil hack that makes programs
harder to understand and makes optimization harder. There aren't
*any* plus points but there are some negatives.
Andrew.
m_l_g3
> m_l_g3 wrote:
> > Andrew Haley:
> >> Andrew Haley <andr...@littlepinkcloud.invalid> wrote:
> >>
> >>> This seems to be assuming that
> >>> : MYEXIT R> DROP ;
> >>> is equivalent to EXIT.
> >> It doesn't. Sorry, I misread the notation.
> >>
> >
> > Yes it does.
> > : myexit r> drop ; ok
> > : foo ." foo1 " myexit ." foo2" ; ok
> > : bar ." bar1 " foo ." bar2 " ; ok
> > bar bar1 foo1 bar2 ok
>
> That works only on systems where the actual return address is on the
> Return Stack. That isn't required on Standard Systems, and on some it
> isn't.
Yes. The calculus gives a formal description of control transfers due
to return address manipulations only for the classical model. One of
the axioms is
addr[ x ] >R EXIT == x
which is not true for the systems you mentioned, and the formalism
obviously is not applicable there. This conforms to common sense:
there's no control transfers due to return stack manipulations on
systems that do not put return addresses onto the return stack.
You see, it is good that it is possible to formalize control transfers
due to return address manipulations at least on some architecture.
They are not a dirty trick but a valuable (though a bit exotic)
technique. By the way, it is possible to prove their correctness (on
the classical model, of course).
Now a question for you and/or Andrew:
"SwiftForth defines FOO EXIT as a tail call of FOO (no return
address)"
True, false, or true under some conditions? (which conditions?)
If not false, was it Mr Moore who invented this?
m_l_g3
> Brad <hwf...@gmail.com> wrote:
> > That puts the onus on vendors to make their tools smarter, but the
> > change doesn't affect users that are already 1994 compliant. It just
> > puts a valuable tool back in the mainstream.
>
> You're rather presuming that return stack manipulation is a useful
> tool. From my point of view it's an evil hack
In SwiftForth it probably is.
> that makes programs
> harder to understand
This depends on the application domain. Embedded and desktop usage are
very different.
I remember once I worked in a C++ project where templates were
prohibited for the same reason.
> and makes optimization harder. There aren't
> *any* plus points but there are some negatives.
>
I could tell you effectively the same thing about floating point. And
about ALLOCATE and FREE. (Both are unnecessary complications.) And
would even remember a task where fixed point maths and static
allocation were used instead of FP and heap. (And, by the way, return
address manipulations were not used there either.)
Brad Eckert
wrote:
>
> You're rather presuming that return stack manipulation is a useful
> tool. From my point of view it's an evil hack that makes programs
> harder to understand and makes optimization harder. There aren't
> *any* plus points but there are some negatives.
>
exception of a simple multitasker) uses return stack manipulation.
There are some cool parsers that use return stack manipulation, but I
suspect those could be made ANS compliant by defining another stack
instead.
-Brad
Hugh Aguilar
> Some programmers don't want tail call optimization because it would
> break their non-ans-compliant code that manipulates the return stack.
> What's needed is a standard way to turn off tail call optimization
> when it's not wanted. The default mode could be "off" so that hidden
> return stack dependencies don't bite the user. I think some Forths may
> already have such a switch, and this should be standardized.
This would be a standard way to be non-standard?
Some compilers hold the return address in a register for functions
that don't call any sub-functions. This is especially true for
compilers that are using the processor's return stack as a data stack,
and are using some register as the r-stack, which results in a slow
push and pop to the r-stack. All in all, you can't expect R@ to give
you the return address on every system. Also, if the processor is
Harvard architecture, you can't have data embedded within the code and
be able to read it.
If you are going to have a standard word for turning off the jump-
termination optimization, then you are going to have to also have a
standard word for indicating that the answer to all of the following
questions is `yes' ---
1.) Does R@ provide the return address?
2.) Does R> DROP xxx >R cause xxx to be the new return address?
3.) Is the return address actually a pointer to the code that is
returned to (unlike on the 65C02 in which it is one off).
3.) Is the data at the return address accessible using @, !, C@ and
C!?
A programmer could then make his program specific to systems in which
all of the above is true, and to abort compilation with an error
message on systems in which some or all of the above is false.
Considering how popular Harvard architecture micro-controllers are
becoming, that would be the majority of systems. All in all, I think
that this kind of code is nothing that you want to incorporate into
the standard.
Mostly this was done in the past for the purpose of allowing words
such as ." to embed the string in the code after the call to <."> and
then have <."> extract it. There are easier ways to do this though.
You can put the string in the constant data section and compile a
literal of the address of the string, which would then be given as a
parameter to <.">.
The whole idea of embedding data in the code is a throwback to the
olden days of the PDP-11 in which the top value of the r-stack was
held in a register, and both code and data were in a single 64K block.
Computers are more complicated nowadays though. These aren't the 1970s
anymore.
Andrew Haley
> Elizabeth D Rather:
> > m_l_g3 wrote:
> > > Andrew Haley:
> > >> Andrew Haley <andr...@littlepinkcloud.invalid> wrote:
> > >>
> > >>> This seems to be assuming that
> > >>> : MYEXIT R> DROP ;
> > >>> is equivalent to EXIT.
> > >> It doesn't. Sorry, I misread the notation.
> > >>
> > >
> > > Yes it does.
> > > : myexit r> drop ; ok
> > > : foo ." foo1 " myexit ." foo2" ; ok
> > > : bar ." bar1 " foo ." bar2 " ; ok
> > > bar bar1 foo1 bar2 ok
> >
> > That works only on systems where the actual return address is on
> > the Return Stack. That isn't required on Standard Systems, and on
> > some it isn't.
> Yes. The calculus gives a formal description of control transfers
> due to return address manipulations only for the classical
> model. One of the axioms is
> addr[ x ] >R EXIT == x
> which is not true for the systems you mentioned, and the formalism
> obviously is not applicable there.
What is the point of this formalism? It doesn't seem to tell us
anything we don't already know.
> Now a question for you and/or Andrew:
> "SwiftForth defines FOO EXIT as a tail call of FOO (no return
> address)"
> True, false, or true under some conditions? (which conditions?)
SwiftForth does this. I don't know the full set of conditions.
> If not false, was it Mr Moore who invented this?
It was certainly in Novix Forth, but it coould have been Chuck or Greg
Bailey. I have no reason to suspect this technique didn't already
exist before then.
Andrew.
Andrew Haley
> On Nov 2, 11:45?am, Andrew Haley <andre...@littlepinkcloud.invalid>
> wrote:
> >
> > You're rather presuming that return stack manipulation is a useful
> > tool. From my point of view it's an evil hack that makes programs
> > harder to understand and makes optimization harder. There aren't
> > *any* plus points but there are some negatives.
> >
> It could well be a lame assumption, since none of my code (with the
> exception of a simple multitasker) uses return stack manipulation.
Well, exactly. That's why this is such a bad trade-off: a useful
optimization is lost for a rare use case. (And one that I'd like to
make even rarer!) IMO, IMO...
> There are some cool parsers that use return stack manipulation, but I
> suspect those could be made ANS compliant by defining another stack
> instead.
Or even good old recursive descent. :-)
Andrew.
Andrew Haley
> > > That puts the onus on vendors to make their tools smarter, but the
> > > change doesn't affect users that are already 1994 compliant. It just
> > > puts a valuable tool back in the mainstream.
> >
> > You're rather presuming that return stack manipulation is a useful
> > tool. From my point of view it's an evil hack
> In SwiftForth it probably is.
I don't follow your reasoning here. I was talking about Forth
programs in general, not some particular implementation.
> > that makes programs harder to understand
> This depends on the application domain. Embedded and desktop usage are
> very different.
I don't follow your reasoning here either. How does readability
depend on application domain?
> I remember once I worked in a C++ project where templates were
> prohibited for the same reason.
> > and makes optimization harder. There aren't *any* plus points but
> > there are some negatives.
> I could tell you effectively the same thing about floating
> point. And about ALLOCATE and FREE. (Both are unnecessary
> complications.) And would even remember a task where fixed point
> maths and static allocation were used instead of FP and heap.
Me too. There are trade-offs here, of course.
> (And, by the way, return address manipulations were not used there
> either.)
I don't think these are even remotely comparable. Floating point,
where hardware is present, adds both performance and a useful
capability. ALLOCATE and FREE, while optional, are occasionally
useful. But neither of these things get in the way of simple
optimizations.
Andrew.
Anton Ertl
>I do not know if I should make a formal proposal for the Forth200x...
Given that you have already done all the work, you might just as well
submit it; you can retract it later if the reactions are negative.
And here's my first take on it: IMO that's something that Forth-94
systems can optimize on their own relatively easily. What some people
(including you AFAIK) wish for would be ways to guarantee something
about the return addresses; and, if done well, these ways would
disable tail-call optimization at the appropriate places and only
there.
>An ambiguous condition exists if no single execution token for the
>original run-time semantics of name exists in the system.
That sounds like an implementation-specific restriction. Please
reformulate it in terms of language features, so a programmer can
easily tell whether TAIL can be used portably on that word. One such
ambiguous condition might be: "An ambiguous condition exists if name
has non-default compilation semantics".
With the introduction of addressable locals in the future (Stephen
Pelc wants to do that) we get another problem: TAIL has to deallocate
locals before calling name, but what if the address of a local is
passed to name?
>DISCUSSION
>==========
>
>This proposal introduces the notion of a tail call. A tail call is
>iteration rather than recursion.
>The proposed wording allows for such usages as
>
> TAIL POSTPONE my-immediate-word
Brr. What usage do you have in mind for that?
>Other programming languages, such as Scheme, do distinguish tail calls
>from calls with return.
How?
- 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 2009: http://www.euroforth.org/ef09/
Anton Ertl
>2. Can it already be done in Standard Forth?
>As for 2, no, it can't.
A standard program cannot force it, but a standard system is allowed
to do it. Given that programs running on standard systems do not rely
on tail-call optimization (i.e., they won't overflow the return stack
if tail recursion is not optimized), I don't think there is a need for
programs to force it; I think this is even true for system-specific
programs written for standard systems that perform tail-call
optimization (SwiftForth?).
OTOH, ColorForth programs rely on tail-call optimization, so if
tail-call optimization was guaranteed, maybe the idioms would change.
Anyway, even Chuck Moore lets the compiler perform the tail-call
optimization instead of introducing stuff like TAIL, so IMO that's the
way to go. If we want to guarantee tail-call optimization, we can
just specify the conditions under which it is guaranteed to happen (it
may also happen in other conditions, but there is not guarantee in
this case).
>As for 3, maybe it makes sense to define FOO EXIT as a tail call [*],
I don't think it's necessary to make the EXIT explicit; the EXIT
implicit in ";" should be sufficient.
>[*] With a few obvious exceptions for FOO such as >R
>R EXIT cannot happen in a standard program anyway. R> EXIT is a more
interesting proposition. However, a simple variant would only
support colon definitions for FOO; that's the only case where tail
recursion is likely anyway.
> immediate words,
If we specify it in terms of semantics appended to the current
definition, it does not matter if these semantics were appended by the
text interpreter or by some immediate word.
Anton Ertl
I don't understand this. New, partially unexplained notation does not
make for easy understandability. Maybe you can explain it in a more
understandable way.
>In fact, I am interested in techniques beyond the standard such as
>return address manipulations, control transfers, and backtracking.
>These methods are not explicitly supported by the current standard,
>but on the other hand there is no conflict. The standard is compatible
>with such practices. If we define FOO EXIT as a tail call, this will
>break a lot of valuable code with environmental dependencies.
If the standard guaranteed tail-call optimization for FOO EXIT, then,
yes, that code would not be able to run on any standard system. But
do we actually need to guarantee tail-call optimization? For what?
OTOH, you might be interested in making these techniques
standard-compliant by guaranteeing certain behaviour wrt return
addresses. The amount of code that uses such techniques is relatively
small, so IMO it should request such guarantees explicitly rather than
making that guarantee the default and disabling tail-call optimization
and inlining by default. IIRC we have had this discussion before, and
have come up with some ideas about what guarantees could be asked for
at that time.
Anton Ertl
>Why is a standard needed to do non-standard things?
A standard is helpful for making things portable. So, if some
features are currently non-standard, the users of these features might
want to standardize some support for them to make them more widely
portable, or to avoid the situation where they become less portable in
the future than they are now.
For return-address manipulations, I don't think that a switch for
turning off tail-call optimization is the right way to
standardization, though.
Anton Ertl
>The next step would be to make the 200x standard less restrictive.
>That means making tail call optimization smart enough to recognize
>words that manipulate the return stack. Is that so hard?
It's impossible for words that call EXECUTE (or that call words that
call EXECUTE). Even for simpler cases it's much harder than tail-call
optimization (the compiler would have to keep track of return-stack
items).
> Some vendors
>have Forths that don't have cell-wide return addresses, but even those
>would not be broken by such a change.
No, but the change would not buy anything.
Also, the standard does not describe which optimizations are allowed
and which aren't, it describes what a standard program is and how a
standard system executes it. E.g., currently the standard does not
describe explicitly that systems can perform tail-call optimizations.
Instead, it describes that return addresses are an opaque type that
programs cannot manipulate; as a side effect of this description
systems can perform tail-call optimization.
So if you want to make programs standard that do things with return
addresses, you describe the return addresses and what programs can do
with them under which circumstances. Then the non-optimizability of
this code falls out by itself.
Note that there are a number of other features in Forth that would be
affected by allowing return-address manipulations, e.g., counted loops
and locals.
Andrew Haley
> m_l_g3 <m_l...@yahoo.com> writes:
> >Other programming languages, such as Scheme, do distinguish tail
> >calls from calls with return.
> How?
I don't think it does. Section 3.5., Proper tail recursion, of the
revised report makes it pretty clear that any call which occurs in a
tail context is a tail call. (It then goes on to describe the
syntactic contexts that are tail contexts.)
With regard to whether FOO EXIT should be a special case for tail
calls, or whether other more complex forms such as
foo then ;
or even
: pling postpone exit ; immediate
...
foo pling
should be considered tail calls, you have to consider the
implementation. A very simple compiler of the form
: (compiler)
-find if immediate? if execute else compile, then
else >number number, then ;
would be somewhat complexified (:-) by having to handle the general
case. It's not hugely difficult, I agree: it's just a matter of
remembering the previous xt passed to COMPILE, and avoiding some
corner cases. But TAIL FOO has the advantage of not requiring such a
compiler to be changed at all, and the implementation of TAIL is
trivial.
Andrew.
Ed
> ...
> Floating point in the 1994 standard could keep floats on the stack,
> but the practice of using a separate floating point stack is so
> widespread that support of a unified stack might as well be retired
> for simplicity's sake.
How so? Separate stack users are privileged since '94 presumes
it to be the default. It is unified stack users that '94 has burdened.
Ed
> ...
> If we want to guarantee tail-call optimization, we can
> just specify the conditions under which it is guaranteed to happen (it
> may also happen in other conditions, but there is not guarantee in
> this case).
Who will decide the conditions under which tail-call optimization
should apply?
The Forth paradigm is to let the user decide (which also results in
a simple compiler). Words like TAIL ?DUP etc afford optimization
for all forths, whether one has an optimizing compiler or not. It is
the user who decides when and where to apply these words.
The question for me is not - how to apply tail call optimization -
but whether it is needed i.e. is it an indispensable technique in
Forth.
m_l_g3
wrote:
First of all, TAIL RECURSE. But once you can do it, you can do
TAIL POSTPONE [ELSE] as well.
> >Other programming languages, such as Scheme, do distinguish tail calls
> >from calls with return.
>
> How?
http://people.csail.mit.edu/jaffer/r4rs_3.html
--quote--
1. Overview of Scheme
1.1 Semantics
Implementations of Scheme are required to be properly tail-recursive.
This allows the execution of an iterative computation in constant
space, even if the iterative computation is described by a
syntactically recursive procedure. Thus with a tail-recursive
implementation, iteration can be expressed using the ordinary
procedure-call mechanics, so that special iteration constructs are
useful only as syntactic sugar.
--/quote--
m_l_g3
Explicit tail call optimization opens a possible direction for growth.
Among other useful things there are:
TAIL RECURSE
TAIL EXECUTE
TAIL my-deferred-word ( mutual recursion)
TAIL unstandard-stuff ( words that manipulate return addresses and so
on)
I think, I could prepare a simplified version of the Open Interpreter
word set proposal. (There have already been two versions, they can be
found via google. I think it would be useful to minimize the normative
part, and propose class 2 etc. as a recommendation. The F-PC double-
cell return addresses are in the past now.)
Aleksej Saushev
> On Nov 5, 3:04О©╫am, "Ed" <nos...@invalid.com> wrote:
>> Anton Ertl wrote:
>> > ...
>> > If we want to guarantee tail-call optimization, we can
>> > just specify the conditions under which it is guaranteed to happen (it
>> > may also happen in other conditions, but there is not guarantee in
>> > this case).
>>
>> Who will decide the conditions under which tail-call optimization
>> should apply?
>>
>> The Forth paradigm is to let the user decide (which also results in
>> a simple compiler). О©╫Words like TAIL ?DUP etc afford optimization
>> for all forths, whether one has an optimizing compiler or not. О©╫It is
>> the user who decides when and where to apply these words.
>>
>> The question for me is not - how to apply tail call optimization -
>> but whether it is needed i.e. is it an indispensable technique in
>> Forth.
>
> Explicit tail call optimization opens a possible direction for growth.
Tail call optimization is replacing call in tail context with a jump, "goto".
> Among other useful things there are:
> TAIL RECURSE
> TAIL EXECUTE
> TAIL my-deferred-word ( mutual recursion)
> TAIL unstandard-stuff ( words that manipulate return addresses and so
> on)
Your "explicit optimization" as you write it is a manual one.
You only need to use proper word rather than "tail" to see it:
GOTO RECURSE ( This reveals that your "TAIL RECURSE" is a hack. )
GOTO EXECUTE
GOTO your-deferred-word
GOTO unstandard-stuff
Which shows again that "tail" is wrong name choice, not only it clashes
with established practice, it hides semantic details.
--
HE CE3OH...
Aleksej Saushev
> On Oct 28, 9:24О©╫pm, an...@mips.complang.tuwien.ac.at (Anton Ertl)
> wrote:
>> m_l_g3 <m_l...@yahoo.com> writes:
>> >I do not know if I should make a formal proposal for the Forth200x...
>>
>> Given that you have already done all the work, you might just as well
>> submit it; you can retract it later if the reactions are negative.
>>
>> And here's my first take on it: IMO that's something that Forth-94
>> systems can optimize on their own relatively easily. О©╫What some people
>> (including you AFAIK) wish for would be ways to guarantee something
>> about the return addresses; and, if done well, these ways would
>> disable tail-call optimization at the appropriate places and only
>> there.
>>
>> >An ambiguous condition exists if no single execution token for the
>> >original run-time semantics of name exists in the system.
>>
>> That sounds like an implementation-specific restriction. О©╫Please
>> reformulate it in terms of language features, so a programmer can
>> easily tell whether TAIL can be used portably on that word. О©╫One such
>> ambiguous condition might be: "An ambiguous condition exists if name
>> has non-default compilation semantics".
>>
>> With the introduction of addressable locals in the future (Stephen
>> Pelc wants to do that) we get another problem: TAIL has to deallocate
>> locals before calling name, but what if the address of a local is
>> passed to name?
>>
>> >DISCUSSION
>> >==========
>>
>> >This proposal introduces the notion of a tail call. A tail call is
>> >iteration rather than recursion.
>> >The proposed wording allows for such usages as
>>
>> > О©╫ О©╫TAIL POSTPONE my-immediate-word
>>
>> Brr. О©╫What usage do you have in mind for that?
>>
>
> First of all, TAIL RECURSE. But once you can do it, you can do
> TAIL POSTPONE [ELSE] as well.
>
>> >Other programming languages, such as Scheme, do distinguish tail calls
>> >from calls with return.
>>
>> How?
>
> http://people.csail.mit.edu/jaffer/r4rs_3.html
> --quote--
> 1. Overview of Scheme
> 1.1 Semantics
> Implementations of Scheme are required to be properly tail-recursive.
> This allows the execution of an iterative computation in constant
> space, even if the iterative computation is described by a
> syntactically recursive procedure. Thus with a tail-recursive
> implementation, iteration can be expressed using the ordinary
> procedure-call mechanics, so that special iteration constructs are
> useful only as syntactic sugar.
> --/quote--
Why do you cite obsolete report?
You cite Scheme, but it is well-known that it is Scheme that pioneered
with tail call optimization requirement. Thus it may well represent a
minority of languages or be the only one. You say nothing about reasons
why it did so. What other means to express iteration does Scheme provide?
--
HE CE3OH...
Anton Ertl
>With regard to whether FOO EXIT should be a special case for tail
>calls, or whether other more complex forms such as
>
> foo then ;
>
>or even
>
> : pling postpone exit ; immediate
> ...
> foo pling
>
>should be considered tail calls, you have to consider the
>implementation. A very simple compiler of the form
>
>: (compiler)
> -find if immediate? if execute else compile, then
> else >number number, then ;
>
>would be somewhat complexified (:-) by having to handle the general
>case. It's not hugely difficult, I agree: it's just a matter of
>remembering the previous xt passed to COMPILE, and avoiding some
>corner cases. But TAIL FOO has the advantage of not requiring such a
>compiler to be changed at all, and the implementation of TAIL is
>trivial.
Chuck Moore lets the compiler do it by itself in ColorForth. If he
does not simplify the compiler by introducing TAIL, I don't think we
need TAIL, either.
Whether we should require the compilers to perform tail-call
optimization and in which cases it is guaranteed is subject to debate.
* Optimized RECURSE EXIT can be replaced by AGAIN (and BEGIN at the
start of the word, and an appropriate CS-ROLL).
* Indirect recursion is harder to optimize into iteration in standard
Forth.
* Optimizing EXECUTE EXIT is something that cannot be done in standard
Forth. One thing one can do with it (and not in standard Forth) is
to implement threaded code.
Anton Ertl
>Anton Ertl wrote:
>> ...
>> If we want to guarantee tail-call optimization, we can
>> just specify the conditions under which it is guaranteed to happen (it
>> may also happen in other conditions, but there is not guarantee in
>> this case).
>
>Who will decide the conditions under which tail-call optimization
>should apply?
As usual: The proponent (if any) makes a proposal, gets feedback for
it, works it into the proposal or ignores it, presents a revised
proposal etc., then there is a poll where implementors say whether
they implement the proposal, and programmers say whether they make use
of it, and eventually the committee decides to accept it into the
standard or not.
Stephen Pelc
wrote:
>I think, I could prepare a simplified version of the Open Interpreter
>word set proposal. (There have already been two versions, they can be
>found via google. I think it would be useful to minimize the normative
>part, and propose class 2 etc. as a recommendation.
I believe that these are more useful than going to tail recursion.
>The F-PC double-cell return addresses are in the past now.
Sorry, they have reappeared on other processors, including ones
that MPE are interested in. Look at many 16 bit CPUs with code
spaces larger than 16 bits.
Stephen
--
Stephen Pelc, steph...@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
Anton Ertl
>On Oct 28, 9:24=A0pm, an...@mips.complang.tuwien.ac.at (Anton Ertl)
>wrote:
>> m_l_g3 <m_l...@yahoo.com> writes:
>> > =A0 =A0TAIL POSTPONE my-immediate-word
>>
>> Brr. =A0What usage do you have in mind for that?
>>
>
>First of all, TAIL RECURSE. But once you can do it, you can do
>TAIL POSTPONE [ELSE] as well.
I already have trouble imagining what POSTPONE [ELSE] is good for; but
the point of tail-call optimizing it definitely escapes me.
>> >Other programming languages, such as Scheme, do distinguish tail calls
>> >from calls with return.
>>
>> How?
>
>http://people.csail.mit.edu/jaffer/r4rs_3.html
>--quote--
[...]
> Thus with a tail-recursive
>implementation, iteration can be expressed using the ordinary
>procedure-call mechanics
So Scheme does not distinguish tail calls from calls followed by
return. Instead, calls followed by return (and probably other cases)
are tail calls.
Ed
> "Ed" <nos...@invalid.com> writes:
> >Anton Ertl wrote:
> >> ...
> >> If we want to guarantee tail-call optimization, we can
> >> just specify the conditions under which it is guaranteed to happen (it
> >> may also happen in other conditions, but there is not guarantee in
> >> this case).
> >
> >Who will decide the conditions under which tail-call optimization
> >should apply?
>
> As usual: The proponent (if any) makes a proposal, gets feedback for
> it, works it into the proposal or ignores it, presents a revised
> proposal etc., then there is a poll where implementors say whether
> they implement the proposal, and programmers say whether they make use
> of it, and eventually the committee decides to accept it into the
> standard or not.
That's all very nice but a discussion on the topic would have been
preferable.
Anton Ertl
>> >Who will decide the conditions under which tail-call optimization
>> >should apply?
>>
>> As usual: The proponent (if any) makes a proposal, gets feedback for
>> it, works it into the proposal or ignores it, presents a revised
>> proposal etc., then there is a poll where implementors say whether
>> they implement the proposal, and programmers say whether they make use
>> of it, and eventually the committee decides to accept it into the
>> standard or not.
>
>That's all very nice but a discussion on the topic would have been
>preferable.
I answered your question. If you had a different question in mind,
please ask it.
Dennis
wrote:
> Andrew Haley <andre...@littlepinkcloud.invalid> writes:
> >With regard to whether FOO EXIT should be a special case for tail
> >calls, or whether other more complex forms such as
>
> > foo then ;
>
> >or even
>
> > : pling postpone exit ; immediate
> > ...
> > foo pling
>
> >should be considered tail calls, you have to consider the
> >implementation. A very simple compiler of the form
>
> >: (compiler)
> > -find if immediate? if execute else compile, then
> > else >number number, then ;
>
> >would be somewhat complexified (:-) by having to handle the general
> >case. It's not hugely difficult, I agree: it's just a matter of
> >remembering the previous xt passed to COMPILE, and avoiding some
> >corner cases. But TAIL FOO has the advantage of not requiring such a
> >compiler to be changed at all, and the implementation of TAIL is
> >trivial.
>
> Chuck Moore lets the compiler do it by itself in ColorForth. If he
> does not simplify the compiler by introducing TAIL, I don't think we
> need TAIL, either.
Isn't this what Chuck did by defining -; ?
DaR
Dennis
Or sorry, too early to be posting.
Chuck didn't give the option to _not_ eliminate tail recursion.
Is that what you mean?
But he sort of does, by making it position dependent. If you follow
the call with anything other than a ; you can still keep it a call.
The programmer is still in control. Can that be said for all the
variants of optimizing Forth compilers?
DaR
Aleksej Saushev
> On Nov 8, 6:29О©╫am, Dennis <druf...@worldnet.att.net> wrote:
>> On Nov 7, 7:43О©╫am, an...@mips.complang.tuwien.ac.at (Anton Ertl)
>> wrote:
>>
>> > Chuck Moore lets the compiler do it by itself in ColorForth. О©╫If he
>> > does not simplify the compiler by introducing TAIL, I don't think we
>> > need TAIL, either.
>>
>> Isn't this what Chuck did by defining -; ?
>
> Or sorry, too early to be posting.
>
> Chuck didn't give the option to _not_ eliminate tail recursion.
>
> Is that what you mean?
>
> But he sort of does, by making it position dependent. If you follow
> the call with anything other than a ; you can still keep it a call.
> The programmer is still in control. Can that be said for all the
> variants of optimizing Forth compilers?
He means that even in colorForth, the one that does tail call
optimization (TCO) the way "some other programming languages" do,
there's no explicit marker of tail context.
--
HE CE3OH...
foxchip
> > does not simplify the compiler by introducing TAIL, I don't think we
> > need TAIL, either.
>
> Isn't this what Chuck did by defining -; ?
Chuck always used implicit tail recursion implemented in semicolon.
Chuck never used a different word to specify tail recursion.
I introduced -; in the nineties. It is a question of style. Chuck
thinks it is simpler to have ; do tail recursion where possible
and only have one symbol. He must think that it is such a simple
thing that it is clear where it happens and that overloading the
; symbol with optional tail recursion is simple, clear and
quite explicit. Some people may think that using two different
symbols is simpler, clearer and more explicit. That's
why I put -; into ventureForth which did many things quite
differently than colorforth. It is a small style issue
that I don't think makes much difference either way.
As standards are concerned it seems like an implementation
issue to me. Since ; can do tail recursion optionally without
breaking the standard and matches other things that rely
on compiler optimizations I don't think that there is a
need to expand the standard with -;
Best Wishes
Aleksej Saushev
> On Nov 8, 6:29О©╫am, Dennis <druf...@worldnet.att.net> wrote:
>> > Chuck Moore lets the compiler do it by itself in ColorForth. О©╫If he
>> > does not simplify the compiler by introducing TAIL, I don't think we
>> > need TAIL, either.
>>
>> Isn't this what Chuck did by defining -; ?
>
> Chuck always used implicit tail recursion implemented in semicolon.
>
> Chuck never used a different word to specify tail recursion.
> I introduced -; in the nineties. It is a question of style. Chuck
> thinks it is simpler to have ; do tail recursion where possible
> and only have one symbol. He must think that it is such a simple
> thing that it is clear where it happens and that overloading the
> ; symbol with optional tail recursion is simple, clear and
> quite explicit. Some people may think that using two different
> symbols is simpler, clearer and more explicit. That's
> why I put -; into ventureForth which did many things quite
> differently than colorforth. It is a small style issue
> that I don't think makes much difference either way.
>
> As standards are concerned it seems like an implementation
> issue to me. Since ; can do tail recursion optionally without
> breaking the standard and matches other things that rely
> on compiler optimizations I don't think that there is a
> need to expand the standard with -;
While the idea is good --- I do miss sometimes of such "restart" word ---
"-;" is a bad name in my opinion. It has more in common with "exit"
than with "recurse" or "again", which would be more appropriate.
--
HE CE3OH...
Jerry Avins
...
> I answered your question. If you had a different question in mind,
> please ask it.
You were more polite than many would have been.
Jerry
--
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������
Anton Ertl
>On Nov 8, 6:29=A0am, Dennis <druf...@worldnet.att.net> wrote:
>> On Nov 7, 7:43=A0am, an...@mips.complang.tuwien.ac.at (Anton Ertl)
>> > Chuck Moore lets the compiler do it by itself in ColorForth. =A0If he
>> > does not simplify the compiler by introducing TAIL, I don't think we
>> > need TAIL, either.
>>
>> Isn't this what Chuck did by defining -; ?
>>
>> DaR
>
>Or sorry, too early to be posting.
>
>Chuck didn't give the option to _not_ eliminate tail recursion.
>
>Is that what you mean?
I mean that a programmer does not need to specify tail-call
optimization explicitly in ColorForth, the compiler just does it for
him; and Chuck Moore does not consider this too complicated.
>But he sort of does, by making it position dependent. If you follow
>the call with anything other than a ; you can still keep it a call.
>The programmer is still in control. Can that be said for all the
>variants of optimizing Forth compilers?
If you write for a specific compiler, you usually can.
If you want to write code portable between systems, you cannot. Now
we can discuss about standardizing portable ways to suppress tail-call
optimization, but IMO this does not make sense as long as there is no
standard code for which the absence of tail-call optimization provides
a benefit.
Hugh Aguilar
wrote:
> If the standard guaranteed tail-call optimization for FOO EXIT, then,
> yes, that code would not be able to run on any standard system. But
> do we actually need to guarantee tail-call optimization? For what?
There are two reasons to *guarantee* tat tail-call optimization is
being done:
1.) Give ourselves a warm feeling knowing that our code is efficient
and fast.
2.) Assure ourselves that our deeply tail-recursive functions won't
overflow the r-stack on any machine that we run them on.
As for #1, producing fast and efficient code is the job of the
compiler writer. The programmer shouldn't have to get involved in the
low-level details.
As for #2, this is more important. Some programmers (mostly those that
learned Lisp as their first language) write tail-recursive functions
that might recurse hundreds of times (traversing a linked list, for
example), and will overflow the r-stack on pretty much any computer.
I don't think we need TAIL or any other explicit demand for tail-
recursion. It might be helpful however, for the compiler vendor to
indicate whether or not his compiler supports tail-recursion, so the
Lisp programmer doesn't spend money on a compiler that doesn't allow
him to program the way that he wants to.
BTW, Isn't it true that the JVM doesn't have an unconditional jump
instructions and hence doesn't support tail-recursion? Isn't that the
big issue with Clojure? If Forth requires tail-recursion, then it is
not going to be able to run under the JVM. I don't know much about the
JVM though, so I may be mistaken about its limitations in regard to
tail-recursion.
Andrew Haley
> BTW, Isn't it true that the JVM doesn't have an unconditional jump
> instructions and hence doesn't support tail-recursion?
No, and yes. Tail calls are hard in the general case because security
checks often need to walk the call stack to determine the context of a
caller. So, code can't tail call anything that might need to check
its permissions. There are ways around this, but they all require VM
changes AFAIK.
> If Forth requires tail-recursion, then it is not going to be able to
> run under the JVM.
I guess not, but the JVM is not ideal for Forth anyway.
Andrew.
Aleksej Saushev
> On Oct 30, 3:49О©╫am, an...@mips.complang.tuwien.ac.at (Anton Ertl)
> wrote:
>> If the standard guaranteed tail-call optimization for FOO EXIT, then,
>> yes, that code would not be able to run on any standard system. О©╫But
>> do we actually need to guarantee tail-call optimization? О©╫For what?
>
> There are two reasons to *guarantee* tat tail-call optimization is
> being done:
There are more reasons why these reasons are not essential.
> 1.) Give ourselves a warm feeling knowing that our code is efficient
> and fast.
>
> 2.) Assure ourselves that our deeply tail-recursive functions won't
> overflow the r-stack on any machine that we run them on.
>
> As for #1, producing fast and efficient code is the job of the
> compiler writer. The programmer shouldn't have to get involved in the
> low-level details.
Contrary to Scheme Forth has rich set of control structures,
you can simply write more efficient code in the first place.
You may not notice it, but Mikhail hasn't answered yet, what are those
"other languages" he refers to when he argues for inclusion of his "TAIL"
into the standard. It may be that Scheme is the only one.
Getting the programmer involved into low-level details is Forth tradition
and part of its "philosophy".
TCO makes debugging a hell, because you lose meaningful stack backtraces,
you see call history at most, but that history is useless, since it does't
refer to program structure.
> As for #2, this is more important. Some programmers (mostly those that
> learned Lisp as their first language) write tail-recursive functions
> that might recurse hundreds of times (traversing a linked list, for
> example), and will overflow the r-stack on pretty much any computer.
First, Forth tradition is not using recursion at all.
Second, Lisp, Common Lisp doesn't guarantee tail call optimization,
and this is well-known to any Lisp programmer. And really deep recursion
presents problem even there.
> I don't think we need TAIL or any other explicit demand for tail-
> recursion. It might be helpful however, for the compiler vendor to
> indicate whether or not his compiler supports tail-recursion, so the
> Lisp programmer doesn't spend money on a compiler that doesn't allow
> him to program the way that he wants to.
Lack of TCO presents quite a minor problem in Lisp world, if it does at all.
> BTW, Isn't it true that the JVM doesn't have an unconditional jump
> instructions and hence doesn't support tail-recursion? Isn't that the
> big issue with Clojure? If Forth requires tail-recursion, then it is
> not going to be able to run under the JVM. I don't know much about the
> JVM though, so I may be mistaken about its limitations in regard to
> tail-recursion.
I don't know where you got it, it took me only 5 minutes to find this:
"3.11.7 Control Transfer Instructions
The control transfer instructions conditionally or unconditionally cause
the Java virtual machine to continue execution with an instruction other
than the one following the control transfer instruction. They are:
...
- Unconditional branch: goto, goto_w, jsr, jsr_w, ret."
--
HE CE3OH...
m_l_g3
> m_l_g3 <m_l...@yahoo.com> writes:
> > Among other useful things there are:
> > TAIL RECURSE
> > TAIL EXECUTE
> > TAIL my-deferred-word ( mutual recursion)
> > TAIL unstandard-stuff ( words that manipulate return addresses and so
> > on)
>
> Your "explicit optimization" as you write it is a manual one.
> You only need to use proper word rather than "tail" to see it:
>
> GOTO RECURSE ( This reveals that your "TAIL RECURSE" is a hack. )
> GOTO EXECUTE
> GOTO your-deferred-word
> GOTO unstandard-stuff
>
> Which shows again that "tail" is wrong name choice, not only it clashes
> with established practice, it hides semantic details.
As I understand, you want to reserve the name TAIL for list
processing, namely, the Lisp's CDR function. This is a bit strange
because the name HEAD is sort of already [ab]used in Forth and means
something related to dictionary entry construction. (Not in the
standard, but de-facto). Please believe me, the really good names CAR
and CDR (as well as CADDAR etc) will never be abused.
Do you do list processing in Forth? What is the problem being solved?
By the way, you are right, GOTO RECURSE reads awful. TAIL RECURSE
looks much better ;) And, finally, GOTO {procedure} is non-sense. If
the destination is a procedure, it is not a GOTO. A tail call is
parametrized, while a goto passes information only via the visible
variables.
Bernd Paysan
> By the way, you are right, GOTO RECURSE reads awful. TAIL RECURSE
> looks much better ;) And, finally, GOTO {procedure} is non-sense. If
> the destination is a procedure, it is not a GOTO.
Well, GOTO <label> is just abusing Forth words as labels. It's not always
so nonsensical. E.g. my OOF has a goto meta-method, where you jump to a
method instead of calling it; this is used as tail recursion, as well - if
you have a list-like class, you may have some next ptr, and a method walking
the list like search or so would say "next goto search" to invoke the search
method of the next element without wasting stack space.
For normal Forth code, I don't think this is all that necessary, you can
usually create a BEGIN .. AGAIN (or UNTIL) loop to do the same, but for the
OOF part, it makes more sense - a method invocation is more complex, so
turning it into a jump is not possible with simple Forth control structures.
> A tail call is
> parametrized, while a goto passes information only via the visible
> variables.
We are in Forth here, not in Fortran. Information is passed on the stack.
--
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://www.jwdt.com/~paysan/
m_l_g3
wrote:
> m_l_g3 <m_l...@yahoo.com> writes:
> >On Oct 28, 9:24=A0pm, an...@mips.complang.tuwien.ac.at (Anton Ertl)
> >wrote:
> >> m_l_g3 <m_l...@yahoo.com> writes:
> >> > =A0 =A0TAIL POSTPONE my-immediate-word
>
> >> Brr. =A0What usage do you have in mind for that?
>
> >First of all, TAIL RECURSE. But once you can do it, you can do
> >TAIL POSTPONE [ELSE] as well.
>
> I already have trouble imagining what POSTPONE [ELSE] is good for; but
> the point of tail-call optimizing it definitely escapes me.
Well, if it was [COMPILE] , you would assume that it (so zu sagen) un-
does immediacy, isn't it? POSTPONE un-does immediacy too.
I copy & paste from the original message in this thread:
mydefer [MYELSE] immediate
mydefer skip-nested
: _skip-nested
bl word count
dup 0= if 2drop refill 0= abort" premature end of stream"
tail skip-nested
then
2dup S" [MYTHEN]" compare 0= if 2drop exit then
2dup S" [MYIF]" compare 0= if 2drop skip-nested tail skip-nested
then
2drop tail skip-nested
;
: _[else]
bl word count
dup 0= if 2drop refill 0= abort" premature end of stream"
tail postpone [MYELSE]
then
2dup S" [MYTHEN]" compare 0= if 2drop exit then
2dup S" [MYELSE]" compare 0= if 2drop exit then
2dup S" [MYIF]" compare 0= if 2drop skip-nested
tail postpone [MYELSE]
then
2drop tail postpone [MYELSE]
;
' _[else] myis [MYELSE]
' _skip-nested myis skip-nested
In fact, one of course can define:
: _WHATEVER .... ; \ non-immediate
: [WHATEVER] TAIL _WHATEVER ; IMMEDIATE \ full functional equivalence
but I would prefer to be able to use only one name instead of two.
>
> >> >Other programming languages, such as Scheme, do distinguish tail calls
> >> >from calls with return.
>
> >> How?
>
> >http://people.csail.mit.edu/jaffer/r4rs_3.html
> >--quote--
> [...]
> > Thus with a tail-recursive
> >implementation, iteration can be expressed using the ordinary
> >procedure-call mechanics
>
> So Scheme does not distinguish tail calls from calls followed by
> return. Instead, calls followed by return (and probably other cases)
> are tail calls.
Anton, we will not play words. Even if the word "distinguish" has
different meanings for us (BTW, both meanings look valid to me), you
understand what I mean. Tail calls are semantically different with no
explicit key word.
Anton Ertl
>On Nov 7, 7:00=A0pm, an...@mips.complang.tuwien.ac.at (Anton Ertl)
>wrote:
>> m_l_g3 <m_l...@yahoo.com> writes:
>> >First of all, TAIL RECURSE. But once you can do it, you can do
>> >TAIL POSTPONE [ELSE] as well.
>>
>> I already have trouble imagining what POSTPONE [ELSE] is good for; but
>> the point of tail-call optimizing it definitely escapes me.
I was assuming you meant the standard word [ELSE]; instead, you use it
in the implementation of [ELSE].
>mydefer [MYELSE] immediate
>mydefer skip-nested
>
>: _skip-nested
> bl word count
> dup 0=3D if 2drop refill 0=3D abort" premature end of stream"
> tail skip-nested
> then
> 2dup S" [MYTHEN]" compare 0=3D if 2drop exit then
> 2dup S" [MYIF]" compare 0=3D if 2drop skip-nested tail skip-nested
>then
> 2drop tail skip-nested
>;
>: _[else]
> bl word count
> dup 0=3D if 2drop refill 0=3D abort" premature end of stream"
> tail postpone [MYELSE]
> then
> 2dup S" [MYTHEN]" compare 0=3D if 2drop exit then
> 2dup S" [MYELSE]" compare 0=3D if 2drop exit then
> 2dup S" [MYIF]" compare 0=3D if 2drop skip-nested
> tail postpone [MYELSE]
> then
> 2drop tail postpone [MYELSE]
>;
>' _[else] myis [MYELSE]
>' _skip-nested myis skip-nested
BEGIN AGAIN would be sufficient here.
In any case, if you really want to tail-recurse here, then
TAIL POSTPONE [MYELSE] looks pretty obscure and is hard to understand.
POSTPONE [MYELSE] EXIT is probably not much better, though.
_[ELSE] EXIT or RECURSE EXIT look like better options.
But BEGIN ... AGAIN is idiomatic and therefore best.
m_l_g3
> m_l_g3 wrote:
> > A tail call
> > is parametrized, while a goto passes information only via
> > the visible variables.
>
> We are in Forth here, not in Fortran. Information is passed on the stack.
OMG...
Yes, it is passed on the stack, but this control transfer must not be
called GOTO in Forth, because it is not a [traditional] goto.
m_l_g3
> --
> Bernd Paysan
> "If you want it done right, you have to do it yourself"
By the way, your sig brilliantly explains why the tail call construct
should be explicit.
Aleksej Saushev
> On Nov 7, 8:26О©╫am, Aleksej Saushev <a...@inbox.ru> wrote:
>> m_l_g3 <m_l...@yahoo.com> writes:
>> > Among other useful things there are:
>> > TAIL RECURSE
>> > TAIL EXECUTE
>> > TAIL my-deferred-word ( mutual recursion)
>> > TAIL unstandard-stuff ( words that manipulate return addresses and so
>> > on)
>>
>> Your "explicit optimization" as you write it is a manual one.
>> You only need to use proper word rather than "tail" to see it:
>>
>> GOTO RECURSE ( This reveals that your "TAIL RECURSE" is a hack. )
>> GOTO EXECUTE
>> GOTO your-deferred-word
>> GOTO unstandard-stuff
>>
>> Which shows again that "tail" is wrong name choice, not only it clashes
>> with established practice, it hides semantic details.
>
> As I understand, you want to reserve the name TAIL for list
> processing, namely, the Lisp's CDR function. This is a bit strange
> because the name HEAD is sort of already [ab]used in Forth and means
> something related to dictionary entry construction. (Not in the
> standard, but de-facto).
This doesn't make reason to continue abuse.
> Please believe me, the really good names CAR
> and CDR (as well as CADDAR etc) will never be abused.
Semantics of "HEAD", "TAIL", "FIRST", "REST" is well established for
more than a quarter of century, and with regard to "tail" it is done
by exactly the language you refer to in your arguments.
> Do you do list processing in Forth? What is the problem being solved?
Yes, I do use lists when I need them.
> By the way, you are right, GOTO RECURSE reads awful. TAIL RECURSE
> looks much better ;) And, finally, GOTO {procedure} is non-sense.
Can you make your views consistent? You use this trick, you file a
proposal to make it standard, but you call it nonsense at the same
time.
> If the destination is a procedure, it is not a GOTO. A tail call is
> parametrized, while a goto passes information only via the visible
> variables.
Forth procedures do not have parameters, they all use the same global
environment which includes parameter stack usually used to pass data.
By the way, do you ever do literature search? Because it seems that you
don't, since it doesn't take even half an hour to find the following.
Even though the trend of requesting TCO be mandatory is quite new,
people correctly identify it as GOTO rather than CALL, and they do
call it this way. E.g.:
1. PERL, http://perldoc.perl.org/functions/goto.html
2. ECMAScript, http://bugs.ecmascript.org/ticket/323
3. C--, http://www.cminusminus.org/extern/man2.pdf (calls it "jump").
The following opinion is of interest:
https://mail.mozilla.org/pipermail/es-discuss/2008-January/001837.html
--
HE CE3OH...
Bernd Paysan
Well, as Aleksej remarked, other languages have such a non-traditional goto,
as well. ECMAscript calls it "goto", C-- calls it "jump", Newsqueak
"become", all three can pass parameters. I won't say I like the word
"goto", but in some sense it is the traditional goto - in the early
languages with GOTO, parameters were passed in global variables, anyway, so
the difference between a call/GOSUB and a GOTO was just that you can't
return from a GOTO destination.
Andrew Haley
> On Nov 5, 3:04?am, "Ed" <nos...@invalid.com> wrote:
> > Anton Ertl wrote:
> > > ...
> > > If we want to guarantee tail-call optimization, we can
> > > just specify the conditions under which it is guaranteed to happen (it
> > > may also happen in other conditions, but there is not guarantee in
> > > this case).
> >
> > should apply?
> >
> > a simple compiler). ?Words like TAIL ?DUP etc afford optimization
> > for all forths, whether one has an optimizing compiler or not. ?It is
> > the user who decides when and where to apply these words.
> >
> > The question for me is not - how to apply tail call optimization -
> > but whether it is needed i.e. is it an indispensable technique in
> > Forth.
> Explicit tail call optimization opens a possible direction for growth.
> Among other useful things there are:
> TAIL RECURSE
> TAIL EXECUTE
> TAIL my-deferred-word ( mutual recursion)
> TAIL unstandard-stuff ( words that manipulate return addresses and so
> on)
Maybe, but Jeff Fox's -; syntax is much nicer IMO. It explicitly
marks where a tail call is needed, and conveys to me just the right
idea.
Andrew.
Ed
> "Ed" <nos...@invalid.com> writes:
> >Anton Ertl wrote:
> >> "Ed" <nos...@invalid.com> writes:
> >> >Who will decide the conditions under which tail-call optimization
> >> >should apply?
> >>
> >> As usual: The proponent (if any) makes a proposal, gets feedback for
> >> it, works it into the proposal or ignores it, presents a revised
> >> proposal etc., then there is a poll where implementors say whether
> >> they implement the proposal, and programmers say whether they make use
> >> of it, and eventually the committee decides to accept it into the
> >> standard or not.
> >
> >That's all very nice but a discussion on the topic would have been
> >preferable.
>
> I answered your question. If you had a different question in mind,
> please ask it.
Where is the answer? So far all I've seen is one line taken out of
context for the purpose of contriving a commentary.
Your response may satisfy those who plainly have their own axe
to grind.
Albert van der Horst
Anton Ertl <an...@mips.complang.tuwien.ac.at> wrote:
>m_l_g3 <m_l...@yahoo.com> writes:
>>On Oct 28, 9:24=A0pm, an...@mips.complang.tuwien.ac.at (Anton Ertl)
>>wrote:
>>> m_l_g3 <m_l...@yahoo.com> writes:
>>> > =A0 =A0TAIL POSTPONE my-immediate-word
>>>
>>> Brr. =A0What usage do you have in mind for that?
>>>
>>
>>First of all, TAIL RECURSE. But once you can do it, you can do
>>TAIL POSTPONE [ELSE] as well.
>
>I already have trouble imagining what POSTPONE [ELSE] is good for; but
>the point of tail-call optimizing it definitely escapes me.
Personally, I would say that [ELSE] is, or sometimes is, a marker.
IMO the standard should forbid the commenting out, postponing or
lowercasing of all conditional compilation words.
It is like in the TV series of the three witches.
You can do about everything with witch craft, but
changing the past leads to paradoxes that endanger the
cosmos, and are utterly forbidden.
The consequences are so dear, that nobody dares to question
that rule. And nobody should.
<SNIP>
>- anton
--
--
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst