Pathological Stack Hell: Underload

Our pathological language this week is [Underload][underload]. Underload is, in some ways, similar to Muriel, only it's a much more sensible language. In fact, there are actually serious
practical languages called *concatenative languages* based on the same idea as Underload: [Joy][joy] and [Factor][factor] are two examples.

[underload]: http://esoteric.voxelperfect.net/wiki/Underload
[muriel]: http://scienceblogs.com/goodmath/2006/11/friday_pathological_programmin…
[joy]: http://www.latrobe.edu.au/philosophy/phimvt/joy.html
[factor]: http://www.factorcode.org/

Underload is a remarkably simple language. It's stack based, like Forth, so all of the data is stored on the stack. Its only means of control is constructing a program on the stack and executing it; and the only data that it can manipulate is lists of characters.

The commands in Underload are:

* `~` - swap the top two elements on the stack.
* `:` - duplicate the top element on the stack.
* `!` - discard the top element on the stack.
* `*` - concatenate the two elements on top of the stack into a single list.
* `a` - take the element on top of the stack, and wrap it in "()"s.
* `(...)` - push the contents of the parens on the stack as a single stack element.
* `S` - print the element on top of the stack.
* `^` - take the element on top of the stack, and append it to the currently executing program
string.

As usual, we'll start with a "Hello world" program.

(Hello world!)S

Simple, right?

Suppose we wanted to add two numbers. The easiest way to handle numbers in Underload is unary format. So suppose want to add 3 + 5. First, we need to put 3 and 5 on the stack. We can represent three as a list `xxx` and 5 as a list `xxxxx`. To push those onto the stack, we need
to wrap them in parens; and t add them, we want to just concatenate the two lists. So the program to add 3 + 5 and print the result is:

(xxx)(xxxxx)*S

As you'd probably expect, an Underload quine is extremely simple:

(:aSS):aSS

I'll walk through that just to make it clear. First, the list `":aSS"` is pushed onto the stack, so writing the stack as a list of comma separated elements, the stack is "`[:aSS]`". Then we execute ":", which duplicates the top of the stack, leaving "`[:aSS,:aSS]`". Then we execute "a", which wraps the element on top of the stack in parens, giving us "`[(:aSS),:aSS]`". Now there are two "S" commands, which output the two top stack elements; so the out is `(:aSS):aSS`.

A program to generate the fibonacci series is also pretty simple:

(()(*))(~:^:S*a~^a~!~*~:(/)S^):^

It looks like a nighmare, but it's really not bad. It starts with "()" (0) and "(*)" (1) on the stack. And the rest of the program basically copies the larger number, adds the smaller and larger (giving the next element of the sequence), leaving two fibonacci numbers of the stack. It duplicates the larger, prints it, and then goes on to the next iteration. The body of the program is `(~:^:S*a~^a~!~*~:(/)S^)`, which at the very beginning `(~:^)` duplicates itself.

There's an online interpreter for [Underload][interp] which does single-stepping. I recommend popping over there, and watching the fibonacci series program execute. It's much more interesting to watch it in action than it would be to read my detailed description of it!

Now, is this Turing complete? It's a little hard to see. But the author of Underload took care of that question, by showing how to compile [Unlambda][unlambda] into Underload.

* Unlambda "`s`" translates to Underload "`((:)~*(~)*a(~*(~^)*))`"
* Unlambda "`k`" translates to Underload "`(a(!)~*)`"
* Unlambda "`i`" translates to Underload "`()`".
* Unlambda "`\```" translates to Underload "~^".
* Unlambda "`.x`" translates to Underload "`((x)S)`".

[interp]: http://esoteric.voxelperfect.net/files/underload/underload.html
[unlambda]: http://scienceblogs.com/goodmath/2006/08/friday_pathological_programmin…