Simplest complete combinator basis pair for flat expressions

Question

In Chris Okasaki's paper "Flattening Combinators: Surviving Without Parentheses" he shows that two combinators are both sufficient and necessary as a basis to encode Turing-complete expressions without the need for an application operator or parentheses.

Compared to John Trump's encodings of combinatory logic in "Binary Lambda Calculus and Combinatory Logic" through prefix coding S and K combinators with an application operator, only needing two combinators for flat expressions increases the code density to optimality. The resulting Goedel numbering maps every integer to a valid, well-formed closed-term expression unlike most calculi and minimal description length relevant esolangs whose canonical representations usually permit descriptions of syntactically invalid programs.

However Okasaki's encoding was meant to be most helpful in a one-way mapping from lambda calculus terms to bitstrings, not necessarily the other way around as the two combinators used in this reduction are relatively complex when used as practical substitution instructions.

What is the simplest complete combinator basis pair that does not require an application operator?

Answer 1

Coming back to this nearly a year later, I realized I had missed some critical research before posting.

Jot seems to fit the bill of what I was asking for, with two relatively simple combinators B & X that can be represented by a compact Goedel numbering.

I've simplified his reference implementation with Python:

def S(x): return lambda y: lambda z: x(z)(y(z))
def K(x): return lambda y: x
def X(x): return x(S)(K)
def B(x): return lambda y: lambda z: x(y(z))
def I(x): return x
def J(n): return (B if n & 1 else X)(J(n >> 1)) if n else I

J(n) returns the built up function denoting the program represented by its Goedel number n.

B (equivalent to Church encoded multiply) serves the function of functional application (parentheses), and can isolate the S/K halves of the single-basis Iota combinator X.

There a few important properties of this language that I'm (almost) shamelessly stealing from the website of the language's inventor Chris Barker, circa 2000.

Jot is a regular language in syntax but Turing-complete. You can see from the implementation of J(n) that if a host language supports tail-recursion, there's no stack space required to parse the bitstring program format.

The proof of Turing-completeness comes from Chris's site as well, implementing the already known Turing-complete combinatory logic using the S and K combinators:

K  ==> 11100
S  ==> 11111000
AB ==> 1[A][B], where A & B are arbitrary CL combinators built up from K & S

Jot has no syntax errors, every program given its Goedel number n is a valid program. This is probably the most important aspect to my own research, as it not only simplifies parsing to triviality, but should also in theory make Jot far more parsimonious than any Turing-complete encoding that has to skip over malformed programs.

I've written a few tools to 'solve' via brute force the semi-decideable problem of finding a function's Kolmogorov complexity in Jot. It works by relying on the programmer to specify some very characteristic training examples of a function's mapping, then enumerates all Jot programs until all training examples are matched, and lastly attempts a proof of equality of a found function with the original verbose implementation.

It currently only works for up to ~40 bits with my limited resources. I'm attempting a rewrite with a SAT solver to learn much larger programs. If you know how to unroll bounded nested closures as a boolean formula, please help out with my new question.

Now for some interesting comparisons to John Tromp's Binary Lambda Calculus, which is known for its conciseness, but does have the problem of possible syntax errors. The following programs were generated by my learning program in a few seconds.

Function    Jot       Binary Lambda Calculus   |J| |B|
--------|----------|--------------------------|---|---
SUCC      J(18400)  "000000011100101111011010" 15  24
CHURCH_0  J(154)    "000010"                    8   6
CHURCH_1  J(0)      "00000111010"               1  11
CHURCH_2  J(588826) "0000011100111010"         20  16
IS_ZERO   J(5)      "00010110000000100000110"   3  23
MUL       J(280)    "0000000111100111010"       9  19
EXP       J(18108)  "00000110110"              15  11
S         J(8)      "00000001011110100111010"   4  23
K         J(4)      "0000110"                   3   7
AND       J(16)     "0000010111010000010"       5  19
OR        J(9050)   "00000101110000011010"     14  20

From my own experiments, the hypothesis that Jot leads to smaller programs is slowly being confirmed as my program learns simple functions, composes them, then learns larger functions from an improved ceiling.