Vein

Vein is a minimal esolanguage based on one boundless execution stack and one unbounded counter.

The language is a fusion of 1. ais523's Countercall, 2. an unreleased (and now defunct) and non-Turing-complete language of mine, 3. new ideas not part of either language. While trying to find a proof of Turing-completeness for Countercall, I found myself beginning to imagine another, simpler language (in my opinion), and how I could prove its Turing-completeness, although I did not have a working scheme right away. Eventually I managed to simplify my new language further and also to show its Turing-completeness. The resulting language is quite different from Countercall, yet indebted to its central idea of an execution stack and a counter. Because of that, I decided to borrow terminology from Countercall.

A program consist of procedures (and there must be at least one). Each non-empty line is a procedure, consisting of the procedure's identifier followed by its commands (any finite number, including zero). The procedure's identifier and its commands are all separated by spaces (and there can be more than one space in a row), and there may be space before the identifier and after the last command. Commands are either '+' or identifiers (each identifier used must exist as a defined procedure somewhere in the program). An identifier cannot be named '+'.

Executing the program is simple. On every cycle, the execution stack is popped twice. Attempting to pop the execution stack containing less than two items is undefined behaviour, and results in an error. It never happens in a valid program. The item that was popped first is ignored, the second is inspected: If the item is '+', the counter is increased by one. This operation is always successful. If the item was not '+', then it is an identifier. If the counter is larger than zero, the counter is decreased by one and the identifier's commands are pushed into the execution stack (beginning from the right-most, moving left, so that the first item in a definition is placed last, and thus top-most in the execution stack). In case the counter is zero, nothing is done (no decreasing, no pushing items). The process is repeated, endlessly.

Here is an example program consisting of three procedures (a, b, c):

a + + b b
b + a + + c c
c + + a a

Initially, the execution stack will have the items of the first defined procedure, 'a' in this case, (+ + b b). In this notation, the top of the stack is on the left. The interpreter also uses this notation to display the stack items. Counter is 0. '+' and '+' are popped. The first is ignored, the second inspected. '+' is '+', thus the counter is increased by one. Next 'b' and 'b' are popped. (Technically, at this instant, the execution stack is empty, but since it became so during the popping, and was not so before it, it is not an error. It is only an error if the stack is empty or has only one item when popping is attempted.) The first is ignored, the second is inspected: 'b' is an identifier. And because the counter is larger than zero, new items are placed into the stack and the counter is decreased by one. Items belonging to the procedure are placed into the execution stack (beginning from the right-most defined, so that the left-most defined will be the top-most item). Now the execution stack is (+ a + + c c) and the counter is 0. Then '+' and 'a' are popped, '+' is ignored and 'a' inspected. Because the counter is 0, nothing happens. The stack is popped again, '+' and '+'. The second popped is '+', thus the counter is increased by one, becoming 1. 'c' and 'c' results in pushing the contents of 'c' into the stack because the counter was larger than zero. The stack is now (+ + a a) and the counter is 0 once again. '+' and '+' are popped, '+' increases the counter by one. 'a' and 'a' are popped, and since counter is larger than zero, it will be decreased by one and items of the 'a' procedure are placed into the stack. The execution stack and the counter are now identical to what they were in the beginning, (+ + b b) and 0, and the program goes on repeating identically.

With more complex programs the execution stack tends to keep growing and growing because more items are pushed than popped and executed (because of branching). It should not be a concern since the execution stack is boundless.

Proof of Turing-completeness via Minsky Machine translation

