A javascript+canvas implementation of the Context Free Art design grammar: Put short code in, get pretty pictures out! How to use it. How it works. Implementation status.
If you have feedback of any kind, drop me a line or leave a comment. Thanks!
Turns out, I'm not the first one to do this. Thankfully, I'm in good company. Check out Algorithm Ink by Aza Raskin, who happens to be the lead designer for Firefox.
There are some definite differences between our implementations.
In a nutshell, you write a short script describing the scene you'd like, and you get a picture of the scene back. The tricky part is that the scripts can be incredibly powerful and thus unintuitive.
Thankfully, there is ample tutorial countent:
For those of you who looked at the source and saw that it was underdocumented and overcomplicated: Sorry about that, it's a hack. As I have time I'll fix it up.
If you're a functional programming afficiando, you'll see a lot of friendly concepts below; if not, it will seem rather alien and unfamiliar.
I used a technique from the functional programming language world called combinator parsing, where you build up a parser by composing lots of little functions together. (A "combinator" is, roughly, a function that combines other functions into a new function.)
This means the code starts with some ugly plumbing, but lets me specify the end grammar rather nicely once the plubming is out of the way:
var p_rule = seq([lit("rule"), ident, alt(number, succeed(1.0)) ,rbody], function(_,nm,wt,bdy) { return rule(nm,wt,bdy); });
Translated to english, this means that a rule definition consists of: The literal string "rule", then an identifier, then an optional number ('1.0' is the alternative, if the number is omitted), then the body of the rule.
To a certain extent, this is the easy part: Drawing things on the canvas is reasonably straightforward, and ditto for keeping track of the transformation and color states.
These issues are potentially nasty ones for a naive implementation -- it can take a long time to render images, and the browser tab or entire browser will be frozen during that time. Further, the user will eventually be prompted to kill the script because it will appear unresponsive. Finally, as a matter of taste, the drawing process will be hidden -- it's far more fun to watch it progress, even at the expense of some speed.
There's a big hammer for these sorts of issues called continuation-passing style. If you've used AJAX, you've already done a little bit of it: Rather than giving you the contents of your request immediately as a return value, and potentially stalling your scripts and the browser while it your request goes out over the network, you instead provide a callback which receives the AJAX results.
Continuation-passing style (CPS) is this idea applied universally: You assume all functions work like an AJAX call: they never return, instead invoking a callback when they're done.
Yes, it's a headache. But look what you get in return: At any point during execution, a setTimeout can be inserted, allowing the browser to remain interactive, and execution will pick right back up where it was before after the timeout!
Since my implementation is fairly direct, where recursion in the CDFG language translates into recursion in Javascript, it will also run into recursion limits in the browser's interpreter.
It turns out that we can solve this problem via a technique called trampolining. Due to our use of CPS, each function's last task is to invoke its continuation (the callback provided in lieu of returning).
However, instead of invoking the callback, it returns the callback, without running it.
This transforms our functions from ones that recurse to arbitrary depths into ones that return the 'next action' (the continutation) to its caller. The root caller's logic is simple: it repeatedly calls the continuation, getting a new one in return, until the program is finished. It's a neat trick: recursive calls in the tail position (calls that are the last ones a function makes) no longer increase the stack depth -- and due to the use of CPS, all function calls are in the tail position.