One of the esoteric programming languages that a fair number of people have heard of, is “Whitespace”. I'm sure this has nothing at all to do with jokes like its source code being so fantastically efficient when being printed out. The language was actually meant as a joke (at least that's how one of its creators puts it when he mentions the language in some of his talks). But even though people are aware of the language's existence, they rarely know how it works. Let's change that, because it's really not all that hard.

At its core, the language describes operations on a stack machine, that has access to a heap. The only data type of the machine are integer values of arbitrary size. There are operations for the machine, that use these values to encode characters as well. And that's about it. The rest is just a peculiar way to encode operations and values using three ASCII whitespace characters (TAB, SPACE and LINEFEED).

Operations are grouped by function. These groups determine an operation's encoding prefix, that the language spec calls “Instruction Modification Parameter”. Many of the operations have no arguments, as they create and consume arguments on the machine's stack. Some however do take an argument: Integers and Labels. Label arguments are used by flow control operations; and integer arguments are used by some of the stack manipulation operations.

Their encoding is similar: Both use strings of spaces and tabs, that are terminated by linefeeds. In labels, the spaces and tabs have no special semantics. At least not within the language specification; more on that later. In integers, tabs encode ones and spaces encode zeroes. Something to note about such integer literals is that they do not use two's complement to encode negative numbers. Instead, they use the literal's leftmost bit as a signedness bit: Tab means negative number, space means positive number. That makes encoding arbitrarily wide integers straight-forward.

When you take a look at actual whitespace programs, you'll sometimes notice extremely long labels. Oftentimes with that, there seems to be a silent convention to use chunks of eight characters to encode eight bits (same semantics as in number literals as to what characters encode ones and zeroes) that are turned into a positive number, which is then mapped to the ASCII encoding (seven would have sufficed, but that's not what the programs I've seen use).

When you try and implement this language, you'll notice a couple of things your machine implementation needs: A stack obviously, since whitespace is a stack-manipulating language. Another stack, used as a callstack, since the language has Call and Return operations. It also needs a heap, mapping addresses to integers. Finally you'll need program memory and a program counter register. You might want a jump-table too, to deal with translating labels to addresses. That's not strictly required, though: You could just translate all labels to addresses before loading the program into your machine.

When I digged deep enough into the language spec to figure this out, I was intrigued enough to actually do yet another implementation of the language. It's called SpaceMan and it is available at gitlab.com/ft/spaceman as well as github.com/ft/spaceman.

I've added an org-mode conversion of the original language homepage, because that one is currently only available via archive.org. When trying some of the more complex examples you can find on the net, I was running into problems. My implementation failed to even parse them. I was verifying my code for quite some time, until I concluded that it was implementing the parser correctly. So I looked at other implementations. And it turned out most of them implemented two additional stack-manipulating operations: Copy and Slide. Apparently, they were added to a later specification of the language. I couldn't find such a spec on the net, though (not that I invested a lot of time — see the update at the end of the post for a resolution to this). However, after implementing these two, spaceman could run the most elaborate examples that I could find online, like a sudoku solver. I've added those two additional operations to the included version of the language spec.

I'm using Megaparsec for parsing purposes. And with a couple of utilities put in place, writing the parser becomes rather pleasant:

stackParser :: Parser StackOperation
stackParser = do
  (      try $ imp [ space ])
  (      try $ Push  <$> number [ space ])
    <|> (try $ operation        [ linefeed, space    ] Duplicate)
    <|> (try $ operation        [ linefeed, tabular  ] Swap)
    <|> (try $ operation        [ linefeed, linefeed ] Drop)
    <|> (try $ Copy  <$> number [ tabular,  space    ])
    <|> (try $ Slide <$> number [ tabular,  linefeed ])

When implementing the language's operations, you'll find that you're facing lots of common instructions that manipulate the virtual machine. You put those common tasks into functions, of course, and like any designer of an assembly language worth their salt, you obviously give your instructions slightly cryptic three letter names. With those, implementing the stack-manipulating operations looks like this:

eval :: WhitespaceMachine -> StackOperation -> IO WhitespaceMachine
eval m (Push n)  = return $ pci $ psh [n] m
eval m Duplicate = return $ pci $ psh h m               where h     = peek 1 m
eval m Swap      = return $ pci $ psh [b,a] $ drp 2 m   where [a,b] = peek 2 m
eval m Drop      = return $ pci $ drp 1 m
eval m (Copy i)  = return $ pci $ psh [n] m             where n = ref  i m
eval m (Slide n) = return $ pci $ psh h $ drp (n+1) m   where h = peek 1 m

Implementing the other groups of operations looks similar. I sort of like it. Each of them would basically fit onto an overhead slide.

As it turns out, editing whitespace programs is tough work. Doing it directly is best done in an hex-editor. But spaceman has a feature, that makes it dump the programs syntax-tree to stdout. And those program dumps are actually executable programs. So if you'd like to edit a whitespace program, you can dump it into a file, edit its AST and then run that program to yield the changed whitespace program.

“Yet another whitespace implemention created” achievement unlocked, I guess.

[Update] Andrew Archibald informs me, that if you spend a little more time looking for the language specification, that includes Slide and Copy, you will find http://compsoc.dur.ac.uk/whitespace/index.php (via archive.org), that contains v0.3 of the whitespace specification, that adds these operations.

