Pattern matching

[minf...@arcor.de]

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]

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

[minf...@arcor.de]

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?

[NN]

I wasnt aware of RECURSIVE and I have not used it before.
Do you have any examples where I can see it being used ?
I looked at gforth manual but the stack comment isnt enough.

[Anton Ertl]

NN <novembe...@gmail.com> writes:
>Do you have any examples where I can see it being used ?

: fac {: n -- n2 :} recursive
n 0= if
1
else
n 1- fac n *
then ;

>I looked at gforth manual but the stack comment isnt enough.

The tutorial contains an example:
<https://www.complang.tuwien.ac.at/forth/gforth/Docs-html/Recursion-Tutorial.html>

The reference part says:

|'recursive' ( compilation -- ; run-time -- ) gforth-0.2 "recursive"
| Make the current definition visible, enabling it to call itself
|recursively.

- 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

[Anton Ertl]

"minf...@arcor.de" <minf...@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 Ertl]

"minf...@arcor.de" <minf...@arcor.de> writes:
>OTOH using RECURSIVE allows for nested calls of yet unfinished definitions
>whereas RECURSE just "jumps back".

Well, with quotations the difference between RECURSIVE and RECURSE
becomes more relevant. Consider:

: foo recursive
... [: ... recurse ... foo ... ;] ... ;

The RECURSE inside the quotation calls the quotation, while the FOO
calls FOO.

>Which one would make tail call eliminati=
>on
>easier?

For tail-call elimination, it does not matter. If you are interested
in tail-recursion elimination only, I guess that RECURSE might be
slightly easier. However, the way I would do it, I would go for
tail-call elimination, which buys much more for typical Forth code and
is not any harder to implement.

[none albert]

In article <2023Mar...@mips.complang.tuwien.ac.at>,

Anton Ertl <an...@mips.complang.tuwien.ac.at> wrote:
>"minf...@arcor.de" <minf...@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.

You have just answered that question in the affirmative.
RECURSIVE does the job. What am I missing?

>
>>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

Groetjes Albert
--
Don't praise the day before the evening. One swallow doesn't make spring.
You must not say "hey" before you have crossed the bridge. Don't sell the
hide of the bear until you shot it. Better one bird in the hand than ten in
the air. First gain is a cat spinning. - the Wise from Antrim -

[Marcel Hendrix]

On Saturday, March 4, 2023 at 5:16:17 PM UTC+1, Anton Ertl wrote:
[..]
> <http://git.savannah.gnu.org/cgit/gforth.git/tree/regexp.fs>

+++1

Any examples to test this out?

-marcel

[Anton Ertl]

albert@cherry.(none) (albert) writes:
>In article <2023Mar...@mips.complang.tuwien.ac.at>,
>Anton Ertl <an...@mips.complang.tuwien.ac.at> wrote:
>>"minf...@arcor.de" <minf...@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?

It's non-standard.

[Anton Ertl]

Marcel Hendrix <m...@iae.nl> writes:

>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?

Looking around, I did not find any, sorry.

[minf...@arcor.de]

minf...@arcor.de schrieb am Samstag, 4. März 2023 um 18:28:53 UTC+1:

> : fib recursive ( u -- fibonacci )
> dup 2 u< ?exit
> dup 1- fib swap 2 - fib + ;
>
> \ : ?exit postpone if postpone exit postpone then ; immediate

Another classic:
: BIN {: n k -- binomial_coefficient :} recursive
n k = IF 1 ELSE
k 0= IF 1 ELSE
n 1- k bin
n 1- k 1- bin +
THEN THEN ;

I'm sure someone can make it faster by obfuscation. ;-)

[Marcel Hendrix]

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

[minf...@arcor.de]

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.

[Gerry Jackson]

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

[Anton Ertl]

Gerry Jackson <do-no...@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.

[Marcel Hendrix]

On Sunday, March 5, 2023 at 3:11:26 AM UTC+1, minf...@arcor.de wrote:
> 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.

