Stack
A stack is a data structure often used as an esoteric programming language's memory. The number of stacks may vary. Many languages have other methods of data storing as well.
Operations
A stack works by the principle of Last In, First Out (LIFO). What is pushed onto the stack first, will be popped off last. This leads to the two primary stack operations: PUSH, which adds something to the top of the stack, and POP, which removes something from the top and returns it. Oftentimes, popping an empty stack causes an error or returns zero.
Additional operations
In addition to PUSH and POP, there are a few other stack manipulation operations that stacks can use that are generally accomplished through scalar variables. Various additional operations are covered in extended pushdown automata, but are highlighted here.
The following table lists them, including the operation, its name, its traditional (or completely made up) laconic representation, its meaning, and an example in "Generic Stack Language" (GSL), a language used solely for example purposes.
| Op | Laconic | Name | Meaning | GSL |
|---|---|---|---|---|
PEEK
|
N/A
|
Peek | Return the top of the stack without removing it. | POP→a; PUSH a; RETURN a;
|
DROP
|
$ or _
|
Drop | Remove the top item of the stack and discard it | POP;
|
DUP
|
:
|
Duplicate | Duplicate the value on the top of the stack. | PEEK→a; PUSH a;
|
SWAP
|
\ or $
|
Swap | Swap the positions of the top two values on the stack. | POP→a; POP→b; PUSH a; PUSH b
|
OVER
|
^
|
Over | Put the second item on the stack on the top of the stack WITHOUT removing it from its original location. | SWAP; DUP; ROT;
|
ROT
|
[
|
Rotate | Rotate the top three items on the stack clockwise. | POP→a; POP→b; POP→c; PUSH a; PUSH c; PUSH b;
|
ROTCC
|
]
|
Rotate Counterclockwise (anticlockwise) | Rotate the top three items on the stack counterclockwise. | POP→a; POP→b; POP→c; PUSH b; PUSH a; PUSH c;
|
Postfix notation
- Main article: Postfix notation
A stack can be used to very easily evaluate expressions written in postfix notation. Simply go through the values on the list, and if it's a number, push it. If it's a unary operator, pop a value, call that operation on it, then push the new value. If it's a binary operator _, evaluate GSL POP→a; POP→b; PUSH b_a. If it has any higher arity, just pop the desired number of arguments from the stack and insert them into the expression in reverse order.
Stack effects
If a stack operation only rearranges the topmost items of a stack, possibly duplicating or dropping some items, then the operation is called a stack effect. A stack effect takes the topmost items as input and leaves its output on top as well. Effects have their own notation which lists a row of input variables and a row of output variables, with rightmost variables at the top of the stack. For example, the following stack effect takes two items and swaps them; it is the effect of SWAP:
swap ( x y -- y x )
Note that we can always add variables to the left of an input and output stack which are effectively unused. The input rank of a stack effect is the minimum number of variables that are used in its input, and symmetrically the output rank of a stack effect is the minimum number of variables used in its output. The input and output ranks of SWAP are 2. By convention, NOP has input and output rank 0.
There is a category StEff of all finite stack effects — not just the operations, but also the rows of variables — whose objects are natural numbers and identity arrows are NOP with extra unused variables. There are terminal objects with arrows given by repeated DROP and products given by concatenation on the stack; for example, given two arrows with effects:
f ( z -- x ) g ( z -- y )
There is a stack effect which combines them:
dup f swap g ( z -- x y )
Note that the product of two objects k × l is given by their sum as natural numbers; above, the product of 1 and 1 is 2. Also note that this category is not Cartesian closed, although it is symmetric monoidal since SWAP SWAP ≈ NOP at rank 2.
We may truncate StEff by imposing a maximum rank. We will denote truncations with maximum rank k as StEff(k).
Usage in esolangs
Here are some examples of esoteric programming languages using stacks:
- Befunge uses one stack, which is not the only way to store data (the other is to make the program modify its own source, stored in the memory of the interpreter during execution).
- False uses a stack for parameters and a return stack for function calls, like Forth.
- GolfScript uses one stack, and that's not its only way to store data. (The other way is to store inside assignable variables)
- TLWNN uses two stacks, and that's its only way to store data.
- Kipple uses many stacks, and that's its only way to store data.
- Stacking uses two stacks, as well as a memory pool.
- Super Stack! uses a single stack for data storage.
- Tarski uses a single stack
- Vitsy uses a two-dimensional program stack and a one-dimensional input stack.
- Volatile uses only one stack for data storage. Stack manipulation is its only way to store data.
- Whitespace uses a stack and a heap.
- <stack> uses only one stack for data storage, and once data is popped out from the stack, it is discarded and cannot be restored.
Computational class
It can be shown that two (unbounded) stacks are equivalent to an unbounded memory tape and therefore that a programming language with at least two stacks is Turing-complete, provided it has a suitable semantics for manipulating stack values. However, one stack is not sufficient for arbitrary computation.
First, we consider a single stack. When can every stack effect in StEff be expressed? We may immediately use definitions to prove a folklore lemma from the concatenative-languages community:
Lemma. Neither ROT nor ROT ROT are arrows of StEff(2).
Proof: Neither stack effect can be written with ranks less than 3 because they both require three variables:
rot ( x y z -- y z x ) rot rot ( x y z -- z x y )
However, with two stacks and ROT, every other stack effect can be implemented. We say that a two-stack system has top-of-stack movement when it has operations >R moving the top of first stack to top of second stack and R> moving the top of second stack to top of first stack.
Lemma. StEff with one stack is a full subcategory of StEff(2) with two stacks and top-of-stack movement.
Proof: We construct a zipper of the first stack onto the second stack. A zipper splits a given row with k variables into two pieces, with the second piece stored backwards. A single stack can access a row at the rightmost end; a zipper can access a row in the middle at a current pointer and can scroll through the row by moving the pointer. Concretely, let the input row have variables x0, x1, …, xk and load it as a zipper by repeating >R k times; this pushes the row backwards onto the return stack and puts the zipper pointer at the zeroth index. Then we have the following operations:
- Scroll the zipper forward/rightward one item:
R> - Scroll the zipper backward/leftward one item:
>R - Delete the item on the left-hand side of the pointer:
DROP - Swap the two items on the left-hand side of the pointer:
SWAP - Insert a duplicate of the left-hand side of the pointer at the pointer (moving the pointer to the right-hand side of the new fencepost):
DUP
This is sufficient to implement any stack effect! By cases,
- Suppose x0 is not in the output. Scroll forward and drop with
R> DROPand then renumber the output row so that we can iterate on the cases again. - Suppose x0 is the leftmost variable of the output row. Scroll forward once, duplicate, and scroll backward once; now a copy of x0 is in the correct position of the output stack. Pop the output row on the left, renumber output variables, and iterate.
- Suppose xl is the leftmost variable of the output row. Scroll forward l + 1 times, duplicate, scroll backward once, and then repeat l times the macro: swap and scroll,
SWAP >R. Finally, swap to put the copy of xl into the correct position. Iterate again. - Suppose the output row is empty. Then repeat k times the macro: scroll and drop,
R> DROPand we're done!
For example, ROT can be constructed by this recipe, given the stack effect ( x y z -- y z x ):
>r >r >r r> r> dup >r swap >r r> r> r> dup >r swap >r swap >r r> dup >r r> drop r> drop r> drop
Algebraically, >R R> ≈ NOP and DUP DROP ≈ NOP, allowing us to optimize this expression to:
>r dup >r swap r> r> dup >r swap >r swap r> drop r> drop
A more efficient algorithm can be obtained by adding two additional cases. Suppose x0 (or xl) is leftmost in the output row and will not be used again. Then the duplication is not required; instead, the input row is incrementally consumed, and renumbering of the output row will merely need to accommodate the 0'th (or l'th) item being removed. Since we consume the input row, we don't need to drop it at the end. The more efficient recipe gives:
>r >r >r r> r> swap >r r> r> swap
Which algebraically reduces to the standard way of implementing ROT in environments where both stacks have roughly the same performance characteristics and picking/rolling is expensive:
>r swap r> swap