“…done in Scheme.” was an idea I had when I started liking Scheme more and more. XMMS2 is my preferred audio player for a long time now. And I always wanted to write a client for it that fits my frame of mind better than the available ones.

I started writing one in C and that was okay. But when you're used to use properly extensible applications on a regular basis, you kind of want your audio player to have at least some of those abilities as well. I started adding a lua interpreter (which I didn't like), a Perl interpreter (which I did before in another application, but which is also not a lot of fun). So I threw it all away, setting out to write one in Scheme from scratch.

To interface the XMMS2 server, I was first trying to write a library that wrapped the C library that the XMMS2 project ships. But now I was back to writing C, which I didn't want to do. Someone on IRC in #xmms2 on freenode suggested to just implement the whole protocol in Scheme natively. I was a little intimidated by that, because the XMMS2 server supports a ton of IPC calls. But XMMS2 also ships with machine readable definitions of all of those, which means that you can generate most of the code and once you've implemented the networking part and have the serialization and de-serialization for the protocol's data types, you're pretty much set. …well, after you've implemented the code that generates your IPC code from XMMS2's definition file.

Most of XMMS2's protocol data types map very well to Scheme. There are strings, integers, floating point numbers, lists, dictionaries. All very natural in Scheme.

And then there are Collections. Collections are a way to interact with the XMMS2 server's media library. You can query the media library using collections. You can generate play lists using collections and perform a lot of operations on them like sorting them in a way you can specify yourself. For more information about collections see the Collections Concept page in the XMMS2 wiki.

Now internally, Collections are basically a tree structure, that may be nested arbitrarily. It carries a couple of payload data sets, but they are trees. And implementing a tree in Scheme is not all that hard either. The serialization and de-serialization is also pretty straight forward, since the protocol reuses its own data types to represent the collection data.

What is not quite so cool is the language you end up with to express these collections. Say, you want to create a collection that matches four Thrash Metal groups you can do that with XMMS2's command line client like so:

xmms2 coll create big-four artist:Slayer \
                        OR artist:Metallica \
                        OR artist:Anthrax \
                        OR artist:Megadeth

To create the same collection with my Scheme library, that would look like this:

(make-collection COLLECTION-TYPE-UNION
    '() '()
    (list (make-collection COLLECTION-TYPE-EQUALS
              '((field . "artist")
                (value . "Slayer"))
              '()
              (list (make-collection COLLECTION-TYPE-UNIVERSE '() '() '())))
          (make-collection COLLECTION-TYPE-EQUALS
              '((field . "artist")
                (value . "Metallica"))
              '()
              (list (make-collection COLLECTION-TYPE-UNIVERSE '() '() '())))
          (make-collection COLLECTION-TYPE-EQUALS
              '((field . "artist")
                (value . "Anthrax"))
              '()
              (list (make-collection COLLECTION-TYPE-UNIVERSE '() '() '())))
          (make-collection COLLECTION-TYPE-EQUALS
              '((field . "artist")
                (value . "Megadeth"))
              '()
              (list (make-collection COLLECTION-TYPE-UNIVERSE '() '() '())))))

…and isn't that just awful? Yes, yes it is. It so is.

In order to reign in this craziness, the library ships a macro that implements a little domain specific language to express collections with. Using that, the above boils down to this:

(collection (∪ (artist = Slayer)
               (artist = Metallica)
               (artist = Anthrax)
               (artist = Megadeth)))

So much better, right? …well, unless you really don't like Unicode characters and the ‘∪’ in there gives you a constant headache… But worry not, you can also use ‘or’ in place if the union symbol if you like. Or ‘UNION’ if you really want to be clear about things.

If you know a bit of Scheme, you may wonder how to use arguments to those operators that get evaluated at run time. Since evidently, the Slayer in there is turned into a "Slayer" string at compile time; same goes for the artist symbol. These transformations are done to make the language very compact for users to just type expressions. If you want an operator to be evaluated, you have to wrap it in a (| ...) expression:

(let ((key "artist") (value "Slayer"))
  (collection ((| key) = (| value)))

These expressions may be arbitrarily complex.

Finally, to traverse Collection tree data structures, the library ships a function called ‘collection-fold’. It implements pre, post and level tree traversal with both left-to-right and right-to-left directions. So, if you'd like to count the number of nodes in a collection tree, you can do it like this:

(define *big-four* (collection (∪ (artist = Slayer)
                                  (artist = Metallica)
                                  (artist = Anthrax)
                                  (artist = Megadeth)))

(collection-fold + 0 *big-four*)   ;; → 9

This would evaluate to 9.

The library is still at an early stage, but it can control an XMMS2 server as the ‘cli’ example, shipped with the library, will show you. There are no high level primitives to support synchronous and asynchronous server interactions. And there is not a whole lot of documentation, yet either. But the library implements all data types the protocol supports as well as all methods, signals and broadcasts the IPC document defines. The collection DSL supports all collection operators and all attributes one might want to supply.

Feel free to take a look, play around, report bugs. The library's home is with my account on github.

[Update] In a previous version of this post I mixed up the terminology for unions and intersections. The library mixed up the set operators associated with ‘and’ and ‘or’, too, and was fixed as well.

In this episode of songs you should have heard, let's have some metal, shall we? In particular, the Devin Townsend Band. Some people are flooding youtube with reaction videos to Devin's performance of Kingdom, which is a good one, but let's have this one instead:

Devin Townsend Band — Accelerated Evolution — Deadhead

• Fantastic Live Version at Red Rocks