home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / lang / forth / 3698 < prev    next >
Encoding:
Text File  |  1992-12-29  |  2.0 KB  |  48 lines
  1. Newsgroups: comp.lang.forth
  2. Path: sparky!uunet!cs.utexas.edu!zaphod.mps.ohio-state.edu!darwin.sura.net!uvaarpa!murdoch!fermi.clas.Virginia.EDU!jvn
  3. From: jvn@fermi.clas.Virginia.EDU (Julian V. Noble)
  4. Subject: Re: Implementing Algolic algorithms in Forth ?
  5. Message-ID: <1992Dec29.204909.21524@murdoch.acc.Virginia.EDU>
  6. Sender: usenet@murdoch.acc.Virginia.EDU
  7. Organization: University of Virginia
  8. References: <2498@itexjct.jct.ac.il>
  9. Date: Tue, 29 Dec 1992 20:49:09 GMT
  10. Lines: 36
  11.  
  12. jacobsen@itexjct.jct.ac.il  writes:
  13. > May the Forth wizards help me with that:
  14. > 
  15. >  I want to implement som 'Algolic languages' algorithms. Let's take
  16. >  the Quick Sort algorithm as an example. In that algorithm the programmer
  17. >  must call the sort function (word, procedure etc.) recursivly, with 
  18. >  sub-array of the array it got as input. 
  19. >  As far as I know, recursion in Forth mean: the ablity of word to use 
  20. >  itself. It is working in those cases when the word use only the stack,
  21. >  like a recursive definition of factorial. How may I write a definition
  22. >  like the quick sort one, in Forth. 
  23. >  
  24. >        Joel
  25. Dear Joel,
  26.  
  27. The short answer is "Get a copy of Scientific FORTH by J.V. Noble (that is,
  28. my humble self) and read the chapter on recursive programming." The book
  29. is available (with program diskette) for $49.95 + s/h from
  30.     Mechum Banks Publishing
  31.     P.O. Box 335
  32.     Ivy, Virginia 22945
  33.     USA
  34.  
  35. The long answer is that you must arrange for the definition that calls
  36. itself to use a stack to hold its arguments. In quicksort, e.g., the
  37. arguments are pointers to the list of items to be sorted. The nice thing
  38. about recursive sorting algorithms is that the stack grows only as 
  39. LOG2(N), where N is the number of items in the list. Thus you don't have
  40. to worry (much) about stack overflow.
  41.  
  42. Finally, I am certain that sorting programs have been written (and pub-
  43. lished!) in Forth, say in Journal of Forth Application and Research or
  44. Forth Dimensions, or even old Dr. Dobbs's (in the days when they used
  45. to publish articles on Forth).
  46.  
  47. Best of luck.   Julian V. Noble
  48.