13 December 2011

Concatenative Rant

What follows is a rant disguised as a question, which I was going to post on Programmers.SE, but I ultimately thought better. Enjoy.

Most of our favourite programming languages get lumped into the categories of “imperative” or “functional”. While those paradigms don’t exactly present a complete picture of what languages are out there—or even how the languages that are out there actually work—they serve to characterise the majority of what we work with on a daily basis. And all is well with the world.

Except perhaps not. Conceptually speaking, in an imperative language, I order the computer to do what I want; in a functional language, I describe what I want the computer to do. However, in a functional language, I have to contend with more than functions, and the fundamental unit of computation is not the function, but rather function application (specifically, beta reduction).

I can still write useful programs in both kinds of languages, but I find it odd that functional languages get the reputation for purity when I can’t even write most expressions in point-free form.

Enter concatenative languages. When your programming language is stack-based, you can think of it imperatively: all terms denote imperative operations on stacks. But you can also think about it declaratively: all terms denote functions, the juxtaposition of terms denotes function composition, and a program is just a single large function, written entirely point-free. It’s turtles all the way down.

That, to me, seems really elegant. It’s the Holy Grail of paradigms: one which is easy to compile, efficient on existing machines, and yet also amenable to straightforward formal analysis. Cat, for instance, is statically typed, with a simple type inference algorithm based on Hindley-Milner.

And don’t get me started on the opportunities for metaprogramming. In some concatenative languages, I can straightforwardly implement comments, strings, or even numbers as syntactic extensions in the language itself.

So what gives? Why aren’t these languages everywhere? Is it simply that exceptional languages can’t be popular because most programmers can’t be exceptional?