Staq

Staq is an esoteric programming language by User:Madk in which operations are done using a stack. It is characterized by its fairly unique take on program flow, which allows intertwined loops and instruction overrides among other oddities. The language has robust access to two separate double-ended stacks, and can be shown to be Turing-complete when using just one.
==Commands==
 & place a new zero value on the top of the stack
 x throw out the top stack value
 X throw out the second stack value
 i increment the top stack value
 d decrement the top stack value
 q square the top stack value
 , bit shift the top stack value left
 . bit shift the top stack value right
 < rotate top stack value bits left
 ~ binary not operation on top stack value
 @ swap the top and second stack values
 $ move the top stack value to the bottom
 s move the bottom stack value to the top
 + add the top and second stack values and place the result in a new value on top of the stack
 - subtract the second from the top stack value
 * multiply the top and second stack values
 / divide the top by the second stack value
 % modulo the top by the second stack value
 > boolean is the top value greater than the second, new value is put on top of the stack
 = boolean is the top value equal to the second, new value is put on top of the stack
 [ jump to corresponding ] if the top stack value is 0 (or if it does not exist)
 ] jump back to corresponding [ if the top stack value is greater than 0
 ( jump to corresponding ) if the top stack value is greater then 0
 ) jump back to corresponding ( if the top stack value is 0 (or if it does not exist)
 ? execute the following command if the top stack value is greater than 0
 ! execute the following command if the top stack value is 0
 : output the topmost stack value to the console as a number
 ; output the topmost stack value to the console as a character
 ' put an inputted number on top of the stack
 ` put an inputted character on top of the stack
 n put the total number of values currently in the stack into a new value on top of the stack
 " print the following characters to the console, until another " is encountered
 | swap the active and passive stacks
 t copy the topmost value of the active stack and place it on top of the passive stack
You can also define functions by using the {} characters. For example,
 {u &+X}
would cause all following instances of the character "u" to be replaced with the code "&+X" when interpreting. Note: {} can be nested. To ignore a character's assigned function and instead perform the default, precede the character in question with a '_'
 _u
* Default commands can be overridden.
* Including a character itself inside its definition will result in recursion.
* If a character is assigned blank data (for example, {*}) it would return to its default purpose. (In this case, * would become the normal multiplication operation rather than whatever inanity you've had assigned to it.)
* Overriding { is generally a bad idea, though it is not illegal.
* Defining a character inside its own definition may or may not result in weirdness.
Do something like this to make a comment:
 &[ this is a comment ]x
==Examples==
===Hello, world!===
 "Hello, world!"
===Cat===
 `;
===99 Bottles===
 {\&iiiqi;x}&iiiqiqdd
 [i:" bottles of beer on the wall, ":" bottles of beer."\"Take one down, pass it around. "d:" bottles of beer on the wall."\d]
 "1 bottle of beer on the wall, 1 bottle of beer."\"Take it down, pass it around. No more bottles of beer on the wall."\
===Collatz sequence===
 {\&iiiqi;x}&&ii"Input a number to determine its Collatz sequence: "'
 [d[si$i:\%($/Xs?)[$@i@*iX@d@s!]xd]i:\!]
 "Total numbers in sequence: "si:
===Fibonacci sequence===
 {\&iiiqi;x}"Calculating the first 24 numbers of the Fibonacci sequence."\
 &i&i:\&iiqiqdd[d$:\+$Xss]
===Deadfish implementation with Hello, world! example===
 &iiqqq&{o:&iiiqi;@X}{T-!@_x}{i_iT}{D_d}{d?DT}{sqT}{ks}{xi}{co}{>id}
 iisiiiisiiiiiiiioiiiiiiiiiiiiiiiiiiiiiiiiiiiiioiiiiiiiooiiio
 dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddo
 dddddddddddddddddddddsddoddddddddoiiioddddddoddddddddo
===Temperature conversion===
 &("Convert C -> F (input 0) or F -> C (input 1)? "'
 (&iiqi&iiiq"How many degrees Centigrade? "'*XX/&iiqiiqdddd+"Result: ":" degrees Fahrenheit"xxxxx?)
 [&iiiq&iiqi"How many degrees Fahrenheit? "'*XX/&iiqiiqdddd-"Result: ":" degrees Centigrade"xxxxx!]
 &iiiqi;;xx)
==Computational class==
===Explanation===
Staq can be proven to be Turing-complete through a skewed form of reduction; a brainfuck program with finite length but unbounded values (which is enough for Turing completeness) can be reproduced in Staq by placing
 {>|n?xtx|}{<n?xtx}{+i}{-d}{,`}{.;}&|&
at the beginning of the program. This allows an arbitrary memory tape size when moving to the right, but won't move left of the origin.
For a bounded tape that wraps, the code
 &iiqqq[d&@]x{>s}{<$}{+i}{-d}{,`}{.;}
has a tape size of 256 which adjustable by altering the &iiqqq portion to generate a different number.
===Hello, world! brainfuck example===
 {>|n?xtx|}{<n?xtx}{+i}{-d}{,`}{.;}&|&
 >+++++++++[<++++++++>-]<.>+++++++[<++++>-]<+.+++++++..+++.>>>++++++++[<++++>-]<.>>>++++++++++[<+++++++++>-]<---.<<<<.+++.------.--------.>>+.
==External resources==
Download Staq interpreter
Category:Languages
Category:Stack-based
Category:Implemented
Category:Low-level
Category:Turing complete
Category:2011