Melanjan
| Paradigm(s) | imperative |
|---|---|
| Designed by | User:Challenger5 |
| Appeared in | 2022 |
| Computational class | Turing complete |
| Reference implementation | See below |
| Influenced by | Aubergine |
| File extension(s) | .mj |
Melanjan is a self-modifying programming language created in 2022 by User:Challenger5. It is a derivative of Aubergine, bearing similarities to Purple. The main differences from Aubergine are:
- all three-operand instruction forms are replaced by a single two-operand subtract instruction;
- there are three general-purpose variables (
a,b,c) rather than two; - writing outside the bounds of the program is still illegal, but reading outside the bounds returns -1 (for negative indices) or 32 (for indices larger than the length of the program), which enables an efficient implementation of comparison.
Specification
The program state is a finite array of arbitrary-size integers. At the beginning of execution, these integers are initialized according to the contents of the program (the exact encoding used is not specified, but at least those characters in the program corresponding to printable ASCII characters should be mapped to their values in ASCII). There are also four more variables, a, b, c, and i, which are all initially zero. The first three variables are general purpose, and the last is the instruction pointer.
Executing an instruction consists of fetching the integer whose index is given by the instruction pointer, and then another integer after that. These values are treated as operands to the subtract instruction, which is performed. After that, the instruction pointer is incremented by 2 unconditionally. If this causes it to point to exactly the end of the program, execution terminates. In general, the instruction xy has the semantics x = y - x, where x is some storage location and y is some value. The following are permitted values for x and y:
a,b,c, andirefer to the corresponding variables and can appear on either side. (Note that the observed value of the instruction pointer is always the address of the instruction, because the increment by 2 is performed after the instruction is executed).A,B,Crefer to locations in memory at addresses given by the corresponding variables, and can appear on either side. If an address is outside the bounds of the program, it is illegal to write to it, but legal to read from it. Reading from a negative address gives -1 and reading from an address beyond the end of the program gives 32.1is the constant 1, and can only appear on the right side.o, when appearing on the right hand side, refers to the code of a character read from standard input (or -1 on EOF). As a special case, when it appears on the left hand side, no subtraction is performed; instead, the right hand side value is treated as the code of a character and written to standard output.
Programs should refrain from jumping outside the bounds of the program by writing to i and from causing commands to be executed which do not follow the syntactic rules described above.
Examples
Note that adding a trailing newline will generally break a Melanjan program.
Read a single character from STDIN, and then write it to STDOUT:
oo
Clear a variable or memory location:
aa
Copy a value:
aaab
Perform a += b, if there is some other value c known to be zero:
acab
Unconditionally jump to address a-1, clobbering a in the process:
a1aiia
Motivation
Melanjan was created due to the author's dissatisfaction with Aubergine, particularly the fact that the limited memory meant it was essentially no different than a Minsky machine. Minsky machines are Turing complete, but have the unfortunate property that, with only increment and decrement, the number of steps needed to represent a dynamically sized data structure with N bits is on the order of 2N. Although Aubergine can perform arbitrary additions in a single step, not just increments, this ends up being insufficient due to the limitations of the : comparison operator. Dividing a number N by 2 requires a decrement-and-compare-to-zero loop and so it is stuck taking O(N) time.
This restriction can be avoided if ordered comparison is provided (a < b) and not just comparison to zero. With the help of this operator, division by 2 can be implemented more efficiently with binary search. Rather than providing this operator directly, though, Melanjan radically simplifies the language and requires that it be implemented using the semantics of out-of-bounds indexing.
The ultimate goal of the Melanjan programmer should be to implement this: find a way to interpret some other, more usable Turing complete language, like Smallfuck, or compile it into Melanjan, with the property that the number of Melanjan instructions executed in the simulation is at worst polynomial in the number of instructions executed by the host language, not exponential. (The original specification describes O(N2) overhead as the goal, but this might be impossible.)