Stacking

Stacking is a stack based esoteric programming language invented in 2009 by Sondre N. Andersen.

Introduction

Stacking is a stack-based language with two stacks, and a register, which can store one value. All the data is stored as unlimited signed integers, however only 0-255 can be printed as ASCII characters. The two stacks are called stack 0, and stack 1, and you can only work on one at the time.

Initially, stack 0 is selected, and both stacks, and the register, are set to zero. Reading from an empty stack returns zero.

All of the operators are one-character, except labels and jumps.

Language Overview

Stack selecting is done with the s operator. It swaps the selected stack, so that if stack 0 is selected, then stack 1 becomes selected, and vice versa. To make it easier to select the right stack, we have the o operator. It selects stack 0. This is optional in the beginning of a program, but good to have there.

The register is mainly meant for transporting values from one stack to the other. There are only three register-operators; p, f and w. Push, p, takes the register, and pushes it onto the selected stack. Fetch, f, pops the selected stack, and saves the value in the register. This way you can move a value from stack 0 to stack 1 with the code psf. The w operator sets the register to zero if stack 0 is selected, and one if stack 1 is selected.

To push values on the stack, you use the numbers 0 to 9. You cannot set numbers higher than 9 directly, so to do that, you need to use arithmetic. The ? operator, pushes a random number from 0 to 999. To seed the generator, you use the ¿ (ASCII-191) command, which pops a value from the selected stack and use it as seed. You can also push ASCII values directly onto the stack. To do this, you write a string inside quotation marks (" "). This means that the code “HI” pushes 72 and 73 on the stack, leaving it “73,72”. If you pop and write it like this, you get the output “IH”, so you will need to write in the string backwards to get it right.

Arithmetic is done to the first, or the two first elements on the selected stack. There are the +, - and * operators witch adds, subtracts and multiplies the two first elements on the selected stack, and replaces them with the answer. For instance if the stack contains “3,5,4”, and you call the - operator, the stack turns into “-2,4”. Then there are the / and % operators. These are integer division, and modulo. Integer division (/) is ordinary division, but you round down afterwards. That means 7/2=3, and 6/4=1. Modulo (%) calculates the remainder of the integer division. This means since 7/2=3 and 3*2=6, 7%2=7-6=1.

The =, < and > operators, compare the two first elements, and replace them with one, or zero. If the stack contains “3,2,5” then > sets it to “1,5” since (3>2)=true, or 1. This is the same for < and =. Note that (2>3)=false, or 0.

The logical operators are &, | and !. And (&) takes the top two values, and replaces them with one, if both values is non-zero, and zero, if one or both of the values are zero. Or (|) is one, if either of the values is non-zero, and zero, if both are zero. The not (!) operator uses only the first value. It replaces it with one, if the value is zero, and zero, if the value is non-zero.

Then there are the special stack-operators. These are \, :, @. The swap (\) operator swaps the tow two elements. That means the stack “5,3,6” becomes “3,5,6”. The duplicate (:) operator duplicates the top element. Turning “5,3,6” into “5,5,3,6”. The @ operator simply pop a value, and does nothing with it, turning “5,3,6” into “3,6”.

I/O is done with tree operators; #, . and ,. # pop the first element of the selected stack, and output it as a number. . pop the first element, and output is as an ASCII-character. If the value is negative, or bigger than 255, then a whitespace character is written. , push a character from the input buffer onto the stack.

There are six program flow operators. First there are labels and jumps. Labels are defined inside parentheses () and can contain small letters a-z, numbers and underscore “_”, like (jump_1). It is up to the compilator/intepreter to define a max-length, but in “real” Stacking, there is no limit. If another character is included, or you forget the ending “)”, you get a syntax error. You also get an error if there are two or more equal labels. Jumping is done by putting the label, to witch you want to jump, inside curly brackets {} like {jump_1}. You get a syntax error if the label to which you are jumping does not exist, and if the brackets contain a non-valid label name.

There are two conditional-jump operators, ô (ASCII-244) and î (ASCII-238). They both jump over the next command, which could be a jump {} command, but does NOT pop a value from the stack. The ô command jumps if this value is zero, and î jumps if it is non-zero. Then there is the sleep command; ~ (ASCII-126). It pops a value from the selected stack, and halts the execution that amount of milliseconds. The last program flow operator is the §. It simply ends the program. Even if you have an infinite program, you need to have this at the end.

The last command is the comment, ;, operator. This comments the rest of the line. All other characters are also treated as comments.

Operator List

Stacking has the following commands:

Command	Description
s	Toggles stack selection
o	Selects stack 0
p	Push register
f	Fetch (pop) register
w	Set register to index of selected stack
0-9	Push corresponding number 0-9
""	Push characters inside
?	Push random number 0-999
¿	Pop value, and use as seed
+	Add top two values
-	Subtract top two values
/	Divide top two values
*	Multiply top two values
%	Modulo top two values
=,<,>	Compare top two values
&	Logical AND top two values
|	Logical OR top two values
!	Logical NOT top values
\	Swap top two values
:	Duplicate top value
@	Pop value, but do nothing
#	Pop value, and output as number
.	Pop value, and output as ASCII
,	Input ASCII
î	Skip if top value is non-zero
ô	Skip if zero
()	Define label
{}	Goto label
~	Pop value, and wait
§	End program

Examples

Hello, world!

0"!dlroW ,olleH"(lp).ô{lp}@55+.§

Unix cat

(lp),.{lp}§

Fibonacci

o95*s10(lp):f\p+:#s:.s{lp}§

99 Bottles of beer

o99*9+8+(main)s0055+55+".llaw eht no reeb fo selttob "055+
".dnuora ti ssap dna ,nwod eno ekaT"55+".reeb fo selttob "055+",
llaw eht no reeb fo selttob "(lp2)s:#s(lp1).ô{lp1}@ô{lp2}sô(main)§

Turing-Completeness Proof

Brainf**k is, as we all know, turing-complete. And so is Stacking, because each BF command can be mapped to a Stacking-code. We use the two stacks, insted of a single tape, and moves values forth and back. The pointer always points at the top of stack 0.

(y and x should be unike labels for every loop-pair).

BF	Stacking
<	osfsp
>	ofsps
+	o1+
-	o1-
.	o:.
,	o@,
[	o(x)î{y}
]	o(y)ô{x}

Thus Stacking is turing-complete :-)