Grammars for Generative Art (Part III)

Part three of a mini-series on using grammars as generators:

• Part I was about Context-Free Grammars and natural language parsing.

• Part II was about Lindenmeyer systems, Context Free design grammars, and Structure Synth.
• Part IV will be about Style Grammars and Shape Grammars.

Issue 1: Fall 2008

(From Issue 1: Fall 2008)

In October 2008, Stephen McLaughlin and Jim Carpenter released ‘Issue 1: Fall 2008′, a 3785 page compilation of poems by more than 3000 contemporary American poets. (Download here).

Besides the stunning size of the book, this would probably have gone relatively unnoticed, if it weren’t for the fact that the 3000+ authors had not submitted any poems to the editors. Neither were they able to recognize any of the poems as their own. This of course created quite a stir.

It turns out that the book was generated by Erica T Carter, which actually is the name of a computer program written by Jim Carpenter.

Erica T Carter

Erica T Carter (ETC3) uses Tree-Adjoining Grammars (TAGs) for generating poems. TAGs are related to formal grammars, but instead of production rules operating on symbolic sequences, TAGs operate on trees.

Considering the example above, a tree may be inserted (substituted) into another tree, if its root node matches a terminal node (the a-2 and a-3 trees may be attached to the NP non-terminal). Besides the substitution operation, it is also possible to do adjoining operations, where a tree may be expanded by inserting another tree inside it (this paper has a short introduction to TAGs).

‘Erica T Carter’ is open source and may be downloaded (or tested) here.

Judging from the source and comments, the phrase structures in the TAGs were handpicked by Jim Carpenter after analyzing works by Frank O’Hara, Sylvia Plath, Gary Snyder, and Rachel Blau DuPlessis (not that I have read anything by them). In the online version of Erica, the default grammar choice is the 166-trees ‘Mimetic’ grammar, which is described as an amalgam of the rest of the grammars – I’m guessing that this is the one used for ‘Issue 1: Fall 2008′.

In addition to the trees, Erica uses a lot of extra information from a 30MB database (public available from the site too). The database contains lexicon tables with entries like ‘abashless = adj’ and ‘abate = v’ apparently based on Emily Dickinson Poems and Joseph Conrad’s Heart of Darkness (‘Apocalypse Now’). The database also contains more exotic tables, like ‘pronunciation’ (‘anachronism = AH0 N AE1 K R AH0 N IH2 Z AH0 M’) which may be used to construct rhymes.

The auto-generated poems seems very impressive, but after skimming through the text some patterns emerge, which seems unlikely if the poems were to be written by different (human) authors: for instance 2205 lines start with “Like a …” (that is 4% of the 55685 total lines!).

On the other hand the poems impress by containing cross serial dependencies as in this example:

Where both the title and content of the poem refer to ‘background’. This particular feature – where different parts of the generated sentences correlate – is difficult to achieve with context free grammars, since the substitutions of symbols does not depend on how other symbols are expanded.

Tree Adjoined Grammars and Context Sensitivity

Tree Adjoined Grammars fits in between the Context Free and Context Sensitive classes in the Chomsky Hierarchy: they describe Mildly Context-sensitive languages.

Where as Context Free grammars have the pleasant property of being parsable in polynomial space and time, they are not adequate for describing for example the natural languages (features such as cross serial dependencies and agreements are difficult to capture: for instance a formal grammar for a natural language may contain ‘noun’ and ‘verb’ non-terminals. But nouns and verbs depend on each other – something which is not easily expressed in a context free grammar, leading to output such as ‘Words is funny’).

So the Mildly context-sensitive languages provide a middle ground – they are better at capturing the structure of natural languages, but still not as difficult to handle as a true context-sensitive language.

Generative Art and the Freedom of Restrictions

Now, why even care about the complexity of the grammars? After all we are not interested in analyzing syntax or deriving mathematical properties of the grammars, we are interested in generating structure.

For instance, why restrict Context Free Art and Structure Synth to context free systems? The cost of generating structures does not increase by switching to a more powerful grammar, only the cost of analyzing the systems.

I think the answer relates to the very essence of ‘generative art’.

For me, generative art is all about exploring systems, without being too much in control. When generating structures, it should not be possible to anticipate how a given structure turns out by looking at the rules. There should be a sense of indeterminism and surprise in the result. The system needs not to necessarily be driven by random choices in order to achieve this – for instance the Mandelbrot set is a good example of this: nobody would have been able to imagine how complex images a simple system like “z -> z^2+c” could create, yet there is nothing stochastic in the generation of the set.

Choosing to work within a restricted rule system is a way to give up some control and force yourself to think differently. You have to explore and work within the limitations of the system, which may lead to interesting and surprising results.

More generic languages, for instance the popular Java-based Processing, have no limitations in expressiveness (Java, like all other general purpose programming languages, is Turing complete). Is Processing not suitable for generative art, because of its universal expressive power? Well, the answer is of course that Processing is very suitable and it is indeed widely used for producing generative art. In fact any Structure Synth or Context Free Art system could be emulated in Processing/Java because of this universal power. But Processing is also suitable for many other applications, like for instance Data Visualization and other non-generative tasks. Context Free Art and Structure Synth on the other hand force you to explore generative systems.

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 (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.