Compact Representation of Church-Encoded Data

Church Encoding is the mechanism by which literal data can be encoded as terms of the lambda calculus. This shows that it's possible to represent arbitrary literal data, but how compact can such a representation be?

Binary Lambda Calculus is a binary encoding of the lambda calculus. The number of bits required to encode some term serves as a pretty good measure of the complexity of that term. As a refresher, the encoding works as follows:

λM    = 00 M         (each abstraction 'costs' 2 bits)
(M N) = 01 M N       (application also 'costs' 2 bits)
0     = 10           (variable reference 'costs' 2+k bits)
1     = 110            (...where k is the de Brujin index)
k     = 1...0          (...of that variable's binding)

Given this cost model, how efficiently can literal data be encoded?

Representing Large Constants as K-Ary Numerals

The "standard" representation of the natural numbers is basically a higher-order encoding of Peano numerals:

0 = λfλx.x
1 = λfλx.(f x)
N = λfλx.(f (... (f x))

This is a unary encoding because it has only the one operation f to apply. It can be made K-ary in several ways, but the one that I like best moves the 'zero value' argument to the front and treats each 'constructor' as a multiplication by N and the addition of a new digit. Thus for binary we have:

0 = ''    = λzλfλt.z               -- 10 bits
1 = '1'   = λzλfλt.(t z)           -- 14 bits
2 = '10'  = λzλfλt.(f (t z))       -- 19 bits
3 = '11'  = λzλfλt.(t (t z))       -- 18 bits
4 = '100' = λzλfλt.(f (f (t z)))   -- 24 bits
5 = '101' = λzλfλt.(t (f (t z)))   -- 23 bits
6 = '110' = λzλfλt.(f (t (t z)))   -- 23 bits
7 = '111' = λzλfλt.(t (t (t z)))   -- 22 bits

The extension to ternary or quaternary numerals should be self- evident. Under the Binary Lambda Calculus cost model, the zero value encodes to 10 bits and each additional digit adds ~4.5 more bits (on average assuming uniform distribution), so a given natural number N encodes to 10 + 4.5*log2(N) bits on average. The same scheme can be extended to arbitrary bases:

Binary:      10 + 4.5*log(N)/log(2)
Ternary:     13 + 5.0*log(N)/log(3)
Quaternary:  16 + 5.5*log(N)/log(4)
Octal:       28 + 7.5*log(N)/log(8)
Decimal:     34 + 8.5*log(N)/log(10)
Hexadecimal: 52 + 11.5*log(N)/log(16)
K-Ary:       4 + 3*K + (3.5 + 0.5*K)*log(N)/log(K)

Suppose that we have 1kiB of data to encode. Thus log2(N) = 1024, and we have the following encoded lengths:

Binary:      10 + 4.5*1024           = 4618 bits (4.5x)
Ternary:     13 + 5.0*1024/log2(3)   = 3243 bits (3.2x)
Quaternary:  16 + 5.5*1024/log2(4)   = 2832 bits (2.8x)
7-Ary:       25 + 7.0*1024/log2(7)   = 2578 bits (2.5x)
Octal:       28 + 7.5*1024/log2(8)   = 2588 bits (2.5x)
Decimal:     34 + 8.5*1024/log2(10)  = 2654 bits (2.6x)
Hexadecimal: 52 + 11.5*1024/log2(16) = 2996 bits (2.9x)

In the limit as N becomes increasingly large a 7-ary encoding is the optimal balance between the unary cost of indexing more and more constructors and the 1/log2(K) factor reducing the length of the description.

However for practical purposes the octal encoding is only 0.2% worse and maps more cleanly to bits and bytes.

⚠ Caveats

Note that these specific numbers only holds for the Binary Lambda Calculus encoding, or more generally a cost model where the marginal cost of each additional variable is constant.

Even more importantly, this analysis all assumes that N is large enough that the constant factors become negligible. Specifying eight distinct constructor functions to convert an octal representation into any other form is going to take a fair number of bits no matter how clever you get. So what about the numbers small enough that those assumptions don't hold?

Encoding Small Naturals

Let's specifically consider the integers 0 to 256. How compactly can these exact values be represented?

In the "Large N" case we could be flexible about what constitutes a "representation" because converting from one data representation to another is generally a constant factor overhead. But here we'll be dealing with encoded lengths in the hundreds of bits at most, so we don't have that luxury. So specifically the question is: What is the most compact encoding of each integer from 0 to 256 as lambda calculus terms equivalent to a Church Numeral?

I've made a (non-exhaustive) list of strategies by which some numeral could be encoded:

• Naively: As a function of the form λfλx.(f ... (f x)). This costs 6 bits of setup and 5 bits per increment.
• Incrementing: λfλx.(f ... (N f x)) where N is another numeral encoding. This costs 13 bits of setup, 5 bits per increment, plus the size of N.
• Addition: The sum of two other numerals expressed as λfλx.(M f (N f x)). This costs 20 bits, plus the size of M and N.
• Multiplication: The product of two other numerals expressed as λf.(M (N f)). This costs 8 bits plus the size of M and N.
• Exponents: The value M to the Nth power via (N M). This costs a mere 2 bits of overhead (plus M and N).
• Self-Exponents: The value N to the Nth power via (λn.(n n) N). This costs 10 bits of overhead, plus a single copy of N.
• Shift-Increment Bitstrings: A value N to which we apply some sequence of 'double' and 'increment' operations:

  ((λiλs.(s (i ... (s N))) INC) SHL)             (8 bits)
    where SHL = λnλfλx.((n f) ((n f) x))         (30 bits)
          INC = λnλfλx.(f ((n f) x))             (24 bits)

  The cost of this encoding is 62 bits of setup, 4 bits per doubling, 5 bits per increment, and then the base value N. It may be possible to eke out a few more bits for some values using variations on this approach, but I didn't care to try more than the one option.

I wrote an exhaustive search (modulo a couple obvious heuristics) to find the shortest way to express each number from 0 to 256 using any of these approaches to combine other integers.

I have not proven that my results are the shortest possible representations of each integer, or even that they're all correct in the first place (I could have made a dumb typo somewhere in the search code), but I don't expect anybody to need copy-pastable representations of small Church Numerals without being in a position to double- check the values anyway.

As a concrete example, the largest value is 239 (at 132 bits) using the binary shift-and-increment encoding atop a base value of 3:

((λiλs.(i (s (i (s (i (s (i (s (s (i (s λfλx.(f (f (f x))))))))))))))
  λnλfλx.(f ((n f) x)))
  λnλfλx.((n f) ((n f) x)))

A plot of the size in encoded bits of each integer from 0 to 256

Perhaps the most interesting thing about the table of encodings is that while the lengths generally follow a sort of "fractal sawtooth" pattern it isn't quite as regular as I would have expected. This may be an indicator that there are other strategies that I've overlooked which would have brought some of the outliers into line.

Conclusion

Large amounts of literal data can be encoded in the Binary Lambda Calculus with an overhead of 2.5 bits-per-bit, which is either pretty great or absolutely terrible depending on your expectations.

Smaller constants are much more challenging from an efficiency perspective because constant factors matter a lot more, but every byte value can be encoded as a Church Numeral in 132 bits at most, with the average being 90 bits.

If any of this ever actually matters though, your best option will likely be defining some other virtual machine using the Lambda Calculus and then representing program and data alike as a large constant data blob.