SKIing and the Lambda Calculus

It's an amazing property of computation that we reduce all of our data (of which there is a staggering variety) to sequences of bits.

It is even more amazing that we can reduce the language of computation to a similarly lean representation.

In class, we've reduced lists, numbers, booleans, control flow operators, continuations, and recursion down to three things: single-argument function definitions, single-argument function applications, and identifiers.

We didn't get a chance to discuss the fact that we can go further.

The S, K, and I "combinators" (simple little functions) are one such representation.  Here's their definitions:

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



I is the identity function.  K builds "constant" functions.  So, for example, (K 3) is a function that evaluates to 3, regardless of what you apply it to.  (Of course, there is no 3 in the SKI calculus until we define one.)  S "swaps around" its arguments, letting you interleave operations.

Stunningly, SKI is all you need for computation.

Can we model Booleans?  Sure.  We use the same strategy as in the lambda calculus.  "TRUE" is a function that takes two arguments and returns the first one.  "FALSE" is a function that takes two arguments and returns the second one.  TRUE is easy; it's just K:

TRUE x y = K x y = x

FALSE is trickier, but doable; it's S applied to K:

FALSE x y = S K x y = (K y) (x y) = y

If you're dubious about the last step, remember that (K y) applied to anything gives you y.  It's the "constant y function".

How about the big one: recursion?  The core of our recursion implementation (without mutable state) was a function that applies another function to itself: (lambda (f) (f f)).  Let's build that function in SKI calculus.  We need a function F such that F x = x x.  Only S lets us "duplicate" something, and it only duplicates its last argument.  So, we need S ?₁ ?₂ x. Working from that, we get S ?₁ ?₂ x = (?₁ x) (?₂ x).  How do we make that equal to x x?  We need ?₁ and ?₂ to be functions that take a value and return that value unchanged, which is what I does!  So:

F x = S I I x = (I x) (I x) = x x

Pretty cool, huh?

Cheers,

Steve

P.S. As much fun as SKI is as a name, we actually don't need the I.  We can simulate it with S and K.  After all, K is almost I already; it just has one too many arguments.  Can you see how you could supply a "dummy" argument to K so that it becomes I?  It should look like:

I x = .... x = x

You get to fill in the ...