# Combinatory logic from scratch

Posted on Fri 28 November 2008 in blog

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