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, two, or three arguments :
S(x) returns (y) => (z) => x(z)(y(z))
S(x)(y) returns (z) => x(z)(y(z))
s(x)(y)(z) returns x(z)(y(z))

In combinatory logic, they wrote :
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 it 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))” ok ? 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 says :)
Barbara :
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, i’ll underline parameters for the bolded combinator :
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 y, it will return S :
B = S (K(x)) (y) (z)
Calling S with three parameters (K(x)), (y), (z) returns (K(x))(z)((y)(z)) :
B = K (x) (z) ((y)(z))
Calling K with two parameters (x), (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]

This entry was posted in C#, Code and tagged . Bookmark the permalink.

One Response to Combinatory logic from scratch

  1. Combinatory logic says:

    Hi Julien,

    I read your post regarding the Combinatory logic from scratch, but seems to be little difficult to grasp, I would be more happy if you could send me an working example of this concept to my mailID([email protected]) to understand it better or else to attach a sample with this blog for better understanding and reach for all the readers of this blog
    Thanks,
    Rajesh

Leave a Reply

Your email address will not be published. Required fields are marked *