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.
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.
There are also other models with additional instructions which are also Turing-complete, covered in extended pushdown automata.