home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / comp / lang / scheme / 2753 < prev    next >
Encoding:
Text File  |  1992-12-15  |  3.1 KB  |  118 lines
  1. Newsgroups: comp.lang.scheme
  2. Path: sparky!uunet!cs.utexas.edu!torn!newshub.ccs.yorku.ca!newshub.ccs.yorku.ca!oz
  3. From: oz@ursa.sis.yorku.ca (Ozan Yigit)
  4. Subject: fibs [Re: Are interpreters now as fast...]
  5. In-Reply-To: schwartz@roke.cs.psu.edu's message of 15 Dec 92 01: 10:15 GMT
  6. Message-ID: <OZ.92Dec15134929@ursa.sis.yorku.ca>
  7. Sender: news@newshub.ccs.yorku.ca (USENET News System)
  8. Organization: York U. Student Information Systems Project
  9. References: <4051@mitech.com> <BzA0Mo.II@cs.psu.edu>
  10. Date: Tue, 15 Dec 1992 18:49:29 GMT
  11. Lines: 105
  12.  
  13. Scott Schwartz writes [in response to the usual simple fib]:
  14.  
  15.    Of course, nothing that runs for that short a time will be a sensible
  16.    yardstick.
  17.  
  18. Here are the FIB routines I had been using in PSI tests. Just something
  19. with more meat for those who are tired of the potatoe :-) version.
  20.  
  21. enjoy...    oz
  22. ---
  23. C++ was invented because Vogon poetry | electric: oz@sis.yorku.ca
  24. wasn't destructive enough. -anonymous | ph:[416] 736 2100 x 33976
  25.  
  26. --- cut here ---
  27. ;;; fib
  28. ;;; shamelessly snarfed from
  29. ;;; R. Kent Dybvig
  30. ;;; Three Implementation Models for Scheme
  31. ;;; Department of Computer Science Technical Report #87-011
  32. ;;; University of North Carolina at Chapel Hill
  33. ;;;  April 1987
  34.  
  35. ;;; fib with peano arithmetic (using numbers)
  36.  
  37. (define addr
  38.    (rec addr
  39.       (lambda (x y)
  40.          (if (zero? y)
  41.              x
  42.              (addr (1+ x) (1- y))))))
  43.  
  44. (define fibr
  45.    (rec fibr
  46.       (lambda (x)
  47.          (if (zero? x)
  48.              0
  49.              (if (zero? (1- x))
  50.                  1
  51.                  (addr (fibr (1- x))
  52.                        (fibr (1- (1- x)))))))))
  53.  
  54. ;;; fib with peano arithmetic (using numbers) in CPS
  55.  
  56. (define addk
  57.    (rec addk
  58.       (lambda (x y k)
  59.          (if (zero? y)
  60.              (k x)
  61.              (addk (1+ x) (1- y) k)))))
  62.  
  63. (define fibk
  64.    (rec fibk
  65.       (lambda (x k)
  66.          (if (zero? x)
  67.              (k 0)
  68.              (if (zero? (1- x))
  69.                  (k 1)
  70.                  (fibk (1- x)
  71.                        (lambda (a)
  72.                           (fibk (1- (1- x))
  73.                                 (lambda (b)
  74.                                    (addk a b k))))))))))
  75.  
  76. ;;; fib with peano arithmetic (using numbers) with set!
  77.  
  78. (define add!
  79.    (lambda (x y)
  80.       ((rec add!
  81.          (lambda ()
  82.             (if (zero? y)
  83.                 x
  84.                 (begin (set! x (1+ x))
  85.                        (set! y (1- y))
  86.                        (add!))))))))
  87.  
  88. (define fib!
  89.    (rec fib!
  90.       (lambda (x)
  91.          (if (zero? x)
  92.              0
  93.              (if (zero? (1- x))
  94.                  1
  95.                  (add! (fib! (1- x))
  96.                        (fib! (1- (1- x)))))))))
  97.  
  98. ;;; fib with peano arithmetic (using numbers) with call/cc
  99.  
  100. (define addc
  101.    (rec addc
  102.       (lambda (x y k)
  103.          (if (zero? y)
  104.              (k x)
  105.              (addc (1+ x) (1- y) k)))))
  106.  
  107. (define fibc
  108.    (rec fibc
  109.       (lambda (x c)
  110.          (if (zero? x)
  111.              (c 0)
  112.              (if (zero? (1- x))
  113.                  (c 1)
  114.                  (addc (call/cc (lambda (c) (fibc (1- x) c)))
  115.                        (call/cc (lambda (c) (fibc (1- (1- x)) c)))
  116.                        c))))))
  117.  
  118.