Pointful Concatenative Programming

Well, I managed to spend the last year or so working on parallelism and vau expressions without actually writing any blog posts about it. Next week I'm giving a conference presentation, and maybe after that I'll come back here and review the last year's work. But for now, I am on to something a little different.

Reading Why Concatenative Programming Matters has inspired me to experiment with concatenative languages. Concatenative languages are often called "stack-based" languages, because they are incredibly easy to implement with stacks, but that article enlightened me to the fact that stacks are not actually necessary- other evaluation options are possible. In fact, type analysis can be used to identify substrings of concatenative programs that take no inputs which correspond to expressions in argument positions in functional languages and can all be executed in parallel. (In retrospect, this should have been obvious since functional languages compile to concatenative ones- this is just the reverse mapping.)

One of the reasons concatenative programming is cool because it's point-free; i.e., you never have to specify variable names, which makes things nice and concise. Unfortunately, that can backfire and end up making things horribly unreadable, which is why concatenative languages tend to suck at expressing basic math. Sometimes, you just want to use a variable to put the same value in multiple places; even in RPN syntax, "y x * y -", using variables to put values in the right place on the virtual stack, is way easier to read and understand than "DUP ROT * SWAP -", using stack effect operators. Not having variables also means that concatenative languages tend to lack the ability to do variable capture, which means no closures.

I have thus been pondering a concatenative language that adds variable-binding lambda expressions. Something like this:

{ a b | b a }

would take two values off the top of the virtual stack and bind them to variables "a" and "b" within the scope of the expression. Variables are just words that take no arguments are return their bound values. The effect of this expression would then be to swap the top two elements on the virtual stack. Lots of otherwise basic, built-in words can be created with these kinds of expressions. E.g., DUP looks like this:

{ x | x x }

These sorts of lambda expressions would be interpreted like words and applied immediately, causing them to function rather like let-bindings in functional languages. Combining lambdas with quotation, however, allows us to create closures:

{ x | [{ y | x y + }] }

This expression binds one argument and returns a closure that takes another argument and adds it to the closed-over value.

Well, that's all for now. Maybe, if I'm lucky, I'll have time this summer to start implementing this thing.