Combinator Patterns in Nock#
The Nock opcodes are simple rules which are concerned with manipulating and navigating binary trees, and with evaluating expressions based on these structures. This means that they are fundamentally a sort of tree-based combinator language. Combinators are functions that operate on other functions or data structures, allowing complex operations to be built up from simple, reusable components. Well-known combinator systems include the \(SKI\) combinator calculus and the \(BCKW\) combinator calculus.
A complete combinator calculus lets you express any computation purely in terms of combinators, without the need for variables or other external constructs. That is, they are Turing complete. Nock is also Turing complete, and has enough in common with the \(SKI\) combinator calculus that from its earliest public announcement, commenters noted the similarities and explored the connections between the two systems. Mario B. remarked,
My first impression is that U is a combinator calculus, except for * and > operators. The best known of the combinator calculi is SK combinator calculus, which you should have no problem googling for. It can be described very briefly, in your notation, as follows:
[name] [pattern] [definition]
(I) (I $a) $a
(K) (K $a $b) $b
(S) (S $a $b $c) ($a $c ($b $c))
Curtis Yarvin, who devised Nock, said at that time in response:
I have not really worked with combinator models, but my general impression is that it takes essentially an infinite amount of syntactic sugar to turn them into a programming language.
The rough analogy between the \(S\) combinator and Nock opcode 2 continued for two decades, but ~lagrev-nocfep recently formalized the connection by showing how the behavior of the \(S\) combinator can be directly represented using Nock’s primitive operations.
Taking \(SKI\) to be their standard expressions:
S x y z = x z (y z)
K x y = x
I x = x
he showed that each of the \(SKI\) combinators can be implemented using Nock’s primitive operations. Here we write that compiler using bracket abstraction:
[[S]] = [1 S] = [1 [1 [1 2]] [1 [0 1]] [[1 1] [0 1]]]
[[K]] = [1 K] = [1 [1 1] [0 1]]
[[I]] = [1 I] = [1 0 1]
[[A B]] = [2 [[B]] [[A]]]