A stack of strings
Most stack languages push numbers. Underload pushes pieces of program text. Its basic value is a string written in parentheses, and its commands rearrange those strings, join them and finally run them. There are no numbers, no variables and no named functions, yet the language is generally regarded as Turing complete. It is a good example of how code and data can be the same thing.
The commands
Underload has a small set of single-character commands:
| Command | Effect |
|---|---|
(text) |
Push the string text onto the stack |
: |
Duplicate the top item |
! |
Discard the top item |
~ |
Swap the top two items |
* |
Join the top two items into one, the lower one first |
a |
Wrap the top item in parentheses |
^ |
Remove the top item and run it as a program |
S |
Print the top item and remove it |
That is essentially all. Parentheses nest, so a string can contain other strings, and the contents are not interpreted until they are run.
First programs
The simplest program prints text:
(Hi)SIt pushes the string Hi and prints it. Now duplicate it first:
(Hi):SSThe stack holds Hi; : makes it Hi and Hi; the first S prints one copy and the second prints the other. The output is HiHi.
Joining works similarly:
(a)(b)*SAfter the two pushes, the stack has a and b, with b on top. The star glues them together as ab, and S prints ab.
Running code that was built as data
What sets Underload apart is the ^ command. Consider:
(Hi)(:SS)^First the stack holds the string Hi, then the string :SS above it. The caret removes :SS and runs it as program text on the remaining stack. That means duplicate, print, print, so the output is HiHi, the same as before but with the printing code built as a value. Code was pushed like a piece of data and executed later. The a command goes the other way, turning an item into a quoted string so that it can be run or passed around later.
This is the same idea as quotations in concatenative languages, taken to an extreme: the only values there are, are chunks of code.
Why this is enough
To loop, you need a way for code to run itself again. In Underload, a piece of code can duplicate itself and then run one copy, which leaves the other to run again. The structure resembles the self-application tricks of the lambda calculus, and the connection is not an accident, because both rely on treating functions as values. Underload programs for loops and conditionals therefore tend to look like small combinator expressions, with duplication and swap instructions playing the role that the combinators play in combinator calculus.
A full loop takes careful setup, so a beginner is better off studying the pieces above first.
Other minimal stack languages
Underload is one of a larger family of tiny stack languages. Some share its focus on strings or quotations. Some use numbers but limit themselves to a handful of operations. Others are essentially a stripped-down Forth. What they have in common is a very small instruction list, usually with duplicate and swap, and an evaluation rule simple enough to describe in a paragraph.
These languages belong with other minimalist languages, where the goal is to find the smallest set of ideas that still produces a universal system. Many also work like rewriting rules, since running a program is a matter of repeatedly replacing text with other text.
Why programs are hard to read
Underload programs are compact and nearly impossible to read at a glance, since a single character can change the structure of the stack, and nested parentheses hide where code begins and ends. The standard defense is to annotate a program with the stack contents after each step, or to write a helper that prints the stack. Both are examples of the broader code readability problem and tracing is usually the only practical way to understand what a given line does.
Why syntax and semantics are tiny here
The grammar of Underload is simply balanced parentheses plus the single-character commands. Its meaning is a short list of stack effects. The language is a reminder that the distinction between syntax and semantics can be reduced to two very small definitions, and still support arbitrary computation.
Getting started
To experiment, write down a stack on paper, apply commands one at a time, and cross out items as they are consumed. Try variations on the three examples above, such as swapping before joining, to see how the output changes. Once the basic effects feel natural, a program that prints a string several times is a nice first target.