The Combinator Approach

The Combinator Approach#

Combinators are a foundational approach to mathematical logic. Expressions are built out of variables like x and y; combinators like S and K; and function applications like (S K). Books like Raymond Smullyan’s To Mock a Mockingbird explore the kinds of complex systems that can be built out of combinator calculi.

There are several different (compatible) formulations of combinatory logic, such as SKI and BCKW. Many authors have preferred to work with one of the most parsimonious systems, SKI, and Nock at its heart is SKI dressed up with some machinery to handle nouns. (Since SKI is a Turing-complete computational system, this demonstrates that Nock is Turing-complete without further ado.)

Nock opcodes 2, 1, and 0 correspond to S, K, and I combinators, so let’s start there. We’ll look at what the combinators do on their own and then as a part of the Nock system.

I Identity Combinator#

The I combinator simply returns its (single) argument:

I x = x

Iterated applications simply reduce one step at a time:

I I x = I x = x

In Nock, our format is a little different because of how opcodes are set up. (Think of this like grammar.) Opcode 0 provides noun addressing, with slot 1 referring to the entire noun. Thus:

[a 0 1] = a

K Constant Combinator#

The K combinator accepts two arguments and discards the second.

K x y = x

Like

K K x y z = K x z = x
K K x y = K x = x

The latter case is interesting. Why does it stop evaluating forward? There is insufficient information to

S Substitute Combinator#

The S combinator distributes a common argument z to two functions x and y, then applies the first result to the second.

S x y z = (x z) (y z)

S (along with K) forms a Turing-complete basis.

Opcode 2 is analogous to the S combinator, in that it is the subject-oriented counterpart to the applicative distribution pattern of S. This structural similarity is why opcode 2 (combined with the other primitives opcode 0 and opcode 1) provides Turing completeness.

Similarity#

Both operations share the pattern “distribute, then combine”:

S Combinator

Nock 2

Common argument: z

Common subject: a

Two functions: x, y

Two formulas: b, c

Distribute: (x z) and (y z)

Distribute: *[a b] and *[a c]

Combine via application

Combine via * evaluation

Differences#

  1. Evaluation model: S uses lambda-style application (f x). Nock uses subject-oriented evaluation (*[subject formula]), which has the opposite argument order convention.

  2. Argument ordering: In S, the first distributed result is the function. In opcode 2, the second distributed result (*[a c]) becomes the formula, and the first (*[a b]) becomes the subject.

  3. Semantics: Lambda application and Nock evaluation aren’t the same operation, though they’re both notions of “running code on data.”

Contents