0x29A

0x29A is an esoteric programming language created by David Lewis in 2004. It uses a mixture of imperative and functional programming, forming a new paradigm the creator calls dysfunctional programming.

Memory

0x29A has a memory consisting of a one-byte register, which is initially zero, two variables called a and b that can contain functions, and a stack of functions, which is initially empty. The two variables are not accessible directly, but are used as a temporary store while popping and pushing functions in the stack. An empty stack behaves as if it contains the identity function ((sk)s).

Commands

Stack-pushing commands

0x29A contains the following six commands which push the functions of the same name onto the stack:

sk+-.,

Looping commands

0x29A features two looping commands, represented by the left and right square brackets. When a left square bracket is encountered, then if the register's value is zero, program flow continues at the matching right square bracket (the program halts if there is no matching right square bracket); otherwise program flow continues at the next instruction. When a right square bracket is encountered, then if the register's value is nonzero, program flow continues at the matching left square bracket (or at the beginning of the program if there is no matching left square bracket); otherwise program flow continues at the next instruction.

Stack-rearranging commands

0x29A contains two commands that rearrange the stack and allow the creation of complex functions.

The command represented by the percentage sign pops two functions from the top of the stack, storing them in the variables a and b, and then pushes them back onto the stack in reverse.

The command represented by a tilde pops two functions from the top of the stack, storing them in the variables a and b, and the pushes (ba) onto the stack.

Function evaluation

After each command is executed, the function at the top of the stack is evaluated if this is possible. The following rules are used when evaluating functions:

• (((sx)y)z) becomes ((xz)(yz))
• ((kx)y) becomes x
• ((.x)y) becomes x, the value of the register is printed (as an ASCII character), and the register is set to 0
• ((,x)y) becomes x, and the register is set to the ASCII value of a character from the input
• ((+x)y) becomes x, and the register is incremented
• ((-x)y) becomes x, and the register is decremented

Computational class

In the evaluation rule for s, it is not specified that either xz or yz are evaluated. This may be a bug. If it is not, Turing completeness is not obvious since a working combinator calculus can no longer be trivially embedded into the language.

Indeed function evaluation alone is then decidable and so not Turing complete. By checking about a hundred cases, we can show that every function either halts or reaches the recognizable growing pattern

(s2k)m(s3k(s2k))((s2k)n(s3k(s2k)))

where fnx=f(f(...(x)...)) and k stands for any of k.,+-. Note that s2kxy=xy so this is just sii(sii) in disguise.

Nevertheless, even with this restriction there are enough ingredients to compile Brainfuck into the language. The basic idea is to represent a brainfuck tape as two functions, one for the part to the left of the pointer and another for the part to the right, while the cell at the pointer is kept in the register.

Each half-tape function, when applied to k, will increment the register by the saved amount, and then return the function for a shifted half-tape with the value popped off.

To shift a value of 3, say, onto a function f, is to replace f by

s(s+)(s(s+)(s(s+)(k f)))

This can be achieved with the commands

k%~ ss+~~%~ ss+~~%~ ss+~~%~

To shift the register to a function, use

 k%~ [ss+~~%~ -%~k~]

Finally, the output operator in 0x29A is destructive whereas the output operator in brainfuck is not, so one needs to clone the value before handing it to the output operator. This is done by making the functions twice (once in top-of-stack, once in next-to-top-of-stack), thereby destroying the register, running it once, restoring the register, running the output and running the second copy.

The translation rules are thus as follows:

+ -> +%~k~
- -> -%~k~
, -> ,%~k~
. -> k%~ kk~ [ss+~~%~ % ss+~~%~ % -%~k~] k~ .%~k~ ~
< -> k%~ [ss+~~%~ -%~k~] % k~ % 
> -> % k%~ [ss+~~%~ ~%~k~] % k~
[ -> [
] -> ]

External resources

• 0x29A website
• A 0x29A implementation and a Brainfuck to 0x29A converter.
• A Haskell program to classify 0x29A dysfunctional expressions.