Here is a method for translating 2-register Minsky Machine (ordinary Minsky Machine, but only programs that use registers A and B) into Vein. The simulation holds the two MM registers in the counter, encoded as multiplications of primes 2 and 3 (2^a * 3^b). To increase a simulated register, the counter is multiplied by 2 or 3, to decrease, the counter is divided (after first determining that it can be divided without a remainder) by 2 or 3. Manipulating a register's value (or checking if it is 0 or not) requires the counter's value turned into a sequence of identifiers, which are then executed to place an altered (or identical) value into the counter - after all, there is only one counter, so the data must be translated into executable code that can return the counter back to its proper state. In the beginning of every MM instruction's simulation, the counter's value is one less than its actual value 'should' be, and at the end of an instruction, right before calling the next instruction, the value is right once again, but this last call decreases it by one again (which is why the value is one less in the beginning of every instruction's simulation). Keep this mind when/if inspecting memory states.

Increase A: Multiply counter's value by two. Call the next instruction.

Increase B: Multiply counter's value by three. Call the next instruction.

Decrease A: See if counter's value is odd or even. If odd, call failure (register A is zero). If even, divide by two. Call success (register A was decreased by one).

Decrease B: See if counter is 1 (meaning that both A and B are zero). If counter is 1, call failure (register B is zero). If larger than 1, see if the counter can be divided by three. If not, call failure (register B is zero). If the counter can be divided by three, divide it, and then call success (register B was decreased by one).

Halt: Call halt again. Halting is simulated with an endless loop that does nothing.

A program to translate MM to Vein can be found here.

Here is an example MM program:

1 inc A 2
2 inc A 3
3 inc A 4

4 dec A 4 5

5 inc B 6
6 inc B 7

7 inc A 8
8 inc A 9
9 dec B 7 10

10 inc B 11
11 halt

And here a Vein translation of it:

i1 . + . a . i2
i2 . + . a . i3
i3 . + . a . i4
i4 . + n a1 i4e i5
i4e . c . i4
i5 . + . b . i6
i6 . + . b . i7
i7 . + . a . i8
i8 . + . a . i9
i9 . + . . . i9n . + . i10
i9n . + . + n b1 i9s i10
i9s . d . i7
i10 . + . b . i11
i11 . + . i11
n + +
e + + n
.
a . a . + . +
b . b . + . + . +
a1 n a2 n + + n
a2 n e n + n a1 a1 n + + n
c . . c c + +
b1 n b2 n + + n
b2 n b3 n + + n
b3 n e n + n b1 b1 n + + n
d . . . . d d + +

The Minsky Machine program halts with the values A=6 and B=1. The above translation will remain looping in i11 (in a manner of speaking), which simulates the halting. The counter's value fluctuates between 192 and 191; the higher of these is the real value of the counter, the reducement happens when i11 is called (to keep the loop going), after which the counter is increased again to what it is supposed to be. The values of A and B can be decoded from the counter's value (192 in this example) by dividing it by 2 and 3 as long as the value can be divided with no remainder. Decoding A's value: 192/2=96 -> 96/2=48 -> 48/2=24 -> 24/2=12 -> 12/2=6 -> 6/2=3. 3 divided by 2 is not clean, so for A, the procedure happened 6 times, meaning that A's value is 6. For B: 192/3=64. 64 cannot be divided by 3 without a remainder. So, for B the process happened only once, thus the register's value is 1.

Efficient Markov translation

This language can be translated into efficient Markov algorithm code. The efficiency here means that there is no moving of data around and that there is only one possible rule to match any given state of the memory. The translator creates output in Markov0 format.

A cycle of Vein - popping execution stack twice, inspecting command, executing command, manipulating counter and stack - can be translated into Markov0 code that accomplishes simulating all those tasks with only one Markov0 line/transformation executed per cycle.

Interpreter and translators

vein.py - Vein interpreter, written in Python. Displays the execution stack and the counter after every step. Displays of the execution stack (top-most left-most) only what fits on a 80-character line. If you wish for more output you will have to modify the program.

mmtovein.py - MM to Vein translator. Treats the first register encountered in the MM program as 'A' and the second as 'B'. If the amount of registers is not one or two, the program stops and displays an error.

veintomarkov0.py - Vein to Markov0 translator.

-- Keymaker, 15.12.2017