Nutes
Nutes is an esoteric programming language invented by Yoel Matveyev and implemented in a prototype form in 2017. The current, more developed version was implemented in 2019. It is an OISC virtual machine operating either on a circular or (theoretically) infinite tape. Each cell of the tape contains a balanced ternary word of a certain number of trits (ternary equivalents of bits). The default word width is 36 trits. The machine takes two operands, predetermines the next jump by the sign of the sum of their signs and replaces the operands a and b by a-b and b-a. Each operation uses three jump addresses (for negative, zero and positive sign sum). Only relative addresses are possible; like in the Turing machine, no inherent addresses are associated with any cell.
Background
According to the author, the machine was inspired by the Soviet ternary computer Setun from 1959 (Nutes is Setun read backwards) and by Subleq, a well known OISC Turing-complete architecture. Since SUBLEQ is easily emulated by Nutes, the Nutes machine is also Turing-complete. Moreover, as it lacks absolute addressing and can operate on an infinite tape, it is, in principle, Turing-complete in true sense.
Description
The head of the machine reads the current cell and two other cells adjacent to it:
x j y
The cell j contains a relative address to another cell, surrounded also by two other adjacent cells. These three cells contain a series of jump addresses relative to j:
j- j0 j+
The cells x and y contain pointers to other two cells, v1 and v2, which contain the actual operands. The pointers are also relative to j.
The choice between the jumps depends on the sum of signs of v1 and v2. The head jumps to j- of cells, if the sum sign is negative, to j+ cells, if the sun sign is positive, or to j0 cells, if the sum sign is 0. Note that, unlike Subleq, the jump is conditioned by the operands and not by the result.
Unless the computation is terminated or interrupted, the values of v1 and v2 are replaced, respectively, by v1-v2 and v2-v1. Termination or interrupts occur in the case, when the operation would lead to an infinite loop stuck to the same cell, which happens in the following case:
If the sum of the signs of the two operands and the next jump address j0 are both 0
Although in some rare edge cases, when either x, j or y is modified by the operation preventing the fall into an infinite loop, such cases may be disregarded as rare exceptions. Normally the interrupt condition indicates an upcoming immediate infinite loop.
Termination and interrupts
The above described halting condition invokes the interrupt engine, which handles input and output in balanced ternary, alphanumerical, decimal and balanced 27-base format. Depending on which absolute value, v1 or v2, is greater, v1 or v2 is respectively used as an opcode for the IO engine. The somewhat complicated way of the opcode decoding is described on the project's page. Note that the interrupt engine is merely a convenient tool, which allows to use the machine as a real-life computer. In order to be Turing-complete and usable, Subleq and other common OISC models also require some halting and I/O mechanisms.
Implementation
Nutes is implemented in Common Lisp. The implementation includes a basic assembler, which allows to write the code in a humanly readable form.
Sample programs
The following Lispy assembly program asks the user's name and outputs "Hello World, [name]":
(prg-var prg 'hello (chars-trytes "Hello ")) (prg-var prg 'world (chars-trytes "World,")) (prg-var prg 'name (chars-trytes "Name? ")) (prg-var prg 'io 9) (prg-var prg 'out 10) (prg-io prg 'io 'name 0) (prg-io prg 'out 'hello 0) (prg-io prg 'out 'world 0) (prg-io prg 'out 'name 0))
When compiled, it looks like this (the starting address is marked as bold:
10 9 16086946250976080 17943922394188172 14852728792888700 0 0 0 0 0 0 -1 1 36 3 3 3 -17 0 -7 -19 -6 -3 -24 0 -13 -23 -12 -9 -30 0 -19 -30 -18 -15 -36 0 -25 -37 -24 -21
The project offers a number of other demo programs and useful assembly macros, including addition, subtraction, copying and swapping numbers, conventional types of conditional jumps, multiplication, ternary shift, Fibonacci numbers and factorial.
Interesting facts
The main Nutes operation, as well as its I/O engine, is designed in such a way that any program written entirely backwards with all its cell values sign-reversed, act precisely as the original one (except that all results, of course, will be sign-reversed as well). Thus the "Hello World" may be rewritten as
21 24 37 25 0 36 15 18 30 19 0 30 9 12 23 13 0 24 3 6 19 7 0 17 -3 -3 -3 -36 -1 1 0 0 0 0 0 0 -14852728792888700 -17943922394188172 -16086946250976080 -9 -10
Criticism
The project lacks proper documentation besides scarce cryptic comments inside the code, and requires considerable familiarity with Common Lisp.