Facilitating the Spread of Knowledge and Innovation in Professional Software Development

Write for InfoQ


Choose your language

InfoQ Homepage News Using ParseTree for LINQ-style queries and extracting metadata

Using ParseTree for LINQ-style queries and extracting metadata

With the introduction of  LINQ in .NET and the resurging interest in LISP, a certain type of metaprogramming has received renewed attention. In LINQ, it's possible to get the Expression Trees, i.e. a tree based representation, of a piece of code.

In LISP (and similar languages), this approach is known as a macro or macro expansion. Macros look like function calls, with the difference that they're evaluated at compile time, i.e. when the code is loaded. The macro gets the Abstract Syntax Tree (AST) of the macro call, but the call is then replaced with the AST the macro returns. This means that the macro call is not the code that actually gets executed, instead it's the returned AST of the macro that gets executed the, i.e. a macro call is expanded to the actual code.

While Ruby doesn't have language support for accessing the AST of a piece of code, there are libraries to handle that. The most popular one is ParseTree, which returns the AST as a s-expr representation, i.e. nested lists of symbols and literals. A group of useful tools are built by the providers of ParseTree, such as
  • Ruby2Ruby
    The tool takes ParseTree ASTs and formats them as Ruby source code. This allows to parse Ruby code, modify it at the AST level (instead of working with the characters of the source code) and finally generate runnable Ruby code again.
  • Heckle
    A tool by Ryan Davis and Kevin Clark that uses Ruby2Ruby to introduce random changes into code to find code with insufficient test coverage.

A new set of libraries is now making use of ParseTree in a way reminiscent of LINQ. Ambition allows to write queries in Ruby syntax, e.g. { |m| == 'jon' && m.age == 21 } 
Or { |m| == 'jon' && m.age == 21 } 
The code inside these Blocks is never actually executed - instead ParseTree is used to get at the AST. This is then analyzed and translated into queries for the target query language. Ambition features extensible adapters, which allow to write new translators from Ruby ASTs to query languages.

Another library that adds this style of queries is Sequel. While it's primarily an ORM, Sequel also allows to write queries in Ruby:
old_nonruby_posts = posts.filter {:stamp > 1.month.ago && :category != 'ruby'} 
It's important to note that, unlike Ambition, this is just one of Sequel's ways of writing queries - it also allows to put the queries in string literals.

A very different way of making use of the AST of Ruby code can be found in Merb. It is used in Parameterized Actions:
Parameterized Actions:
If you specify parameters in your action methods, incoming query parameters will automatically get assigned as appropriate. Some examples:
class Foos < Merb::Controller
 def index(id, search_string = "%")
 @foo = Foo.find_with_search(id, search_string)
Going to /foos/index/12 will call the index method with the parameters "12" and "%" (the default provided). Going to /foos/index will throw a BadBehavior error (status code 400) because id is a required parameter, but it was not passed in. Going to /foos/index/5?search_string=hello will call the index method with parameters "5" and "hello". The bottom line is that you get to use your actions like real methods.
The feature is implemented by looking getting the AST of the method that handles the action, and extracting the default arguments. In a way, this allows a kind of introspection/reflection that's not normally available.

These examples show the power of this type of introspection. However, Sequel and Merb also show one downside of this approach: the ParseTree based features are optional, i.e. the tools don't rely on them. If ParseTree is not available on the system, these features are simply not available. This is due ParseTree's nature as a native Ruby extension. Some of the deployment problems of a native extension are being solved, eg. ParseTree on Windows or ParseTree on MacOS X.
Problems remain though. ParseTree doesn't support Ruby 1.9 yet, although possible solutions are being considered. Ruby 1.9 actually comes with some access to ASTs with Ripper. There's very little information available about Ripper, but one way of using it is as a SAX-style parser. Eg.
require 'ripper'
 class MyRipper < Ripper
 def on_gvar(node)
 puts node
 def on_int(node)
 puts node
 # etc.
 # Handle each element of the AST with an on_* method
This can then be used as such:
f ="$foo = 1") 
Next to Ruby 1.9 support, ParseTree also has varying support on alternative Ruby implementations. Rubinius makes heavy use of ParseTree AST representation. JRuby has a nearly complete port of ParseTree, but the .NET based Ruby implementations seem to be without support for now.

Rate this Article