lambda.rkt

#lang racket
(require (only-in racket
                  (+ old+)))

(define (dechurch n)
  (n (λ (i) (old+ i 1)) 0))

(define (zero f x)
  x)

(define (one f x)
  (f x))

(define (two f x)
  (f (f x)))

(define (succ n)
  (λ (f x) (f (n f x))))

(define (+ a b)
  (λ (f x) (a f (b f x))))

(define (* a b)
  (a (λ (n) (b succ n)) zero))

(define (cons a b)
  (λ (f) (f a b)))

(define (car c)
  (c (λ (a b) a)))

(define (cdr c)
  (c (λ (a b) b)))

(define three (succ two))

(define six (+ three three))

(define (pred n)
  (car (n (λ (c) (cons (cdr c) (succ (cdr c))))
          (cons zero zero))))

(define (- a b)
  (b pred a))

(define (true a b)
  a)

(define (false a b)
  b)

(define (if p c a)
  ((p c a)))

(define (not p)
  (λ (a b) (p b a)))

(define (and a b)
  (if a (λ () b) (λ () false)))

(define (zero? n)
  (n (λ (_) false) true))

(define (<= a b)
  (zero? (- a b)))

(define (= a b)
  (and (<= a b) (<= b a)))

(define y
  (λ (x)
    ((λ (proc)
       (x (λ (arg) ((proc proc) arg))))
     (λ (proc)
       (x (λ (arg) ((proc proc) arg)))))))

(define fib
  (y
   (λ (f) (λ (n)
            (if (<= n one)
                (λ () n)
                (λ () (+ (f (- n one)) (f (- n two)))))))))


(dechurch (fib (+ six (+ two (+ two two)))))