Introduction – Simple Kombinator Interpreter

Foreword

Combinatory logic is a minimalistic functional programming language.

It was discovered in 1920 by Moses Schönfinkel as a way to drive lexical variables out of logical expressions (hence "logic").

Little did he know that the tool is in fact too powerful for the task. Neither Gödel's incompleteness theorem, nor the halting problem were known at the time.

The research was continued by Haskell Curry, Alonzo Church, and others, influencing the development of lambda calculus and functional programming languages such as Lisp and Haskell.

Although combinators turned out to be too cumbersome for direct use in practical programming, they do appear here and there, sometimes in disguise.

A combinator itself is a higher-order function that returns an application of its arguments and possibly some previously defined terms. Said arguments may be omitted, swapped, composed, and duplicated in doing so.

The interpreter syntax

A term is either an uppercase letter, a lowercase identifier, a nonnegative integer, the + operator, or a parenthesized expression.
Uppercase identifiers like S, K, B are always one-letter and can be lumped together, without whitespaces in between.
Lowercase identifiers like x, y, pred, list, foo_42 must be spaced from one another.
A term followed by one or more terms is called an application. Application is left-associative: a b c, a (b) (c), and (a b) c all mean the same but a (b c) doesn't.
Unknown terms are just moved around as is. Terms with known semantics may be reduced when applied to enough arguments, see below.
The following combinators are predefined:
- B x y z = x (y z);
- C x y z = x z y;
- I x = x;
- K x y = x;
- S f g x = f x (g x);
- W f x = f x x;
- 0 f x = x;
- 1 f x = f x;
- 2 f x = f(f(x));
- 3 f x = f(f(f x));
- n f x = f(f(… { n times } …(f x)…)) — this is called Church numerals;
- + n f x = f(n f x) — this is called increment combinator: when applied to a Church numeral n, this combinator produces an expression equivalent to the next numeral. In this case our interpreter would replace that expression by the combinator n + 1 to keep computations human-readable. To compute a sum n + m of two numerals, one can apply increment combinator n times to m, written (n +) m or simply n + m.
New terms may be declared as name = impl, where impl is some expression. Multiple definitions may be given, separated by semicolon; in this case only the last one will be executed and/or added to the term inventory. Intermediate definitions are local to one computation and may shadow (i.e., temporarily override) previoursly defined terms.
The interpreter also supports anonymous functions, written as var -> impl. Such operation is called an abstraction. Abstraction is right-associative: x->y->z is the same as x->(y->z), whereas (x->y)->z simply makes no sense and causes a syntax error.

Application has higher precedence than abstraction. So if a lambda expression is applied to something else, it must be parenthesized: (x->x x)(y->y y).

Variables are local to the abstraction's right hand part and will shadow any previously defined terms with the same name.

Lambda expressions (as defined above) are out of scope of combinatory logic per se, but are still available as an extension and behave consistently with combinators.

How computations work

If the starting term in an expression is followed by enough arguments, it may be replaced by its returned value, with the extra arguments (if any) simply applied at the end as is. This is called reduction, and the replaced term is called a redex

For example, given the expression K x y z, the term K x y is a redex, and will be reduced to x, yielding x z for the whole expression. However, the expression x K y z cannot be reduced, provided of course that x has no previous definition.

This process may be repeated until there are no terms eligible for reduction. Such form, if it exists, is called the normal form of the expression. If there are multiple redexes at the same time, different reduction strategies may be picked, and not all of them may lead to termination. However, if to strategies do terminate, the normal form will always be the same.

The reduction strategy that always picks the leftmost outermost redex is called normal order. This strategy has the property of always reaching normal form if it exists, hecne the name. It's not the only such strategy but probably the easiest to implement. This interpreter also uses normal reduction strategy.

Note on lambdas. They are lazy, that is, no reductions to the right of a -> will be performed until all required arguments are supplied. This behavior is consistent with partial applications of combinators.

Example computations

Now with this bit of theory, let's define some combinators and fool around.

The simplest of all is I, the identity: I x = x. It only has one argument, and returns that argument, unmodified. Looks pointless but it's vital for transitions between other, more complex terms.

Some real-life examples of identity combinator include no-op functions/transforms/filters, the Unix cat command, and continue operator in C-like languages (as in: leave the program's state alone and proceed with the next iteration).

The K combinator, or constant, has two arguments: K x y = x. As you can see, it discards the second argument. Note that K x is itself a combinator with just one argument that always returns x.

The S combinator has three arguments: S f g x = f(x)(g(x)). It can perhaps be broken down a bit:
S f g x = { let y = f(x); let z = g(x); return y(z); }.

This may seem like a completely counterintuitive construct, but it's quite powerful, not to say universal. It combines the operations of composition, duplication, and swapping. It can be perhaps compared to NAND/NOR gates in boolean logic (except that it's not enough to produce all combinators on its own, lacking discarding).

Let's see how the three work together. We'll use bold text for terms eligible for reduction.

SII(SII)
I(SII)(I(SII))
SII(I(SII))
SII(SII)
...
Oops... We've reached the starting expression! So here is an infinite loop. Note that we had to deviate from normal reduction strategy on step 3: otherwise this expression also loops but also generates a lot of nested I combinators that, as we already know, do nothing.

S(K(SI))K x y
K(SI)x(K x)y
SI(K x)y
Iy(K x y)
y(K x y)
y x
The terms x and y just got swapped!

Incidentally, the term implemented above is called the T combinator: T x y = y x. Just like with K x, the term T x can be viewed as a promise waiting for a callback (y).

SKKx
Kx(Kx)
x
And we just emulated I using S and K.

One more example:
S(KS)K f g x
KSf(Kf) g x
S(Kf) g x
Kf x(g x)
f(g x)
This is the B combinator: B f g x = f(g x), which represents function composition. B f g is a function in and of itself, regardless of what the last argument is. Unlike application, composition is associative: B (B f g) h (x) = B f (B g h) (x).

Combinators and lambdas

Just like T and K, any combinator of arity n plus an argument is a combinator of arity n − 1, per definition (it applies its arguments to themselves and possible some previously defined terms). So a combinator may be thought of as a one-argument function returning a combinator or an application thereof. This technique is known as currying.

Similarly, since application is left-associative, we might as well say it's a binary operation. The expression tree then becomes a binary tree, and the root value becomes the leftmost leaf value. (Picture pending).

These observations lead us to a somewhat formal definition of what a term or expression is:
expr ::= ident | expr expr | ident -> expr
— which is of course the definition of lambda calculus.

Any combinatory logic expression may be expressed in terms of lambdas. The reverse, however, is only true for specific sets of starting terms called bases. In particular, {S, K} and {B, C, K, W} are such bases. Single combinator bases as well as bases not requiring parentheses exist, too, but are out of scope of this document.

In place of a conclusion

What next?