home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / forth / compiler / fpc / tutor / l7p150 < prev    next >
Text File  |  1990-07-15  |  4KB  |  91 lines
  1.        ╔═════════════════════════════════════════════════════╗
  2.        ║  Lesson 7 Part 150 F-PC 3.5 Tutorial by Jack Brown  ║
  3.        ╚═════════════════════════════════════════════════════╝
  4.  
  5.            ┌────────────────────────────────────────┐
  6.            │  Using Recursion in Forth Programming  │
  7.            └────────────────────────────────────────┘
  8.  
  9. I can remember, it seems like only yesterday, studying arithmetic
  10. progressions in high school.  I don't know why but for some reason I
  11. hated them.  We started of with a definition something like the
  12. following:
  13.  
  14. Definition 5.0101  An arithmetic progression is a sequence in which each
  15. term after the first is obtained by adding the same fixed number, called
  16. the common difference, to the preceding term.
  17.  
  18. I realize now what the problem was, and why I was bothered! This is a
  19. recursive definition.  Apparently humans are supposed to relate well to
  20. recursive definitions.  But why do we call this a recursive definition?
  21. It is because the next term of the progression is defined in terms of
  22. the previous one.
  23.  
  24. Here is what the definition is saying. If d is the common difference, a
  25. fixed constant for any given arithmetic progression then you can find
  26. the nth term by the following formula:
  27.  
  28.           A(n) = A(n-1) + d      (n) and (n-1) are subscripts
  29.   where   A(0) = a     the 0th term ( some call it the 1st)
  30. Example:  if  A(0) = a = 3  and d = 5  then
  31.    then:  A(1) = A(0) + d = 3  +  5 =  8
  32.           A(2) = A(1) + d = 8  +  5 = 13
  33.           A(3) = A(2) + d = 13 +  5 = 18
  34.  
  35. And so on and so on ad infinitum!  But what's all this got to do with
  36. FORTH programming?  Well... we can write a FORTH program to find the nth
  37. term of an arithmetic progression even though the only formula I have
  38. given for the nth term is "recursive" Here is the algorithm:
  39.  
  40.  To find A(n):
  41.        examine n:
  42.      IF   ( n is not zero )
  43.            call myself with argument (n-1)
  44.            and add d, the common difference to result.
  45.      ELSE ( n is equal to zero )
  46.           then the answer is just
  47.           A(0) = a , the 0th term.
  48.  End of algorithm:
  49.  
  50. Implementing this algorithm in FORTH is going to present a slight
  51. problem.  If we call the procedure  APN for nth term of an arithmetic
  52. progression. Then we are going to have to use the procedure (word) APN
  53. in its own definition.
  54.  
  55. FORTH program for computing the nth term of an arithmetic progression:
  56.  
  57.    VARIABLE A     3 A !    ( the 0th term )
  58.    VARIABLE D     5 D !    ( the common difference )
  59.  : APN  ( n -- nth)
  60.           DUP IF   ( n is not zero )
  61.                    1- APN  D @ +
  62.               ELSE ( n is zero )
  63.                    DROP A @
  64.               THEN  ; 
  65.  
  66. If you try to enter this you are in for a rude surprise. FORTH does not
  67. like you using a definition in itself! Depending on the FORTH system you
  68. are using the procedure for getting a word to compile itself is
  69. different. If you are using a fig-FORTH or FORTH-79 and some FORTH-83
  70. systems you would replace the word APN in the middle of the definition
  71. with the word MYSELF or RECURSE Check your system to see if you have
  72. these words. If you don't here are their definitions.
  73.  
  74.  
  75.   : MYSELF  LAST @ NAME> ,  ; IMMEDIATE    \  F83  definition
  76.   : MYSELF  LAST @ NAME> X, ; IMMEDIATE    \  F-PC definition
  77.   : RECURSE LAST @ NAME> ,  ; IMMEDIATE    \  F83  definition
  78.   : RECURSE LAST @ NAME> X, ; IMMEDIATE    \  F-PC definition
  79.                                            \  Already in F-PC 3.5
  80. You don't need both, either one will do.  LAST is just a variable which
  81. contains the name field address of the most recently defined word. NAME>
  82. converts the name field address into the compilation address or cfa  and
  83. the , compiles the cfa into the dictionary.  The definition must be
  84. immediate so that MYSELF or RECURSE  execute during compilation so as to
  85. compile the word being defined ( APN in our example )
  86.  
  87. ┌────────────────────────────────────┐
  88. │  Please Move to Lesson 7 Part 160  │
  89. └────────────────────────────────────┘
  90.  
  91.