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.
[muriel]: http://scienceblogs.com/goodmath/2006/11/friday_pathological_programmin_5.php
[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.
* `~` – 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.
(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)`”.
[unlambda]: http://scienceblogs.com/goodmath/2006/08/friday_pathological_programmin_3.php

0 thoughts on “Pathological Stack Hell: Underload”

1. Oliver

(…) – push the contents of the parents on the stack as a single stack element.
I think that should be “parens”. Amazing how that t makes it so much more confusing.

2. Jonathan Vos Post

I loved my parens, Mom and Dad. Now I’m a paren, also.
There are some steps missing in the Turing Completeness of Underload, via Unlambda.
I hope that you, or one of your active readers, will complete the proof.
And is there a Categorical apprach to that proof, with Currying and so forth?

3. John Armstrong

JVP: of course this whole thing is very categorical. Let X be an object in a category with finite products.
Here’s the category theory interpretations for a few of the operations
~ – twist map from X2 to itself
: – canonical comultiplication from X to X2
! – canonical counit from X to T
* – multiplication from X2 to X

The others I’m not entirely sure about, but a few guesses follow

(…) – defines an arrow from T to X. This is the categorical notion of an “element of X”, familiar from topoi.
a – sends X to hom(T,X) (related to currying?)
S – categorically extraneous
^ – no clue

Of course, if I put more time into it I could probably find a good interpretation for the other terms. Actually, I think this probably manages to be a very close (if terse) parallel to a hypothetical language growing out of Baez’ seminar.
Pathological maybe, but categorically beautiful.

4. Mark C. Chu-Carroll

John:
Thanks for that! It is beautiful in a way, isn’t it? That’s really what I look for in the languages for my friday posts – languages that are bizzare, and yet have a kernel of beauty laying underneath the insanity.
Underload is also *very* fun to program it.

5. David

Hah, what a marvellous language! Now I wish all programming languages involved writing a program that writes dozens of little programs onto the stack that does some foo, then calls the next little program down the line in a lovely cascade. Nest as necessary.
To hell with plodding old single-step iteration! Let recursion disappear up its own bumhole! This is what control flow should be about! It’s not the end result that counts, it’s the getting there!
My magnum opus so far is a program that takes the factorial of however many colons are in the first set of parents. I feel I should share, in case anyone out there has a pressing need for exactly 5060 colons:
(:::::::):(:((^:()~((:)*~^)a~*^!!()~^))~*()~^^)~(^a(*~^)*a~*()~^!()~^)a~**^!!^S