(* CMSC 330: Lambda Calculus *)










(* Booleans *)

let _true = fun x y -> x
let _false = fun x y -> y

let _ifthenelse a b c = a b c

let ift = _ifthenelse _true "b" "c"
let iff = _ifthenelse _false "b" "c"

let _not a = a _false _true

let nott = _not _true
let notf = _not _false 

let dec_bool b = b true false
let nott = dec_bool (_not _true)
let notf = dec_bool (_not _false)

let _and a b = a b _false

let andtt = dec_bool (_and _true _true)
let andtf = dec_bool (_and _true _false)
let andft = dec_bool (_and _false _true)
let andff = dec_bool (_and _false _false)

let _or a b = a _true b

let ortt = dec_bool (_or _true _true)
let ortf = dec_bool (_or _true _false)
let orft = dec_bool (_or _false _true)
let orff = dec_bool (_or _false _false)


(* Pairs *)

let _pair a b = fun x -> _ifthenelse x a b
let _fst a = a _true
let _snd a = a _false

let ab = _pair "a" "b"
let fstab = _fst ab
let sndab = _snd ab


(* Natural Numbers *)

let _0 = fun f z -> z
let _1 = fun f z -> f z
let _2 = fun f z -> f (f z)
let _3 = fun f z -> f (f (f z))

let dec_int n = n (fun x -> x + 1) 0

let dec0 = dec_int _0
let dec3 = dec_int _3

let _succ n = fun f z -> f (n f z)

let decsucc0 = dec_int (_succ _0)

let rec enc_int (i: int) = fun f z ->
  match i with
  | 0 -> z
  | i -> f (enc_int (i-1) f z)

let decenc5 = dec_int (enc_int 5)

let _iszero n = n (fun x -> _false) _true

let isz0 = dec_bool (_iszero _0)
let isz3 = dec_bool (_iszero _3)

let _plus m n = fun f z -> (m f) ((n f) z)
let _plus' m n = m _succ n
let _mult m n = fun f -> n (m f)
let _mult' m n = m (_plus n) _0

let plus1_1 = dec_int (_plus _1 _1)
let mult3_2 = dec_int (_mult _3 _2)
let plus1_1' = dec_int (_plus' _1 _1)
let mult3_2' = dec_int (_mult' _3 _2)

let _exp m n = n m
let exp2_3 = dec_int (_exp _2 _3)

(* challenge *)
(*
let _pred n =
let pred1 = dec_int (_pred _1)
let pred0 = dec_int (_pred _0)
*)