StackStacks

:Not to be confused with Stackstack.
StackStacks is an esoteric programming language
designed and implemented by User:Oj742 in 2014, taking inspiration from Forth. It doesn't store any data (excluding two flags);
instead, all stacks contain stacks within themselves, so that a theoretically unlimited level of recursion can be reached.
It is likely that if you read this article in its entirety, you will become sick of the word stack.
== Overview ==
The stacks in StackStacks don't hold data, but instead hold other stacks. There are four variables in the language:
*The root stack, the first stack from which all other stacks are made within.
*The working stack, which is actually just a pointer to a stack. All instructions are local to the working stack.
*The FAIL flag, which is set whenever a failable instruction is executed; 0 if the instruction succeeded, and 1 if it fails.
*The TEST flag, which is used by conditional branching instructions.
Since there needs to be some data for i/o, stacks can be translated into data and vice versa. Translation is as follows:
*Stack -> Data : The size of the stack becomes the value of the data (an integer/character/boolean).
*Data -> Stack : Create a stack with x empty stacks inside of it, where x is the value of the data (integer/character/boolean).
At the beginning of execution, the working stack is set to the root stack; you can think of the stacks like directories in a file system. You can move the working stack up, to its parent, or down, to its head.
StackStacks uses functions, in a similar way to C (though without any parameters). Functions are declared by a name outside any code block, followed by a code block. Execution begins at the function called 'main'. Code blocks are also similar to those in C.
Comments are made like this:
 /* a comment */
While inline comments are made like this:
 //a comment
== Instructions ==
=== Data ===
Instruction	Stack 	Description
num 	-- num 	push a "number" onto the stack
"string" 	-- a{string.last .. string.first}	push a stack filled with "characters" onto the stack
'string' 	-- string.last .. string.first 	push each "character" in the string onto the stack, in reverse order (so that the first character becomes the top item)
push 	-- 0 	push an empty stack onto the stack
pop 	a -- 	remove the top stack from the stack
pop2 	a b -- 	
tuck 	a -- 0 a 	add an empty stack to the stack as the second item
nip 	a b -- a 	remove the second stack from the stack
clear 	a .. z -- 	remove all stacks from the stack
.size 	-- working.size 	pushes the size of the working stack onto the stack
.level 	-- working.level 	pushes the level of the working stack onto the stack (the root stack is at level 0)
.fail 	-- FAIL 	pushes the FAIL flag onto the stack
.test 	-- TEST 	pushes the TEST flag onto the stack
.leaf 	-- leaf.level 	pushes the level of the lowest, currently accessible stack onto the stack
=== Basic stack manipulation ===
Instruction	Stack 	Description
dup 	a -- a a.size 	
cdup 	a -- a a 	push a complete copy of the top stack onto the stack
dup2 	a b -- a b a.size b.size 	
swap 	a b -- b a 	
swap2 	a b c d -- c d a b 	
over 	a b -- a b a.size 	
-over 	a b -- b.size a b 	
cover 	a b -- a b a 	
-cover 	a b -- b a b 	
over2 	a b c d -- a b c d a.size b.size	
-over2 	a b c d -- c.size d.size a b c d	
rot 	a b c -- c a b 	
-rot 	a b c -- b c a 	
cycle 	a .. z -- z a .. 	pop the top stack and send it to the bottom of the stack
-cycle 	a .. z -- .. z a 	remove the bottom stack and push it to the stack
=== Interstack manipulation ===
Instruction	Stack 	Description
pack 	a{} b -- a{b} 	pop the top stack and push it onto the stack after it
-pack 	a b{} -- b{a} 	
unpack 	a{A} -- a{} A 	pop the top stack off the top stack and push it onto the stack
inc 	a{} -- a{0} 	push an empty stack to the top stack
dec 	a{A} -- a{} 	pop the top stack off the top stack
shftl 	a{} b{A} -- a{A} b{} 	pop the top stack off the top stack and push it to the second stack
shftr 	a{A} b{} -- a{} b{A} 	pop the top stack off the second stack and push it to the top stack
xchg 	a{A} b{B} -- a{B} b{A} 	exchange the top stacks of the top two stacks with each other
add 	a{A..} b{B..} -- a{B.. A..} 	
cat 	a{A..} b{B..} -- a{A.. B..} 	
take 	a b{A .. Z} -- b{Z .. [a.size]} c{[a.size-1] .. A}	
=== Comparison ===
Instruction	Stack 	Description 	
not 	a -- !a.size 	 	
eq 	a b -- (b.size==a.size) 	 	
ls 	a b -- (b.size<a.size) 	 	
grt 	a b -- (b.size>a.size) 	 	
neq 	a b -- (b.size!=a.size) 	 	
lseq 	a b -- (b.size<=a.size) 	 	
grteq 	a b -- (b.size>=a.size) 	 	
or 	a b -- (b.size 	a.size) 	
and 	a b -- (b.size&&a.size) 	 	
xor 	a b -- (b.size xor a.size)	 	
test 	a -- 	pop the top stack off the stack and set the TEST flag to bool(a.size)	
=== I/O ===
Instruction	Stack 	Description
outi 	a -- 	output the top stack's size as an integer
outc 	a -- 	output the top stack's size as a character
outa 	a .. z -- 	output each stack's size as a character
outs 	a -- 	output each stack's size in the top stack as a character
geta 	-- input.last .. input.first 	push all "characters" from input to the stack in reverse order (so that the first character ends up on the top of the stack)
gets 	-- a{input.last .. input.first}	
endl 	 	output a newline
=== Stack traversal ===
Instruction	Stack	Description
\up 	 	move the working stack up a level (into the parent stack)
\down 	 	move the working stack down a level (into the top stack)
\root 	 	move the working stack to the root stack
\leaf 	 	move the working stack to the lowest, currently accessible stack
\goto 	a -- 	move the working stack to the a.size level (if it cannot be moved to that level, push the popped stack back onto the stack)
=== Branch ===
Instruction	Description
?skip 	skip the next instruction if TEST == true
?do 	skip the next instruction if TEST == false
?loop 	goto the beginning of the current code block if TEST == true
?exit 	exit the current code block if TEST == true
@foo 	call the function foo
=== Debug ===
Instruction	Description
debug 	display the contents of the working stack (and all stacks within and below it)
debuga 	display the contents of the root stack (and all stacks within and below it)
debuge 	display the TEST and FAIL flags, and the level of the working stack
debugc 	display the call stack
== Examples ==
Note that these examples don't really take advantage of StackStacks 'stacks within stacks'.
=== Hello World ===
 main
 {
 'Hello World!\n' outa //'"Hello World!\n" outs' is also viable
 }
