; 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)))))) (define EXPT (lambda (m) (lambda (n) (n m)))) ; Booleans (define TRUE (lambda (x) (lambda (y) x))) (define FALSE (lambda (x) (lambda (y) y))) ; slight cheats: must always call with 2 parameters (define ANDD (lambda (A B) ((A B) FALSE))) (define ORR (lambda (A B) ((A TRUE) B))) (define NOT (lambda (A) ((A FALSE) TRUE))) ; Equality: test for equality to zero for Church numerals: (define EQZ (lambda (n) ((n (lambda (x) FALSE)) TRUE))) ; returns FALSE if non-zero, True if Zero ; 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 ZERO) ; null can be anything (define fewprimes (PAIR 2 (PAIR 3 (PAIR 5 (PAIR 7 (PAIR 11 NULL)))))) (display (HEAD (TAIL (TAIL fewprimes)))) ; prints 5 ; Normal-order fixed point combinator: (define FIX0 (lambda (M) (lambda (x) (M (x x))) (lambda (x) (M (x x))))) ; 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))))))) ; tests between PAIRs and NULL: (define ISNULL (lambda (n) ((n (lambda (y) (lambda (z) (lambda (z2) FALSE)))) TRUE))) (display (((ISNULL NULL) 1) 2)) (display (((ISNULL fewprimes) 1) 2)) ; function to add all numbers, using built-in arithmetics: (define SUM (FIX (lambda (f) (lambda (n) (IFELSE (ISNULL n) (lambda (y) 0) (lambda (y) (+ (HEAD n) (f (TAIL n))))))))) (display "\n=========\n") (display (SUM NULL)) (display "\n=========\n") (display (SUM fewprimes)) ; sum should be 28 (display "\n=========\n") ;------------------------- FURTHER EXAMPLES ----------------- ; Convert between pure lambda true/false, and Scheme true/false: ; notation: (define (f x) M) is the same as (define f (lambda (x) M)) ; take a function that takes two parameters at once into a curried function: (define (curry f) (lambda (x) (lambda (y) (f x y)))) (define (Uncurry g) (lambda (x y) ((g x) y))) (define (bool x) ((Uncurry x) #t #f)) ; convert Church numerals into scheme numbers, and back: (define (unchurch c) ((c (lambda (y) (+ 1 y))) 0)) (define (church n) (if (= n 0) ZERO ((Uncurry ADD) ONE (church (- n 1))))) (display (unchurch (lambda (f) (lambda (x) (f (f (f x))))))) ; 3 (display "\n=========\n") (display (unchurch (church 4))) (display "\n=========\n") (define PURENUMS (PAIR (church 2) (PAIR (church 4) (PAIR (church 9) NULL)))) (define PURESUM (FIX (lambda (f) (lambda (n) (IFELSE (ISNULL n) (lambda (y) ZERO) (lambda (y) ((ADD (HEAD n)) (f (TAIL n))))))))) (display (unchurch (PURESUM PURENUMS))) ; sum should be 15