Category Archives: Context Free

Assorted Links

Generative Music Software

Adam M. Smith has begun working on cfml – a context-free music language. It is a Context-Free Design Grammar – for music. I’m very interested in how this develops.


A graphical representation of cfml output (original here)

Cfml is implemented as an Impromptu library. Impromptu is a live coding environment, based on the Scheme language, and has existed since 2005. Andrew Sorensen, the developer of Impromptu, has created some of the most impressive examples of live coding I have seen. In particular, the last example, inspired by Keith Jarrett’s Sun Bear Concerts, is really impressive. (I might be slightly biased here, since I believe that Jarrett’s solo piano concerts – especially the K√∂ln Concert and the Sun Bear Concerts – rank among the best music ever made).

Finally, Supercollider 140 is a selection of audio pieces all created in Supercollider in 140 characters or less. An interesting example of using restrictions to spur creativity. Another example is the 200 char Processing sketch contest.

Free Indy Game Development

This month also saw the release of the Unreal Development Kit, basically a version of the Unreal Engine 3, that is free for non-commercial use. This is great news for amateur game developers, but for me, the big question was whether this could be used as a powerful platform for generative art or live demos. I downloaded the kit and played around with it for a while, but while the 3D engine is stunning, UDK seems very geared towards graphical development (I certainly do not want to do draw my programs, and the built-in Unrealscript does not impress me either).

In related news, that basic version of Unity 2.6 is now also free. The main focus of Unity is also game development, but from a generative art / live demo perspective it holds greater promise. Unity offers an advanced graphics engine with user-scriptable shaders, integrated PhysX physics engine, and 3D audio.

Unitys development architecture is also very solid: scripts are written in (JIT-compiled) JavaScript, and components can be written in C# (using Mono, the open-source .NET implementation). Using a dynamic scripting language such as JavaScript to control a more rigid body of classes written in a more strict, statically typed environment, such as C#, is a good way to manage complex software. All Mozilla software – including Firefox – is built using this model (JavaScript + XPCOM C++ components), and newer platforms, such as Microsoft’s Silverlight platform also use it (JavaScript + C# components).

I made a few tests with Unity, and it is simple to control and instance even pretty complex structures. I considered writing a simple Structure Synth viewer using Unity, but was unfortunately put a bit off, when I discovered that Screen Space Ambient Occlusion and Full Screen Post-Processing Effects are not part of the free basic edition. The iPhone version of the Unity engine is not free either, but that is probably as could be expected.

It will be interesting to see if Unity will be picked up by the Generative Art community.

SIGGRAPH Asia

Finally two papers presented at SIGGRAPH Asia 2009 should be noted:

Shadow Art creates objects which cast three different shadows.

Sketch2Photo creates realistic photo-montages from freehand sketches annotated with text labels.

Grammars for Generative Art (Part II)

As discussed in the previous part, formal grammars can be used to generate and manipulate text strings.

The question is how this can be extended to generate pictures, movies, or music.

One possibility would be to interpret the symbolic output as some sort of representation or encoding, which could be unfolded to create the final output.

For instance it would be rather simple to create a grammar, which created an SVG XML file for output. A wide used example of this approach is Lindenmayer systems, where the output is interpreted as a sort of ‘LOGO Turtle Graphics’.

Lindenmayer Systems

Lindenmayer Systems (or simply L-systems) are related to formal grammars, but in contrast to formal grammars which describe the syntax for the infinite number of sentences for a formal language, L-systems describe a generational process for manipulating text strings. They were used by Lindenmayer to simulate plant and tree growth.

In L-systems you iteratively apply all the production rules to the output of the previous iteration. L-systems do not have terminal symbols in the same sense as formal grammars do – so the expansion never stops. L-systems may, however, have optional constants which are not replaced and in this sense acts a bit like terminal symbols. In contrast to formal grammars, L-systems are not expected to terminate with a string of constants, they will keep on ‘growing’. Since the expansion never stops, L-systems are usually calculated for a given number of generations.

An example L-system:

A-> B-A-B
B-> A+B+A

Starting with the symbol ‘A’, this system would yield the following expansion: A, B-A-B, A+B+A-B-A-B-A+B+A, …., and so forth. Notice the difference to formal grammars: if these were production rules in a formal grammar, ‘B-B-A-B-B’ would be a valid sentence: this is not the case for L-systems, since all rules must be applied at each step.

The way L-system traditionally are used for generative purposes is by applying geometric semantics to the output: for instance, we could interpret A and B as moving one step forward, and + and – as turning 60 degrees clockwise or counter-clockwise. With this interpretation we get the following output:

– a fractal Koch curve.

‘The Algorithmic Beauty of Plants’ by Prusinkiewicz and Lindenmayer describes L-systems in details and is now available for free at Algorithmic Botany.

At this point I must admit that I always found L-systems to be quite dull and boring. Usually texts about L-systems are accompanied by Koch or Dragon curves and one or more simple plant or tree structure. However recently I stumbled upon this site: L-systems in Architecture by architect Michael Hansmeyer. Some of his creations are stunning, and the presentation is excellent, complete with step-by-step animations.


(Example image from L-Systems in Architecture.)

Context Free Design Grammar

In L-systems the symbol generation and the geometrical interpretation are two independent steps.

A perhaps more interesting approach is to embed the geometry inside the production rules. This requires a slight extension to the formal grammars.

Chris Coyne created the Context Free Design Grammar, which just like a formal grammar has production rules and non-terminal and terminal symbols – though it only has three terminal symbols: the ‘circle’, ‘square’ and ‘triangle’ geometrical primitives.

The Context Free Design Grammar extends the syntax of the formal grammars by including transformation operators (which are called ‘adjustments’ in CFDG terms). These transformation operators modify the current rendering state. Notice that while (rendering) states are being introduced in the CFDG, the actual expansion of a non-terminal symbol is still context-free. The CFDG also allows different weights to be assigned to each production rules.

Mark Lentczner and John Horigan created a cross-platform (Windows/Mac/Linux) graphical front-end simply called Context Free for CFDG. It is a wonderful little application – it is very easy to use and play around with.

Here is an example of CFDG code:

yielding the following output:

EisenScript and Structure Synth.

After I discovered Context Free I decided that I wanted to create a similar program for 3D geometry, a project that turned into the Structure Synth application.

In order to describe a grammar for 3D modelling I had to alter the CDFG syntax a little, which resulted in the EisenScript used in Structure Synth (named after the Russian film director Sergei Eisenstein).

I deliberately chose a new name, since I was not sure that the EisenScript was going to be a context free grammar – being slightly more pragmatic, I wanted to sacrifice the purity of CDFG for having more control over the graphical output. In particular, I added the possibility of ‘retiring’ rules: after a rule has reached a certain recursive depth, it can either be terminated or substituted by a new rule. (Actually I am a little in doubt, whether this ‘retiring’ is just a form of shorthand notation for specifying something which would be possible to express in a context free grammar). This ‘retiring’ rule makes it possible to create structure like a Menger sponge.

Also a few other alterations of CFDG were made:

The ‘startrule’ statement: in CFDG startrules are explicitly specified. In EisenScript, a more generic approach is used: statements which can be used in a rule definition, can also be used at the top-level scope. What actually happens is that Structure Synth collects everything at the top-level scope and creates an implicit start rule.

Termination criteria: in CFDG recursion automatically terminates when the objects produced are too small to be visible. This is a very elegant solution, but it is not easy to do in a dynamic 3D world, where the user can move and zoom with the camera. Several options exist in Structure Synth for terminating the rendering.

Transformation order: in CFDG transformations (which CFDG refers to as adjustments) in curly brackets are not applied in the order of appearance, and if multiple transformations of the same type are applied, only the last one is actually carried out. For transformations in square brackets in CFDG the order on the other hand is significant. In Structure Synth the transformation order is always significant and no transformations are omitted: transformations are applied starting from the right-most one. Also in CFDG the transformation are specified after the rule call, in EisenScript they must appear before the rule call.

An EisenScript program similar to the one above would look like this:

EisenScript example

EisenScript example (click to enlarge)

Of course there are also other obvious differences between CFDG and EisenScript: the transformation rules were altered to new 3D equivalents, and a new set of primitives were chosen. (Take a look at the EisenScript Reference for more details.).

Differences to procedural programming

An EisenScript grammar like the one above looks a lot like a ‘normal’ computer program – the syntax is actually quite close to the syntax of procedural programming languages like C, Java, Pascal, or Basic. And instead of thinking of EisenScript as a grammar and its output as sentences in the language specified by this grammar, it is perhaps easier to think of EisenScript as an ordinary computer language.

The similarities may be a bit deceptive though, since there are two major differences: functions (which are the rules in EisenScript) may have multiple definitions each with a arbitrary weight. And recursion is handled ‘breadth first’.

