Categories

Dealing with lots of paranthesis…

While dealing with lambda calculus expression that I mentioned in my previos post, from time to time many paranthesis appears. Exampli gratia: While trying to SKI equivalent of

λx.λy.+ x y,

intermediate expressions like

S (S (K S) (S (K (S (K +))) (S (λx K) (λx x)))) (λx I)

can be encountered. While dealing with such expression text [...]

Finding SKI Equivalents of λ-Calculus Expressions

Define S, K and I as

S x y z = x z (y z)

K x y = x

I x = x

Apply following transformations to lambda calculus expression until the expression becomes free of lambda abstractions and variables.

1) λx.e1 e2 => S (λx e1) (λx e2)

2) λx.x => I

3) λx.c => K c [Here, c should [...]