In my book, that is not obfuscation, that is using a better algorithm.

-marcel

[none albert]

In article <tu1gof$18j58$1...@dont-email.me>,

And then there is Albert's method which is actually c's.

:F FIB ; \ Forward definition, full header
:R FIB DUP 1- FIB SWAP FIB + ; \ Infinite loop, but we don't care.

:R couples the body into the previous header.

This works nice with recursive function.

[
c:
void func();
\ and later
void func()
{
printf("We are tired of Fibonacci series\n");
}

]


>Gerry

[none albert]

In article <49a2d13f-3158-49e2...@googlegroups.com>,

Try 10000 2 CHOOSE

I prefer
2 \ For N M return "N OVER M " (N/M)
3 : CHS >R R@ - 1 R> 1+ 1 ?DO OVER I + I */ LOOP NIP ;

It can be sped up by
: CHS 2DUP 2/ > IF >R DUP R> - THEN CHS ;

Double recursion is a loss. Single recursion looses to looping,
which is equivalent to tail recursion.

>
>-marcel

[Marcel Hendrix]

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 ;
)

FORTH> 1000000 TO #times TEST

\ bin0 : 3.356 seconds elapsed.
\ bin1 : 2.965 seconds elapsed.
\ bin2 : 3.056 seconds elapsed.
\ bin3 : 3.800 seconds elapsed.
\ bin4 : 2.636 seconds elapsed.
\ bin5 : 0.007 seconds elapsed.
\ bin6 : 0.039 seconds elapsed. ok
FORTH>

In iForth bin6 is really slow.
FORTH> 100000000 TO #times TEST MANY
\ bin5 : 0.587 seconds elapsed.
\ bin6 : 3.901 seconds elapsed.
\ bin5 : 0.581 seconds elapsed.
\ bin6 : 3.901 seconds elapsed.
...
\ bin5 : 0.594 seconds elapsed.
\ bin6 : 3.901 seconds elapsed.
\ bin5 : 0.593 seconds elapsed.
\ bin6 : 3.902 seconds elapsed. ok

I have a hard time understanding that...

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

[none albert]

In article <64382e20-7aff-461b...@googlegroups.com>,

Marcel Hendrix <m...@iae.nl> wrote:
>On Sunday, March 5, 2023 at 2:03:18 PM UTC+1, none albert wrote:
>
>> Try 10000 2 CHOOSE
>
>or 6 20 CHS

I have improved ?DO , at the cost of not reproducing ISO-required
crashes.

6 20 CHS .
0 OK

MARK-TIME 10,000 2 CHS . ELAPSED .uS
49995000 128 uS OK

>
>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 ;
>)

Something like that.

>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
>

This means that bin5 is more sensible than the double recursion?

[minf...@arcor.de]

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 ....

[Gerry Jackson]

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.

Can't you use TRAVERSE-WORDLIST ( i*x xt wid -- j*x )
where the word with execution token xt has ( k*x nt -- l*x f )

With the xt of a word such as (untested):

: test-for-?|* ( nt -- f )
name>string
begin
over c@ dup '?' = over '*' = or ( -- ca u ch f )
if ( process the name ... ) then
while
1 /string
repeat
0
;

' test-for-?|* a-wid traverse-wordlist

--
Gerry

[Marcel Hendrix]

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 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

[Anton Ertl]

