Sesos

Sesos is an esoteric programming language created by Github user @DennisMitchell in 2016. Semantically, it is almost equivalent to brainfuck, except that it allows slightly more types of loop. The main innovation is in the syntax, which repurposes sequences of commands that would otherwise be useless (such as incrementing a cell and then immediately decrementing it) in order to allow for a very highly compressed representation of typical brainfuck code.

Specification

Like in brainfuck, Sesos is based around an infinite tape that is initially all zeroes, combined with a data pointer that points to a tape element. The tape is infinite in both directions; the specification does not specify the maximum value of each element (but the official interpreter can be made to use either 8-bit tape elements that wrap modulo 256, or tape elements that are unbounded integers).

A Sesos program consists of a sequence of bits, that are interpreted by reading them in chunks of three bits at a time (interpreted as an octal digit). Commands can be multiple digits long, but the digits are split into four groups, and each command uses digits from only a single group; a file can initially be roughly parsed into commands via looking for points where a digit from one group is adjacent to a digit from another group, although sometimes a block of digits that all belong to a single group will correspond to multiple commands. Here are the digit groups, and the commands they correspond to:

Control instructions (digits 0 and 1)

Control instructions handle control flow (jumping and looping), together with EOF-aware I/O.

0 and 1 0 each start a loop (in Sesos assembly, these are named jmp and nop respectively). When using jmp, the loop starts by performing the loop test (what the loop test is depends on which command is used to end the loop), in the style of a while loop. When using nop, the loop unconditionally runs one iteration before performing the test, in the style of a do … while loop.

1 and 0 1 each end a loop (in Sesos assembly, these are named jnz and jne respectively). jnz uses the standard brainfuck-style loop test: it checks whether the current tape element is nonzero, and continues/starts the loop if it is nonzero, exiting/skipping the loop if it is zero. jne attempts to read one byte of input into the current tape cell, and continues/starts the loop if the read was successful; the loop is exited/skipped if the read failed due to an end-of-file condition.

The specification is unclear as to how ambiguous sequences of control instructions are interpreted; it specifies that no sequence of commands may be interpreted as containing a jmp followed by jne or vice versa, and that the file cannot end with a start-of-loop instruction, but these rules are not sufficient to disambiguate all possible sequences of commands.

Arithmetic instructions (digits 2, 4 and 5)

Arithmetic instructions handle changing the values of tape elements, typically by adding to or subtracting from them, but possibly by reading values into them.

A block of arithmetic instructions starts with zero or more 2s, each of which is represented in Sesos assembly as a get command. Each of these reads a byte from standard input and stores it in the current tape cell (meaning that if there is more than one 2, the later reads will overwrite the values read by earlier reads).

It is possible for the block to contain only get commands; in other cases, there will be a 4 or 5 after the possibly empty string of leading 2s. 4 represents a subtraction from the current tape cell (sub); 5 represents an addition (add).

After specifying an addition or subtraction, the rest of the block specifies the amount to add or subtract. The notation for the numbers used here is defined recursively as follows: the empty string has a value of 1, x 2 has value 3y-1 where y is the value of x, x 4 has value 3y where y is the value of x, and x 5 has value 3y+1 where y is the value of x.

Pointer instructions (digits 6 and 7)

Pointer instructions change which tape element is considered to be the current tape element.

The direction to move the tape is specified by the first digit of the block; 6 represents a movement to the left (rwd), and 7 represents a movement to the right (fwd).

The amount to move the tape is specified by the rest of the block. This uses a similar notation to the arithmetic instructions, but in binary rather than ternary; the empty string has a value of 1, x 6 has value 2y where y is the value of x, and x 7 has value 2y+1 where y is the value of x.

Output instruction (digit 3)

Each 3 instruction writes the byte stored in the current tape cell to standard output. This is represented in Sesos assembly as put.

If the loops in a program do not fully match, the program will be interpreted as containing additional jmp added to the start, or jnz added to the end, to complete any incomplete loops. Additionally, a jmp … jnz loop will be treated as jmp … jne if it entirely surrounds the program (otherwise, the program would exit immediately upon starting).

Computational class

It is possible to directly compile brainfuck into Sesos as long as it contains no comments, does not start with [, and does not use any of the following sequences of commands: <> >< +- -+ +, -, [] ][. Because brainfuck is trivially Turing-complete even under these restrictions, Sesos is also Turing-complete.

External resources

• Official specification and reference interpreter
• Online assembler, and interpreter for Sesos assembly, at Try It Online!