=== Cat ===
 main
 {
 geta outa //As with hello world, 'gets outs' would also work
 }
=== 99 bottles of beer ===
main
{
	1 99 { @bottles "of beer on the wall, " outs @bottles "of beer.\n" outs @takedown
	dup not not test swap ?skip not dup test swap ?loop }
}	
bottles
{
	dup
	1 eq test ?do { //one bottle
		"1 bottle " } ?skip {
	dup 0 eq test ?do { //zero bottles
		"No more bottles "
	} ?skip { //more than one bottle
		dup outi " bottles "
	} } outs //output
}
takedown
{
	dup 0 neq test ?skip {
	"Go to the store, buy some more, 99 bottles " outs
	} ?do {
	"Take one down, pass it around, " outs
	dec dup //take one down
	@bottles
	} "of beer on the wall.\n\n" outs
}
=== Quine ===
main
{
	"main"
	cdup outs endl 123 outc endl 9 outc 34 pack 0 34 pack cat outs endl 1
	"cdup outs endl 123 outc endl 9 outc 34 pack 0 34 pack cat outs endl 1"
	"swap { 9 outc -cycle dup test dec cycle cdup ?do { outs endl 9 outc 34 pack 0 34 pack cat outs } ?skip { 34 pack 0 34 pack cat outs endl 9 outc outs } endl ?loop 125 outc endl }"
	swap { 9 outc -cycle dup test dec cycle cdup ?do { outs endl 9 outc 34 pack 0 34 pack cat outs } ?skip { 34 pack 0 34 pack cat outs endl 9 outc outs } endl ?loop 125 outc endl }
}
=== Truth-machine ===
main
{
 geta dup '0' eq test ?do outc ?exit '1' eq test ?do { 1 outi ?loop }
}
== Turing-completeness ==
Turing-complete by reduction from brainfuck. If you start the program with
 main { 0 0 0
and end it with
 }
then the following reduction is true:
Brainfuck	StackStacks Equivalent
> 	swap -cycle pack \down cycle .size 3 eq test ?skip { 0 0 }
< 	-cycle \up .fail test ?skip unpack cycle ?skip swap
+ 	inc
- 	dec
[ 	dup test ?do {
] 	dup test ?loop }
. 	dup outc
, 	-cycle dup test ?skip { pop gets 1 cat } unpack swap cycle nip
== External resources ==
Oj742's (Crude) Interpreter
Category:Languages
Category:Stack-based
Category:Turing complete
Category:Implemented
Category:2014