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

It applies from the left:

K K x y z = K y z = y

((K K) x) y z    -- parse left-associatively
= K y z          -- because (K K) x reduces: K's first arg is K, second is x, returns first → K
= y              -- K applied to y and z returns y

It also halts if there is insufficient information to continue:

K K x y = K y

((K K) x) y
= K y            -- same first step as above

The latter case is interesting. Why does it stop evaluating forward? K y is a partial application: K needs two arguments and only has one; evaluation halts not because of any deep ambiguity, but simply because K is unsaturated.

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.

S K K x
= K x (K x)     -- by S's rule, with z = x
= x             -- K x (K x) = x, since K discards its second argument

This fully reduces:

S K x y
= K y (x y)     -- by S's rule
= y             -- K discards (x y)

but something like S K x does not, because there is insufficient information to resolve the combinators further.

This example has four arguments:

S x y z z'      -- four arguments
= x z (y z) z'  -- S consumes only the first three; z' rides along

z appears twice on the right-hand side. That duplication is what makes S and K together Turing-complete; K can throw arguments away, S can copy them, and between the two you can route any value anywhere.

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.”