Argh!

Argh! and its successor Aargh!, both invented by Sascha Wilde, are Befunge-like esoteric programming languages, laid out in two dimensions. Each is limited to 80 columns wide, but Aargh! has an unlimited number of rows, whereas Argh! is limited to 40. The idea was to make sure Aargh! was Turing-complete.
Each character of the grid is either a one-cell wide command or value. The language also supports a stack of unbounded size. It has 27 documented commands.
==Instructions==
Argh! has the following commands:
Letter	Befunge equivalent	Description
A 	 	add value of the cell above the current cell to the value on top of the stack (see "R")
a 	 	add value of the cell below the current cell to the value on top of the stack
D 	 	delete top value off stack
d 	: 	duplicate top value on stack
E 	 	insert value of system EOF in cell above
e 	 	insert value of system EOF in cell below
F 	 	fetch (pop) value from top of stack and store to cell above
f 	 	fetch (pop) value from top of stack and store to cell below
G 	 	get one byte from stdin and store in cell above
g 	 	get one byte from stdin and store in cell below
H 	 	jump (move instruction pointer) left to the next cell whose value matches the value on top of the stack, and set execution direction to "left"
h 	< 	set execution direction to "left"
J 	 	jump down to the next cell whose value matches the value on top of the stack, and set execution direction to "down"
j 	v 	set execution direction to "down"
K 	 	jump up to the next cell whose value matches the value on top of the stack, and set execution direction to "up"
k 	^ 	set execution direction to "up"
L 	 	jump right to the next cell whose value matches the value on top of the stack, and set execution direction to "right"
l 	> 	set execution direction to "right"
P 	 	send value above the current cell to stdout (does not remove the value)
p 	 	send value below the current cell to stdout
q 	@ 	quit: end program execution
R 	 	reduce the value on top of the stack by the value of the cell above (see "A")
r 	 	reduce the value on top of the stack by the value of the cell below
S 	 	store (push) value of the cell above the current cell to stack (does not remove the value)
s 	 	store (push) value of the cell below the current cell to stack
X 	 	if the value on top of the stack is negative, turn the execution direction 90 degrees to the left
x 	 	if the value on top of the stack is positive, turn the execution direction 90 degrees to the right
# 	 	behaves just like 'j', but only if its position in the code/data array is 0,0 (the left/top corner) and only if there is a '!' in the cell on its right side.
A program that tries to leave the grid or execute a value that isn't a command causes the language's standard error message, "Argh!" or "Aargh!" as appropriate, to be emitted, followed by the program terminating.
==Examples==
The following program prints out "hello, world":
 j world
 lppppppPPPPPPsrfj
 hello, * j
 qPh
Execution begins with the j in the top left corner, which indicates the starting direction of execution is down. The next command is an l, which means to now process commands to the right. Each p indicates that the value below it should be printed; each P indicates that the value above it should be printed.
The next part is more interesting: the goal is to output a linefeed (ASCII value 10, often written as "\n"). This special character has to be generated: the s stores the character below (<"*", ASCII 42) on the stack, the r reduces the value on the stack by the value of the character below (42 minus " ", ASCII 32, is 10), the f fetches the top value from the stack and inserts it below, so the cell below the f will hold the value 10, which is ASCII linefeed. The following j lead us down (we already know this) and the h sets the execution direction to go left and the P finally prints the linefeed. The q (for quit) command ends the program.
This program is a truth-machine:
 lglj
 j
 jShh
 lrllxpq
 0jph0
 j1k
 llk
==Computational class==
Suppose that the instruction pointer moves downwards into an f. If the top of the stack starts with a number of f followed by a k, then each fs in turn will be written to the grid below the previous f (below the original f for the first one), then the instruction pointer will start moving upwards and will write the content of the stack below each of the fs on the way back up. For example, after encountering an f moving downwards with the top of the stack starting with fffkpqrs, those eight stack elements will be popped and place s, r, q, p below the original f. The same trick can be accomplished moving upwards with F and j.
Now, suppose that there is a column of j above an f. If the top of the stack starts with fkk?F? (where a ? could be any value), then the fkk? will place a ? and k below the f, the instruction pointer will bounce off a j, the original f will run again and place an F below itself, which will then replace the original F with a ? – but then the instruction pointer will bounce off the k and encounter an F, meaning that a crafted sequence on the top of the stack can replace the f and the elements above it with anything. In particular, it can write an f further up the column of j. Alternatively, by adding more f at the start of the process, it is possible to move the f down the column of j, adding j in between.
This basic technique makes it possible to represent a counter using a column of j followed by f (in each case, jumping back upwards with K when the increment/decrement is complete – the element below K on the stack specifies what symbol to look for), controlling the counter using the state of the stack upon moving down the column of j:
* Increment: ffkkF??fjK
* Decrement: fkk?F?Ff?K
A zero test can be done by moving sideways across the position of the column that represents 0, with a K on top of the stack. In the below example, the test starts by entering along the row of l, and most of the characters are in the grid before the test is performed, but the K is added during the test:
 zero nonzero
 
 j j
 j j
 lfll llljlll
 K f
 K
If the counter is discovered to be zero, the K and its jump label will be left on the stack, but can trivially be popped using, e.g., F while moving horizontally.
In Aargh!, which has unbounded vertical height, this makes it possible to produce counters that can store arbitrary nonnegative integers and can be incremented, decremented and zero-tested, which is enough power to implement various sorts of counter machine. The limited width of the grid is an issue for some constructions (as it means a limited number of counters are supported, and there is not enough room to create fully arbitrary control flow); however, it is sufficient to implement The Waterfall Model, which has very simple control flow (with the idea being to zero-test all the counters in sequence, pushing a sequence that represents a zeroing trigger onto the stack when a counter is found to be zero or a steady decrement if none of them are). Commands like L can be used for wire crossings, and only three columns are needed to push a constant string onto the stack, e.g. pqrs can be pushed like this (starting by moving upwards from the bottom k):
 ks
 kSh
 rk
 lSk
 kq
 kSh
 pk
 lSk
 k
The only remaining problem is to steer the IP to the appropriate counter to increment/decrement/zero-test, which can be done using x and X to read the strings that were pushed onto the stack.
As such, Aargh! is Turing-complete. (Argh! is a bounded-storage machine unless the grid cells support arbitrarily large integers.)
==External resources==
* Argh! website (in German)
* Argh! and Aargh! language specification
* Argh! Mercurial Repository
* Argh! project on Freshmeat.net
* Interpreter in wxHaskell
* Argh! in the Esoteric File Archive
Category:Languages
Category:Two-dimensional languages
Category:2004
Category:Turing complete
Category:Implemented
Category:Cell-based
Category:Stack-based
Category:Self-modifying