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…

More like this

All week, I've been buried by a wave of requests to write about LOLCODE today. Normally, I do try to honor requests from readers, but from the time I started my friday pathological languages, I've always tried to stick to languages that actually had *something* interesting about their semantics.…
Todays bit of programming insanity is a bit of a novelty: it's an object-oriented programming language called Glass, with an interpreter available here. So far in all of my Friday Pathological Programming columns, I haven't written about a single object-oriented language. But Glass is something…
For todays dose of pathological programming, we're going to hit the worlds simplest language. A Turing-complete programming language with exactly *two* characters, no variables, and no numbers. It's called [Iota][iota]. And rather than bothering with the rather annoying Iota compiler, we'll just…
I'm sure that in the friday pathological programming languages, I have a fondness for languages that make your code beautiful: languages like [SNUSP][snusp], [Befunge][befunge], [Piet][piet], and such. Those languages all you two-dimensional layouts for their programs. [snusp]: http://scienceblogs…

(...) - 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.

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?

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.

By John Armstrong (not verified) on 08 Dec 2006 #permalink

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.

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