Skip to content

Instantly share code, notes, and snippets.

Created Apr 9, 2010
What would you like to do?

As some of you know, one of my projects is an implementation of Context Free Art in Scheme. It was a part of Abstracting and has been ported to Agave.

The only part of the task that I'd tackled was a core engine which would interpret low-level state machine instructions and a way to render the results of this interpretation. The Scheme versions of the CFDG programs were thus much longer; the flow control of the program was explicit, whereas most of this is implicit in the CFDG language.

I always knew there were a couple of ways to proceed on this project.

One is to use one of the available parsing systems for Scheme to specify the actual CFDG language grammar and use the parser as a front end to the low-level system I'd set up.

The other, to "embed" the language within Scheme with the help of higher-order procedures and macros.

Recently I decided to work on the latter method and the results are quite surprising!

Here's an actual CFDG program.

Here's the Scheme version written in the low-level style.

I created a macro called 'rule'. Here's the same program in terms of it.

Much closer to the original!

Let's zero in on a part of this example. Here's how the 'BLACK' rule is defined in the CFDG language:

rule BLACK 60 {
     CIRCLE {s .6}
     BLACK {x .1 r 5 s .99 b -.01 a -.01}

rule BLACK {
     WHITE {}
     BLACK {}

Here is what it looks like in Scheme:

(rule black

       (60 (circle (s 0.6))
           (black (x 0.1) (r 5) (s 0.99) (b -0.01) (a -0.01)))

       (1  (white)

Notice there's a '1' in the Scheme version but not in the CFDG version. That number indicates the "weight" of the branch and is implicitly '1' if you don't specify it in CFDG. I chose to make this explicit for now.

rule is a simple syntax-rules macro (source).

The core library (agave demos cfdg) is only 268 lines.

I chose to implement not the complete CFDG language, but a subset which I found to be sort of a "sweet spot"; enough features to render the really cool examples I'd seen.

Does the fact that CFDG was so straightforward to embed and implement mean that the designers of that language did a great job of coming up with something truly small and elegant? Or is it a testament to the power of Scheme? I think it is both. :-)

Agave includes a few CFDG demos. Each of these will kick one off:

 ikarus --r6rs-script ~/agave/demos/cfdg-spirales.scm
 ikarus --r6rs-script ~/agave/demos/cfdg-chiaroscuro.scm
 ikarus --r6rs-script ~/agave/demos/cfdg-game1-turn6.scm

As usual, they all run under Ypsilon and Chez Scheme as well.

I think the earliest piece of software which influenced me to think along the lines which led to design choices in this project is Scsh. In particular it's embedding of process forms, the awk macro, and SREs. So thanks to Olin Shivers for leading the way. :-)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment