User:I am islptng/Lambda Calculus Tutorial

Thanks for YouTuber 2swap (His video helps a lot.)

Since I was confused about lambda calculus at first, and I took a long time to understand it. So I'll write this article to help others.

Also evaluating lambda expressions is a good way to kill my time. :D

This is still a work in progress. It may be changed in the future.

Part 1: Combinators

This is a function, when applied, returns its argument:

f(x) = x

This is equivalent:

S K K

Yes, no x, no f, just S and K.

Let's see how it works:

  S K K x
⊢ K x ( K x )
⊢ x

See? It returns x, which is the thing put into it.

The procedure, is called a β-reduction. The symbol ⊢ means "reduce to".

Let's start with K.

Definition: K a b ⊢ a

K takes 2 things after itself, and leaves only the first. In the example above, step 2:

K x ( K x ) ⊢ x

Note the parentheses: Those in parentheses should be saw as a whole things.

S is a bit more complex: S a b c ⊢ a c ( b c )