# 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*