Combinatory logic from scratch

Cause it's sooooo sexy, let's speak about Combinatory Logic!

• Rule 1: You don't talk about Combinatory Logic
• Rule 2: You don't talk about Combinatory Logic
• Rule 3: Combinatory Logic is based on Lambda Calculus (see Wikipedia for both)
• Rule 4: A combinator is a Lambda expression taking One and only One combinator as parameter, and returning a Combinator.

As i'm speaking to developers, I'LL use the C# Lambda syntax which is: (parameter) => statement Let's now try our first Combinator, named the Identity Combinator I = (a) => a; I named it I, it takes one parameter, localy named a and return the parameter as is.

Important point: How to build combinator taking more than one parameter ? In C# you should use (a, b, c) => blah blah... but the Rule 4 forbid us to give more than one paraneter, so let's cheat, imagine : K = (x) => (y) => x; K is a combinator taking x, returning a combinator taking y and returning x. so we have K(x) = (y) => x and K(x)(y) = x! So K take two arguments, x and y, and returns x, but! K can take only one argument, look at the K(x) = (y) => x ...

Let's try with three arguments:

S = (x) => (y) => (z) => x(z)(y(z))

can be called with one,

S(x) returns (y) => (z) => x(z)(y(z))

two,

S(x)(y) returns (z) => x(z)(y(z))

or three arguments:

s(x)(y)(z) returns x(z)(y(z))

In combinatory logic, they write:

• I a = a
• K x y = x
• S x y z = x(z)(y(z))

then they say that in fact, I can be build from S and K:

I = SKK

Ok but what does that means?

Where are arguments? it's easy: I = S(K)(K); S can take 2 parameters S(x)(y) returns (z) => x(z)(y(z)), so: I = (z) => K(z)(K(z)) We have to execute it from left to right, remember, K(a)(b) returns a, so (with a == z and b == K(z)): I = (z) => z;

Do you want more?

Let's try to understand

B = S (K S) K x y z

B stands for Barbara, from "Syllogism Barbara" (Wikipedia explains:

• All men are animals.
• All animals are mortal. -All men are mortal.

So before all, write B as we understand it, and for readability reasons, currently executed combinator and it's arguments will be emphased:

• B = S (K(S)) K (x) (y) (z)

We have to execute it from left to right, and we have a S with three parameters: S(a)(b)(c) returns a(c)(b(c)):

• B = K (S) (x) (K(x)) (y) (z)

From left to right we have a K with two parameters, S and x, it will return S:

• B = S (K(x)) (y) (z)

Calling S with three parameters (K(x)), (y), and(z)returns(K(x))(z)((y)(z))`:

• B = K (x) (z) ((y)(z))

Calling K with two parameters (x), and (z), it returns x:

• B = x((y)(z))

Which can be simplified to:

• B = x(y(z))

It's time to try it !

delegate C C(C c);
static void Main(string[] args)
{
    C K = (a) => (b) => a;
    C S = (a) => (b) => (c) => a(c)(b(c));
    C I = S(K)(K);
    C B = S(K(S))(K);
}

It works! Enjoy!! Next time, we will try a Swap combinator, a Combinator reducing to himself and progressing step to the Y Combinator! dramatic chord