Hollow

Hollow is an esolanguage based on low-level string-manipulation, designed by Keymaker in 2011, but completed and published in 2012. The language is Turing-complete. The memory model is an unbound stack of strings. Below is a nine-line program to showcase the language (the program's execution detailed in a section down the page):
 {}>
 {.1.0}|>
 {*0}=>|>>
 {.10**.1}<
 {1}=>|>>
 {.10*.1}<<<
 {0}=>|>>
 {.1.1}<<<<<
 {.1.9}:?
This program turns the given binary number input (terminated by EOF) into a string of '*' characters which it then outputs along with a new-line. The conversion is done using the Markov algorithm. For example, input 1001001 (dec 73) would yield *************************************************************************.
==Line(s)==
A Hollow program consist of lines (zero or more). A line has three parts.
* Data part.
* Instruction.
* Success/failure.
Data part is a string of data inside {} brackets. It forms, often using special characters (namely ".1"), a string that the instruction part deals with. The instruction is one character (or none). Success/failure determines where the program flow / line pointer continues next. Success happens only if all the operations of the line went right, otherwise the line is a failure. A line might look like this:
 {a.1}\>|>>>
In which the data part would be "a.1", instruction "\", success ">", and failure ">>>".
==Instructions==
The instructions are:
* (nothing) Pushes the data part into stack. Example line: "{abc}>>"
* . Discards the data part. Example line: "{.1.1}.>|<<"
* + Pushes the data part into stack twice. Example line: "{data}+>"
* \ Searches the stack from bottom to top, looking for a string that contains the data part. If such string is found, it will be removed from its place and moved to the top of the stack. Example line: "{DAT001}\>"
* = Divides the top-most stack item into two parts by using the data part. Example line: "{;}=>|<<<<"
* : Outputs the data part. Example line: "{hello, world.6.9}:?"
The data part itself may already affect the line's success/failure. (See below.) Instructions \ and =, if trying to access empty stack, use data that is the empty string, or otherwise cannot complete their task, cause the line to be a failure.
==Data part==
The data part inside {} may not have characters '{', '}', new-line, or '.' as such. '.' represents a special character, and to have ordinary dot, one must use special character ".6". The special characters, when creating the data string, replace themselves with the data they return. They are:
* .0 Inputs a character. If there is EOF / no more input, it returns the empty string and marks that line's condition as failure. In case there is input, it returns that character.
* .1 Pops the stack and returns the data. If stack is empty, returns the empty string and causes the line to be failure.
* .6 Returns ".".
* .7 Returns "{".
* .8 Returns "}".
* .9 Returns a new-line.
==Line pointer==
The control flow is determined by the success/failure part of the line. They are strings of '<' or '>' (zero or more instances), or a single '?'. The arrows move the line pointer as many times as there are arrows. << would move two lines up, >>> three down. ? terminates the program. '|' separates the success/failure parts, and is not required. A success/failure part that does not have any characters is not undefined, it simply means that in either case there is no movement for the line pointer. Line pointer may also try to access a line that does not exist, in which case the interpreter must get stuck in an infinite loop. A program is always ended with a '?' -- in case it is a finite program.
==Deciphering the example program==
 1. {}>
 2. {.1.0}|>
 3. {*0}=>|>>
 4. {.10**.1}<
 5. {1}=>|>>
 6. {.10*.1}<<<
 7. {0}=>|>>
 8. {.1.1}<<<<<
 9. {.1.9}:?
Here is the example program with line numbers added (thus it is no longer valid Hollow, do not attempt to run it) to make explaining the program easier. Execution begins on line 1, where "" (empty string) is pushed to stack, which is always success, so move to line 2. There input is read, character by character, and placed at the end of the string that is on top of the stack (first taking that string with ".1", then reading input with ".0", the resulting data placed into stack). In case of failure, which here means the input is EOF, move to line 3. Lines 3 & 4, 5 & 6, and 7 & 8 form the code that checks for the three substituting rules of the Markov algorithm. Line 3 divides the top-most (and only) string in stack into two parts, using "*0". In case of failure, which here is because of "*0" not appearing in the string, the code for the next rule is tried (line 5). In case of success, move to line 4, where a new string is assembled of the two parts executing line 4 successfully created. The data of the rule's substitution part ("0**") is placed between these pieces. Now the (only) string in stack has been altered. Move back to line 3 and try the same substitution again. The two rules work similarly. If the dividing is failure on all three lines, it means the conversion is completed. Execution moves to line 9 which creates data of the string in stack, adds a new-line after it, and prints it. "?" quits the program successfully.
Here are the rules the Markov algorithm uses:
 1. *0 -> 0**
 2. 1 -> 0*
 3. 0 -> (nothing/empty string)
==Some esolang interpreters in Hollow==
* Underload interpreter
* Cyclic Tag interpreter
* Etre interpreter
* coming some day, Hollow-in-Hollow
==External resources==
* Hollow page (specs, programs, interpreter)
Category: Turing complete
Category: Languages
Category: Stack-based
Category: Implemented 
Category: 2012