lambda-calculus.rkt

#lang racket

(module+ test
  (require rackunit))

; boolean
(define @true (lambda (t) (lambda(f) t)))
(define @false (lambda (t) (lambda(f) f)))
(define (->boolean boolean) ((boolean #t) #f))
(module+ test
  (check-equal? (->boolean @true) #t)
  (check-equal? (->boolean @false) #f))

; boolean Operator
(define @and (lambda (a) (lambda (b) ((a b) @false))))
(module+ test
  (check-equal? ((@and @true) @true) @true)
  (check-equal? ((@and @true) @false) @false)
  (check-equal? ((@and @false) @true) @false)
  (check-equal? ((@and @false) @false) @false))

(define @or (lambda (a) (lambda (b) ((a @true) b))))
(module+ test
  (check-equal? ((@and @true) @true) @true)
  (check-equal? ((@and @true) @false) @false)
  (check-equal? ((@and @false) @true) @false)
  (check-equal? ((@and @false) @false) @false))

(define @not (lambda (a) ((a @false) @true)))
(module+ test
  (check-equal? (@not @true) @false)
  (check-equal? (@not @false) @true))

; control-flow
(define @if (lambda (condition) (lambda (t) (lambda (f)
  ((condition t) f)))))
(module+ test
  (check-equal? (((@if @true) #t) #f) #t)
  (check-equal? (((@if @false) #t) #f) #f))

; pair
(define @pair (lambda (first) (lambda (second)
  (lambda (boolean) ((boolean first) second)))))
(define @first (lambda (pair) (pair @true)))
(define @second (lambda (pair) (pair @false)))
(define (->pair pair) (list (@first pair) (@second pair)))
(module+ test
  (check-equal? (->pair ((@pair 1) 2)) '(1 2))
  (check-equal? (@first ((@pair 1) 2)) 1)
  (check-equal? (@second ((@pair 1) 2)) 2))

; number
(define @zero (lambda (succ) (lambda (init) init)))
(define @one (lambda (succ) (lambda (init) (succ init))))
(define @two (lambda (succ) (lambda (init) (succ (succ init)))))
(define (->number number) ((number (lambda (n) (+ n 1))) 0))
(define @successor (lambda (number)
  (lambda (succ) (lambda (init) (succ ((number succ) init))))))
(define @predecessor
  (lambda (number)
    (let ([zz ((@pair @zero) @zero)]
          [ss (lambda (p) ((@pair (@second p)) (@successor (@second p))))])
      (@first ((number ss) zz)))))
(define (@number n)
  (if (= n 0)
      @zero
      (@successor (@number (- n 1)))))
(module+ test
  (check-equal? (->number @zero) 0)
  (check-equal? (->number @one) 1)
  (check-equal? (->number @two) 2)
  (check-equal? (->number (@number 0)) 0)
  (check-equal? (->number (@number 1)) 1)
  (check-equal? (->number (@number 2)) 2)
  (check-equal? (->number (@number 3)) 3)
  (check-equal? (->number (@successor @zero)) 1)
  (check-equal? (->number (@successor @one)) 2)
  (check-equal? (->number (@successor @two)) 3)
  (check-equal? (->number (@predecessor @one)) 0)
  (check-equal? (->number (@predecessor @two)) 1))

; number operator
(define @add (lambda (a) (lambda (b)
  (lambda (succ) (lambda (init) ((a succ) ((b succ) init)))))))
(define @add* (lambda (a) (lambda (b)
  ((a @successor) b))))
(define @sub (lambda (a) (lambda (b)
  ((b @predecessor) a))))
(define @mul (lambda (a) (lambda (b) (
  (a (@add b)) @zero))))
; TODO: div
(define @eq (lambda (a) (lambda (b) ((@and (@zero? ((@sub a) b))) (@zero? ((@sub b) a))))))
(define @ne (lambda (a) (lambda (b) (@not ((@eq a) b)))))
(define @gt (lambda (a) (lambda (b) ((@and ((@ne a) b)) (@zero? ((@sub b) a))))))
(define @ge (lambda (a) (lambda (b) (@zero? ((@sub b) a)))))
(define @lt (lambda (a) (lambda (b) (@not ((@ge a) b)))))
(define @le (lambda (a) (lambda (b) (@not ((@gt a) b)))))
(define @pow (lambda (b) (lambda (e) ((e (@mul b)) @one))))
(define @zero? (lambda (n) ((n (lambda (_) @false)) @true)))
(module+ test
  (check-equal? (->number ((@add @one) @one)) 2)
  (check-equal? (->number ((@add @one) @two)) 3)
  (check-equal? (->number ((@add* @one) @one)) 2)
  (check-equal? (->number ((@add* @one) @two)) 3)
  (check-equal? (->number ((@sub @two) @one)) 1)
  (check-equal? (->number ((@sub @two) @zero)) 2)
  (check-equal? (->number ((@sub (@number 123)) (@number 111))) 12)
  (check-equal? (->number ((@mul @one) @two)) 2)
  (check-equal? (->number ((@mul @two) @two)) 4)
  (check-equal? (->number ((@mul @two) (@number 3))) 6)
  (check-equal? (->number ((@pow @two) @one)) 2)
  (check-equal? (->number ((@pow @two) @two)) 4)
  (check-equal? (->number ((@pow @two) (@number 3))) 8)
  (check-equal? (->boolean (@zero? @zero)) #t)
  (check-equal? (->boolean (@zero? @one)) #f)
  (check-equal? (->boolean ((@eq @one) @one)) #t)
  (check-equal? (->boolean ((@eq @zero) @one)) #f)
  (check-equal? (->boolean ((@eq @one) @zero)) #f)
  (check-equal? (->boolean ((@ne @one) @one)) #f)
  (check-equal? (->boolean ((@ne @zero) @one)) #t)
  (check-equal? (->boolean ((@ne @one) @zero)) #t)
  (check-equal? (->boolean ((@gt @one) @one)) #f)
  (check-equal? (->boolean ((@gt @zero) @one)) #f)
  (check-equal? (->boolean ((@gt @one) @zero)) #t)
  (check-equal? (->boolean ((@gt @one) @two)) #f)
  (check-equal? (->boolean ((@gt @two) @one)) #t)
  (check-equal? (->boolean ((@ge @one) @one)) #t)
  (check-equal? (->boolean ((@ge @zero) @one)) #f)
  (check-equal? (->boolean ((@ge @one) @zero)) #t)
  (check-equal? (->boolean ((@ge @one) @two)) #f)
  (check-equal? (->boolean ((@ge @two) @one)) #t)
  (check-equal? (->boolean ((@ge @two) @two)) #t)
  (check-equal? (->boolean ((@lt @one) @one)) #f)
  (check-equal? (->boolean ((@lt @zero) @one)) #t)
  (check-equal? (->boolean ((@lt @one) @zero)) #f)
  (check-equal? (->boolean ((@lt @one) @two)) #t)
  (check-equal? (->boolean ((@lt @two) @one)) #f)
  (check-equal? (->boolean ((@le @one) @one)) #t)
  (check-equal? (->boolean ((@le @zero) @one)) #t)
  (check-equal? (->boolean ((@le @one) @zero)) #f)
  (check-equal? (->boolean ((@le @one) @two)) #t)
  (check-equal? (->boolean ((@le @two) @one)) #f)
  (check-equal? (->boolean ((@le @two) @two)) #t))

; list
(define @empty (lambda (c) (lambda (n) n)))
(define @cons (lambda (head) (lambda (alist) (lambda (c) (lambda (n) ((c head) ((alist c) n) ))))))
(define @empty? (lambda (alist) ((alist (lambda (head) (lambda (tail) @false))) @true)))
(define @head (lambda (alist) ((alist (lambda (head) (lambda (tail) head))) @false)))
(define @tail (lambda (alist) (@first ((alist (lambda (x) (lambda (p) ((@pair (@second p)) ((@cons x) (@second p)))))) ((@pair @empty) @empty)))))
(define (->list-of-numbers alist) (map ->number ((alist (lambda (head) (lambda (tail) (cons head tail)))) empty)))
(module+ test
  (check-equal? (->list-of-numbers @empty) '())
  (check-equal? (->list-of-numbers ((@cons @one) @empty)) '(1))
  (check-equal? (->list-of-numbers ((@cons @two) ((@cons @one) @empty))) '(2 1))
  (check-equal? (->boolean (@empty? @empty)) #t)
  (check-equal? (->boolean (@empty? ((@cons @one) @empty))) #f)
  (check-equal? (->boolean (@empty? ((@cons @two) ((@cons @one) @empty)))) #f)
  (check-equal? (->number (@head ((@cons @one) @empty))) 1)
  (check-equal? (->number (@head ((@cons @two) ((@cons @one) @empty)))) 2)
  (check-equal? (->list-of-numbers (@tail ((@cons @one) @empty))) '())
  (check-equal? (->list-of-numbers (@tail ((@cons @two) ((@cons @one) @empty)))) '(1)))

; combinator
(define @fix (lambda (f) ((lambda (x) (f (lambda (y) ((x x) y)))) (lambda (x) (f (lambda (y) ((x x) y)))))))
(module+ test
  (let ([factorial (@fix (lambda (fac) (lambda (n) ((((@if (@zero? n)) (lambda (x) @one)) (lambda (x) ((@mul n) (fac (@predecessor n))))) @zero))))]
        [factorial2 (@fix (lambda (fac) (lambda (n) (if (= (->number n) 0) @one ((@mul n) (fac (@predecessor n)))))))])
    (check-equal? (->number (factorial (@number 1))) 1)
    (check-equal? (->number (factorial (@number 2))) 2)
    (check-equal? (->number (factorial (@number 3))) 6)))