; Some pure lambda calculus in Scheme

(set! load-noisily? #t)

; I, K, S combinators:

(define I (lambda (x) x))
(define K (lambda (x) (lambda (y) x)))
(define S (lambda (x) (lambda (y) (lambda (z) ((x z) (y z))))))

; Church numerals

(define ZERO (lambda (f) (lambda (x) x)))
(define ONE (lambda (f) (lambda (x) (f x))))
(define ADD (lambda (m) (lambda (n) (lambda (f) (lambda (x) ((m f) ((n f) x)))))))
(define MULT (lambda (m) (lambda (n) (lambda (f) (lambda (x) ((m (n f)) x))))))

; Booleans

;(define TRUE (lambda (x) (lambda (y) x)))
;(define FALSE (lambda (x) (lambda (y) y)))
; slight cheats:
(define TRUE (lambda (x y) x))  ; must always apply with two parameters
(define FALSE (lambda (x y) y))
(define NOT (lambda (A) (A FALSE TRUE)))
(define ANDD (lambda (A B) (A B FALSE)))
(define ORR (lambda (A B) (A TRUE B)))

; ifelse
(define IFELSE0 (lambda (x a b) (x a b)))

; but scheme is applicative-order (call-by value, so this won't work); need
; to explicitly delay evaluation.

(define IFELSE (lambda (x a b) ((x a b) I)))
; usage: instead of (IFELSE0 FALSE ZERO ONE), use
; (IFELSE FALSE (lambda (d) ZERO) (lambda (d) ONE)).  That is, pass pointers
; not to values but to CODE that will be excuted only when needed.

; Data structures : pairs and linked lists

(define PAIR (lambda (a b) (lambda (s) (s a b)))) ; s will be TRUE or FALSE
(define HEAD (lambda (P) (P TRUE)))
(define TAIL (lambda (P) (P FALSE)))
(define NULL I)  ; null can be anything

(define fewprimes (PAIR 2 (PAIR 3 (PAIR 5 (PAIR 7 (PAIR 11 NULL))))))

; Applicative order fixed point combinator
(define FIX (lambda (M) (lambda (x) (M (lambda (y) ((x x) y)))) (lambda (x) (M (lambda (y) ((x x) y))))))