Crement
Crement is a programming language invented by User:Zzo38 and named by User:Ais523.
The program consists of a list of instructions, where the first instruction has address zero, and they increase from there. Each instruction consists of the opcode, polarity, address, and data. The opcode is ADDRESS, DATA, or JUMP. The polarity is positive or negative. Address and data are each integers (of unlimited range). This program language is involving self-modifying code.
Instructions
ADDRESS: Write one more than (if the polarity of this instruction is positive) or one less than (if the polarity of this instruction is negative) the data field of this instruction into the address field of the instruction at the address specified by the address field of this instruction, and then execute the instruction at the address after this instruction.
DATA: Like ADDRESS, but writes into the data field of the instruction it points to instead of writing into the address field.
JUMP: If the condition is true, then execute the instruction at the address given by the address field of this instruction, otherwise execute the instruction at the address after this instruction. If the polarity is positive, then the condition is if the data field of this instruction is positive. If the polarity is negative, then the condition is if the data field of this instruction is negative.
Execution
Execution normally proceeds in order (starting from address zero) unless a JUMP instruction changes it. The program halts if trying to execute anything at an address greater than the last address in the program; writing to such addresses does nothing.
Jumping to or writing to negative addresses is undefined, although some implementations may use it to implement I/O.
Syntax
Here is describing the standard syntax to write the program in a text file (an implementation can work differently though, but should have some way to convert from this standard syntax into their format if needed).
Each instruction is written with three or four pieces with white spaces in between (you can have one or more spaces between two adjacent pieces). The pieces are:
- Label: Optional. Put a colon and then the name.
- Polarity/opcode: Put - or + for polarity, followed by A or D or J to specify the opcode.
- Address field: A number.
- Data field: A number.
A name is any alphabetic ASCII character and underscore and digits, but can't start with a digit. Each label must have a different name.
A number is written with one or more terms. A term consists of - or + followed by either a name, or a ASCII decimal notation of a natural number, or @ to indicate the address of this instruction. It is allowed to omit the sign before the first term, in which case + is assumed. Any name mentioned in here must exist as a label in the program (it can come before or after or on this instruction).
Comments can be written by an asterisk and end at a line feed or end of file; the entire comment is then treated as a space during parsing.
Macros
If macros are implemented, then the following syntax can be used. To define a macro, use $ followed by the macro name, and then the definition in parentheses. Within the definition, use $ to replace it with the argument (a list of zero or more tokens). You can't nest macro definitions. Use a macro by giving its name with the argument in parentheses directly afterward. Macros can call other macros, including using the argument as the name of the macro to call.
A program with macros can always be preprocessed to convert into an equivalent form without macros.
Computational class
Crement is Turing complete by reduction from a two counter Minsky machine variant in which all instructions have a label and include the label of the next instruction. Rather than having increment and decrement instructions for both counter, there is a "swap" operation for swapping the counters. The operations are:
<label> INC1 <next> * increment counter1 <label> SWAP <next> * swap counter1 and counter2 <label> DEC1 <next> <next_z> * decrement counter1 or jump to next_z
Translations: Each instruction becomes a block of code. Before a block is executed, the data fields of the first two instructions are filled with the current counter values.
<label> INC1 <next>
label: +D @next+0 0 * +0 [store counter1+1 at next+0]
+D @label+2 0 * +1 [store counter2+1 at +2]
-D @next+1 0 * +2 [store counter2 at next+1]
+J @next 0 * +3 [jump to next]
<label> SWAP <next>
label: +D @label+2 0 * +0 [store counter1+1 at +2]
+D @label+3 0 * +1 [store counter2+1 at +2]
-D @next+1 0 * +2 [store counter1 at next+1]
-D @next+0 0 * +3 [store counter2 at next+0]
+J @next 0 * +4 [jump to next]
<label> DEC1 <next> <next_z>
label: -D @label+5 0 * +0 [store counter1-1 at +5]
-D @label+12 0 * +1 [store counter2-1 at +12]
+J @label+5 1 * +2 [jump to +5]
-D @label+6 1 * +3 [disable jump at +6]
+A @label+5 @label+16 * +4 [modify offset at +5]
+D @label+16 0 * +5 [copy counter1 to +16/+17]
+J @label+4 1 * +6 [jump to +4/skip]
+A @label+5 @label+15 * +7 [reset offset at +5]
+D @label+6 0 * +8 [enable jump at +6]
+J @label+12 1 * +9 [same logic as previous 7 instructions]
-D @label+13 1 * +10
+A @label+12 @next_z+0 * +11
+D @next+1 0 * +12 [copy counter2 to next+1/next_z+1]
+J @label+10 1 * +13
+A @label+12 @next+0 * +14
+D @label+13 0 * +15
-D @next+0 0 * +16 [store counter1-1 at next+0]
+J @next 0 * +17 [jump if counter1>0]
-D @next_z+0 1 * +18 [store 0 at next_z+0]
+J @next_z 1 * +19 [jump to next_z]
The key insight is that one can easily build a loop that is executed twice, allowing a value to be copied to two locations. Two such loops appear in the translation of DEC1, from lines +2 to +8 and from +9 to +15.