I’ve had a long, difficult week, so I’ve decided to pick something pointlessly
pathological for today. It’s a remarkably goofy language called “Chef”, designed by David Morgan-Mar, in which programs are recipes. Since aside from being a programming language
nutjob, I’m also a pretty good chef, combining two of my favorite things naturally has
some appeal – particularly when done in a pointlessly twisted way.
Todays pathological language is actually in the form of a challenge for you. (Isn’t that
exciting?) It’s a very clever numerical programming language in the vein of Conway’s Fractran,
called NULL. The author of NULL describes it
as a reaction to 2 and 3 dimensional languages in the Befunge tradition; NULL is a 0
dimensional language – a program is just a single point. It’s quite clever in its way; the only
problem is that is that there’s only one example program written in it. So the challenge is
to see if you can actually come up with some implementations of interesting programs.
I decided that for today, I’d show the most thoroughly evil programming language ever
devised. This is a language so thoroughly evil that it’s named Malbolge after a circle
of hell. It’s so evil that it’s own designer was not able to write a hello world program! In
fact, the only way that anyone managed to write a “Hello World” was by designing a genetic algorithm
to create one. This monstrosity is so thoroughly twisted that I decided to put it in the “Brain and Behavior” category on ScienceBlogs, because it’s a demonstration of what happens when you take a brain, and twist it until it breaks.
I’m hitting on something deeply twisted this week. It’s called homespring. Homespring is interesting for two reasons. First, it’s got a sort of reverse flavor to it: it consists of active agents in a passive structure. So, for example, you can’t do anything like control flow – that’s a dynamic change in the control flow of the program; in Homespring, you need to trick the agents into doing something using the static, unchanging structure of the program. And second, it challenges you to write your program in the form of a poem! And the icing on the cake? The agents are salmon,
and the passive structure is a network of streams.
Today, I have something really fun and twisted for you. It’s my favorite variation on
BrainF**k, called “BFM”, which is short for “BrainFunct-Macro”. It’s a doubly-Turing-equivalent language – it’s got two complete and distinct Turing equivalent computing systems in it: it’s
got regular BF on the bottom… But before BF gets going to run the program,
the program is pre-processed by a complete lambda-calculus macro expander.
Today, I’m going to show you a very simple, very goofy little language called “SCEQL”, which standards for “slow and clean esoteric queue language”. It’s based on nothing but a circular queue
of numbers with nothing but 8 commands. It’s not one of the more exciting languages, but it can
be a lot of fun to figure out how to make the circular queue do what you want it to.
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_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.
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_3.php
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.com/goodmath/2006/08/beautiful_insanity_pathologica.php
[befunge]: http://scienceblogs.com/goodmath/2006/07/friday_pathological_programmin.php
[piet]: http://scienceblogs.com/goodmath/2006/11/programming_in_color_fixed.php
Among the nutters that make up the community of folks interested in this kind of thing, looking
at these languages led to a theoretical question, which was named *”the wire-crossing problem”*. The
basic question was:
>Is it possible to define a two-dimensional flow-based language which does *not* ever need
>one execution path to *cross* another execution path?
Alternatively:
>Is it possible to express every computable function as a two-dimensional graph
>where no edges ever cross?
This question raged for quite a while without an answer. Todays pathological language is
a very simple language designed for the sole purpose of demonstrating, once and for all, that
*yes*, you can write every computable function with no wire-crossing.
Todays tidbit of torture is a simple little language called [Leszek][leszek], with an implementation available [here][leszek-impl]. Leszek is based on the idea of *iterative string rewriting*, which is actually a useful and valuable concept. Of course, Leszek takes it to an extreme of insanity which takes a perfectly good idea, and turns it into a horror. But thats what makes it fun!
[leszek]: http://www.esolangs.org/wiki/Leszek
[leszek-impl]: http://students.mimuw.edu.pl/~js248325/zsyp/leszek.tar.gz
In Lezsek, there are no variables; no loops; no state. A program is just a string with
a collection of embedded rewriting operators. The way that things work is, the interpreter looks
at the string. It finds all of the rewriting commands in the string, and executes them, concatenating the *results* of those commands. When it’s done all of
the rewrites in the entire program, it takes the *resulting* program string, and executes *that*. It keeps going until there is no possibility of any more rewrites generating output, and then it halts.
Due to work stuff, I’m very busy this week, and I don’t have time to write a detailed
pathological language post, so I chose something that doesn’t take a lot of explanation, but
which is delightfully twisted. It’s a language called [Muriel](http://web.archive.org/web/20021205092706/http://demo.raww.net/muriel/), aka
the *”Monumentally Useless ReIterative Execution Language”.
Muriel is based on the idea of [*quines*](http://www.nyx.net/~gthompso/quine.htm). A quine for a programming language is a program in that language which produces itself as output. Quines are
considered interesting puzzles in some circles, which has led to generation of huge collections of quines in just about every imaginable programming language. Follow the link above to see one such collection. Muriel takes things a step further: instead of quines being an interesting (if pointless) challenge, in
Muriel, they’re an essential part of the language!