How to express a context free design grammar as an internal DSL in Python?

[Note: Rereading this before submitting, I realized this Q has become a bit of an epic. Thank you for indulging my long explanation of the reasoning behind this pursuit. I feel that, were I in a position to help another undertaking a similar project, I would be more likely to get on board if I knew the motivation behind the question.]

I have been getting into Structure Synth by Mikael Hvidtfeldt Christensen lately. It is a tool for generating 3D geometry from a (mostly) context free grammar called Eisenscript. Structure Synth is itself inspired by Context Free Art. Context free grammars can create some stunning results from surprisingly simple rulesets.

My current Structure Synth workflow involves exporting an OBJ file from Structure Synth, importing it into Blender, setting up lights, materials, etcetera, then rendering with Luxrender. Unfortunately, importing these OBJ files often brings Blender to a grinding halt as there can be thousands of objects with fairly complex geometry. I say 'fairly' because Structure Synth only generates basic shapes, but a sphere represented by triangles still has many faces.

Thus, generating the structures directly in Blender would be preferable to the current process (Blender's deep support for Python scripting should make this possible). An intelligent Python library could use Blender's instancing abilities to use one mesh to generate myriad objects, thus saving memory. Plus Blender is a full-featured 3D suite and its ability to interpret a CFDG would provide creative possibilities far beyond what Structure Synth can offer.

And so my question is how best to translate the Eisenscript grammar into a Python DSL. Here's what a simple Eisenscript looks like:

set maxdepth 2000
{ a 0.9 hue 30 } R1 

rule R1 { 
  { x 1  rz 3 ry 5  } R1
  { s 1 1 0.1 sat 0.9 } box
}

rule R1 { 
  { x 1  rz -3 ry 5  } R1
  { s 1 1 0.1 } box
}

To explain, the first call to R1 (line 2) will randomly invoke one of the two definitions of R1. Each definition of R1 recursively calls R1 (randomly invoking one of the two definitions) and also creates a box. The first line kills generation after recursion has gone 2000 levels deep.

Jeremy Ashkenas (of CoffeeScript fame) successfully imple开发者_开发问答mented a context free DSL in Ruby using blocks. Internally, it works by creating a hash key for each rule 'name', and stores the blocks for each definition of that rule in an array, to be randomly chosen when the rule is invoked.

The previous Eisenscript rule definitions would translate to the Ruby DSL like so:

rule :r1 do
  r1 :x => 1, :rz => 3, :ry => 5
  box :s => [1, 1, 0.1], :sat => 0.9
end

rule :r1 do
  r1 :x => 1, :rz => -3, :ry => 5
  box :s => [1, 1, 0.1]
end

I am a novice Python user and so have been doing some research on Python's functional programming capabilities. It seems like lambda is too limited to create something similar to Jeremy's Ruby DSL, and, as far as I can tell, lambda is the only option for anonymous functions?

How might an experienced Pythonista approach the design?

Writing a parser for a context free grammar is hard. You're probably better off using some sort of library to make things easier on yourself.

I would check out the PyParsing module. The download comes with a number of examples, one of which is a simple SQL parser, which might be enlightening to look at, at least as a first step.

I decided to build the initial prototype by translating the Ruby library's blocks into predefined functions that are passed into the ContextFree instance, augmented with a condition to avoid infinite loops, and added to the instance as instance methods. Here's the current state. Critique is welcome; this is some of my first Python code and I'm ready and willing to retrain my Ruby idioms to Python idioms.

import random

class ContextFree(object):
  def __init__(self):
    self.rules = {}
    # grab any instancemethod to get an instance of the instancemethod class
    self.instancemethod = type(self.add_rule)
    self.max_depth = 100
    self.depth = 0

  def add_rule(self, func, prob=1):
    rule_name = func.__name__

    if not rule_name in self.rules:
      self.rules[rule_name] = { 'funcs' : [], 'total' : 0 }

    total = self.rules[rule_name]['total']
    self.rules[rule_name]['funcs'].append([range(total,(prob+total)), func])
    self.rules[rule_name]['total'] += prob

    def augmented_func(self, options={}):
      if not self.depth >= self.max_depth:
        self.depth += 1
        pick = self.determine_rule(rule_name)
        print('Generation', self.depth)
        pick(self)

    self.__dict__[rule_name] = self.instancemethod(augmented_func, self)

  def determine_rule(self, rule_name):
    rule = self.rules[rule_name]
    winning_number = random.randrange(0, self.rules[rule_name]['total'])
    for func in rule['funcs']:
      if winning_number in func[0]:
        return func[1]

cf = ContextFree()

def box(self):
  print('Rule for box1')
  self.box()

cf.add_rule(box)

def box(self):
  print('Rule for box2')
  self.box()

cf.add_rule(box)

cf.box()

# Output:
## Generation 1
## Rule for box2
## Generation 2
## Rule for box2
## Generation 3
## Rule for box1
## Generation 4
## Rule for box2
## Generation 5
## Rule for box1
## Generation 6
## Rule for box2
## Generation 7
## Rule for box2
## Generation 8
## Rule for box1
## Generation 9
## Rule for box2
## Generation 10
## Rule for box2
## Generation 11
## Rule for box1
## Generation 12
## Rule for box1
## Generation 13
## Rule for box1
## Generation 14
## Rule for box1
## Generation 15
## Rule for box2
## Generation 16
## Rule for box1
## Generation 17
## Rule for box1
## Generation 18
## Rule for box1
## Generation 19
## Rule for box1
## Generation 20
## Rule for box1
## Generation 21
## Rule for box2
## Generation 22
## Rule for box2
## Generation 23
## Rule for box1
## Generation 24
## Rule for box2
## Generation 25
## Rule for box1
## Generation 26
## Rule for box2
## Generation 27
## Rule for box2
## Generation 28
## Rule for box1
## Generation 29
## Rule for box2
## Generation 30
## Rule for box2
## Generation 31
## Rule for box2
## Generation 32
## Rule for box2
## Generation 33
## Rule for box2
## Generation 34
## Rule for box1
## Generation 35
## Rule for box2
## Generation 36
## Rule for box1
## Generation 37
## Rule for box1
## Generation 38
## Rule for box1
## Generation 39
## Rule for box1
## Generation 40
## Rule for box2
## Generation 41
## Rule for box1
## Generation 42
## Rule for box1
## Generation 43
## Rule for box1
## Generation 44
## Rule for box1
## Generation 45
## Rule for box2
## Generation 46
## Rule for box1
## Generation 47
## Rule for box2
## Generation 48
## Rule for box1
## Generation 49
## Rule for box2
## Generation 50
## Rule for box1
## Generation 51
## Rule for box1
## Generation 52
## Rule for box1
## Generation 53
## Rule for box2
## Generation 54
## Rule for box2
## Generation 55
## Rule for box2
## Generation 56
## Rule for box2
## Generation 57
## Rule for box2
## Generation 58
## Rule for box1
## Generation 59
## Rule for box1
## Generation 60
## Rule for box1
## Generation 61
## Rule for box2
## Generation 62
## Rule for box2
## Generation 63
## Rule for box2
## Generation 64
## Rule for box1
## Generation 65
## Rule for box2
## Generation 66
## Rule for box2
## Generation 67
## Rule for box2
## Generation 68
## Rule for box2
## Generation 69
## Rule for box2
## Generation 70
## Rule for box1
## Generation 71
## Rule for box2
## Generation 72
## Rule for box2
## Generation 73
## Rule for box2
## Generation 74
## Rule for box1
## Generation 75
## Rule for box2
## Generation 76
## Rule for box1
## Generation 77
## Rule for box1
## Generation 78
## Rule for box2
## Generation 79
## Rule for box1
## Generation 80
## Rule for box2
## Generation 81
## Rule for box1
## Generation 82
## Rule for box1
## Generation 83
## Rule for box1
## Generation 84
## Rule for box1
## Generation 85
## Rule for box2
## Generation 86
## Rule for box1
## Generation 87
## Rule for box1
## Generation 88
## Rule for box2
## Generation 89
## Rule for box2
## Generation 90
## Rule for box1
## Generation 91
## Rule for box1
## Generation 92
## Rule for box1
## Generation 93
## Rule for box1
## Generation 94
## Rule for box1
## Generation 95
## Rule for box1
## Generation 96
## Rule for box2
## Generation 97
## Rule for box1
## Generation 98
## Rule for box2
## Generation 99
## Rule for box1
## Generation 100
## Rule for box2