Urn

Urn is a minimal esolanguage designed by Keymaker, published in 2013.
==Description==
The language is based on an instruction/a mechanism that moves signals from in-source to out-source.
 ( in-source : code-for-1s : code-for-0s : out-source )
An instruction may have any number of instructions nested in it, and there may be any number of instructions in a row.
There are three possible in-sources:
* Input (denotated with "" / nothing)
* Static binary string (length of at least 1, using characters '0' and '1' only)
* Register (length of at least 1, using characters a-z only)
There are two possible out-sources:
* Output (denotated with "" / nothing)
* Register (just as in in-sources)
Registers are as if queues of binary data, initially empty. Executing an instruction empties its in-source. In case of input, input is collected until EOF is received (input that is not '0' or '1' or EOF is illegal).
An instruction is executed only as long as it receives a signal from its in-source. It's possible that there's no signal, in which case the instruction isn't executed. If there's a signal (0/1), the respective code-for-1s or code-for-0s is executed and the signal is killed (if the signal's respective code-for-xs is empty, the signal isn't killed and continues to the out-source).
Comment lines are marked with a ';' as the last character of the line (not counting spaces or a new-line).
==Examples==
Simple moving of data:
 ; move "101" to 'a' ;
 (101 : : : a)
 
 ; for 1-signals, execute "(11:::b)" which sends "11" to 'b' ;
 ; every time there is 1. for 0-signals, there is no code, ;
 ; so the 0-signal gets to out-source, which is 'b' here ;
 (a : (11:::b) : : b)
 
 ; now output the contents of 'a' and 'b' ;
 (a:::)
 (b:::)
 ; 'a' had no data, so it produced no output ;
 ; 'b' had "11011", which was output, and now 'b' is empty too ;
A cat is easy:
 (:::)
Simple infinite loop:
 first move "1" to 'a' ;;
 (1:::a)
 (a:
 ...code for 1s...;
 ;; move "1" to 'a' to make it have data again ;;
 (1:::a)
 ;; move "11" to 'memory' register (no reason) ;;
 (11:::memory)
 :
 
 ...code for 0s...;
 ;; nothing here ;;
 :
 )
See the Urn page for longer, more complex programs.
==Minsky Machine to Urn translation==
The language is Turing-complete, as can be shown with the following method of translating Minsky machine to it. Here is a Python program to do the work: http://yiap.nfshost.com/esoteric/urn/mmtourn.py
Below is an example program that first increases A register twice, then B twice, and then executes a simple loop of decreasing B and increasing A until B is 0, after which it halts. In the end A register will be 0 and B will be 4.
 1 inc A 2
 2 inc A 3
 3 inc B 4
 4 inc B 5
 5 dec B 6 7
 6 inc A 5
 7 halt
The resulting MM-to-Urn translation:
 (1:::loop)(1:::insta)(0:::rega)(0:::regaa)(loop:(1:::next)
 (insta:(1:::tmp)(rega:::tmp)(tmp:::rega)(1:::instaa)::)
 (instaa:(1:::tmp)(rega:::tmp)(tmp:::rega)(1:::instaaa)::)
 (instaaa:(1:::tmp)(regaa:::tmp)(tmp:::regaa)(1:::instaaaa)::)
 (instaaaa:(1:::tmp)(regaa:::tmp)(tmp:::regaa)(1:::instaaaaa)::)
 (instaaaaa:(regaa:(regaa:::tmp)(1:::instaaaaaa):(0:::tmp)(1:::instaaaaaaa):)(tmp:::regaa)::)
 (instaaaaaa:(1:::tmp)(rega:::tmp)(tmp:::rega)(1:::instaaaaa)::)
 (instaaaaaaa:(next:::end)::)
 (next:::loop)::)
This method is not the fastest to execute, but it's the simplest to understand and generate. First the program has code to set "1" to 'loop' register, "1" to 'insta' register to mark the very first instruction to be executed first. Then code to set every register, 'regX', to "0". The program runs until 'loop' register becomes empty. In the beginning of the main loop the 'next' register gets "1" moved into it and at the end of the loop the contents of 'next' are moved to 'loop' to ensure the 'loop' is executed again (it won't be if a halt-instruction moves the contents of 'next' to 'end', causing the program to end). Every MM instruction has a corresponding 'instX' instruction, which allows an easy way to determine which instruction is to be executed, and make the that instruction set the next instruction that is to be executed next.
The way the registers' values are interpreted is the following:
* Value 0 is "0".
* Value 1 is "10".
* Value 2 is "110".
And so forth, without any limit.
INC instructions are essentially
 (1:::tmp)(regX:::tmp)(tmp:::regX)
 (1:::instX)
which is code for moving "1" to 'tmp' ('tmp' always empty at that point), then moving the register's contents to 'tmp', then moving all of 'tmp' back to the register. This adds "1" to the beginning of the register's value. Then the instruction that is executed next is chosen by moving "1" to it ('instX').
DEC instructions are essentially
 (regX:
 (regX:::tmp)(1:::instX)
 :
 (0:::tmp)(1:::instY)
 :)
 (tmp:::regX)
which is a loop executed in 'regX' that first, by the nature of Urn loops, takes one signal from 'regX'. This signal is inspected.
* If it's 1, it means the value of the register was at least 1 (and therefore it can be -- and actually already was -- reduced by one). The remaining data in 'regX' is all moved to 'tmp', and the instruction that is executed after successful decreasing gets "1" moved into it ('instX').
* If it's 0, it means the value of the register was 0. Move "0" to 'tmp', set the instruction that is next in this case ('instY').
Whatever the value of 'regX' was, 'regX' is now empty, and its correct next state (whether it was decreased or left to zero) is in 'tmp', which is moved to 'regX'.
HALT is
 (next:::end)
which moves the contents of 'next' to 'end'. The main loop ends once 'loop' does not receive a new "1" from 'next'.
Notice that the end of 'loop' loop may not be reached after every instruction; for instance, instruction 1 may set instruction 2 to be executed next, and as the instruction lines are sequentially (or should be, to ensure the Python translator program works properly), execution may move from insta to instaa without first reaching the end of 'loop'. This behaviour causes no problems, on the contrary it adds a little speed.
==External resources==
* Urn page (the specs, .urn programs, an interpreter in Python)
Category: Turing complete
Category: Turing tarpits
Category: Low-level 
Category: Languages
Category: Implemented 
Category: 2013