Why reversal is almost free
The program stack returns items in the opposite order from the one in which they were pushed. Push a, b, c and the pops come back c, b, a. So reversing a sequence needs no swapping, indexing or temporary array: push everything, then pop everything.
Compared with most languages, where reversing a string means writing a loop that swaps ends or builds a new string backward, this is a case where the data structure does nearly all the work. The program only has to supply two Befunge loops, one to read and push, and one to pop and print.
The two stopping problems
Each loop needs a way to know when to stop.
- Reading. The program stops when it sees a newline. A newline is character code 10, so a loop can subtract 10 from each character and stop on zero.
- Printing. The program needs to know when the stack has run out of characters. Popping an empty stack in Befunge-93 gives zero rather than an error, which suggests a trick: put a zero at the bottom first, and stop when zero comes off. A zero is a safe choice because it is not a character you would normally type.
Using zero as the bottom marker is only reliable if the input never contains a zero character. For ordinary text that is fine.
The program
0v <
>~:55+-| v,<
>$ >:|
@Typing stack and pressing Enter prints kcats.
Marker. The first row begins with 0, which pushes the marker. The v turns the pointer down to the second row.
Read loop. On the second row the right arrow sends the pointer east. The tilde reads one character and pushes its code. Dup copies it, 55+ makes 10, and - subtracts, so the stack holds the character and, above it, the character minus 10. The vertical-if pops that difference. If it is nonzero the character is not a newline and the pointer goes up to the left arrow at the end of the first row, which sends it west back to the v, and so back down to the read loop. The character stays on the stack. If it is zero, the pointer drops to the third row with the newline on top.
Hand-off. The right arrow in the third row sends the pointer east. $ discards the newline, leaving the marker and then the characters, with the last one typed on top.
Print loop. The pointer reaches a second small loop. It copies the top value and the vertical-if pops the copy. If the value is nonzero the pointer goes up to the left arrow in row 1 and moves west. There it meets the comma, which pops and prints the character, and then the v, which returns it to the test. If the value is zero, it is the marker, and the pointer drops to @.
The stack for the input stack
After each character is read, the stack looks like this, bottom to top:
| Read | Stack |
|---|---|
| s | 0, s |
| t | 0, s, t |
| a | 0, s, t, a |
| c | 0, s, t, a, c |
| k | 0, s, t, a, c, k |
After the newline is discarded, the print loop pops k, c, a, t, s, and finally meets the 0 marker and stops. The output is kcats.
Things that can go wrong
- No newline. If the input ends without a newline, the read loop never sees a zero difference. Many interpreters return a special value such as −1 at end of input, and the loop would keep pushing it forever. How end of input is reported varies between interpreters, which is one of the known difficulties of interpreter input output. Always end the typed line with Enter.
- A zero in the input. A zero character would be mistaken for the marker, so the output would stop early.
- Very long lines. The stack has no fixed small limit in most interpreters, but some may impose one, and a long line is the first thing to test it.
- Spaces. Spaces are ordinary characters with code 32, so they are reversed along with everything else.
When a loop fails to stop, the first thing to check is the stack depth: a stack underflow or an unbalanced loop body often shows up as wrong characters or an endless run.
Using string mode instead of input
You do not have to read input. Quote mode lets you write a fixed string directly in the program, and it pushes the characters left to right. That means the last character of the literal ends up on top, so printing by popping gives the string reversed with no input loop at all. Writing "stack" and then five comma instructions prints kcats. That is the shortest possible reversal program, and it is a good illustration of what string mode does to the stack.
Related ideas
The same push-then-pop pattern shows up whenever order must be flipped. Base conversion produces digits least significant first and needs exactly this reversal. Palindromic programs are a different puzzle that plays with reading order in the code itself rather than in the data. And stack machines in general use this behavior on purpose, since a postfix expression is evaluated by pushing operands and popping them in reverse as operators arrive.