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. LOLCODE is funny because of its goofy grammar; but it’s really incredibly dull semantically. And while there are lots of programs written in it,
there’s no implementation (at least not yet).
Anyway, what I decided to do instead is a twistedly beautiful language called [Sortle][sortle]. Sortle is a very simple language which is based on insertion sort. The basic idea of how it works is: it takes the lines of the program, and sorts them. Then it executes them; when a line is executing, it can modify itself; when it gets modified, the interpreter re-sorts the line into its correct position in the sorted order according to its new value. So control flow is completely driven by the sort-order of the lines of the program.

Statements in Sortle consist of a statement name, and an expression, “name:=expr. The statement name is just a string, which is going to get used to sort the statement into the correct location in the program.
The expression is a stack-oriented expression; when the expression is done executing, it must leave *exactly* one value on the stack, and that value will become the *new* name for the statement. If the new name is the empty string, then the statement is *deleted* from the program; if the new name is already the name of an existing statement, that statement is deleted and replaced by the newly renamed statement.
The interpreter executes statements in sorted order; when it gets to the end of the list of statements, it loops back to the beginning. It continues execute statements until there is only one statement left, and then it will output the value of that statement’s name.
An expression can use the following operators:
* “+”: add the top two numbers on the stack.
* “*”: multiply the top two numbers on the stack.
* “/”: divide the top number on the stack by the second number on the stack.
* “%”: divide the top number on the stack by the second number on the stack, and
leave the remainder on the stack.
* “^”: compare the top two values on the stack, leaving the larger one.
* “~”: contatenate the top two values on the stack.
* “?”: match regular expression against the top of the stack, leaving the appropriate
match on the stack.
* “$”: string compare, permitting nulls.
So, for example, the statement “Hello:="hello" "world" ~“, when executed, would become “helloworld:="hello" "world" ~“.
Regular expressions are formed from the following characters:
* “.”: match any character.
* “[chars]”: match the sequence of characters “[chars]”. (Note that this is *not*
what “[]”s do )
* “!” means match whatever comes before 0 or more times. (“*” in usual regexp syntax)
* “@” means match whatever comes before 1 or more times (“+” in usual regexp syntax)
* parens change what is returned by the match; if there are no parens, then the entire
string matching the regexp will be left on the stack; if there are parens, then
if the string matches, the part that matches the part of the regexp inside the parens
is left on the stack.
Regular expressions are very important in Sortle – they’re basically the only real way of transferring information between statements. The way that that works is, if the string to match against the regular expression is empty, then the list of all statement labels other that the label of the current statement will matched against the regular expression.
Which brings us to our first example – a simple “Hello World” program.
world := “”
hello := “hello, ” “.!” “” ? ~
When this is executed, first things are sorted. So “hello” is executed before “world”. What “hello” does is push the string “hello, ” onto the stack; then it pushes the regular expression “.!” onto the stack; then it pushes an empty string on the stack. Then it does a regexp match. Since the empty string is on top of the stack, the subject of the search is the *other* statement name labels. The string to match is “.!” , which is *any* sequence of characters. Since there’s only one other statement, the first match is “world”. So the regexp leaves “world” on top of the stack. The stack is now (“hello, “,”world”). It then executes a string concatenation, producing “hello, world”. So the line becomes “hello, world:="hello, " ".!" "" ? ~“.
Next, it moves on to the next line, which is “world := ""“, which deletes itself. That leaves only one statement left – so it outputs the statement’s name, and exits.
Another variant of Hello world is even simpler:
hello := “hello, world”
world := “hello, world”
So “hello” runs first, renaming itself to “hello, world”; then “world” runs, also renaming itself to “hello, world”, replacing the other one, and leaving one statement in the program, whose label is “hello, world”. So the label gets output, and the program ends.
One last example (sorry, but the implementation only comes with these three examples, and I didn’t have time this week to hack together any examples of my own; if someone writes any interesting ones, I’ll be glad to add them to this article!):
hello := “hello, ” “.!” “” ? ~
world := “(…..),.!” “” ? “, world” ~
This is really just a clever combination of the previous two. Both statements are regular expressions that use the values of the labels of the *other* statement to change their labels to “hello, world”; one stomps the other, leaving one, and voila! “hello, world” goes to the output.
I love Sortle – the idea of insertion sort as a control flow mechanism is brilliantly insane. It takes an utterly trivial language – nothing but a tiny bit of arithmetic and string primitives, and with the regular expressions, turns insertion sort into a turing complete computing system. I wish *I’d* thought of it.
[sortle]: http://esoteric.voxelperfect.net/files/sortle/