Super Stack!

Super Stack! is a stack-based esoteric programming language by User:Orange.
== How programs are run ==
Programs consist of keywords separated by spaces, tabs, and/or newlines.
There is only one stack the program can manipulate.
== Instructions ==
Instruction	Description
123 	Push a number onto the stack.
add 	Pop two numbers, add them, and push the result.
sub 	Pop two numbers, subtract the first from the second, and push the result.
mul 	Pop two numbers, multiply them, and push the result.
div 	Pop two numbers, divide the first from the second, and push the result.
mod 	Pop two numbers, perform modulus on the first and second, and push the result.
random 	Pop the top number, and push a random number from 0 to the number popped minus 1. So if you have the number 5 and you use random, you will get 0, 1, 2, 3, or 4.
and 	Pop two numbers, and them, and push the result.
or 	Pop two numbers, or them, and push the result.
xor 	Pop two numbers, xor them, and push the result.
nand 	Pop two numbers, nand them, and push the result.
not 	Pop the top number, not it, and push the result.
Note:
*For all logic commands, 0 is false, and anything else is true (negative or positive).
*When pushing results 1 is true and 0 is false.	Note:
*For all logic commands, 0 is false, and anything else is true (negative or positive).
*When pushing results 1 is true and 0 is false.
output 	Pop the top number and output it as a number followed by a space.
input 	Get a single number from input and push it.
outputascii	Pop the top number and output as an ascii character.
inputascii 	Get a string of characters from input and push each ascii character on the stack backwards, so the first letter in the string is on the top, and the last letter of the string is on the bottom.
pop 	Pop the top number and discard it.
swap 	Swap the top two numbers.
cycle 	Put the top number on the bottom of the stack.
rcycle 	Put the bottom number on the top of the stack.
dup 	Duplicate the top number.
rev 	Reverse the entire stack.
if 	While loop. If the top number is true, loop. Does not pop top number.
fi 	End loop.
quit 	End program.
debug 	Output entire stack. (Does not pop anything.)
== Example Programs ==
===Hello, World!===
 0 33 100 108 114 111 87 32 44 111 108 108 101 72
 if outputascii fi
First, push ASCII codes onto the stack for "Hello, World!"
Then while there are nonzero numbers on the stack output them.
===Cat program===
 1
 if
 0
 inputascii
 if outputascii fi `output-stack
 pop
 10 outputascii
 fi
Explanation:
*1 is pushed and then a while loop is entered. The 1 makes the loop run forever.
*0 is pushed so we can tell when input ends.
*Input is pushed onto the stack.
*While the top number is not 0, pop and output number.
*Pop the 0.
*Push 10 and output it(new line).
*The stack now only has the number 1 on it, so the program will loop again.
As you can see keywords can be separated by spaces or newlines.
===Fibonacci sequence===
 0 1
 if
 dup output
 dup cycle add
 fi
*Push 0 and 1 on the stack to start the fib.
*If for an infinite loop.
*Output the top of stack.
*Dup top number then put it on the back of the stack.
*Add the top two.
*Loop. Top of the stack will always be more than 0.
===Guess the pass code===
 0
 58 101 100 111 67 32
 115 115 97 80 32
 114 101 116 110 69
 if outputascii fi pop
 
 inputascii
 
 `compare each letter
 109 sub
 not if pop
 97 sub
 not if pop
 114 sub
 not if pop
 115 sub
 not if pop
 104 sub
 not if pop
 	0
 	100 101 116 110 97 114 71 32
 	115 115 101 99 99 65
 	if outputascii fi pop
 	quit
 fi fi fi fi fi
 
 `wrong
 0
 71 78 79 82 87
 if outputascii fi pop
A little game. Guess what the password is.
===FizzBuzz===
The stupid fizzbuzz problem.
 -100
 if
 dup 101 add
 
 dup output
 
 dup 3 mod
 not if
 pop
 0 122 122 105 102 `fizz
 if outputascii fi pop
 0
 fi pop
 
 dup 5 mod
 not if
 pop
 0 122 122 117 98 `buzz
 if outputascii fi pop
 0
 fi pop
 
 10 outputascii `newline
 
 pop
 1 add
 fi
 
 inputascii
===Simple chat bot===
 1 if pop
 0 58 116 117 112 110 105
 if outputascii fi pop
 
 inputascii 0
 
 5 random
 if pop
 cycle if cycle fi
 0 fi pop
 
 0 58 116 117 112 116 117 111
 if outputascii fi pop
 
 cycle if dup outputascii cycle fi
 10 outputascii
 1 fi
First the program gets a string inputted onto the stack. Strings are represented by a 0 and then a series of characters that lead up to the next string.
After the input, we randomly cycle from string to string.
Then, we output the string and loop the program.
==Implementations==
* v2 of the Python implementation
* Super Stack!/superstack.ml, an implementation in Ocaml that almost matches the specs
* Super Stack! compiler for the Digirule, as part of the dgtools package. Try it online here.
==Computational Class==
Super Stack! is Turing-complete. Its only data structure is actually more "powerful" than a simple stack, due to commands instructions like cycle and rcycle. It is easy to transpose any given brainfuck into an equivalent Super Stack! program, for instance using the following algorithm:
* Begin the program with the code -1 0.
* Replace every brainfuck instruction by the matching Super Stack! instruction sequence in the conversion table below:
brainfuck	Super Stack!
> 	cycle dup 1 add not if 0 swap not fi pop
< 	rcycle dup 1 add not if not swap cycle dup fi pop
+ 	254 sub if 255 add fi
- 	dup not if swap 255 add swap not fi pop 1 sub
. 	dup outputascii
, 	pop inputascii
[ 	if
] 	fi
Note that this conversion is far from being efficient; its only purpose is to prove that Super Stack! is brainfuck-equivalent. It emulates an infinite tape, navigating with cycle and rcycle, pushing an extra 0 every time -1 is on top. It is assumed that the tape is right- and left-infinite and that brainfuck cells contain numbers between 0 and 255, with wrapping for + and -. It is also assumed that inputascii reads one character only, which may be slightly inconsistent with the specifications above.
Category:LanguagesCategory:2009Category:Turing completeCategory:ImplementedCategory:Stack-basedCategory:High-level