However fib won't compile because fib is invisible to itself while compiling.
Simple question: Is there any standard way to make a Forth definition
visible during its compilation?? Some old compilers employed a smudge bit
in headers, but what do you do today?
On Saturday, March 4, 2023 at 3:17:39 PM UTC+1, minf...@arcor.de wrote: [..]
However fib won't compile because fib is invisible to itself while compiling.
Simple question: Is there any standard way to make a Forth definition visible during its compilation?? Some old compilers employed a smudge bit in headers, but what do you do today?( RECURSIVE ) RECURSE
Marcel Hendrix schrieb am Samstag, 4. März 2023 um 15:30:07 UTC+1:
On Saturday, March 4, 2023 at 3:17:39 PM UTC+1, minf...@arcor.de wrote: [..]
However fib won't compile because fib is invisible to itself while compiling.
Simple question: Is there any standard way to make a Forth definition visible during its compilation?? Some old compilers employed a smudge bit( RECURSIVE ) RECURSE
in headers, but what do you do today?
Okay, right, I forgot RECURSIVE. But it is only a gforth word IIRC.
Perhaps a good candidate to become standardized.
OTOH using RECURSIVE allows for nested calls of yet unfinished definitions whereas RECURSE just "jumps back". Which one would make tail call elimination
easier?
Do you have any examples where I can see it being used ?
I looked at gforth manual but the stack comment isnt enough.
I have been dabbling with simple string pattern matching in Forth
(with ? replacing single characters and * replacing substrings, no regex). >While formulating the code I began thinking about integrating pattern >matching into my Forth : tricky/difficult(?) because Forth's wordlist search >mechanism is too dumb.
The classic
\ factorial definition
\ fac(0)=1 (hidden: stop recursion)
\ fac(n)=n*fac(n-1)
cannot be translated 1:1 to Forth. Other experiences?
Simple question: Is there any standard way to make a Forth definition
visible during its compilation??
Some old compilers employed a smudge bit
in headers, but what do you do today?
OTOH using RECURSIVE allows for nested calls of yet unfinished definitions >whereas RECURSE just "jumps back".
Which one would make tail call eliminati=
on
easier?
<http://git.savannah.gnu.org/cgit/gforth.git/tree/regexp.fs>
"minf...@arcor.de" <minforth@arcor.de> writes:
I have been dabbling with simple string pattern matching in Forth
(with ? replacing single characters and * replacing substrings, no regex). >>While formulating the code I began thinking about integrating pattern >>matching into my Forth : tricky/difficult(?) because Forth's wordlist search >>mechanism is too dumb.
<http://git.savannah.gnu.org/cgit/gforth.git/tree/regexp.fs>
Currently only documented (slightly) in the source code.
The classic
\ factorial definition
\ fac(0)=1 (hidden: stop recursion)
\ fac(n)=n*fac(n-1)
cannot be translated 1:1 to Forth. Other experiences?
You have to insert an IF, like in most other programming languages.
Close enough for me.
Simple question: Is there any standard way to make a Forth definition >>visible during its compilation??
No.
Some old compilers employed a smudge bit
in headers, but what do you do today?
The smudge bit is an implementation technique. The other
implementation technique (at least as old as the 1980s) is REVEAL:
only insert the word into the current wordlist when it should become
visible. AFAIK both techniques are still in use.
- anton
In article <2023Mar4.170531@mips.complang.tuwien.ac.at>,
Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
"minf...@arcor.de" <minforth@arcor.de> writes:
Simple question: Is there any standard way to make a Forth definition >>>visible during its compilation??
No.
You have just answered that question in the affirmative.
RECURSIVE does the job. What am I missing?
On Saturday, 4 March 2023 at 15:23:27 UTC, minf...@arcor.de wrote:
Marcel Hendrix schrieb am Samstag, 4. März 2023 um 15:30:07 UTC+1:
On Saturday, March 4, 2023 at 3:17:39 PM UTC+1, minf...@arcor.de wrote:
[..]
However fib won't compile because fib is invisible to itself while compiling.
Simple question: Is there any standard way to make a Forth definition visible during its compilation?? Some old compilers employed a smudge bit( RECURSIVE ) RECURSE
in headers, but what do you do today?
Okay, right, I forgot RECURSIVE. But it is only a gforth word IIRC. Perhaps a good candidate to become standardized.
OTOH using RECURSIVE allows for nested calls of yet unfinished definitions whereas RECURSE just "jumps back". Which one would make tail call eliminationI wasnt aware of RECURSIVE and I have not used it before.
easier?
Do you have any examples where I can see it being used ?
I looked at gforth manual but the stack comment isnt enough.
On Saturday, March 4, 2023 at 5:16:17=E2=80=AFPM UTC+1, Anton Ertl wrote: >[..]
<http://git.savannah.gnu.org/cgit/gforth.git/tree/regexp.fs>
+++1
Any examples to test this out?
NN schrieb am Samstag, 4. März 2023 um 16:42:33 UTC+1:
On Saturday, 4 March 2023 at 15:23:27 UTC, minf...@arcor.de wrote:
Marcel Hendrix schrieb am Samstag, 4. März 2023 um 15:30:07 UTC+1:
On Saturday, March 4, 2023 at 3:17:39 PM UTC+1, minf...@arcor.de wrote:
[..]
However fib won't compile because fib is invisible to itself while compiling.
Simple question: Is there any standard way to make a Forth definition( RECURSIVE ) RECURSE
visible during its compilation?? Some old compilers employed a smudge bit
in headers, but what do you do today?
Okay, right, I forgot RECURSIVE. But it is only a gforth word IIRC. Perhaps a good candidate to become standardized.
: fib recursive ( u -- fibonacci )OTOH using RECURSIVE allows for nested calls of yet unfinished definitionsI wasnt aware of RECURSIVE and I have not used it before.
whereas RECURSE just "jumps back". Which one would make tail call elimination
easier?
Do you have any examples where I can see it being used ?
I looked at gforth manual but the stack comment isnt enough.
dup 2 u< ?exit
dup 1- fib swap 2 - fib + ;
\ : ?exit postpone if postpone exit postpone then ; immediate
minf...@arcor.de schrieb am Samstag, 4. März 2023 um 18:28:53 UTC+1:[..]
I'm sure someone can make it faster by obfuscation. ;-)
S >R recursiveS R@ = IF -S -R 1 EXIT ENDIF
On Saturday, March 4, 2023 at 8:38:47 PM UTC+1, minf...@arcor.de wrote:
minf...@arcor.de schrieb am Samstag, 4. März 2023 um 18:28:53 UTC+1:[..]
I'm sure someone can make it faster by obfuscation. ;-)I doubt faster, not obfuscation:
ANEW -binomial
: BIN0 ( n k -- binomial_coefficient )
PARAMS| n k | recursive
n k = IF 1 ELSE
k 0 = IF 1 ELSE
n 1- k bin0
n 1- k 1- bin0 +
ENDIF ENDIF ;
: BIN1 ( n k -- binomial_coefficient )
PARAMS| n k | recursive
n k = IF 1 EXIT ENDIF
k 0 = IF 1 EXIT ENDIF
n 1- k bin1
n 1- k 1- bin1 + ;
: BIN2 ( n k -- binomial_coefficient )
S >R recursiveS R@ = IF -S -R 1 EXIT ENDIF
S 0 = IF -S -R 1 EXIT ENDIF
R@ 1- S bin2
R@ 1- S 1- bin2 + -S -R ;
#1000 VALUE #times
: TEST CR TIMER-RESET ." \ bin0 : " #times 0 ?DO #20 3 BIN0 DROP LOOP .ELAPSED
CR TIMER-RESET ." \ bin1 : " #times 0 ?DO #20 3 BIN1 DROP LOOP .ELAPSED
CR TIMER-RESET ." \ bin2 : " #times 0 ?DO #20 3 BIN2 DROP LOOP .ELAPSED ;
FORTH> 1000000 TO #times TEST
\ bin0 : 3.838 seconds elapsed.
\ bin1 : 3.754 seconds elapsed.
\ bin2 : 3.729 seconds elapsed. ok
I have been dabbling with simple string pattern matching in Forth
(with ? replacing single characters and * replacing substrings, no regex). While formulating the code I began thinking about integrating pattern matching into my Forth : tricky/difficult(?) because Forth's wordlist search mechanism is too dumb. The classic
\ factorial definition
\ fac(0)=1 (hidden: stop recursion)
\ fac(n)=n*fac(n-1)
cannot be translated 1:1 to Forth. Other experiences?
Of course simple things can be converted easily to recursions. F.ex.
(not discussing slow locals here, they are just for visibility)
: END postpone exit postpone then ; IMMEDIATE
: fac {: a :} \ factorial
a 0= IF 1 END
a
a 1- recurse ( fac ) * ;
: fib {: a :} \ fibonacci
a 0= IF 0 END
a 1 = IF 1 END
a 1- fib
a 2 - fib + ;
However fib won't compile because fib is invisible to itself while compiling.
Simple question: Is there any standard way to make a Forth definition
visible during its compilation?? Some old compilers employed a smudge bit
in headers, but what do you do today?
Marcel Hendrix schrieb am Samstag, 4. März 2023 um 23:18:30 UTC+1:[..]
On Saturday, March 4, 2023 at 8:38:47 PM UTC+1, minf...@arcor.de wrote:
minf...@arcor.de schrieb am Samstag, 4. März 2023 um 18:28:53 UTC+1:[..]
I'm sure someone can make it faster by obfuscation. ;-)I doubt faster, not obfuscation:
I think memoization tables would be the first choice for speed improvement up to certain n's.
For higher values recursion can be abbreviated for k>n/2 using Pascal's triangle symmetry.
synonym foo recurse ok
: foo dup . dup 10 < if 1+ foo else drop then ;
1 foo 1 2 3 4 5 6 7 8 9 10 ok
This could be hidden from the user by a defining word that copied
"SYNONYM FOO RECURSE" to a buffer to be EVALUATEd. It would be nice to
use EXECUTE-PARSING but SYNONYM parses twice
On Saturday, March 4, 2023 at 8:38:47 PM UTC+1, minf...@arcor.de wrote:
minf...@arcor.de schrieb am Samstag, 4. März 2023 um 18:28:53 UTC+1:[..]
I'm sure someone can make it faster by obfuscation. ;-)
I doubt faster, not obfuscation:
ANEW -binomial
: BIN0 ( n k -- binomial_coefficient )
PARAMS| n k | recursive
n k = IF 1 ELSE
k 0 = IF 1 ELSE
n 1- k bin0
n 1- k 1- bin0 +
ENDIF ENDIF ;
: BIN1 ( n k -- binomial_coefficient )
PARAMS| n k | recursive
n k = IF 1 EXIT ENDIF
k 0 = IF 1 EXIT ENDIF
n 1- k bin1
n 1- k 1- bin1 + ;
: BIN2 ( n k -- binomial_coefficient )
>S >R recursive
S R@ = IF -S -R 1 EXIT ENDIF
S 0 = IF -S -R 1 EXIT ENDIF
R@ 1- S bin2
R@ 1- S 1- bin2 + -S -R ;
#1000 VALUE #times
: TEST CR TIMER-RESET ." \ bin0 : " #times 0 ?DO #20 3 BIN0 DROP LOOP .ELAPSED
CR TIMER-RESET ." \ bin1 : " #times 0 ?DO #20 3 BIN1 DROP LOOP .ELAPSED
CR TIMER-RESET ." \ bin2 : " #times 0 ?DO #20 3 BIN2 DROP LOOP .ELAPSED ;
FORTH> 1000000 TO #times TEST
\ bin0 : 3.838 seconds elapsed.
\ bin1 : 3.754 seconds elapsed.
\ bin2 : 3.729 seconds elapsed. ok
-marcel--
On 04/03/2023 14:17, minf...@arcor.de wrote:
I have been dabbling with simple string pattern matching in Forth
(with ? replacing single characters and * replacing substrings, no regex). >> While formulating the code I began thinking about integrating pattern
matching into my Forth : tricky/difficult(?) because Forth's wordlist search >> mechanism is too dumb. The classic
\ factorial definition
\ fac(0)=1 (hidden: stop recursion)
\ fac(n)=n*fac(n-1)
cannot be translated 1:1 to Forth. Other experiences?
Of course simple things can be converted easily to recursions. F.ex.
(not discussing slow locals here, they are just for visibility)
: END postpone exit postpone then ; IMMEDIATE
: fac {: a :} \ factorial
a 0= IF 1 END
a
a 1- recurse ( fac ) * ;
: fib {: a :} \ fibonacci
a 0= IF 0 END
a 1 = IF 1 END
a 1- fib
a 2 - fib + ;
However fib won't compile because fib is invisible to itself while compiling.
Simple question: Is there any standard way to make a Forth definition
visible during its compilation?? Some old compilers employed a smudge bit
in headers, but what do you do today?
I can think of three ways
The first is delightfully simple but may be regarded as cheating but is >nevertheless valid
synonym foo recurse
e.g.
synonym foo recurse ok
: foo dup . dup 10 < if 1+ foo else drop then ;
1 foo 1 2 3 4 5 6 7 8 9 10 ok
This could be hidden from the user by a defining word that copied
"SYNONYM FOO RECURSE" to a buffer to be EVALUATEd. It would be nice to
use EXECUTE-PARSING but SYNONYM parses twice
-----------------------
The second way is to access the xt left on the stack by :noname
: r: >in @ defer >in ! depth >r :noname depth r> - 1- roll ' defer! ;
e.g.
r: foo dup . dup 10 < if 1+ foo else drop then ; ok
1 foo 1 2 3 4 5 6 7 8 9 10 ok
The use of DEPTH is to reach below control stack stuff that may be left
on the data stack after :NONAME
--------------------------
The third is to use a wordlist, e.g.
wordlist constant rec-wl
defer foo
get-current rec-wl set-current
: foo dup . dup 10 < if 1+ foo else drop then ;
set-current
rec-wl >order ' foo previous is foo
1 foo 1 2 3 4 5 6 7 8 9 10 ok
But why go to this trouble when a simple synonym will do >-----------------------------
I have a fourth method in mind but I need to think about it and will
return to it later today
Gerry
Try 10000 2 CHOOSE
On Sunday, March 5, 2023 at 2:03:18 PM UTC+1, none albert wrote:
Try 10000 2 CHOOSE
or 6 20 CHS
I should know better than try to challenge the locals here...
( I assume you meant
: bin5 ( n m -- b ) >R R@ - 1 R> 1+ 1 ?DO OVER I + I */ LOOP NIP ;
: bin6 ( n m -- b ) 2DUP 2/ > IF >R DUP R> - THEN bin5 ;
)
With 200 3 instead of 20 3, and with only 1000 iteration instead of 100,000: >FORTH> TEST
\ bin0 : 4.126 seconds elapsed.
\ bin1 : 3.433 seconds elapsed.
\ bin2 : 3.453 seconds elapsed.
\ bin3 : 5.474 seconds elapsed.
\ bin4 : 3.145 seconds elapsed.
\ bin5 : 0.000 seconds elapsed. 1313400
\ bin6 : 0.001 seconds elapsed. 1313400 ok
-marcel--
I have been dabbling with simple string pattern matching in Forth
(with ? replacing single characters and * replacing substrings, no regex). While formulating the code I began thinking about integrating pattern matching into my Forth : tricky/difficult(?) because Forth's wordlist search mechanism is too dumb.
On Sunday, March 5, 2023 at 2:03:18 PM UTC+1, none albert wrote:
Try 10000 2 CHOOSE
or 6 20 CHS
I should know better than try to challenge the locals here...
( I assume you meant
: bin5 ( n m -- b ) >R R@ - 1 R> 1+ 1 ?DO OVER I + I */ LOOP NIP ;
: bin6 ( n m -- b ) 2DUP 2/ > IF >R DUP R> - THEN bin5 ;
)
Marcel Hendrix schrieb am Sonntag, 5. März 2023 um 15:23:21 UTC+1:[..]
On Sunday, March 5, 2023 at 2:03:18 PM UTC+1, none albert wrote:
( I assume you meantSee? For speed you sacrificed visibility of the recursive algorithm.
: bin5 ( n m -- b ) >R R@ - 1 R> 1+ 1 ?DO OVER I + I */ LOOP NIP ;
: bin6 ( n m -- b ) 2DUP 2/ > IF >R DUP R> - THEN bin5 ;
)
Not bad per se, it is a design decision.
When your code has to be maintained by other guys anytime later,
you better make a good decision.
More than once I even had to dig myself through my own "optimized
years ago" code and hated it ....
On Sunday, March 5, 2023 at 6:21:07=E2=80=AFPM UTC+1, minf...@arcor.de wrot= >e:...
Marcel Hendrix schrieb am Sonntag, 5. M=C3=A4rz 2023 um 15:23:21 UTC+1:[..]
On Sunday, March 5, 2023 at 2:03:18=E2=80=AFPM UTC+1, none albert wrote= >:
( I assume you meant
: bin5 ( n m -- b ) >R R@ - 1 R> 1+ 1 ?DO OVER I + I */ LOOP NIP ;
: bin6 ( n m -- b ) 2DUP 2/ > IF >R DUP R> - THEN bin5 ;
Apparently, processors have advanced so much that some=20
optimizations became detrimental (why is bin6 so much
slower than bin5?). That is worrisome :--(
In article <49a2d13f-3158-49e2...@googlegroups.com>,
Marcel Hendrix <m...@iae.nl> wrote:
Double recursion is a loss. Single recursion looses to looping,
which is equivalent to tail recursion.
On Sunday, March 5, 2023 at 6:21:07 PM UTC+1, minf...@arcor.de wrote:
Marcel Hendrix schrieb am Sonntag, 5. März 2023 um 15:23:21 UTC+1:[..]
On Sunday, March 5, 2023 at 2:03:18 PM UTC+1, none albert wrote:
( I assume you meantSee? For speed you sacrificed visibility of the recursive algorithm.
: bin5 ( n m -- b ) >R R@ - 1 R> 1+ 1 ?DO OVER I + I */ LOOP NIP ;
: bin6 ( n m -- b ) 2DUP 2/ > IF >R DUP R> - THEN bin5 ;
)
Not bad per se, it is a design decision.
When your code has to be maintained by other guys anytime later,
you better make a good decision.
More than once I even had to dig myself through my own "optimizedI wrote lots of tricky code before I wrote my (extremely tricky) optimizer. The nicest thing about it is that I can now write Forth in a way that
years ago" code and hated it ....
is almost illiterate. The easier I can read it, the easier it is for the compiler to optimize it. It gives me more time to debug and
think about the (top-level) problem I want to solve.
Apparently, processors have advanced so much that some
optimizations became detrimental (why is bin6 so much
slower than bin5?). That is worrisome :--(
-marcel
none albert schrieb am Sonntag, 5. M=C3=A4rz 2023 um 14:03:18 UTC+1:
In article <49a2d13f-3158-49e2...@googlegroups.com>,
Marcel Hendrix <m...@iae.nl> wrote:=20
Double recursion is a loss. Single recursion looses to looping,=20
which is equivalent to tail recursion.=20
Can this really be generalized? IMO recursion benchmarks put stress
rather on a particular calling and return stack handling mechanism
than on the algorithm.
BTW a classic recursion benchmark is calculating the Ackermann function=20
\ Ackermann test
: ACK {: m n -- ackermann :} recursive
m 0=3D IF n 1+ EXIT THEN
n 0=3D IF m 1- 1 ACK EXIT THEN
m 1- m n 1- ACK ACK ;
: T-ACK ." A(3,9) in " 3 9 timer-reset ACK .elapsed ." -> " . ;
T-ACK
Tested with gforth. Increase m or n and the system will crash sooner than l= >ater.
Gforth apparently benefits little from the tail-recursion elimination, similarly for VFX, while lxf benefits a lot (despite taking almost the
same number of instructions). This time around VFX did not suffer as
badly from its locals implementation, but interestingly neither did it benefit much from the conversion to TO N TO M. Gforth suffers from
the conversion to TO N TO M.
Marcel Hendrix schrieb am Sonntag, 5. März 2023 um 15:23:21 UTC+1:
On Sunday, March 5, 2023 at 2:03:18 PM UTC+1, none albert wrote:
Try 10000 2 CHOOSE
or 6 20 CHS
I should know better than try to challenge the locals here...
( I assume you meant
: bin5 ( n m -- b ) >R R@ - 1 R> 1+ 1 ?DO OVER I + I */ LOOP NIP ;
: bin6 ( n m -- b ) 2DUP 2/ > IF >R DUP R> - THEN bin5 ;
)
See? For speed you sacrificed visibility of the recursive algorithm.
Not bad per se, it is a design decision.
When your code has to be maintained by other guys anytime later,
you better make a good decision.
More than once I even had to dig myself through my own "optimized
years ago" code and hated it ....
I wrote lots of tricky code before I wrote my (extremely tricky) optimizer. >The nicest thing about it is that I can now write Forth in a way that
is almost illiterate. The easier I can read it, the easier it is for the >compiler to optimize it. It gives me more time to debug and
think about the (top-level) problem I want to solve.
Apparently, processors have advanced so much that some
optimizations became detrimental (why is bin6 so much
slower than bin5?). That is worrisome :--(
-marcel
Marcel Hendrix <m...@iae.nl> writes:
On Sunday, March 5, 2023 at 6:21:07=E2=80=AFPM UTC+1, minf...@arcor.de wrote:...
Marcel Hendrix schrieb am Sonntag, 5. M=C3=A4rz 2023 um 15:23:21 UTC+1:[..]
On Sunday, March 5, 2023 at 2:03:18=E2=80=AFPM UTC+1, none albert wrote >:
( I assume you meant
: bin5 ( n m -- b ) >R R@ - 1 R> 1+ 1 ?DO OVER I + I */ LOOP NIP ;
: bin6 ( n m -- b ) 2DUP 2/ > IF >R DUP R> - THEN bin5 ;
Apparently, processors have advanced so much that someGiven that I don't know what arguments you passed for benchmarking,
optimizations became detrimental (why is bin6 so much
slower than bin5?). That is worrisome :--(
and I don't understand what's bin6 and bin5 do, I don't know what the
machine code is you are benchmarking, I can only make wild guesses.
E.g., we found that implementing FM/MOD through UM/MOD on Intel
Skylake is slow for negative dividends (IIRC, and of course the usual positive divisors), because that invokes the slow 128/64-bit division
rather than the faster 64/64-bit division. So we went back to
sythesizing FM/MOD from SM/REM (actually the idiv instruction). Who
knows what hardware characteristic bin6 runs afould of?
- 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: https://forth-standard.org/
EuroForth 2022: https://euro.theforth.net
S >R recursiveS R@ = IF -S -R 1 EXIT ENDIF
"minf...@arcor.de" <minf...@arcor.de> writes:
none albert schrieb am Sonntag, 5. M=C3=A4rz 2023 um 14:03:18 UTC+1:
In article <49a2d13f-3158-49e2...@googlegroups.com>,
Marcel Hendrix <m...@iae.nl> wrote:=20
Double recursion is a loss. Single recursion looses to looping,=20
which is equivalent to tail recursion.=20
Can this really be generalized? IMO recursion benchmarks put stress
rather on a particular calling and return stack handling mechanism
than on the algorithm.
BTW a classic recursion benchmark is calculating the Ackermann function=20
\ Ackermann test
: ACK {: m n -- ackermann :} recursive
m 0=3D IF n 1+ EXIT THEN
n 0=3D IF m 1- 1 ACK EXIT THEN
m 1- m n 1- ACK ACK ;
: T-ACK ." A(3,9) in " 3 9 timer-reset ACK .elapsed ." -> " . ;
T-ACK
Tested with gforth. Increase m or n and the system will crash sooner than l=
ater.
Here are some variations on that:
s" gforth" environment? [if]
: ACK {: m n -- ackermann :} recursive
m 0= IF n 1+ EXIT THEN
n 0= IF m 1- 1 ACK EXIT THEN
m 1- m n 1- ACK ACK ;
: ack2
case {: m n -- ackermann :} recursive
m 0= ?of n 1+ exit endof
n 0= ?of m 1- 1 contof
m 1- m n 1- ack2
next-case ;
[then]
: ACK3 {: m n -- ackermann :}
m 0= IF n 1+ EXIT THEN
n 0= IF m 1- 1 recurse EXIT THEN
m 1- m n 1- recurse recurse ;
: ack4 {: m n -- ackermann :}
m n begin begin to n to m
m 0= if n 1+ exit then
n 0= while m 1- 1 repeat
m 1- m n 1- recurse
again ;
ACK is the original. ACK2 performs manual tail-call elimination using
CONTOF and NEXT-CASE, which are ideal for the job. ACK3 is a standard variant of ACK: replace RECURSIVE by using RECURSE. ACK4 is a
standard version of ACK2: replace case ... with begin begin, and
replace locals definition at the start of each iteration with TO N TO
M.
The behaviour is not very obvious, so let's shed some light on it by
showing execution counts:
: ack4 ( 22345074) {: m n -- ackermann :}
( 22345074) m n begin ( 44690147) begin ( 44698325) to n to m
( 44698325) m 0= if ( 22345074) n 1+ exit then ( 22353251)
( 22353251) n 0= while ( 8178) m 1- 1 repeat ( 22345073)
( 22345073) m 1- m n 1- recurse
( 22345073) again ;
The case counts are the same for the other variants: The first and
last cases have the same (but one) execution counts, and the middle
one has the (small) rest. So tail-recursion elimination eliminates
roughly half of the recursions.
Let's see how they perform (on a Ryzen 5800X):
for i in ack ack2 ack3 ack4; do LC_NUMERIC=prog perf stat -e cycles:u -e instructions:u ~/nfstmp/gforth-amd64/gforth-fast -l 1G -r 1G -d 1G -e "include $HOME/forth/ackermann.4th 3 10 $i . bye"; done
for i in ack3 ack4; do LC_NUMERIC=prog perf stat -e cycles:u -e instructions:u vfx64 "include $HOME/forth/ackermann.4th 3 10 $i . bye"; done
for i in ack3 ack4; do LC_NUMERIC=prog perf stat -e cycles:u -e instructions:u lxf "include $HOME/forth/ackermann.4th 3 10 $i . bye"; done
ACK ack2 ACK3 ACK4 cycles:u
739_768_612 717_251_597 745_004_140 1_276_903_646 gforth-fast
477_151_202 437_875_753 vfx64
408_972_990 276_978_910 lxf
ACK ack2 ACK3 ACK4 instructions:u
2_373_134_143 2_194_315_903 2_373_134_090 3_043_508_701 gforth-fast 1_059_344_723 1_126_322_867 vfx64
939_060_171 939_035_622 lxf
SwiftForth 4.0.0-RC52 crashed, and I was too lazy to find out how to increase the stack sizes.
Gforth apparently benefits little from the tail-recursion elimination, similarly for VFX, while lxf benefits a lot (despite taking almost the
same number of instructions). This time around VFX did not suffer as
badly from its locals implementation, but interestingly neither did it benefit much from the conversion to TO N TO M. Gforth suffers from
the conversion to TO N TO M.
- 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: https://forth-standard.org/
EuroForth 2022: https://euro.theforth.net
: TAK {: x y z -- takeuchi :} recursive...
y x < IF=20
x 1- y z TAK
y 1- z x TAK
z 1- x y TAK=20
TAK
ELSE z THEN ;
=20
: TAK1 {: x y z -- takeuchi :}
y x < IF
x 1- y z recurse
y 1- z x recurse
z 1- x y recurse
recurse
ELSE z THEN ;
=20
: TAK2 {: x y z -- takeuchi :} \ tail recursive?
y x >=3D IF z EXIT THEN
x 1- y z recurse
y 1- z x recurse
z 1- x y recurse
recurse ;
Unsurprisingly RECURSE makes for faster code than RECURSIVE,
Anton Ertl schrieb am Montag, 6. März 2023 um 10:44:53 UTC+1:[..]
Those locals should not make any timing difference. This is no test[..]
for absolute speed.
On my battered old laptop (Windows 11):
include tak.mf
TAK: 18.938586900s
TAK1: 17.137006100s
TAK2: 17.369053900s ok
Unsurprisingly RECURSE makes for faster code than RECURSIVE, but neglible IMO.
The difference between TAK1 and TAK2 is practically zero, but perhaps I did something wrong here.
On Monday, March 6, 2023 at 11:21:22 AM UTC+1, minf...@arcor.de wrote:
Anton Ertl schrieb am Montag, 6. März 2023 um 10:44:53 UTC+1:[..]
Those locals should not make any timing difference. This is no test
for absolute speed.
On my battered old laptop (Windows 11):[..]
include tak.mf
TAK: 18.938586900s
TAK1: 17.137006100s
TAK2: 17.369053900s ok
Unsurprisingly RECURSE makes for faster code than RECURSIVE, but neglible IMO.Indeed. The tail-call removal does not make it faster. Neither does local removal.
The difference between TAK1 and TAK2 is practically zero, but perhaps I did
something wrong here.
-marcel
ANEW -tak
: TAK PARAMS| x y z | \ -- u
recursive
y x < IF
x 1- y z TAK
y 1- z x TAK
z 1- x y TAK
TAK
ELSE z ENDIF ;
: TAK1 PARAMS| x y z | \ -- u
y x < IF
x 1- y z recurse
y 1- z x recurse
z 1- x y recurse
recurse
ELSE z ENDIF ;
: TAK2 PARAMS| x y z | \ -- u tail recursive?
y x >= IF z EXIT ENDIF
x 1- y z recurse
y 1- z x recurse
z 1- x y recurse
recurse ;
: TAK3 PARAMS| x y z | \ -- u tail recursive?
BEGIN
y x >= IF z EXIT ENDIF
x 1- y z recurse
y 1- z x recurse
z 1- x y recurse
TO z TO y TO x
AGAIN ;
: TAK4 ( x y z -- u ) \ tail recursive?
BEGIN
OVER 3 PICK >= IF NIP NIP EXIT ENDIF
3DUP ROT 1- -ROT recurse >S
3DUP SWAP 1- SWAP ROT recurse >S
1- -ROT recurse S> S> SWAP ROT
AGAIN ;
: TAK-TEST
cr ." \ TAK: " #19 1 #19 timer-reset tak drop .elapsed
cr ." \ TAK1: " #19 1 #19 timer-reset tak1 drop .elapsed
cr ." \ TAK2: " #19 1 #19 timer-reset tak2 drop .elapsed
cr ." \ TAK3: " #19 1 #19 timer-reset tak3 drop .elapsed
cr ." \ TAK4: " #19 1 #19 timer-reset tak4 drop .elapsed ;
\ TAK: 1.966 seconds elapsed.
\ TAK1: 1.971 seconds elapsed.
\ TAK2: 2.129 seconds elapsed.
\ TAK3: 2.254 seconds elapsed.
\ TAK4: 2.075 seconds elapsed.
TAK-TEST
Hi,
I maybe missing something (it is too late here) but these two 'fib' and 'fact' are simple in a sense that recursion at first seems for me to fight against the so called Forth-Way (simple small steps).
: fib ( n1 n0 -- n2 ) OVER + SWAP ; \ another fun thing I did before is to CODE 'XADD' x86 instruction.
1 0 fib CR .S
1 1
fib CR .S
2 1 \ ... etc
: fact ( n -- fn ) 1 SWAP 1+ 1 DO I * LOOP ;
if by pattern matching it was meant visual text organization, then i used to change some the normal Forth words '[' ']' and add another one 'I' from Oberon (or Pascal), all for syntactic sugars, otherwise please ignore my post:
VOCABULARY test ALSO test DEFINITIONS
SYNONYM ` POSTPONE \ backtick borrowed from CL in a try to reduce the verbose postpone
: [ ` IF ` DROP ; IMMEDIATE
: ] ` EXIT ` THEN ; IMMEDIATE
: | DUP ; \ this with above two act in a sense as a CASE construct.
: fact ( n -- fn )
| 0 = [ 1 ]
| 1- RECURSE * ;
: fib ( n -- fn )
| 0 = [ 0 ]
| 1 = [ 1 ]
| 1- RECURSE SWAP 2- RECURSE + ;
Hope it help.
In article <03e84c31-013f-4bcc...@googlegroups.com>,
Then I got bored, and eliminated the 12 versions from my
library, as it isn't deserving for a library, not even as
an example.
Marcel Hendrix schrieb am Dienstag, 7. März 2023 um 01:18:49 UTC+1:
On Monday, March 6, 2023 at 11:21:22 AM UTC+1, minf...@arcor.de wrote:neglible IMO.
Anton Ertl schrieb am Montag, 6. März 2023 um 10:44:53 UTC+1:[..]
Those locals should not make any timing difference. This is no test[..]
for absolute speed.
On my battered old laptop (Windows 11):
include tak.mf
TAK: 18.938586900s
TAK1: 17.137006100s
TAK2: 17.369053900s ok
Unsurprisingly RECURSE makes for faster code than RECURSIVE, but
local removal.The difference between TAK1 and TAK2 is practically zero, but perhaps I didIndeed. The tail-call removal does not make it faster. Neither does
something wrong here.
-marcel
ANEW -tak
: TAK PARAMS| x y z | \ -- u
recursive
y x < IF
x 1- y z TAK
y 1- z x TAK
z 1- x y TAK
TAK
ELSE z ENDIF ;
: TAK1 PARAMS| x y z | \ -- u
y x < IF
x 1- y z recurse
y 1- z x recurse
z 1- x y recurse
recurse
ELSE z ENDIF ;
: TAK2 PARAMS| x y z | \ -- u tail recursive?
y x >= IF z EXIT ENDIF
x 1- y z recurse
y 1- z x recurse
z 1- x y recurse
recurse ;
: TAK3 PARAMS| x y z | \ -- u tail recursive?
BEGIN
y x >= IF z EXIT ENDIF
x 1- y z recurse
y 1- z x recurse
z 1- x y recurse
TO z TO y TO x
AGAIN ;
: TAK4 ( x y z -- u ) \ tail recursive?
BEGIN
OVER 3 PICK >= IF NIP NIP EXIT ENDIF
3DUP ROT 1- -ROT recurse >S
3DUP SWAP 1- SWAP ROT recurse >S
1- -ROT recurse S> S> SWAP ROT
AGAIN ;
: TAK-TEST
cr ." \ TAK: " #19 1 #19 timer-reset tak drop .elapsed
cr ." \ TAK1: " #19 1 #19 timer-reset tak1 drop .elapsed
cr ." \ TAK2: " #19 1 #19 timer-reset tak2 drop .elapsed
cr ." \ TAK3: " #19 1 #19 timer-reset tak3 drop .elapsed
cr ." \ TAK4: " #19 1 #19 timer-reset tak4 drop .elapsed ;
\ TAK: 1.966 seconds elapsed.
\ TAK1: 1.971 seconds elapsed.
\ TAK2: 2.129 seconds elapsed.
\ TAK3: 2.254 seconds elapsed.
\ TAK4: 2.075 seconds elapsed.
TAK-TEST
Even TAK4 didn't make the day. Deep recursion seems to walk
the stacks too much in slow RAM, so that native code compilation
using CPU registers cannot really demonstrate its speed advantage.
Gerry Jackson <do-not-use@swldwa.uk> writes:
synonym foo recurse ok
: foo dup . dup 10 < if 1+ foo else drop then ;
1 foo 1 2 3 4 5 6 7 8 9 10 ok
This could be hidden from the user by a defining word that copied
"SYNONYM FOO RECURSE" to a buffer to be EVALUATEd. It would be nice to
use EXECUTE-PARSING but SYNONYM parses twice
That does not mean that you cannot use EXECUTE-PARSING. Gforth's
SYNONYM parses only once, so we cannot use that for checking, so let's
define a word that parses twice:
: pseudo-sym ( "name1 name2" -- )
>in @
cr ." name1: " parse-name type
cr ." name2: " parse-name type
>in !
cr ." name1: " parse-name type
cr ." name2: " parse-name type
;
s" x y" ' pseudo-sym execute-parsing
Works both with the built-in EXECUTE-PARSING and with the
implementation in standard Forth in compat/execute-parsing.fs.
: (rec) postpone recurse ;
: r: >in @ >r : r> >in ! postpone (rec) postpone ; immediate : ;
r: foo dup . dup 10 < if 1+ foo else drop then ;
3 foo 3 4 5 6 7 8 9 10 ok
Gerry Jackson <do-not-use@swldwa.uk> writes:
: (rec) postpone recurse ;
: r: >in @ >r : r> >in ! postpone (rec) postpone ; immediate : ;
r: foo dup . dup 10 < if 1+ foo else drop then ;
3 foo 3 4 5 6 7 8 9 10 ok
Cute. But unfortunately does not work for the cases where RECURSIVE
really allows things that RECURSE does not support:
: foo recursive ... ['] foo map-list ... ;
: bar recursive ... [: ... bar ... ;] ... ;
- anton
Gerry Jackson <do-not-use@swldwa.uk> writes:
: (rec) postpone recurse ;
: r: >in @ >r : r> >in ! postpone (rec) postpone ; immediate : ;
r: foo dup . dup 10 < if 1+ foo else drop then ;
3 foo 3 4 5 6 7 8 9 10 ok
Cute. But unfortunately does not work for the cases where RECURSIVE
really allows things that RECURSE does not support:
: foo recursive ... ['] foo map-list ... ;
: bar recursive ... [: ... bar ... ;] ... ;
- anton
| Sysop: | Keyop |
|---|---|
| Location: | Huddersfield, West Yorkshire, UK |
| Users: | 475 |
| Nodes: | 16 (2 / 14) |
| Uptime: | 18:43:21 |
| Calls: | 9,487 |
| Calls today: | 6 |
| Files: | 13,617 |
| Messages: | 6,121,093 |