Cthulhu

Cthulhu is an esoteric programming language heavily based off of Deadfish i.

Structure

Cthulhu programs consist of a list of function definitions, with one on each line. These definitions are the function's id (a nonnegative integer followed by a letter from A to D) followed by a space and the function's source code. Each function has its own accumulator. Execution consists of executing function 0A.

Commands

Instruction set

The Cthulhu language has the following commands:

Command	Function
i	Increment this function's accumulator.
d	Decrement this function's accumulator.
[	Must be immediately followed by a function id. Calls that function.
]	Must be immediately followed by a letter. Calls the function with that letter and with a number equal to this function's accumulator
o	Output this function's accumulator.
*	Get input into this function's accumulator.
E	Must be immediately followed by a function id. Moves this function's accumulator into the accumulator of the function with that id.
e	Same as E, but reverse direction.

Function calls

After a function's last command is executed, it returns to the function that called it, at the point immediately after it was called. If 0A returns, the program halts. If an attempt is made to call a nonexistent function, the program instead calls the function with the same letter and with the largest number less than the one specified to call. If none exists (likely as a result of calling a negative id), the program calls the function with the same letter and the highest number at which a function with that letter exists. If this still does not exist, the call is ignored.

Example programs

Infinite loop

0A [0A

Count up

0A io[0A

Addition

0A *iE1A*E1B[1A
1A d]B
1B i[1A
0B e1Bo

Deadfish interpreter

0A *]A
1A i
2A i[6A
3A e2AdE2A[6A
4A e2AE2BE4Be8AE3B[0B[6A
5A e2Ao[0A
6A e2Aiiiiiiii]A
7A E2A[0A
8A [0A
264A E2A[0A
265A [0A
0B e4B]C
0C e3BE2A
1C e4BdE4Be2BE5B[1B[0B
1B e5B]D
0D i
1D e5BdE5Be3BiE3B[1B

Note that since there is no character input in Cthulhu, input is supplied as numbers - 1 is end, 2 is i, 3 is d, 4 is s and 5 is o. This interpreter does indeed implement deadfish arithmetic instead of the logical way of doing things - iissiso returns 289.

Computational class

Cthulhu is Turing-complete because it can implement a Minsky machine with two registers. The value of R1 can be stored as 0A accumulator, and R2 can be stored as the 1A accumulator. States are stored as different functions with letter B. To increment a register, it can be directly accessed and incremented.
To decrement a register, first store two values in registers - the place to jump to if the register is zero and the place to jump to otherwise (the numbers are actually numbers of functions in letter B). The first location can be stored in 0C (if decrementing R1) or 0D (if decrementing R2). The second location can be stored in 2A. Then, jump to letter C (for R1) or D (for R2) using ]. 0 will be jumped to if register is zero and 1 otherwise, as these will be the only two functions defined for C and D. 0 will jump to the value stored in its register, which was set previously. 1 will decrement the corresponding register and then jump to the value stored in 2A. (Note: the word "jump" is used instead of "call" because these are tail calls - effectively jumps.) The following program implements a Minsky machine that counts up. State zero increments R1 and decrements R2, jumping back to state zero.

0A [0B
0C ]B
1C ]B
0D e0AdE0Ae2A]B
1D e1AdE1Ae2A]B
0B e0AiE0Aoe4AE0De4AE2Ae1A]D

State 0B increments 0A's accumulator (e0AiE0A), stores 0 into both 0D and 2A (e4AE0De4AE2A), then jumps to D numbered by 1A (R2) (e1A]D). Note: 4A is used as a "zero" value, and the number is output before R2 is decremented.

Implementation

Here is the link of an implementation in ocaml : https://github.com/Yul3n/esoo/blob/master/cthulhu/cthulhu.ml.

C# interpreter implementation : https://github.com/Grensorcer/YouAndCthulhu