Nest
Nest is an esoteric programming language designed by Sam Bleckley. It is a turing-complete language whose low-level instructions are nested, allowing unusual self-modifying behavior. Instructions include the digits 0-7 and !. Because all data is used in base 8, all strings of instructions between !'s are valid data, and all data are also valid instructions.
Instructions
0
|
is a no-operation instruction. It does nothing. |
1 |
takes the following n bits (where n is the value of the DCNT register) of the currently executing orthostruct and places them in DATA. The next instruction to execute is that following those n bits. |
2 |
reads the orthostruct found at the address contained in ADDR, and places the value into DATA. |
3 |
writes the value of DATA into the orthostruct at the address contained in ADDR. |
4 |
swaps the values of DATA and ADDR |
5 |
adds the value of the orthostruct located at the address in ADDR to the value of DATA, and places the result in DATA. |
6 |
subracts the value of the orthostruct located at the address in ADDR from the value of DATA, and places the result in DATA. |
7 |
tests DATA. If the value of DATA is zero, then execution of the orthrostruct halts, and the orthostruct at address EXEC+1 is executed. If DATA is non-zero, 7 acts as 0. |
Bang
! is not an instruction which is executed at runtime. Instead, it is a separator between orthostructs.
Orthostructs
An orthostructs consists of all valid instructions (0-7) between two !'s. They are so named because when written in a program (like this Fibonacci generator),
10!5!7!3!1!0!0!0!7 310044241006434100545410044310064241005431007424101246!!1!
The orthostructs run horizontally, while the program as a whole runs vertically. Note that line breaks are not mandatory, however, and non-instruction characters are comments. Orthostructs should be seen as high-level instructions --- with the benefit that they can be modified by themselves, while they are in the process of executing.
Constant registers
Nest has 4 special orthostructs, which use the first four addresses (0-4). Located at (0) is the execution register (EXEC). This register holds the address of the currently executing instruction. Located at (1) is the data register (DATA). It holds an orthostruct for manipulation. General purpose. Located at (2) is the address register (ADDR). It holds an address used by the 2, 3, 5, and 6 instructions. Located at (3) is the data count register (DCNT). The value of this register is the number of digits that the interpreter will accept as data after recieving the '1' instruction. In implimentation, it makes more sense to hold these four addresses separately in the interpreter. Doing so not only speeds the process, but also allows multiple threads to run simultaneously in the same space. Initializing these four values differently will entirely change the behavior of a program.
The Interpreter
A nest interpreter does three things; it initializes programs, executes orthostructs, and terminates.
Initialization
An interpreter takes as input a text string, containing the digits 0-7 and !. Other characters should be stripped. All characters between between the start of the string and the first bang are labeled an orthostruct with address 0. The strings between each of the following bangs are addressed consecutively from 1 in base 8.
The first four orthostructs are loaded into the interpreter as EXEC, DATA, ADDR, and DCNT (in that order). Then EXEC is read, the value is used as an address, and the orthostruct located at that address is loaded for execution, and execution begins.
Executing an Orthostruct
Execution of an orthostruct when the interpreter is in its normal state takes place one character at a time. The orthostruct is loaded from its address before each instruction; note that this is not equivalent to retaining the orthostruct in memory from instruction to instruction; nor is it the same as loading the orthostruct pointed to by EXEC each instruction.
A character of the orthostruct is read. What occurs next depends on the character:
0
|
The interpreter continues in normal mode. |
1 |
The interpreter enters data mode (see 'Data Mode') |
2 |
The interpreter reads ADDR, and copies the orthostruct at that address into DATA. |
3 |
The interpreter copies the orthostruct in DATA into the orthostruct addressed by the value of ADDR, replacing what was previously there. |
4 |
The orthostruct in DATA is copied into ADDR, replacing what was previously there. The value of ADDR previous to the copying operation is copied into DATA, replacing DATA's previous contents completely. |
5 |
The interpreter reads the orthostruct addressed by the value in ADDR, and sums (base 8) the retrieved data with the orthostruct in DATA. (See 'Note on Arithmetic'). The result is placed in DATA. |
6 |
The interpreter reads the orthostruct addressed by the value in ADDR, and subtracts (base 8) the retrieved data from the orthostruct in DATA (See 'Note on Arithmetic'). The result is placed in DATA. |
7 |
If the value of DATA is non-zero, the interpreter continues with the next instruction in normal mode. If the value of DATA is zero, then EXEC is incremented (base 8) by 1, and the interpreter ceases execution of the current orthostruct. The next orthostruct is loaded and executed. The interpreter remains in normal mode. |
! |
Upon encountering a bang, the interpreter ceases execution of the current orthostruct, and begins the cycle again (loading from the address in EXEC, etc) |
Data Mode
When the interpreter enters data mode, the orthostruct in DCNT is read as a base 8 number N. The next N consecutive characters of the currently executing orthostruct are read and stored (as a group) in DATA. The interpreter returns to normal mode, and executes the next unread character - that is, the next character after the N which were stored to DATA.
Note on Arithmetic
When performing addition or subtraction of orthostructs, the following rules must be followed (in addition to the classical rules of arithmetic base 8):
Preceding Zeros - Though preceding zeros do no change the value of an orthostruct, they do change it's behavior in execution. Therefore, if the longer (not larger) of the two orthostructs has preceding zeros, those zeros must be maintained in the final sum or difference. E.g. 001320 + 10211 = 011531
Carry digit - In the addition of two numbers, if there is a carry digit remaining after the sum is completed, it is concatenated to the sum; e.g. 702 + 511 = 1413.
Negative numbers - There are no negative orthostructs, nor can orthostructs overflow. Therefore, in any subtraction, the smaller value is subtracted from the larger (keeping in mind that the smaller value is not necessarily the shorter).
Termination
The interpreter terminates execution upon loading a null orthostruct (!!) in for execution. In all other cases, null orthostructs are treated as containing value 0. An interpreter may then print out the entire contents of the program (as Nest has no output stream, only change in state).
Properties of Nest
The most unusual property of nest is it's extreme flexibility when it comes to self modifying code. Because the memory and format of data and instructions are identical, reading, writing, and executing one string of instructions is exactly like any other, even if that set of instructions is the orthostruct currently being executed.
One drawback of Nest is it's unusually low omega; because the EXEC register does not increment by default, most random-string programs that get so far as to execute a single orthostruct never terminate. However, given that ALL strings created from the [0,1,2,3,4,5,6,7,!] set are valid, runnable Nest programs, a low omega is not surprising.