bds@mtgzz.UUCP (b.d.szablak) (05/01/86)
I would appreciate it if someone well versed in forth programming
could give this novice hints on coding recursive algorthims (the two Forth
texts I have manage to avoid this topic). It seems the very first word that
I (in all innocence) attempted to define was to evaluate the fibinocci
function (in C):
fib(n)
{
if( n==1 || n==2 ) return 1;
return fib(n-1) + fib(n-2);
}
I eventually came up with an iterative solution after spending more time
than I would have liked so instructive comments on this would also be
appreciated:
: fib ( n1 -- n2 ) \ fibinocci value of n1
-1 swap 0 swap \ stack: pending calcs., answer, current calc.
begin dup 0> \ do until current calc is <= 0
while dup 1 = \ fib 1 is 1
if + \ add fib 1 to answer
swap \ next pending calc -> current calc.
else dup 2 = \ fib 2 is 1
if drop 1+ \ add fib 2 to answer
swap \ next pending calc -> current calc.
else 1- tuck \ fib(n-1) is a pending calc.
1- \ fib(n-2) is current calc.
then
then
repeat
drop \ leave answer on top of stack - all pending calcs done
;makdisi@yale.ARPA (Makdisi) (05/02/86)
Summary: Expires: Sender: Followup-To: Distribution: Keywords: In article <1854@mtgzz.UUCP> bds@mtgzz.UUCP (b.d.szablak) writes: > > I would appreciate it if someone well versed in forth programming >could give this novice hints on coding recursive algorthims (the two Forth >texts I have manage to avoid this topic). It seems the very first word that >I (in all innocence) attempted to define was to evaluate the fibinocci >function (in C): > > fib(n) > { > if( n==1 || n==2 ) return 1; > return fib(n-1) + fib(n-2); > } > >I eventually came up with an iterative solution after spending more time >than I would have liked so instructive comments on this would also be >appreciated: > [ ... long and confusing definition follows ... ] Here's a simple way to find the nth Fibonacci number (a trick I learnt on my cousin's programmable calculator, a TI58): : fib ( n1 -- n2, the n1th Fibonacci number ) 0 1 ( Stack is initially fib[0] fib[-1] ) rot 0 do ( repeat n1 times ) over + swap ( fib[i] fib[i-1] --becomes--> fib[i+1] fib[i] ) loop ( at end of loop, stack is fib[n1] fib[n1-1] ) drop ( leave fib[n1] on the stack ) ; or, more succinctly, : fib 0 1 rot 0 do over + swap loop drop ; You don't want to do things like finding the nth fibonacci number recursively, since recursively defining fib(n) = fib(n-1) + fib(n-2) on a non-psychic computer makes the computer call fib many more times than is needed. I.e. a call to fib(5) makes the computer call fib(4) and fib(3), which make the computer call fib(3), fib(2), fib(2), and fib(1). The remaining fib(3) calls fib(2) and fib(1). Thus we've called fib(1) twice, fib(2) three times, and fib(4) twice, even though we only needed to call each of those once. Recursion is not advisable in such cases (where a recursive procedure calls itself more times than it needs to get the same result). You can often be better off writing something iterative. Recursion is useful for algorithms that look ugly in iterative form, but can be expressed cleanly and elegantly in recursive form. An example is Number of nodes in an empty tree = 0 Number of nodes in a non-empty tree = Number of nodes in the left subtree + Number of nodes in the right subtree + 1 (the root of the tree) The idea here is also that the algorithm only "visits" each node in the tree once. It does not calculate the number of nodes in a given tree twice (unless some parts of the tree are shared). Regarding recursion in forth: Brodie makes no mention of it in either of the two books of his that I've read (_Starting Forth_ and _Thinking Forth_). I've heard of a forth implementation somewhere that allowed a word to call itself with the special word MYSELF (anyone know where that is?). The only way I can think of to do recursion in forth is as follows: 0 variable fib-addr : fib fib-addr @ execute ; : fib-recurse dup 3 < if drop 1 else dup 1- fib swap 2- fib + then ; ' fib-recurse fib-addr ! (Although, I repeat, I wouldn't calculate fibonacci numbers recursively except for demonstrative or teaching purposes.) Hope this helps! - K K-M "Disclaimers galore" -- Kamal Khuri-Makdisi (makdisi@yale.ARPA) ...!ihnp4!hsi!yale!makdisi (makdisi@yalecs.BITNET) ...!decvax!yale!makdisi LAMAKDISIDKAMAL LAMAKDISIDKAMAL LAMAKDISIDKAMAL
alfke@cit-vax.Caltech.Edu (J. Peter Alfke) (05/04/86)
In FIG-influenced versions of FORTH, each word has a 'smudge' bit in its header. This bit is normally off, but is set while the word is in the process of being defined. The smudge bit inhibits recognition of the word in a dictionary search. The purpose of this is to let you redefine a word and have references to the word call the old version, i.e. : cr crcount @ 1+ crcount ! cr ; ( keep track of cr's) To defeat this in special cases (recursion), there's a word called 'smudge' which toggles this bit in the most-recently-defined word. So: : fact smudge ...blah blah blah, including calls to fact which are real recursive calls... ; All FIG implementations have this, and I don't know how many others. Check yours and see. This is one of the many things I figured out by reading and understanding my way through a complete FIG-FORTH listing (for the 6502, no less); one of the others is just how the hell <builds - does> works. -- --Peter Alfke "Man, Woman, Child: alfke@csvax.caltech.edu All Is Up Against the Wall of SCIENCE" --Firesign Theatre
luscher@nicmad.UUCP (05/04/86)
In article <1854@mtgzz.UUCP> bds@mtgzz.UUCP (b.d.szablak) writes: > > I would appreciate it if someone well versed in forth programming >could give this novice hints on coding recursive algorthims (the two Forth >texts I have manage to avoid this topic). It seems the very first word that >I (in all innocence) attempted to define was to evaluate the fibinocci >function (in C): > > fib(n) > { > if( n==1 || n==2 ) return 1; > return fib(n-1) + fib(n-2); > } > I recognize the Fibbonacci series here but I don't remember any deffinition that gave a single number for it! Anyway here is the FORTH code: : fib ( n ) DUP 3 < IF DROP 1 ( return 1 for 1 or 2, assumes n>=1 ) ELSE [ SMUDGE ] ( allow for recursion ) DUP 1- fib ( here is your fib{n-1} ) SWAP 2- fib ( followed by fib{n-2} ) + [ SMUDGE ] ( sum two fib s, end recursability ) THEN ; For arguments of n= 1 2 3 4 5 6 7 8 this gives results= 1 1 2 3 5 8 12 21 I don't know if this is quite what you wanted, but the RECURSION works fine! Best wishes in exploring FORTH! -- ihnp4------\ Jim Luscher harvard-\ \ Nicolet Instruments / Test Instrument Div seismo!uwvax!nicmad!luscher 5225 Verona Rd. Bldg-2 topaz-/ / Madison, Wi 53711-0288 decvax------/ (608) 271-3333 x 2274
kwh@bentley.UUCP (KW Heuer) (05/05/86)
> I would appreciate it if someone well versed in forth programming >could give this novice hints on coding recursive algorthims (the two Forth >texts I have manage to avoid this topic). My own solution is to use a version of forth that supports recursion. (Well, it supports direct recursion, anyway. Someday I'll add indirect recursion.) >I eventually came up with an iterative solution ... If your goal is to learn how to simulate recursion, then what you wrote is probably as good as anything. But if you really want a fib function, the function : fib 0 1 rot 1 do dup rot + loop swap drop ; is simpler and faster (linear time as opposed to exponential), and won't overflow the stack. (There's also an O(log n) algorithm, but I won't bore you with the details unless you're interested.) Karl W. Z. Heuer (ihnp4!bentley!kwh), The Walking Lint
steve@jplgodo.UUCP (Steve Schlaifer x3171 156/224) (05/05/86)
In article <1854@mtgzz.UUCP>, bds@mtgzz.UUCP (b.d.szablak) writes: > > I would appreciate it if someone well versed in forth programming > could give this novice hints on coding recursive algorthims (the two Forth > texts I have manage to avoid this topic). > [........] Essentially, all you need for creating a recursive routine is a word that can compile the CFA of the LATEST word into the dictionary. I don't have a FORTH available here at work right now so I can't check the following out but I think it is essentially correct for FIG FORTH. : MYSELF ( compile CFA of LATEST into dictionary ) ?COMP LATEST PFA CFA , ; IMMEDIATE LATEST stacks the NFA of the most recent word in the dictionary whether that word has been finished yet or not. PFA CFA then converts this into the CFA of the most recent word. Finally, , compiles it into the dictionary. MYSELF can then be used as follows: : RECURS ( decrements TOS until it is 0 ) DUP IF 1 - MYSELF THEN ; Tail recursion could be implemented by modifying MYSELF into the following: : TAIL ( tail recursion word ) ?COMP COMPILE R> COMPILE DROP LATEST PFA CFA , ; IMMEDIATE which drops the return address from the return stack before calling the word it gets used in. -- ...smeagol\ Steve Schlaifer ......wlbr->!jplgodo!steve Advance Projects Group, Jet Propulsion Labs ....group3/ 4800 Oak Grove Drive, M/S 156/204 Pasadena, California, 91109 +1 818 354 3171
florman@randvax.UUCP (Bruce Florman) (05/06/86)
> > I would appreciate it if someone well versed in forth programming > could give this novice hints on coding recursive algorthims (the two Forth > texts I have manage to avoid this topic). It seems the very first word that > I (in all innocence) attempted to define was to evaluate the fibinocci > function (in C): > > fib(n) > { > if( n==1 || n==2 ) return 1; > return fib(n-1) + fib(n-2); > } > > I eventually came up with an iterative solution after spending more time > than I would have liked so instructive comments on this would also be > appreciated: > : fib ( n1 -- n2 ) \ fibinocci value of n1 > -1 swap 0 swap \ stack: pending calcs., answer, current calc. > begin dup 0> \ do until current calc is <= 0 > while dup 1 = \ fib 1 is 1 > if + \ add fib 1 to answer > swap \ next pending calc -> current calc. > else dup 2 = \ fib 2 is 1 > if drop 1+ \ add fib 2 to answer > swap \ next pending calc -> current calc. > else 1- tuck \ fib(n-1) is a pending calc. > 1- \ fib(n-2) is current calc. > then > then > repeat > drop \ leave answer on top of stack - all pending calcs done > ; I'm not really "someone well versed in forth programming" as I've only been doing it for about 3 weeks, but I'll risk ridicule and humiliation and throw my 2 cents in. I'm using a FORTH implementation called MACH 1 (on an Apple Macintosh) which allows named input parameters. The manual gives the following example: : FIB RECURSIVE { num } num 2 < IF 1 ELSE num 1- FIB num 2- FIB + THEN ; Without the named input parameters, the following modification does the same computation: : FIB RECURSIVE ( n1 -- n2 ) DUP 2 < IF DROP 1 ELSE DUP 1- FIB SWAP 2- FIB + THEN ; I'm not sure if the word RECURSIVE is in the 83 standard or not. In MACH 1 it's required for a definition to reference itself. While not a full treatment of the subject, maybe this example helps to shed some light on the subject. Bruce Florman florman%gnu@rand-unix.ARPA
jb@rti-sel.UUCP (Jeff Bartlett) (05/06/86)
> In article <1854@mtgzz.UUCP> bds@mtgzz.UUCP (b.d.szablak) writes: > > > > I would appreciate it if someone well versed in forth programming > >could give this novice hints on coding recursive algorthims (the two Forth > >texts I have manage to avoid this topic). It seems the very first word that > >I (in all innocence) attempted to define was to evaluate the fibinocci > >function (in C): > > > > fib(n) > > { > > if( n==1 || n==2 ) return 1; > > return fib(n-1) + fib(n-2); > > } > > > > Regarding recursion in forth: Brodie makes no mention of it in either of the > two books of his that I've read (_Starting Forth_ and _Thinking Forth_). I've > heard of a forth implementation somewhere that allowed a word to call itself > with the special word MYSELF (anyone know where that is?). I think it is : MYSELF LATEST PFA CFA , ; IMMEDIATE Jeff Bartlett Center for Digital Systems Research Research Triangle Institute jb!rti-sel@mcnc
steve@jplgodo.UUCP (Steve Schlaifer x3171 156/224) (05/07/86)
In article <439@cit-vax.Caltech.Edu>, alfke@cit-vax.Caltech.Edu (J. Peter Alfke) writes: > In FIG-influenced versions of FORTH, each word has a 'smudge' bit in its > header. This bit is normally off, but is set while the word is in the > process of being defined. The smudge bit inhibits recognition of the word > in a dictionary search. > > The purpose of this is to let you redefine a word and have references to > the word call the old version, i.e. > > : cr crcount @ 1+ crcount ! cr ; ( keep track of cr's) > > To defeat this in special cases (recursion), there's a word called > 'smudge' which toggles this bit in the most-recently-defined word. > So: > > : fact smudge > ...blah blah blah, including calls to fact which are > real recursive calls... > ; > This is more or less correct. However, SMUDGE is not usually IMMEDIATE so you need to do a : FACT [ SMUDGE ] ...blah blah blah and when ; executes it will do a SMUDGE which toggles the bit so you need : FACT [ SMUDGE ] ...blah blah blah [ SMUDGE ] ; Personally, I find the use of MYSELF clearer and less prone to errors like forgetting the [ ] stuff needed above. -- ...smeagol\ Steve Schlaifer ......wlbr->!jplgodo!steve Advance Projects Group, Jet Propulsion Labs ....group3/ 4800 Oak Grove Drive, M/S 156/204 Pasadena, California, 91109 +1 818 354 3171
jb@rti-sel.UUCP (Jeff Bartlett) (05/09/86)
> : fib ( n ) DUP 3 < IF DROP 1 ( return 1 for 1 or 2, assumes n>=1 ) > ELSE [ SMUDGE ] ( allow for recursion ) > DUP 1- fib ( here is your fib{n-1} ) > SWAP 2- fib ( followed by fib{n-2} ) > + [ SMUDGE ] ( sum two fib s, end recursability ) > THEN ; If you the SMUDGE method make sure that there is a matching pair (as above). I believe Fig-Forth SMUDGE toggles the smudge (visability) bit. The ';' defining word will flip the bit also, so watch-out or you may end up with an 'invisible' word. Jeff Bartlett Center for Digital Systems Research Research Triangle Institute rti-sel!jb@mcnc
peter@baylor.UUCP (05/10/86)
In FIG-forth (forth-77):
: myself ?comp latest pfa cfa , ; immediate
Or, alternatively:
: recursive-function
...code...
[ smudge ] recursive-function [ smudge ]
...code... ;
Where smudge toggles the smudge-bit in the header. Equivalent code can be
written for any reasonably sane forth. Incidentally, is there anyone else out
there who thinks Chuck Moore should be kept out of Forth standards meetings?
--
-- Peter da Silva
-- UUCP: ...!shell!{baylor,graffiti}!peter; MCI: PDASILVA; CIS: 70216,1076peter@baylor.UUCP (05/10/86)
> : fact smudge > ...blah blah blah, including calls to fact which are > real recursive calls... > ; 1) smudge isn't immediate, so you have to put it in brackets. 2) smudge is a toggle, so you have to add another one before the next definition. -- -- Peter da Silva -- UUCP: ...!shell!{baylor,graffiti}!peter; MCI: PDASILVA; CIS: 70216,1076