(load "chez-init.ss")

;;; plain fib:
(define fib
  (lambda (n)
    (cond [(= n 1) 1]
	  [(= n 2) 1]
	  [else (+ (fib (- n 1)) (fib (- n 2)))])))


;;; adding a parameter:
(define fib
  (lambda (n k)
    (apply-cont k (cond [(= n 1) 1]
			[(= n 2) 1]
			[else (+ (fib (- n 1)) (fib (- n 2)))]))))

;;; Move k in. Since all conditionals of the cond are simple, we get:
(define fib
  (lambda (n k)
    (cond [(= n 1) (apply-cont k 1)]
	  [(= n 2) (apply-cont k 1)]
	  [else (apply-cont k (+ (fib (- n 1)) (fib (- n 2))))])))

;;; When pushing in the continuation of the else case, move one the two
;;; calls to fib up to take the place of "apply-cont". We pick the
;;; first one.

;;; We now create a new continuation, to indicated that we still need
;;; to make another call to fib and eventually add the two values together.

;;; The data that we need is the (- n 2). Finally, we encapsulate the
;;; continuation k. 


(define fib
  (lambda (n k)
    (cond [(= n 1) (apply-cont k 1)]
	  [(= n 2) (apply-cont k 1)]
	  [else (fib (- n 1) (fib-cont (- n 2) k))])))  


;;; not cps 
;(define fib
;  (lambda (n k)
;    (cond [(= n 1) (apply-cont k 1)]
;	  [(= n 2) (apply-cont k 1)]
;	  [else (fib (- n 1) (add-cont (fib (- n 2) k) k))])))


(define-datatype continuation continuation?
  (halt-cont)
  (add-cont
   (n number?)
   (next-cont continuation?))
  (fib-cont
   (n number?)
   (next-cont continuation?)))


(define apply-cont
  (lambda (cont val)
    (cases continuation cont
	   [halt-cont ()
		      val]
	   [add-cont (n next-cont)
		      (apply-cont next-cont (+ val n))]
	   [fib-cont (n next-cont)
		     (fib n (add-cont val next-cont))])))