Figurehead

Figurehead is a minimal esolanguage designed by Keymaker. The language was formed while the author was designing another language, and once the idea for Figurehead struck, the other one was abandoned. The language uses two characters, "|" and " ", and a memory that's mostly accessed as a stack. Programs can only consist of the two characters, everything else is forbidden. Only sequences of two or more of the same character are counted, that is, only they cause computation to happen. Sequences of one character may be used to distinguish different sequences from each other. The memory is unbounded and infinite.

Instructions

"|"-sequences (starting from "||") form a value that is pushed to the right end of the memory. For example "|||" would push "|||" or 3, however you want to see it, into memory.

" "-sequences (starting from "  ") form loops, and need a matching part. Loops may be nested, and an identical loop sequence used later. Once a loop is encountered, the rightmost value is popped from the memory (an empty memory results in an error), and the memory loops as long as there are instances of the value indicated by the value that was popped, and whilst looping one instance is removed from the memory at the beginning of each cycle, the instance chosen by moving from left to right in the memory (to keep the language deterministic). It is also possible for a loop to be executed zero times (not at all, in other words).

An example

As an example, let's have the following program:

|| || ||   |||   |

The last "|" is not necessary but it's included to avoid problems with the wiki cutting out trailing spaces. Anyway, the program begins by pushing "||" into memory three times. Then a loop. Memory is popped, and there are two instances of "||" left. That is more than zero, so the loop may begin. On each cycle one "||" is removed from the memory, thus the loop will be executed twice. On each time "|||" is pushed into memory. The state of the memory after the program is finished is two "|||" values.

Computational class

The language is Turing-complete. It's easy to have infinite values stored in it (decoded as amount of instances of certain values), and thus it's easy to create any unbound number of registers with any natural number as their capacity. Minsky Machines, which are Turing-complete, can be translated into Figurehead, proving its Turing-completeness. (This is done explicitly, too. See the external Figurehead page.)

External resources

• Figurehead page (specs, programs, interpreter, Minsky Machine to Figurehead compiler)