But I’ve never seen anything like this before. It’s a multilingual quine: the program below is not just a quine, but it’s simultaneously a quite in three different languages: OCaml, Haskell, and Scheme. I have no idea how the author managed to figure out how to do this; and I probably don’t want to. 🙂
Today’s friday programming language insanity is a tad different. I’m going to look at another twisted stack-based language. I’ve got a peculiar fondness for these buggers, because back in the day, I was a serious Forth addict. One of the ideas that’s actually come up in serious programming languages in the last few years is creating a sort of cross between functional languages and stack-based languages, producing what are known as concatenative languages. An excellent example of an extremely powerful and useful member of this family is called Factor, by Slava Pestov.
But serious useful languages aren’t the realm of my regular friday pathology. So I’m going to tell you about a not-really-serious version of a concatenative language, called False. Semantically, False is actually not a horrible language. In fact, if it weren’t for the bogglingly awful syntax, it’s something I could imagine using for tiny file-filtering utilities. But the syntax is designed to be truly horrible, and when you blend the natural potential for confusion that you get from doing everything backwards on a stack with a syntax that looks like line-noise, you get something that can really sprain your brain.
As promised, this week, I’ve got a new friday pathological programming language. This one is another 2-dimensional language, but it’s pretty different from any of the 2d languages I’m written about before. It’s called “Flip“, and the warped minds behind describe it as being sort of like “Programmers Billiards”. It’s a seriously neat language, but it is pretty large and complicated. So I’m not going to describe everything about it in detail: you’ll have to read the language manual for that. But I’ll describe enough to give you the flavor of it, and show you a couple of examples to whet your appetite.
Today’s bit of pathology is a really silly, and really fun language called Clunk, with a downloadable package containing a perl implementation here. I’m
not sure that it’s Turing compete, but my best guess is that it is. It’s another two dimensional
language, but it’s very different from any of the other 2d languages that we’ve look at, because it
doesn’t rely on an instruction pointer moving around the playfield; instead, it computes by
creating an image by fitting together pieces according to some pre-determined rules.
For reasons that I’ll explain in another post, I don’t have a lot of time for writing a long pathological programming post, so I’m going to hit you with something short, sweet, and beautiful: binary combinatory logic.
I’ve written in the past about lambda calculus, and it’s equivalent variable-free form, the SKI combinator calculus. I’ve ever written about other combinator calculus based languages, like Unlambda and Iota.
Binary combinatory logic, aka BCL, is a language based on SKI calculus – except that it encodes the entire thing into binary. Two characters, plus two rewrite rules, and that’s it – a complete
combinator calculus based programming language.
SKI combinator calculus is a simple variable-free calculus with three constructs: S, K, and I; and I isn’t really primitive, but can be defined in terms of S and K.
S=λx y z.x z (y z)
So, in BCL, S is written “01”; K is written “00”. And there are two rewrite rules, which basically define “1” without a zero prefix as a a paren-like grouping construct:
“1100xy”, where “x” and “y” are valid BCL terms (that is, complete syntactic units),
gets rewritten to be “x”. If you follow that through, that means that it reduces to ((Kx)y).
“11101xzy” gets rewritten to “11xz1yz”. Again, following it through, and that
reduces out to “(((Sx)y)z)”.
So, following on unlambda’s method of handling IO, “hello world” in BCL is:
And here’s the really neat thing. Write an interpreter for BCL in BCL. Take the bit string that results, and convert it to a bitmap. That’s what’s over the right here. So, for example, the first line is “1111100000111001”; keep going, and you’ll find the entire BCL interpreter.
For today’s installation of programming insanity, I decided to go with a relative of Thue, which is one of my favorite languages insane languages that I wrote about before. Thue is a language based on a rewriting system specified by a semi-Thue grammar. Todays language is called Thutu (pronounced tutu); it’s a string rewriting system like Thue, only it’s based on regular expressions instead of grammars, and it’s even got regular expression-based control flow mechanisms, making it a sort of hybrid language.
The scary thing about Thutu is that it’s not all that different from a language I’ve wanted to find some time to write myself – except that the one I want to write isn’t intended to be pathological. I’ve never stopped missing Teco for writing text processing programs; and since
my TECO programs tended to be roughly of the form: “Find something matching this pattern, and then take this action”, a regular-expression based language would make a lot of sense.
But anyway, today we’re looking at Thutu, which is a deliberately obscure version of this idea.
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
special. It’s actually sort of a warped cross between Smalltalk and Forth – two things that should never have gotten together; in the words of the language designer, Gregor Richards, “No other language is implemented like this, because it would be idiotic to do so.”
Back in the very early days of what eventually became computer science, many of the people working in the field invented all sorts of automatons/computing formalisms. The one that I’ve always found the most confounding is the Tag machine invented by Emil Post.
The tag machine is simple to the point of triviality. The machine is a queue of characters (with one character designated as “Halt”), and a set of rules. Each rule has a different character that selects the rule, and a string of characters. Each step, the machine looks at the first character of the queue, and selects the rule that that is associated with that character. If the character is “Halt”, the machine just stops, and whatever is left on the queue is the result of the computation. Otherwise, it appends the selected rule’s string of characters to the end of the queue, and then removed a fixed number of characters from the front of the queue. The machines are called “n-Tag” machines where “n” is number of character dropped each step.
That’s it. Look at the front of the queue, use it to pick a set of characters to append, and then remove and discard the first N characters from the queue..
For any N≥2, a Post N-tag machine is Turing equivalent.
Like I said above – I’ve always found the Post Tag machine to be thoroughly confounding. I can grasp why it’s Turing equivalent, but for the life of me, I’ve never been able to figure out how to actually implement anything interesting on one. So, I figured, there are tons of esoteric/pathological language fans out there who love nothing more than the challenge of writing interesting programs for bizarre languages; I’ll write a post-tag language, and throw it to the wolves, and see what happens!
Todays pathology is playing with stacks. Lots of lots of stacks. Stacks for data. Stacks for control. Stacks out the wazoo. It’s called Kipple for no particularly good reason that I know of.
Kipple happens to be one of the pathological languages that I highly recommend trying to write some programs in. It’s crazy enough to be a challenge, but there is a basic logic to how you program to it – which makes figuring out how to write programs rewarding rather than just frustrating.
In light of the recent posts and discussions about multidimensional
numbers,today’s pathological language is Recurse, a two-dimensional language – like Befunge, sort of. But I find it more interesting in its own peculiar little
way. It’s actually a function-oriented two-dimensional language where every
function is rectangular.