help with understanding combinatory logic

Hi, was wondering if someone could explain more in detail about "combinatory logic" in a simplistic way. I am not a programmer, I do 3-D animation and I fell into Lambda Calculi while reading I believe an article about a video games that mentioned something about functional progaming. Anyway I started getting an interested in Lambda Calculi and I found a lot of articles about it online. It took me a while to understand it but when I did, the concept around it seemed rather easy. Now I'm trying to learn how combinatory logic works, but there isn't as much material on it as there is with Lambda Calculi. Usually it is lumped into a Lambda Calculi article without much dedication to it. Or I find it talked about in a programing languages such as "unlambda" but as I am not a programming, so I get confused. I started to "get" Lambda Calculi, when I started learning how Church numbers work, and saw examples of how to do simple arthritic like adding and multiplying. So far I can't find anything like this with combinatory logic, can someone show examples of how to make numbers with combinatory logic and to do something like add or multiply with it? This would be a great help.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

The best non-programming intro is likely...

...Raymond Smulyun's To Mock a Mockingbird. A couple of other introductions would be To Dissect a Mockingbird or to play around you can use Combinatory Logic Tutorial.

(Then there's the collection of arbitrary things on my combinator birds page).

I second that!

I think Chris's combinator birds page is an excellent place to learn about combinatory logic (CL) and its relation to the lambda calculus.

I don't particularly enjoy metaphors, so I am not a big fan of Smulyun's book. However I do find the bird names are a great mnemonic device.

I don't know if this helps, but here is how I understand CL. CL is really just the lambda calculus (LC) with formal arguments omitted. This is achieved by building up function definitions from a basis, such as the S and K functions, which are defined in LC as follows:

  S = \a.\b.\c.((a(c))(b(c)) 
  K = \a.\b.(a) 

There is an infinite number of bases possible. Another famous basis is the B,C,K,W system. There are a number of minimal bases all possible using just a single combinator, frequently named X (e.g. Fokker's X combinator and Barker's X combinator).

Does this help? Can anyone help further refine (or correct) this definition?

How to transform lambda-calculus programs to combinatory logic

Since you mentioned some familiarity with the lambda-calculus, you might find it interesting that there is a simple, straightforward procedure for transforming lambda-calculus programs to combinatory logic. These lecture notes by Grigore Rosu list the rules on slide 65. Try using the rules to transform some simple lambda-calculus expressions to combinatory logic. The process of working it out is really useful for understanding what you can do with S and K. Plus there's not much to read (if you'd like a definition of how S and K work, look at slide 61).

Example:
lambda x . (f x)
-- rule 1 -->
[x] (f x)
-- rule 3 -->
S ([x] f)([x] x)
-- rule 2b (x != f) -->
S (K f)([x] x)
-- rule 2a (x == x) -->
S (K f)(S K K)

And that's the end result. You can check that it's correct by applying it to an argument. Just write "z" to the right of the lambda-expression, and to the right of the combinatory logic expression, and check that they both end up simplifying to the same thing.

Note that the variable f is still there because I didn't say "lambda f ..." anywhere (f is a "free variable"). The combinatory logic expression gets significantly more complicated if you add multiple levels of lambdas (at least if you directly follow the rules without performing any simplification). This is because you end up having to apply rules 3, 4 and 5 a lot. If you do try an example like that (say, lambda f . lambda x . (f x)), keep in mind that (S K K) is the same thing as ((S K) K). Or in general, (a b c ... y z) means (((...((a b) c)...) y) z). For example:

lambda x . (a b c)
-- rule 1 -->
[x] (a b c)
-- rule 3 -->
S ([x] (a b)) ([x] c)
-- rule 3 -->
S (S ([x] a) ([x] b)) ([x] c)
-- rule 2b (3 times) -->
S (S (K a) (K b)) (K c)

Hindley and Seldin

Lambda-Calculus and Combinators An Introduction 2nd Edition (July 31,2008)

Rosetta stone

Here are four different descriptions of the same structure from the point of view of physics, topology, logic, and computation. The computation point of view is about combinators.

Physics, Topology, Logic and Computation: A Rosetta Stone

Two sources

If you know some category theory there's some excellent motivation for combinatory logic in Lambek and Scott's "Higher Order Categorical Logic". On page 42 they start with a cartesian closed category and then apply Occam's razor to it, whittling away anything in the structure that seems redundant. The bare bones that you are left with are a version of combinatory logic.

I also think Torsten Grust's notes on writing a SASL compiler are really helpful. It's easy to write a "virtual machine" that does combinatory logic and these notes show how to compile lambda expressions to combinator expressions that can run on such a machine. This also makes it clear that combinatory logic is complete, in the sense that any lambda expression can be rewritten using it.

Scheme-based exposition on combinators

I used to get some nice comments on (and lots of links to) an old course lab I wrote at Oberlin College on combinators. It's certainly aimed at a pretty low level, although it assumes some knowledge of Scheme. I was surprised to see that it's still available via the Wayback Machine:

Oberlin DRAGN Project Combinator Lab

Please forgive the day-glo colors and the funky web navigation: hey, it was the 1900s, you know? :)