The last point requires an explanation: Whenever a procedural programming language executes a function or procedure, it does so in sequential order – the individual statements in the function are executed in the order of appearance. If one of the statements is a procedure call, this procedure is executed and must be completed before the next statement is executed. The state of the currently executing function (the return address pointer, local variables, …) are stored in stack frames on a call stack, in order to be able to return after executing a function. Put differently, this means the function call tree for the program is traversed ‘depth-first’.

Recursion in Structure Synth is handled differently. Instead of a call stack, there is generational stack: whenever a rule is encountered, all sub rules and primitives in the rule definition are pushed onto a new stack that will be evaluated at the next generation. This means the rules are traversed ‘breadth first’ – all calls at the same recursive depth are processed at the same time.

Consider the following example:

Procedure recurse() {
recurse(); // call myself
another(); // call another function
}

A traditional programming language would never reach the ‘another()’ function. It would recurse until the call stack overflowed. In contrast, In Structure Synth the first generation would process both the ‘recurse’ and ‘another’ statement. (When processing the ‘recurse’ statement it would schedule new ‘recurse’ and ‘another’ calls for the next generation).

Well, this concludes part II.

Part III will describe other grammar approaches to generative art and procedural modelling: namely Style Grammars and Shape Grammars.

Grammars for Generative Art (Part I)

For some time, I’ve wanted to write about the origins of Structure Synth – in particular Context Free and the design grammar approach.

Formal Grammars

The structure of both ordinary languages and computer languages have been studied for quite some time.

Formal grammars provide a way to exactly describe the structure of all valid sentences for a language. A formal grammar consists of production rules which describe valid transformations of symbol sequences. For instance a production rule might state that an English sentence consists of either a ‘Simple Sentence’ of a ‘Compound Sentence’.

Of course we cannot stop here – ‘Simple sentence’ is not a terminal symbol – it needs to be replaced and broken down into one or more terminal symbols. The terminal symbols in English would be the actual English words, while the non-terminal symbols would be structural placeholders such as ‘Simple sentence’ or ‘Verb phrase’.

Here is an example for an incomplete grammar for the English language:


[English Sentence] = [Simple Sentence] | [Compound Sentence]
[Simple Sentence] = [Declarative Sentence] | [Interrogative Sentence] | [Imperative Sentence] | [Conditional Sentence]
[Declarative Sentence] = [subject] [predicate]
[subject] = [simple subject] | [compound subject]
[simple subject] = [noun phrase] | [nominative personal pronoun]
[nominative personal pronoun] = "I" | "you" | "he" | "she" | "it" | "we" | "they"
[predicate] = ([verb] | [verb phrase]) [complement]
[verb] = [linking verb] | ...
[linking verb] = "am" |"are" |"is" | "was"| "were" | ....

The rules above are only a tiny fragment (see more here).

Generating output

While formal grammars are perhaps mostly used in Computer Science for parsing and checking the syntax of computer languages, they have interesting applications in other domains. For instance, it is possible to create a formal grammar for a specific domain of a natural language, and then use the grammar to generate random sentences:

SCIgen is an example of a generator, which builds random computer science papers. As can be seen from the example above it is not difficult to generate a valid sentence if the formal grammar is at hand – just pick your start symbol (e.g. ‘English Sentence’) and choose at random one of the possible substitutions. Continue doing this until only terminal symbol are left.

SCIgen actually managed to get one of its generated papers accepted at the WMSCI 2005 conference. Here is a fragment of the grammar used:


EVAL_ANALYZE_ONE = note the heavy tail on the CDF in EXP_FIG, exhibiting DIFFERENT EVAL_MEASUREMENT
EVAL_ANALYZE_ONE = the many discontinuities in the graphs point to DIFFERENT EVAL_MEASUREMENT introduced with our hardware upgrades
EVAL_ANALYZE_ONE = bugs in our system caused the unstable behavior throughout the experiments
EVAL_ANALYZE_ONE = Gaussian electromagnetic disturbances in our EXP_WHERE caused unstable experimental results
EVAL_ANALYZE_ONE = operator error alone cannot account for these results

Here the upper cased words are the non-terminals, which are to be substituted. The complete grammar (with ~3000 production rules) can be found here: scirules.in. Also more respectable institutions have accepted SCIgen papers – in 2007 the Elsevier journal ‘Applied Mathematics and Computation’ accepted this article (now removed – but read more about this at the SCIgen blog).

Another spectacular (and funny) example of grammar generated text is the Postmodernism generator (based on the Dada Engine). It creates postmodernistic ramblings that would have made Alan Sokal proud!

