Learn to Cry by writing parse trees in Ruby
Thursday, June 5th, 2008
Cry is a Ruby library that provides a nice object oriented way to create, transfer, and manipulate frozen parse trees. The idea behind the name is that you end up writing in parse tree format, in a syntax more verbose than CLOS… hence “Cry” =) In reality Cry would mainly be used in meta-programming though, and is designed to have a simple & consistent api.
Let’s say we have an instance of an “Account” class stored in the local variable “acnt”. It has a “withdraw” method that takes an “amount” parameter.
In Ruby you would normally call this method like so:
acnt.withdraw(50)
In Common Lisp’s CLOS you would do it like this:
(withdraw acnt 50)
Notice that because CLOS deals with objects, the second parameter is the instance of the class that the method will be called on. Cry copies this parameter order in its parse trees:
Cry::ParseTree.new(:withdraw, acnt, 50).evaluate
In Ruby classes are just instances of the “Class” class. Thus, the syntax for class methods remains the same:
Cry::ParseTree.new(:sqrt, Math, 16).evaluate # => 4.0
Another neat thing is that the parse tree instances are not evaluated until you call the evaluate method. This lets you pass them around, similar in concept to Procs (aka lambdas.)
parse_tree = Cry::ParseTree.new(:+, Cry::ParseTree.new(:*, 2, 3), Cry::ParseTree.new(:/, 16, 2)) # => (:+, (:*, 2, 3), (:/, 16, 2))
parse_tree.evaluate # => 14
Notice that the object and any of the parameters can each be parse trees as well (and even those can continue recursively nesting parse trees with their respective objects and parameters.)
There are also convenient getter methods for our parse tree components:
parse_tree.node_method # => :+
parse_tree.node_object # => (:*, 2, 3)
parse_tree.node_arguments # => [(:/, 16, 2)]
Similarly, there are setters that could be used like this:
parse_tree.node_object = parse_tree.node_object.evaluate # => 6
parse_tree.node_arguments = parse_tree.node_arguments.map{|p| p.evaluate } # => 8
parse_tree.evaluate # => 14
The previous example takes components of our parse tree and evaluates them separately, then sets the results back. This opens up possibilities for having a very deeply nested parse tree, and evaluating certain sections in parallel.
In traditional Ruby the above can be explicitly written like so:
2.*(3).+(16./(2)) # => 16
The big difference is that this would be evaluated immediately, whereas you can delay and manipulate the whole structure by using a parse tree.
We previously used setter methods to manually evaluate the parse trees for the object and arguments. However, we could also change something, such as the object:
parse_tree.node_object = 5
parse_tree.evaluate # => 40
Or, we could change every part of the parse tree:
parse_tree.node_method = :new
parse_tree.node_object = Array
parse_tree.node_arguments = [5, 9]
parse_tree.evaluate # => [9, 9, 9, 9, 9]
Certain methods are defined with blocks, for these simply pass in a Proc as the last argument:
# Traditional Ruby
[1, 2, 3].inject(2) {|sum, i| sum + i } # => 8
# Cry::ParseTree Ruby
parse_tree = Cry::ParseTree.new(:inject, [1, 2, 3], 2, lambda{|sum, i| sum + i })
parse_tree.evaluate # => 8
Cry::ParseTree extends from Array, and internally stores the method, object, and arguments in that order respectively. Knowing this, we could have done the following to switch out the block to be used for our parse tree:
old_block = parse_tree.pop
parse_tree.push lambda{|product, i| product * i }
parse_tree.evaluate # => 12
We have access to all methods Array does, so this would work too:
parse_tree.each {|p| puts p.inspect }
:inject
[1, 2, 3]
2
#<Proc:0x0005526c@(irb):67>
=> (:inject, [1, 2, 3], 2, #<Proc:0x0005526c@(irb):67>)
That about wraps things up. If you would like to follow development, or fork/contribute to the project, you can find Cry on github. Even if you just wonder if something will work, feel free to try out your Ruby parse tree masterpieces by adding funky ones as tests.
In case anyone is interested, I made this so I could have an easy datastructure to manipulate when dealing with Genetic Programming algorithms. I’m working on an interesting project that involves them, and will be sure to put it on github and make a post when it’s ready.
I really like the concept of the Uniform Interface. One of my favorite things to do is spend hours on my whiteboard (and sometimes days) fiddling with ideas that express what I consider to be elegance. This ranges from macroscopic elegance (ie: the architecture level) to microscopic elegance (ie: the function/method level). Somewhere in the middle lies my fascination with sets, my favorite topic in Discrete Mathematics.
