Re: recursion

On 2024-07-15 18:45, Marc Olschok wrote:

On Mon, 15 Jul 2024 15:29:17 Anton Ertl wrote:

minforth@gmx.net (minforth) writes:

On Mon, 15 Jul 2024 10:41:54 +0000, albert@spenarnc.xs4all.nl wrote:

So I prefer:
>
:F binom ;
>
:R binom  ( n1 n2 -- nd ) \ n k --> C(n,k)
   dup 0=
   IF     2drop 1 s>d
   ELSE   2dup 1- swap 1- swap binom 2swap m*/
   THEN ;
>
In my efforts to Make A Lisp (a github https://github.com/kanaka/mal )
I discovered that using recurse is an ugly cludge that present
a lot of problems in refactoring code, if not prevent it.
Forward and resolve definitions is the more sane method, cf. c.
It is hardly more complicated.

>
IIRC gforth has RECURSIVE to avoid duplicating definitions.

>
Yes.  So for a direct recursion like this one you can write
>
: binom  ( n1 n2 -- nd ) recursive \ n k --> C(n,k)
   dup 0=
   IF     2drop 1 s>d
   ELSE   2dup 1- swap 1- swap binom 2swap m*/
   THEN ;

 Oh that is nice, I did not know about that. And it also avoids the
source paste problem that Albert noted.

I think, the word "recursive" is confusing. It looks like an ordinary word, but behaves like an immediate word that changes the current word list, and it does not add any behavior to the current definition.
Some better variants:
   : binom [recursive] ... binom ... ;
   recursive
   : binom ... binom ... ;
   rec: binom ... binom ... ;
An even more better and more general approach:
   : binom ... forward binom ... ;
   : binom ... forward:binom ... ;
The later one can also be used as:
   : foo ... ['] forward:foo ... ;
An advantage of this approach is that it is more general than the "recursive" word, and you also don't have to repeat the definition name.

>
RECURSIVE also allows you to tick the word in its own definition (not
possible with RECURSE), a feature that I actually have used;

I think, there should be a standard method to get the xt of the current definition (regardless whether it is a named definition, or nameless definition).

something along the lines:
>
: walk ( node -- ) recursive
   dup is-leaf? if
     ... \ do something for the leaf
   else \ the node has subnodes
     node ['] walk for-each-subnode
   then ;
>
Gforth (development) also has FORWARD, which also allows you to do
mutual recursion, e.g.
>
forward foo
>
: bar ( n -- ) dup . 1- foo ;
>
: foo ( n -- ) dup 0> if bar else drop then ;
>
5 foo \ prints "5 4 3 2 1 "
>
let's see what the decompiler says:
>
simple-see foo
$7F54E256E870 dup    0->0
$7F54E256E878 0>    0->0
$7F54E256E880 ?branch    0->0
$7F54E256E888 <foo+$40>
$7F54E256E890 call    0->0
$7F54E256E898 bar
$7F54E256E8A0 branch    0->0
$7F54E256E8A8 <foo+$48>
$7F54E256E8B0 drop    0->0
$7F54E256E8B8 ;s    0->0  ok
simple-see bar
$7F54E256E810 dup    0->0
$7F54E256E818 call    0->0
$7F54E256E820 .
$7F54E256E828 1-    0->0
$7F54E256E830 call    0->0
$7F54E256E838 foo
$7F54E256E840 ;s    0->0  ok
>
$7F54E256E838 @ hex. \ prints $7F54E256E870
>
The last like shows that the call to FOO inside BAR directly calls the
FOO defined above, no DEFER or somesuch involved in this case.
>
The definition of FORWARD is quite intricate and uses several recent
features of Gforth.  Read all about it in
<2018Dec31.161743@mips.complang.tuwien.ac.at>.

 Will these parts eventually go into future standards?
 

--
Ruvim