Code patternsDataA stack
A stack
Keeps values in a pile: you add to the top and take from the top.
Watch it run
The form “Push a constant” works on 4 cells, named “base”, “item”, “top” and “free”. Press Play, drag the step slider forwards and back, or change constant with the slider and edit the stack, bottom first:
The figure needs JavaScript. The program below is the result for the example values.
The tape itself is the pile, and the pointer is the top. To push, step right and write. To drop, clear and step left.
Nothing has to be searched for, because the program always stands on the newest value. That makes every operation a short flat piece.
Whole programs can be written this way: every piece takes its inputs from the top and leaves its result there.
The code
This is the program the figure ran, written for these values. The pointer starts on “top” (cell 2). It is brainfuck as it stands: copy it, or open it in the playground, where you can change it:
>+++
What it needs
- The pointer rests on the top item. The cells to the right of the top are zero (two of them for "duplicate" and "multiply").
- Any cell size.
Common mistakes
- Leaving rubbish above the top. The next push adds to it.
- Dropping below the base of the pile: the pointer walks off the tape.
What it costs
A plain step is one command. An optimised step is one step of an interpreter that folds runs of the same command and flat loops. Choose the values and watch the two bars; What costs what explains how cost is counted:
The figure needs JavaScript. The table below has the measured steps.
Cost as a formula, and measured
| Form | Plain steps | Optimised steps |
|---|---|---|
| Push a constant | 1 + the constant | 1 |
| Drop | 2 + 2 × top | 2 |
| Duplicate the top | 5 + 15 × top | 3 |
| Add the two top items | 2 + 5 × top | 2 |
| Swap the two top items | 7 + 12 × top + 5 × the one below | 4 |
| A small program: (2 + 3) squared | 821 | 29 |
| Form | Values | Bits | Characters | Plain steps | Optimised steps |
|---|---|---|---|---|---|
| Push a constant | constant = 3; s = 5, 8 | 8 | 4 | 4 | 1 |
| Drop | s = 5, 8 | 8 | 4 | 18 | 2 |
| Duplicate the top | s = 5, 8 | 8 | 20 | 125 | 3 |
| Add the two top items | s = 5, 8 | 8 | 7 | 42 | 2 |
| Swap the two top items | s = 5, 8 | 8 | 24 | 128 | 4 |
| A small program: (2 + 3) squared | no values to choose | 8 | 79 | 821 | 29 |
Other forms
Drop
Clear the top, step left.
[-]<
Run this form step by step
The form “Drop” works on 3 cells, named “base”, “item” and “top”. Press Play, drag the step slider forwards and back, or edit the stack, bottom first:
The figure needs JavaScript. The program below is the result for the example values.
Duplicate the top
A copy, with the cell two above as scratch.
[->+>+<<]>>[-<<+>>]<
Run this form step by step
The form “Duplicate the top” works on 5 cells, named “base”, “item”, “top”, “free” and “scratch”. Press Play, drag the step slider forwards and back, or edit the stack, bottom first:
The figure needs JavaScript. The program below is the result for the example values.
Add the two top items
Two items become one.
[-<+>]<
Run this form step by step
The form “Add the two top items” works on 3 cells, named “base”, “item” and “top”. Press Play, drag the step slider forwards and back, or edit the stack, bottom first:
The figure needs JavaScript. The program below is the result for the example values.
Swap the two top items
Three moves, with the free cell above as scratch.
[->+<]<[->+<]>>[-<<+>>]<
Run this form step by step
The form “Swap the two top items” works on 4 cells, named “base”, “item”, “top” and “free”. Press Play, drag the step slider forwards and back, or edit the stack, bottom first:
The figure needs JavaScript. The program below is the result for the example values.
A small program: (2 + 3) squared
Push 2, push 3, add, duplicate, multiply. The pointer starts on cell 1, the first place of the pile.
++>+++[-<+>]<[->+>+<<]>>[-<<+>>]<[-<[->>+>+<<<]>>>[-<<<+>>>]<<]<[-]>>[-<<+>>]<<
Run this form step by step
The form “A small program: (2 + 3) squared” works on 5 cells; the named ones are “base”, “result”, “free” and “scratch”. Press Play, drag the step slider forwards and back:
The figure needs JavaScript. The program below is the result for the example values.
Where it is used
- Compilers from other languages to brainfuck usually lay their values out like this.
- The challenges ask for a small calculator built from these pieces.
Sources
- Source: Esolang wiki: Brainfuck algorithms: the pieces are the wiki's move, copy and swap, placed at the top of a pile; the arrangement is our own.
Every program on this page was run on many inputs, in plain and in optimised mode, and compared with JavaScript. The explanations are written for this page.