CODEWITHSUNDEEP
typesschemefibonacci
sudshekhar
sudshekhar

Reputation: 1666

Fibonacci program in Scheme (using define-datatype)

I have been trying to write the Fibonacci program in scheme using the define-datatype approach but am unable to do so. Please tell me how its done.

I have written the representation independence code below:

(define (top-k k)
   k)

(define (applyk k n)
  (k n))

(define (fibind n k)
  (cond
   [(= n 0) (k 1)]
   [(= n 1) (k 1)]
   [else (fibind (- n 1) (fib1 n k))]))

(define fib1
  (lambda (n k)
    (lambda (v)
      (fibind (- n 2) (lambda (w) (k (+ v w)))))))

EDIT: I basically want a code (similar to the one below) that finds fibonacci numbers

;;;;k:: []-> continuation?
(define-datatype k k?
 [topk]
 [fact1-k (n number?) (saved-k k?)])

;;;appylk:: nat? continuation? -> nat?
(define apply-k
  (lambda (v c)
  (cases k c
   [topk () v]
   [fact1-k (n saved-k)
      (apply-k (* n v) saved-k)])))

;;;fact :: nat? continuation? -> nat? 
(define (fact n k)
   (if (< n 2)
      (apply-k n k)
      (fact (- n 1) (fact1-k n k))))

Upvotes: 2

Views: 903

Answers (2)

TheCrazyProgrammer
TheCrazyProgrammer

Reputation: 8588

Here is the code for fibonacci CPS Representation Independence,

#lang racket

(define top-k
  (lambda(v)
    v))

(define fib
  (lambda (n)
    (fib/k n top-k)))

(define fib/k
  (lambda (n k)
    (cond 
      [ (= 1 n)
                (apply-k k 0) ]
      [ (= 2 n)
                (apply-k k 1) ]

      (else
           (fib/k (sub1 n) (fib1-k n k) )
      )
    )
  )
)

(define fib1-k
  (lambda (n k)
    (lambda(v)
      (fib/k (- n 2) (fib2-k v k))
      )))


(define fib2-k
  (lambda(v k)
    (lambda (w)
      (apply-k k (+ w v))
    )))



(define apply-k
  (lambda(k v)
    (k v)))

For details refer page 198 of book Essentials of Programming Languages

I do not know what you are calling as representation independent is really so or not.

Upvotes: 1

Joshua Taylor
Joshua Taylor

Reputation: 85843

Your code makes it look like you're trying to do this in continuation passing style. First, let's take a look at the naïve direct way of implementing the nth Fibonacci number:

(define (fib n)
  ;; This is a naïve implementation, and will get 
  ;; *very* slow, *very* quickly.  It's much more 
  ;; common to implement this as an iterative process
  (cond
    ((= n 0) 1)
    ((= n 1) 1)
    (else (+ (fib (- n 1))
             (fib (- n 2))))))

Now, to translate that into continuation passing style, we just break down where certain things happen. For the cases that n is 0 or 1, we just call the continuation with 1. On the recursive case, though, we need to compute the Fibonacci number for (- n 1) (call it f1), and call some continuation with it. That continuation isn't k though, since there's still work to be done; we still need the number for (- n 2)! The continuation takes f1 as an argument, and computes the Fibonacci number of (- n 2) for us (call it f2) and must call some continuation with it. That continuation isn't k, either, though. The new continuation will have access to f1 and f2 though, and their sum is what k needs:

(define (fib% n k)
  (cond
    ((= n 0) (k 1))
    ((= n 1) (k 1))
    (else (fib% (- n 1)
                (lambda (f1)
                  (fib% (- n 2)
                        (lambda (f2)
                          (k (+ f1 f2)))))))))

> (fib% 1 display)
1
> (fib% 5 display)
8
> (fib% 8 display)
34

There are much more efficient ways to compute numbers in the Fibonacci sequence, though. The typical one starts with 1 and 1, then computes the next value (2), adds that to the previous value (1) to get 3, adds that the previous value (2) to get 5, adds that to the previous value (3) to get 8, and so on. That looks like:

(define (fib-it n)
  ;; This is much more efficient, since it moves
  ;; computes the numbers in the sequence sequentially.
  (let fib ((a 1) (b 1) (n n))
    (if (zero? n)
        a
        (fib b (+ a b) (sub1 n)))))

This is already pretty much in a continuation passing style, except that the named let function, fib, returns a instead of calling k with it. This could be done with:

(define (fib-it% n k)
  (let fib ((a 1) (b 1) (n n))
    (if (zero? n)
        (k a)
        (fib b (+ a b) (sub1 n)))))

This doesn't feel like it's accomplished as much, because it's a continuation passing style version of a function that didn't make any self-recursive calls anyhow; the iteration with the named let took care of that. We might as well have written the following, but it's not much fun:

(define (fib-it% n k)
  (k (let fib ((a 1) (b 1) (n n))
       (if (zero? n)
           a
           (fib b (+ a b) (sub1 n))))))

Upvotes: 4

Related Questions