Sam Gentle.com

When it all comes together

I've been working on a little Javascript utility library called Catenary for the last couple of weeks. It's based on the concatenative (aka stack-based) paradigm, and particularly inspired by the Factor language. It initially just started as me noodling around writing some Factor primitives in JS, but it's turned out to be a lot more fun than I expected.

It's still not ready for the real world yet, but while working on it today I had one of those "a-ha!" moments. I think they're the most satisfying thing you can really experience while working on an idea. You stumble around in the dark working off nothing but feel, completely lost. But, slowly you piece together shapes. Certain movements start to seem familiar. Suddenly, something clicks. This part is the same as that part. In fact, maybe they're all the same part. A-ha!

With catenary, you can write things like this (final syntax pending):


coffee> cat(2, 3, 4)
{ _stack: [ 2, 3, 4 ] }
coffee> cat(2, 3, 4).plus
{ _stack: [ 2, 7 ] }
coffee> cat(2, 3, 4).plus.times
{ _stack: [ 14 ] }

Basically, we use property access to perform operations on a data stack. As well as performing operations on the stack, you can get data into and out of the stack using the special functions .cat and .$, like this:


coffee> cat(1, 2).cat(3)
{ _stack: [ 1, 2, 3 ] }
coffee> cat(1, 2).cat(3).plus
{ _stack: [ 1, 5 ] }
coffee> cat(1, 2).cat(3).plus.plus
{ _stack: [ 6 ] }
coffee> cat(1, 2).cat(3).plus.plus.$
6

So that's fun, but when you want to do anything higher-order you need a way to create those function chains without executing them immediately. For that, you can use a function-building style, which allows you to build up a Javascript-friendly function whose arguments become values on the stack, like this:


coffee> cat.plus
{ [Function] _funstack: [ [Function] ] }
coffee> cat.plus(3, 4)
7
coffee> cat.plus.times
{ [Function] _funstack: [ [Function], [Function] ] }
coffee> cat.plus.times(2, 3, 4)
14

The way it works is actually fairly simple, the function stack (aka _funstack) is built up with every property you access. When you're ready to call your function, it initialises an empty data stack and calls all of the funs in the funstack in order.

My particular a-ha came today when I was trying to sort out how to do flow control. To call a function, on the stack, you do this:


coffee> cat(1, 2, cat.plus).exec
{ _stack: [ 3 ] }

Which can be pretty awkward, especially if you want to chain a lot of function calls together. So I started working on the idea of a cat.fun operator which would allow you to enter function-building style at any time. That is, you could refactor the above into this:


coffee> cat(1, 2).fun.exec(cat.plus)
{ _stack: [ 3 ] }

Under the hood, cat.fun works exactly the same as our original function-building style. It creates an internal funstack with cat.exec in it, which is then invoked when you call the returned function. The only difference is that instead of starting with an empty data stack, you use the one you had when cat.fun is called ([1, 2]). Another way to think about it is that cat.fun is a placeholder that gets filled in later with the argument (cat.plus) when the function is called.

So what's the a-ha? Well, if you remember cat.cat from before, it adds things to the stack after the stack is created, so cat(1,2,3) is equivalent to cat(1).cat(2).cat(3). And that's the exact same thing as cat.fun! It just adds things to the funstack as well as the data stack.

Which means all three of these are the same:


coffee> cat(1, 2, 3)
{ _stack: [ 1, 2, 3 ] }
coffee> cat(1, 2).cat(3)
{ _stack: [ 1, 2, 3 ] }
coffee> cat(1, 2).fun(3)
{ _stack: [ 1, 2, 3 ] }

In that last example, cat.fun adds 3 to the stack, then calls its (empty) funstack.

That led to the realisataion that there might be no need for a separate idea of function-building style and regular style at all. Every catenary can have a data stack and a funstack, and that means a much more elegant system.

In fact, I've had this vague uneasy feeling about data stacks and function stacks for a while. I keep catching glimpses of something that might mean I could drop the distinction entirely and just have one single glorious omnistack.

That's at least one more a-ha away though.