; Booleans
;;;;;;;;;;
(define Ltrue (lambda (x) (lambda (y) x)))
(define Lfalse (lambda (x) (lambda (y) y)))
(define Lif (lambda (x) (lambda (y) (lambda (z) ((x y) z)))))

; Examples
(((Lif Ltrue) 1) 2)
(((Lif Lfalse) 1) 2)

; more functions
(define Lnot (lambda (x) ((x Lfalse) Ltrue)))
(define Land (lambda (x) (lambda (y) ((x y) Lfalse))))
(define Lor (lambda (x) (lambda (y) ((x true) y))))
; can you define xor?

; Natural numbers (Church numerals)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define Czero (lambda (f) (lambda (y) y)))
(define Cone (lambda (f) (lambda (y) (f y))))
(define Csucc (lambda (n) (lambda (f) (lambda (z) (f ((n f) z))))))
; (define Ctwo (Csucc Cone))
; (define Cthree (Csucc Ctwo))

(define Ctoint (lambda (n) ((n (lambda (x) (+ x 1))) 0)))
(define Cfromint (lambda (x) 
                   (lambda (f) 
                     (lambda (y) 
                       (if (= x 0) y (f (((Cfromint (- x 1)) f) y)))))))

(define Ciszero? (lambda (n) (n (lambda (y) Lfalse) Ltrue)))
(define Cadd (lambda (n) (lambda (m) (lambda (f) (lambda (y) ((n f) ((m f) y)))))))
(define Cmul (lambda (n) (lambda (m) (lambda (f) (lambda (y) ((n (m f)) y))))))
(define Cmult (lambda (n) (lambda (m) (lambda (f) (n (m f))))))

(Ctoint Czero)
(Ctoint Cone)
(define Ctwo ((Cadd Cone) Cone))
(define Cthree (Cfromint 3))
(Ctoint ((Cmul Ctwo) Ctwo))
(Ctoint ((Cmul Cthree) Cthree))
(Ctoint ((Cmult Cthree) Cthree))

; Fixpoint combinators
;;;;;;;;;;;;;;;;;;;;;;

(define Y (lambda (f) ((lambda (x) (f (x x))) (lambda (x) (f (x x))))))
(define aux (lambda (f) (lambda (n) (if (= n 0) 1 (* n (f (- n 1)))))))
;the code below will run forever, because Y does not work with cal-by-value
;(define badfact (Y aux))

;an alternative to Y for Scheme, which is call-by-value
(define Z (lambda (f) ((lambda (x) (f (lambda (y) ((x x) y)))) 
                       (lambda (x) (f (lambda (y) ((x x) y)))))))
(define fact (Z aux))
(fact 4)