Hypercube

hypercube is an esoteric programming language developed by Alex Meiburg in 2011. The memory of a program is one hypercube of bits, and only two operations change that memory: a NAND operation, and a copy operation. NAND is universal for computation, so those two operations are sufficient for every boolean function. The other basic control flow of recursive functions jumps this from "universal for Boolean function" to "Turing complete".

The language has no variable and no branch. A test comes from the lazy rule of the NAND operation, and a second kind of test comes from the handler of a failure. Therefore all control flow of the language comes from a speed rule and an error.

The memory

The memory is one cube of bits. The cube has n inds. An "ind" is one index of the cube (one dimension), so the cube holds 2ⁿ bits. The value of n can be 0, and a cube with 0 inds holds one bit.

The first ind divides the cube into two halves. The left half holds the bits with the first index 0, and the right half holds the bits with the first index 1. Each half is a cube with n−1 inds.

The number of inds is the type of the memory. Every program moves that number by a fixed amount, and the rules below reject a program that does not agree with itself about the number.

The two operations

Program	Name	Effect on the inds
=	copy	n becomes n+1
@	NAND	n becomes n−1

= adds a new first ind. Both halves of the result are equal to the input. The operation is always valid.

@ applies NAND to the two halves and removes the first ind. At each position i the result is in[0][i] NAND in[1][i]. The input must have one ind or more. If the input has 0 inds, the operation fails.

A program runs from right to left, in the manner of the notation for function composition. The rightmost part runs first.

Therefore @= is NOT. First = copies every bit. Then @ applies NAND to each bit and its copy, and x NAND x is NOT x.

The empty program is the identity program. @=@= and @@== are also identity programs.

Splits

( A , B )

A split divides the cube at the first ind. It runs the program A on the left half, runs the program B on the right half, and joins the two results into one cube.

The input must have one ind or more. The two results must have the same number of inds. If the numbers are different, the split fails.

A split cannot move a bit from one half to the other half, so at first the language appears to compute at each position only. But NAND(NOT L, TRUE) is L, so a program can take one half of the cube:

LEFT  := @(NOT,TRUE)
RIGHT := @(TRUE,NOT)

The pattern (F,G)= then builds a new cube from two functions of the complete input, because = gives a copy of the input to F and to G. With these programs a program can move a bit to any place, and the language becomes general.

Names, blocks and loops

NAME := PROGRAM
[ BODY ]
[ BODY , HANDLER ]

A line can give a name to a program, and other programs can then use that name.

Square brackets make a block. The symbol # runs the block again, which gives recursion and therefore loops. #& names the block one level above, and each further & adds one level. A split does not make a level, so only the square brackets count.

Three events make a failure:

1. The program applies @ to a cube with 0 inds.
2. The program applies a split to a cube with 0 inds.
3. The two halves of a split give a different number of inds.

The HANDLER part of a block catches a failure, and the handler then runs on the input of the block.

A failure is the base case of a walk over the cube. This program gives the AND of every bit, at every position of the cube:

ALL := [=#@=@,]

The body applies AND to the two halves and then calls itself, so the cube becomes smaller at each step. The last call has a cube with 0 inds, so @ fails. The handler is empty, so that call gives its input back. Each level then applies =, and the one bit goes back to every position.

Lazy evaluation

NAND(false, y) is true for every value of y. An implementation uses that rule: for @(X,Y) it runs X first, and it does not run Y if the result of X holds only false bits.

The rule is the only conditional of the language. This is the pattern:

@( @(COND,THEN)= , @(NOTCOND,ELSE)= )=

If COND is false everywhere, the rule skips THEN, and the result is ELSE. If COND is true everywhere, the rule skips ELSE. THEN can therefore hold a recursive call, and the loop stops without a failure.

The two kinds of test are not the same, and a program needs both:

• A test with @ needs both parts to give the same number of inds, because the split must join them again. It chooses between two values of one shape.
• A block never compares its body with its handler, so a block chooses between two programs of different shapes. This is the only construct of the language with that property.

A program that changes the size of its own memory needs the second kind, because the size of the result is not the same in the two parts.

Examples

Each gate below takes a cube with the shape (a,b) and gives a cube of one ind less. The result holds the gate of a and b at every position.

NOT   := @=
TRUE  := @(NOT,)=
FALSE := NOT TRUE
NAND  := @
AND   := @=@
OR    := @(NOT,NOT)
XOR   := AND (OR, NAND) =

TRUE is a copy of the cube, then NOT on the left half, then NAND. NAND(NOT x, x) is true for every x.

IF takes a cube with the shape ((a,a),(b,c)). It gives b where a is true and c where a is false. It is the standard multiplexer of four NAND gates:

IF := @@((,NOT),)

Input and output

A file that starts with the line IO uses an interface of requests. The implementation runs the program again and again, and the first cube is one false bit. The result of the program says what must happen next:

Result	Meaning
(0,x)	The program is complete.
(1,(0,y))	Read one byte. The program starts again with (1,(byte,y)).
(1,((1,a),y))	Write the 8 low bits of a. The program starts again with (1,y).

The state of the program is therefore one value, and the program is a pure function of that value.

One program without names

A name is only a short way to write a program, so an implementation can replace every name with its body. A # counts brackets and not definitions, and a definition can never hold a # without brackets of its own. Therefore the substitution never changes the block that a # names.

Every character of the language is one token, so the result needs no space. The interpreter for brainfuck becomes one expression of about 183,000 characters, and that expression uses eight different characters only:

@ = ( ) [ ] , #

Note that this particular program never uses &. A name that calls itself through other names cannot expand out through direct substitution in this way. Such a loop must use # and a block.

Computational class

hypercube is Turing complete.

= makes a cube one ind larger, so a program can make its own memory larger while it runs. The program (,FALSE)= doubles a cube and puts the old bits in the low half, so every bit keeps its place:

(,FALSE)= on 1101 gives 11010000

An interpreter for brainfuck uses that program. It starts with 32 bytes of program and 16 cells, and it doubles every part of its state each time the state is full. A pointer is a one-hot mask and not a number, so a step of a pointer is a shift of the mask, and the mask grows with the block that it names.

A program of that kind cannot use a fixed number of = operations for a test, because the size of the state changes. Every test must keep the shape of the state, in this manner:

ANY AND ( , MASK )=

MASK is a state with true bits at one field only, AND keeps the shape, and ANY gives the answer of the test at every position, whatever the size of the state is.

External resources

• hypercube on GitHub — an interpreter in C++, a library of programs, binary arithmetic, the bottles of beer song, and two interpreters for brainfuck. One of the two makes its own memory larger without limit.