Marcel Hendrix <m...@iae.nl> writes:
>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 :--(

Given that I don't know what arguments you passed for benchmarking,
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?

[minf...@arcor.de]

none albert schrieb am Sonntag, 5. März 2023 um 14:03:18 UTC+1:
> 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.

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

\ Ackermann test
: 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 ;
: 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 later.

[P Falth]

Try instead

: bin6 over 2/ over < if >r dup r> - then bin5 ;

You are turning 20 3 into 20 17 witch takes much longer time to calculate!

Peter

> -marcel

[Anton Ertl]

"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.

[none albert]

In article <0637fb7a-7574-41dd...@googlegroups.com>,

bin5 is not optimised. It is the only sensible implementation of
choose for integer, not approximate, results.
bin6 is slightly optimised based in an obvious way.
The other approach is by reals. m!/n!/(m-n)! that could be had by the
real approximation formula for the faculty operator.

I always choose transparancy over speed. For example ciforth's
don't use the ubiquitous optimisation of keeping the top of stack
in a register. I work on a separate optimiser, that you can choose
not to use.

Groetjes Albert

[minf...@arcor.de]

Anton Ertl schrieb am Montag, 6. März 2023 um 10:44:53 UTC+1:
> 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.

In his paper about textbook recursive functions Knuth mentioned also the
heavily recursive Takeuchi function.

: TAK {: x y z -- takeuchi :} recursive
y x < IF
x 1- y z TAK
y 1- z x TAK
z 1- x y TAK
TAK
ELSE z THEN ;

: 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 ;

: TAK2 {: x y z -- takeuchi :} \ tail recursive?
y x >= IF z EXIT THEN
x 1- y z recurse
y 1- z x recurse
z 1- x y recurse
recurse ;

: 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 ;

TAK-TEST

Those locals should not make any timing difference. This is no test
for absolute speed.

On my battered old laptop (Windows 11):

Gforth 0.7.9_20200709
Authors: Anton Ertl, Bernd Paysan, Jens Wilke et al., for more type `authors'
Copyright © 2019 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <https://gnu.org/licenses/gpl.html>
Gforth comes with ABSOLUTELY NO WARRANTY; for details type `license'
Type `help' for basic help
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.

[none albert]

In article <9ce0c7f4-8f77-4c84...@googlegroups.com>,
Marcel Hendrix <m...@iae.nl> wrote:
<SNIP>

>
>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.

Exactly my thoughts, if not my influence.

>Apparently, processors have advanced so much that some
>optimizations became detrimental (why is bin6 so much
>slower than bin5?). That is worrisome :--(

bin6 has to be used in circumstances where you would rather
find chs(100,97) than chs(100,3). There you will reap
a substantial benefit.

CHS is often useful in investigating small examples.
E.g. for solving euler project 813 you can get an idea
of what happens , but it is not used in the final solution.

>
>-marcel

[Marcel Hendrix]

On Sunday, March 5, 2023 at 11:09:41 PM UTC+1, Anton Ertl wrote:
> 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 some

> >optimizations became detrimental (why is bin6 so much
> >slower than bin5?). That is worrisome :--(
> Given that I don't know what arguments you passed for benchmarking,
> 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

Albert already cleared this up. His optimization was the other way around
and I trusted without checking.

ANEW -binomial

0 VALUE res

: 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 DUP TO res ;

: 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 + DUP TO res ;

: 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 DUP TO res ;

: BIN3 ( n k -- binomial_coefficient )

PARAMS| n k | recursive
n k = IF 1 EXIT ENDIF
k 0 = IF 1 EXIT ENDIF

n 2 = k 1 = AND IF 2 EXIT ENDIF
n 3 = k 1 = AND IF 3 EXIT ENDIF
n 3 = k 2 = AND IF 3 EXIT ENDIF
n 1- k bin3
n 1- k 1- bin3 + DUP TO res ;

: BIN4 ( n k -- binomial_coefficient )
recursive
2DUP = OVER 0= OR IF 2DROP 1 EXIT ENDIF
OVER 1- OVER bin4 -ROT
SWAP 1- SWAP 1- bin4 + DUP TO res ;

-- AvdH
: bin5 ( n m -- b ) >R R@ - 1 R> 1+ 1 ?DO OVER I + I */ LOOP NIP DUP TO res ;
: bin6 ( n m -- b ) 2DUP 2/ > IF >R DUP R> - ENDIF bin5 ;

#1000000 VALUE #times
#20 3 DVALUE #input

: TEST ( -- )
CR ." #input = " #input SWAP . .
CR TIMER-RESET ." \ bin0 : " #times 0 ?DO #input BIN0 DROP LOOP .ELAPSED SPACE res .
CR TIMER-RESET ." \ bin1 : " #times 0 ?DO #input BIN1 DROP LOOP .ELAPSED SPACE res .
CR TIMER-RESET ." \ bin2 : " #times 0 ?DO #input BIN2 DROP LOOP .ELAPSED SPACE res .
CR TIMER-RESET ." \ bin3 : " #times 0 ?DO #input BIN3 DROP LOOP .ELAPSED SPACE res .
CR TIMER-RESET ." \ bin4 : " #times 0 ?DO #input BIN4 DROP LOOP .ELAPSED SPACE res .
CR TIMER-RESET ." \ bin5 : " #times 0 ?DO #input BIN5 DROP LOOP .ELAPSED SPACE res .
CR TIMER-RESET ." \ bin6 : " #times 0 ?DO #input BIN6 DROP LOOP .ELAPSED SPACE res . ;

\ FORTH> #20 #17 TO #input 1000000 TO #times TEST
\ bin0 : 3.628 seconds elapsed. 1140
\ bin1 : 3.691 seconds elapsed. 1140
\ bin2 : 3.730 seconds elapsed. 1140
\ bin3 : 4.181 seconds elapsed. 1140
\ bin4 : 3.371 seconds elapsed. 1140
\ bin5 : 0.035 seconds elapsed. 1140
\ bin6 : 0.006 seconds elapsed. 1140 ok

\ FORTH> #20 3 TO #input 1000000 TO #times TEST
\ bin0 : 3.405 seconds elapsed. 1140
\ bin1 : 3.228 seconds elapsed. 1140
\ bin2 : 3.076 seconds elapsed. 1140
\ bin3 : 3.998 seconds elapsed. 1140
\ bin4 : 2.749 seconds elapsed. 1140
\ bin5 : 0.007 seconds elapsed. 1140
\ bin6 : 0.038 seconds elapsed. 1140 ok

DOC
(*
' bin5 idis
FORTH> ' bin5 idis
$0133EB80 : bin5
$0133EB8A pop rbx
$0133EB8B pop rdi
$0133EB8C sub rdi, rbx
$0133EB8F push rdi
$0133EB90 push 1 b#
$0133EB92 lea rbx, [rbx 1 +] qword
$0133EB96 push rbx
$0133EB97 mov rbx, 1 d#
$0133EB9E pop rcx
$0133EB9F call (?DO) offset NEAR
$0133EBA9 lea rax, [rax 0 +] qword
$0133EBB0 pop rdi
$0133EBB1 mov rax, [rbp 0 +] qword
$0133EBB5 mov rdx, [rbp 0 +] qword
$0133EBB9 push rdi
$0133EBBA push rbx
$0133EBBB lea rbx, [rdi rax*1] qword
$0133EBBF push rbx
$0133EBC0 mov rbx, rdx
$0133EBC3 pop rcx
$0133EBC4 pop rax
$0133EBC5 imul rcx
$0133EBC8 idiv rbx
$0133EBCB mov rbx, rax
$0133EBCE add [rbp 0 +] qword, 1 b#
$0133EBD3 add [rbp 8 +] qword, 1 b#
$0133EBD8 jno $0133EBB0 offset NEAR
$0133EBDE add rbp, #24 b#
$0133EBE2 pop rdi
$0133EBE3 mov $0133E2C0 qword-offset, rbx
$0133EBEA push rbx
$0133EBEB ;
*)
ENDDOC

-marcel

[Ala'a]

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.

[P Falth]

I made a version without locals to see the difference on lxf.

: ack5 ( m n -- ackermann )
over 0= if nip 1+ exit then
dup 0= if drop 1- 1 recurse exit then
over 1- -rot 1- recurse recurse ;

Compared to ack3 its size is half and it runs in 30% of the time!
67% of the time of ack4.
2 of the recursive calls are transformed to tail jumps.

BR
Peter Fälth

[Anton Ertl]

"minf...@arcor.de" <minf...@arcor.de> writes:
>: 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,

That's pretty surprising, because they generate the same code:

simple-see tak simple-see tak1
$7F13CFD4AAF0 >l $7F13CFD4AC28 >l
$7F13CFD4AAF8 >l $7F13CFD4AC30 >l
$7F13CFD4AB00 >l $7F13CFD4AC38 >l
$7F13CFD4AB08 @local1 $7F13CFD4AC40 @local1
$7F13CFD4AB10 @local0 $7F13CFD4AC48 @local0
$7F13CFD4AB18 < $7F13CFD4AC50 <
$7F13CFD4AB20 ?branch $7F13CFD4AC58 ?branch
$7F13CFD4AB28 <TAK+$F0> $7F13CFD4AC60 <TAK1+$F0>
$7F13CFD4AB30 @local0 $7F13CFD4AC68 @local0
$7F13CFD4AB38 1- $7F13CFD4AC70 1-
$7F13CFD4AB40 @local1 $7F13CFD4AC78 @local1
$7F13CFD4AB48 @local2 $7F13CFD4AC80 @local2
$7F13CFD4AB50 call $7F13CFD4AC88 call
$7F13CFD4AB58 TAK $7F13CFD4AC90 TAK1
$7F13CFD4AB60 @local1 $7F13CFD4AC98 @local1
$7F13CFD4AB68 1- $7F13CFD4ACA0 1-
$7F13CFD4AB70 @local2 $7F13CFD4ACA8 @local2
$7F13CFD4AB78 @local0 $7F13CFD4ACB0 @local0
$7F13CFD4AB80 call $7F13CFD4ACB8 call
$7F13CFD4AB88 TAK $7F13CFD4ACC0 TAK1
$7F13CFD4AB90 @local2 $7F13CFD4ACC8 @local2
$7F13CFD4AB98 1- $7F13CFD4ACD0 1-
$7F13CFD4ABA0 @local0 $7F13CFD4ACD8 @local0
$7F13CFD4ABA8 @local1 $7F13CFD4ACE0 @local1
$7F13CFD4ABB0 call $7F13CFD4ACE8 call
$7F13CFD4ABB8 TAK $7F13CFD4ACF0 TAK1
$7F13CFD4ABC0 call $7F13CFD4ACF8 call
$7F13CFD4ABC8 TAK $7F13CFD4AD00 TAK1
$7F13CFD4ABD0 branch $7F13CFD4AD08 branch
$7F13CFD4ABD8 <TAK+$F8> $7F13CFD4AD10 <TAK1+$F8>
$7F13CFD4ABE0 @local2 $7F13CFD4AD18 @local2
$7F13CFD4ABE8 lp+!# $7F13CFD4AD20 lp+!#
$7F13CFD4ABF0 #24 $7F13CFD4AD28 #24
$7F13CFD4ABF8 ;s $7F13CFD4AD30 ;s

There might be code alignment effects at work here, otherwise I have
no explanation for the speed difference.

Let's see if I can reproduce this on the Ryzen 5800X:

tak tak1 tak2
22_099_055_171 23_462_308_360 21_880_314_922 cycles:u
78_640_379_117 79_692_648_633 75_834_327_753 instructions:u

So here TAK is slightly faster than TAK1 (but I have also seen runs
where TAK1 takes 29G cycles), and the number of instructions is also
slightly higher for tak1 (possibly the result of nop-padding for
aligning branch targets).

[Marcel Hendrix]

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.
> The difference between TAK1 and TAK2 is practically zero, but perhaps I did
> something wrong here.

Indeed. The tail-call removal does not make it faster. Neither does local removal.

-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

[minf...@arcor.de]

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.

[minf...@arcor.de]

Thanks for your input. Actually pattern matching with numbers is a too simple exercise
because it boils down to comparing and handling different cases, with or without recursion,
as shown at length within this thread.

Simple pattern matching with strings is also feasible, for more you'll soon need a regexp package.
For tuples/structures, lists/arrays you need a library, most probablay in a DIY way. Arity check or
type check is practically impossible in Forth.

But at least in Forth you can build a mini-DSL (or syntactic sugar as you coined it). My own
syntax ideas had run around this concept:

: FDIV ( nom den -- quot )
| 0 0 => INVALID | \ special signalling NaN
| 0 _ => SATURATION _ 0< IF FNEGATE THEN | \ special signalling NaN
| _ _ => F/ ;

Is it worth it? Definitely not for someone who can read Forth already. But it could ease things
for other guys who have to understand what you did, eg for doing software maintenance.

[none albert]

In article <03e84c31-013f-4bcc...@googlegroups.com>,

I ended up with the mutually recursive version only using the
stacks.

(It is indeed version 12)

( tak12 using 3SWAP NIP and PICK )
: PICK 1+ CELLS DSP@ + @ ;
: NIP SWAP DROP ;
: 3SWAP SWAP ROT ; \ Reverse top 3 elements.
: tak' ; ( Forward reference)
\ Auxiliary: For Z Y X --- return Z Y X tak(X-1,Y,Z)
: kat
2DUP 1- < IF
1- ROT RECURSE >R ROT RECURSE >R ROT RECURSE >R 1+
R> R> R> tak'
ELSE
2 PICK
THEN ;
: tak 3SWAP 1+ kat NIP NIP NIP ;
'tak >DFA @ 'tak' >DFA ! ( Solve forward reference)

It looks prettier by using forward definitions:
\ ---------------------------
:F kat ; :F tak ;

\ Auxiliary: For Z Y X --- return Z Y X tak(X-1,Y,Z)
:R kat
2DUP 1- < IF
1- ROT kat >R ROT kat >R ROT kat >R 1+
R> R> R> tak
ELSE
2 PICK
THEN ;
:R tak 3SWAP 1+ kat NIP NIP NIP ;
\ ---------------------------

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.

[minf...@arcor.de]

none albert schrieb am Dienstag, 7. März 2023 um 11:30:24 UTC+1:
> 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.

I can follow you. The Takeuchi function seems to be of interest only
for doing some esoteric statistics or for benchmarking variants of
Lisp or Haskell etc.

At least I had found another exercise in Mecrisp Forth:
https://github.com/rabbithat/Takeuchi_function

[Gerry Jackson]

On 05/03/2023 08:16, Anton Ertl wrote:
> Gerry Jackson <do-no...@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.
>

I take your point but I think EXECUTE-PARSING was a red herring as it is
unnecessary and probably couldn't use a system's internals to generate
an efficient equivalent of SYNONYM. One way is to define a colon
definition that postpones RECURSE for example

: (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

[Anton Ertl]

Gerry Jackson <do-no...@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 ... ;] ... ;

[Gerry Jackson]

On 07/03/2023 22:31, Anton Ertl wrote:
> Gerry Jackson <do-no...@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

Yeah well that's an additional requirement.

<quote>Charles Babbage 1791–1871
If you speak to him of a machine for peeling a potato, he will pronounce
it impossible: if you peel a potato with it before his eyes, he will
declare it useless, because it will not slice a pineapple.</quote> :)

--
Gerry

[Gerry Jackson]

On 07/03/2023 22:31, Anton Ertl wrote:

> Gerry Jackson <do-no...@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

The second solution I gave works for those cases:

: r: >in @ defer >in ! depth >r :noname depth r> - 1- roll ' defer! ;

: map-list cr ." Calling FOO" -1 swap execute ;
r: foo if cr ." FOO executing" else ['] foo map-list then ;
0 foo
Calling FOO
FOO executing ok

r: bar if cr ." BAR executing"
else [: cr ." Calling BAR" -1 bar ;] execute
then
;
0 bar
Calling BAR
BAR executing ok

As the third solution also works via a deferred word that should work as
well.


--
Gerry