Lambda Expression Evaluator

Write your lambda expression here. Note that we have 3 grammars:

1. Var
2. Var=>Body
3. (E)(F)

Try these Church number programes:

• 0: f=>x=>x
• 1: f=>x=>(f)(x)
• 2: f=>x=>(f)((f)(x))
• 3: f=>x=>(f)((f)((f)(x)))
• let Add = a=>b=>f=>x=>((a)(f))(((b)(f))(x))

  Then ((Add)(1))(2) can be expended as: ((a=>b=>f=>x=>((a)(f))(((b)(f))(x)))(f=>x=>(f)(x)))(f=>x=>(f)((f)(x)))

• let Mul = n=>m=>f=>x=>((n)((m)(f)))(x)

  Then ((Mul)(2))(3) can be expended as: ((n=>m=>f=>x=>((n)((m)(f)))(x))(f=>x=>(f)((f)(x))))(f=>x=>(f)((f)((f)(x))))

• let Pred = n=>f=>x=>(((n)(g=>h=>(h)((g)(f))))(u=>x))(u=>u)

  Then 3-1 can be expended as: (n=>f=>x=>(((n)(g=>h=>(h)((g)(f))))(u=>x))(u=>u))(f=>x=>(f)((f)((f)(x))))

• let IsZero = m=>((m)(x=>T=>F=>F))(T=>F=>T)

  Then (((IsZero)(3))(Branch1))(Branch2) can be expended as: (((m=>((m)(x=>T=>F=>F))(T=>F=>T))(f=>x=>(f)((f)((f)(x)))))(Branch1))(Branch2)

• Y combinator: f=>(x=>(f)((x)(x)))(x=>(f)((x)(x)))
• Z combinator: f=>(x=>(f)(u=>((x)(x))(u)))(x=>(f)(u=>((x)(x))(u)))
• let Fac(N) = 1 if N===0 else N * Fac(N-1)": ((Y)(Fac=>N=>(((IsZero)(N))(1))(((Mul)(N))((Pred)(N)))))(3)

  Then factorial 3 (Fac(3))can be expended as: ((f=>(x=>(f)((x)(x)))(x=>(f)((x)(x))))(Fac=>N=>(((m=>((m)(x=>T=>F=>F))(T=>F=>T))(N))(f=>x=>(f)(x)))(((n=>m=>f=>x=>((n)((m)(f)))(x))(N))((n=>f=>x=>(((n)(g=>h=>(h)((g)(f))))(u=>x))(u=>u))(N)))))(f=>x=>(f)((f)((f)(x))))

f=>x=>(f)(x)