krell@xanth.UUCP (Mike Krell) (07/22/87)
I am a beginning Forth user, and I am intrigued by Forth's syntax, which is completely different than anything else I've ever tinkered with. Since Forth is a stack oriented language, it seems to me that it would be very suitable for recursive programming. Do any implementations of Forth directly support recursively defined words? Is it possible to program extensions in Forth that will add this capability? Mike Krell "I may be accused of being confused, UUCP: krell@xanth.UUCP but I'm average weight for my height. 2428 Heutte Drive My philosophy, like color TV, Norfolk, VA 23518 is all there in black and white." (804)-587-3133 M. Python
oster@dewey.soe.berkeley.edu (David Phillip Oster) (07/24/87)
In article <1644@xanth.UUCP> krell@xanth.UUCP (Mike Krell) writes: >Do any implementations of Forth directly >support recursively defined words? Is it possible to program extensions in >Forth that will add this capability? Most versions of Forth already do this, if not, it is trivial to add. The immediate problem is that since forth allows: : PrintFour ( - ) 4 ; ( a first attempt) : PrintFour ( - ) PrintFour . ; (oops, forgot the "print" last time) I.e., if you use a name within the definition of that name, you How do you get a reference to the old version. Now, how can you use a name for recursion? You could play games with the compiler, but that would not work for a set of mutually recursive routines: : g IF f THEN ; : f IF g THEN ; where f and g are expected to call each other. (This is the common case for recursive forth programs, like tree walkers or complex compilers.) What you need is the FORTH equivalent of a forward declaration. : BADFORWARD errorPrint" unsatisfied forward reference!" ; : FORWARD: ( - ;name declares a forward dec.) CREATE ['] BADFORWARD , DOES> @ EXECUTE ; Now, for our "f" "g" example: FORWARD: f FORWARD: g : (f) IF g THEN ; ' (f) SATISFIES f : (g) IF f THEN ; ' (g) SATISFIES g Now we just have to write SATISFIES . : : SATISFIES ( cfa - ;name) ' >BODY SWAP ! ; I hope you like this package, it is what I use myself. Obviously, one could do better: one could have the compiler keep a chain of unsatisfied references, and a list of words that have been forward declared. When you define a new word, if it is on the list of forward declares, the compiler could then patch all the references. I'd like to see the code to do this. --- David Phillip Oster --My Good News: "I'm a perfectionist." Arpa: oster@dewey.soe.berkeley.edu --My Bad News: "I don't charge by the hour." Uucp: {seismo,decvax,...}!ucbvax!oster%dewey.soe.berkeley.edu
jin@hropus.UUCP (Jerry Natowitz) (07/24/87)
> > I am a beginning Forth user, and I am intrigued by Forth's syntax, which > is completely different than anything else I've ever tinkered with. Since > Forth is a stack oriented language, it seems to me that it would be very > suitable for recursive programming. Do any implementations of Forth directly > support recursively defined words? Is it possible to program extensions in > Forth that will add this capability? I worked on a FORTH from Transportable Software (now defunct) that included a RECURSIVE word that would recursively "thread" the currently constructing colon definition. As an example ( no flames please, I haven't written FORTH code for over two years). : FACTORIAL ( N -> M ASSUME N >= 1 ) DUP 1 <> IF 1 - * RECURSIVE THEN ; I believe that RECURSIVE looked at current and got the CFA or whatever and did a "," (store word in dictionary). -- ---------------- Jerry Natowitz ihnp4!hropus!jin
jrusso@topaz.rutgers.edu (Jim Russo star@gold) (07/25/87)
Why go to all that trouble to do self recursion? According to
the books I learned forth from, you use SELF, which compiles
a reference to the word into itself.
Ex:
: fact ( num -- num! )
dup 1 = if
else
1- self * ;
<MC>
CROSSPOSTED by Jrusso@topaz
David_Douthitt@circle.UUCP (David Douthitt) (07/25/87)
There was an issue of Computer Language that described a recursive
mechanism as follows (it was jun '85):
: | SMUDGE ; IMMEDIATE
: TORIAL DUP 1 = IF DUP * ELSE DUP 1- | TORIAL | * THEN ;
: FAC TORIAL . ;
I dont know why everyone takes such circuitous routes to recursion... in
Mad Apple Forth, we have a word called MYSELF:
: MYSELF LATEST 2+ 1 TRAVERSE 1+ , ; IMMEDIATE
This would work very nicely for any recursion I might need... for
example:
: FACTORIAL DUP 1 = IF DUP * ELSE DUP 1- MYSELF * THEN ;
It also is much more mnemonic than anything else I've seen to date. BTW,
the definition of MYSELF assumes that LATEST returns the current
(compiling) def's NFA (if memory serves) ... this is an indirect setup
with nfas unlimited in size, but marked by hibits set at either end.
Does this help?
FidoNet: 121/1
UUCP: seismo!geowhiz!uwvax!hobbes!circle!david_douthitt
"Curiouser and curiouser," said Alice.