Context Free Grammars

In the fifties Noam Chomsky categorized the formal grammars into four classes.

This classification can be understood in terms of how the productions rules look: For instance, for the third class – the socalled Context Free Grammars – the left hand side of the production rule is always a single non-terminal symbol (this is also the case for the natural language examples above). This means, that it is possible to apply the production rule no matter where the given non-terminal symbol is placed – the production rule is not dependent on the context of the symbol.

While formal grammars have interesting applications in computer science and natural language research, they are merely tools for analyzing or generating symbol sequences. In Part II I’ll describe the Context Free Design Grammar used in Context Free, and its relation to the EisenScript used in Structure Synth.

The Second Coming of JavaScript

Some months ago, John Resig created processing.js – an impressive JavaScript port of processing, which draws its output on a ‘canvas’ element entirely client-side inside your browser (at least if your web-browser is Firefox 3 or a recent nightly build of WebKit, that is).

Now Context Free (the original inspiration for Structure Synth) has been ported to JavaScript too: Aza Raskin has created ContextFree.js (Source here).

JavaScript has undergone a tremendous evolution. From creating cheesy ‘onMouseOver’ effects for buttons on web pages to being the ‘glue’ binding together complex applications like Firefox or Songbird (the Mozilla application frameworks works by stringing together C++ components with JavaScript). Likewise Microsoft chose to build their Silverlight technology on .NET components which can be controlled by JavaScript in the browser.

And of course the ActionScript in Adobe Flash is also JavaScript. Adobe (and/or Macromedia) has put a lot of effort into creating fast JavaScript implementations – most notably their Tamarin virtual machine and Just-In-Time compiler, which in theory should make JavaScript almost as fast as native code – or at least comparable to other JIT compiled languages such as Java and the .NET languages. Tamarin is open-sourced, and will eventually make it into Firefox 4.

Finally, while the Tamarin virtual machine was built to execute (and JIT) bytecode originating from JavaScript, other languages may target Tamarin as well. Adobe has demonstrated the possibility of compiling standard C programs into Tamarin parseable byte-code (their demo included Quake, a Nintendo emulator, and several languages like Python and Ruby).

So perhaps a future version of Structure Synth could be running as C++ compiled into Tamarin bytecode in a Flash application…

(Structuring) Structure Synthesis

Well, I started worked on a spare time project, called Structure Synth: a small application for generative structure synthesis (in 3D). The app itself will be built around an embedded editor with a OpenGL visualization window next to it. Here is a mock-up shot:

Structure Synth GUI

Structure Synth GUI

The structures are designed in a simple language, EisenScript (named after the Great Russian director, Sergei Eistenstein, of course). It will be similar, but not identical, to the Context Free Design Grammer that Context Free uses.

An EisenScript defines a Rule Set, where each rule is defined as a number of Actions.

An Action would typically be to perform a Transformation and either call another rule, or one of the built-in drawing primitives. As in Context Free rules can be defined recursively in terms of themselves.

Rules are allowed to be ambiguous: more than one definition for a rule can exist, and when ambiguous rules are encountered the Builder will choose one at random. Again, as in Context Free, it will also be possible to specify a weighting for each of the rule definitions.

Here is an example of how an EisenScript rule set might look:

EisenScript example

Structure Synth will be built in C++/Qt4.3/OpenGL and will be Open Source (GPL). It should be cross-platform (Windows, Linux, and Mac).

I’ve started a subversion repository here (Google Code Hosting), but will probably move to SourceForge.

Generative Art

The Syntopia logo above was created by my first script in Context Free, a program I can highly recommend. It is a bit like Logo (does anyone remember this?) on steroids.

However, I’ve been thinking of ways of extending Context Free into 3D, and will start posting some of my design sketches for Structure Synth – an IDE/Language for creating generative art (like Context Free).

I plan to write it in C++/Qt4.3/OpenGL and it should be runnable on Windows/Mac/Linux.

Variation on the Syntopia Logo

Variation on the Syntopia Logo

For an example of a Context Free script, the syntax for the above picture can be downloaded here: circles.cfdg.

The syntax for Structure Synth will be quite similar to CFDG-script but with a few twists: like the ability to ‘retire’ rules after a certain number of either recursions or iterations, and the option to change (rendering) settings when a rule is executed. Naturally the ‘state’ operators (like rotations and deformations) also need to be adapted to a 3D world.

There will be an integrated OpenGL viewer, and I plan to add PovRay support for creating high-quality views of the 3D-models.

More details will follow in the next weeks.