{λ calc}

Alain Marty | copyleft GPL | 2017/04/20

As an example of the {λ way} project's capabilities, {λ calc} is an implementation of the λ calculus built on a {λ talk} syntax reduced to 150 lines of plain JavaScript coming with two special forms, lambda and def - def could be forgotten -, and a dictionary reduced to two functions, lib and +. Everyting else is made of user defined functions, see more informations in word2talk and followings. More about {λ talk} in brussels' slides.

Input

Output

Examples

{lib}

1) An example of simple substitution:
{def GOOD_DAY {lambda {o a} oh happy day!}}
{GOOD_DAY oOOOo aAAAa}
{GOOD_DAY ♠ ♥}

2) building a set of user functions to compute 5! :
{def CHURCH  {lambda {:n} {{:n {lambda {:x} {+ :x 1}}} 0}}}
{def TRUE    {lambda {:z} {:z {lambda {:x :y} :x}}}}
{def FALSE   {lambda {:z} {:z {lambda {:x :y} :y}}}}
{def IF      {lambda {:x :y :z} {:z :x :y}}}
{def ZERO    {lambda {:f :x} :x}}
{def ISZERO  {lambda {:n} {:n {lambda {:x} FALSE} TRUE}}}
{def SUCC    {lambda {:n :f :x} {:f {{:n :f} :x}}}}
{def PRED    {lambda {:n} 
  {TRUE {{:n {lambda {:p} 
   {IF {FALSE :p} {SUCC {FALSE :p}}}}} {IF ZERO ZERO}}}}}  
{def MUL     {lambda {:n :m :f} {:m {:n :f}}}}

{def FIVE {SUCC {SUCC {SUCC {SUCC {SUCC ZERO}}}}}}
{CHURCH {FIVE}}

{def FAC
 {lambda {:n}
  {{lambda {:b :t :f :n}
   {{{:b :n} {IF :t :f}} :n} }
    {lambda {:n} {ISZERO :n}}
    {lambda {:n} {SUCC ZERO}} 
    {lambda {:n} {MUL :n {FAC {PRED :n}}}}
    :n 
}}}

{CHURCH {FAC {FIVE}}}

3) compute 5! without constants:
3.1) iterative way: 5! = 1*2*3*4*5
{{lambda {:n} {{:n {lambda {:x} {+ :x 1}}} 0}} 
{{lambda {n} {{lambda {z} {z {lambda {x y} y}}} {{n {lambda {z} {{lambda {x y z} {z x y}} {{lambda {n f x} {f {{n f} x}}} {{lambda {z} {z {lambda {x y} x}}} z}} {{lambda {n z f} {z {n f}}} {{lambda {z} {z {lambda {x y} x}}} z} {{lambda {z} {z {lambda {x y} y}}} z}}}}} {{lambda {x y z} {z x y}} {lambda {f x} {f x}} {lambda {f x} {f x}}}}}}
 {lambda {f x} {f {f {f {f {f x}}}}}}}

3.2) recursive way via lazyness: 5! = 5*4! until 1 
{{lambda {n} {{n {lambda {x} {+ x 1}}} 0}}
 {{lambda {n} {{lambda {g n} {g g n}} {lambda {g n} {{lambda {p t f g n} {{{p n} {{lambda {x y z} {z x y}} t f}} g n}} {lambda {n} {{lambda {n} {n {lambda {x} {lambda {z} {z {lambda {x y} y}}}} {lambda {z} {z {lambda {x y} x}}}}} n}} {lambda {g n} {{lambda {n f x} {f {{n f} x}}} {lambda {f x} x}}} {lambda {g n} {{lambda {n q f} {q {n f}}} n {g g {{lambda {n} {{lambda {z} {z {lambda {x y} x}}} {{n {lambda {p} {{lambda {x y z} {z x y}} {{lambda {z} {z {lambda {x y} y}}} p} {{lambda {n f x} {f {{n f} x}}} {{lambda {z} {z {lambda {x y} y}}} p}}}}} {{lambda {x y z} {z x y}} {lambda {f x} x} {lambda {f x} x}}}}} n}}}} g n}} n}}
 {lambda {f x} {f {f {f {f {f x}}}}}}}}

{lib}