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