;; Assignment 3 Sample Solution
;; CS 131, Fall 2001
;; Chris Stone


(let
   ((tt (lambda (x) (lambda (y) x)))
    (ff (lambda (x) (lambda (y) y)))
    (zero (lambda (f) (lambda (b) b)))
    (succ (lambda (n) 
            (lambda (f) (lambda (b) (f ((n f) b))))))
    (one (succ zero))
    (two (succ one))
    (three (succ two))
    (four (succ three))
    (pair (lambda (x) (lambda (y) (lambda (f) ((f x) y)))))
    (fst (lambda (p) (p (lambda (x) (lambda (y) x)))))
    (snd (lambda (p) (p (lambda (x) (lambda (y) y)))))
    (pred2 (lambda (p) ((pair (snd p)) (succ (snd p)))))
    (pred (lambda (x) (fst ((x pred2) ((pair zero) zero)))))
    (iszero (lambda (n) ((n (lambda (x) ff)) tt)))
    (plus (lambda (x) (lambda (y) ((x succ) y))))
    (Y (lambda (f)
          ((lambda (x) (f (x x))) (lambda (x) (f (x x))))))
    (FIB (lambda (g) 
           (lambda (n)
            (((iszero n) zero)
             (((iszero (pred n)) one) 
              ((plus (g (pred n))) (g (pred (pred n)))))))))
    (fib (Y FIB))
   )
   (fib four))