Exploring Boo’s Abstract Syntax Tree (AST)

Currently I’m going through AST, but the documentation is scarce. AST is in-memory tree representation of code that can be modified and is used while creating syntactic macros. I was wondering what is the best way to check how syntax is transformed to AST when I came across Luis Diego Fallas’ post in which he shows a little application that parses Boo source file and displays AST in tree control. Unfortunately there are some issues with this application. Firstly, it contains a bug and doesn’t show full syntax tree. Secondly, it only displays node names without information what code the node represents. So I decided to modify his code and fix this. Here is a sample screenshot:

There is AST tree structure of code on the left and information about selected subtree on the right. It includes the code itself and serialized form of the subtree. Name of the file to parse is passed to the application as a parameter.

Visitor pattern is employed to visit all nodes in AST tree. Unfortunately deriving from Boo’s DepthFirstVisitor is a tedious task, because there are as many methods to override as there are AST node types. Luis proposed a solution basing on dynamically created type, that derives from DepthFirstVisitor. Method overrides are constructed in-memory from AST nodes and then the dynamic type is compiled. While being compact, this solution is not very readable, especially when you’re not familiar with AST. Fortunately there seems to be alternative way to do this, namely the mysterious [| <code here> |] syntax. I think it’s called quasiquotes. I couldn’t find any documentation for this, only one example in Boo package. From what I was able to figure out, this code (where m is instance of MethodInfo class):

// Node for TreeNode('')
tnCreation = MethodInvocationExpression(ReferenceExpression("TreeNode"))                                 
tnCreation.Arguments.Add(
        StringLiteralExpression(m.GetParameters()[0].ParameterType.Name))

// Create node for 't = TreeNode('')' 
decl = DeclarationStatement(
      Declaration: Declaration(Name:"t",
                 Type: SimpleTypeReference("System.Windows.Forms.TreeNode")),
      Initializer: tnCreation)

is equivalent to this code:

decl = [| t = TreeNode($(m.GetParameters()[0].ParameterType.Name)) |] 

So there is a huge improvement. Code between [| and |] is being transformed to AST and assigned to a variable. The $() construct is similar to string interpolation construct. It allows you to insert a string from variable as if it was part of the code (here it is a parameter of the TreeNode constructor, but it also can be a method name for example). When using this syntax, you have to be careful about the indentation. It seems that statements can be in the same line as [|, but when declaring members, they have to be in new line and indented. Otherwise you get compilation errors.

Luis has overridden “Enter*” and “Leave*” (for example EnterBlockExpression) methods of DepthFirstVisitor, which is a problem because “Enter*” and ”Leave*” methods exist only for nodes that can contain subnodes. So for example there is no Enter method for IntegerLiteralExpression node. In my code I override the “On*” methods.

Here is the full code:

import System
import System.Reflection
import System.IO
import Boo.Lang.Compiler
import Boo.Lang.Compiler.Ast
import Boo.Lang.Compiler.Ast.Visitors
import Boo.Lang.Parser
import System.Windows.Forms
import System.Xml.Serialization
import System.Drawing


// Get the type instance for DepthFirstVisitor
a = Assembly.Load("Boo.Lang.Compiler")
visitorType = a.GetType("Boo.Lang.Compiler.Ast.DepthFirstVisitor")

// Create a class definition for a custom visitor
myVisitor = ClassDefinition(Name: "DynamicVisitor")
myVisitor.BaseTypes.Add(SimpleTypeReference("Boo.Lang.Compiler.Ast.DepthFirstVisitor"))

// Add a new field for our node stack
stackField = [| 
    public stack as System.Collections.Stack 
|]
myVisitor.Members.Add(stackField)

// Override On* methods
for m as MethodInfo in [m for m in visitorType.GetMethods() if m.Name.StartsWith("On")]:
    method = [|
        def $(m.Name)(node as $(m.GetParameters()[0].ParameterType.FullName)):
            t = TreeNode($(m.GetParameters()[0].ParameterType.Name))
            t.Tag = node;
            (stack.Peek() as TreeNode).Nodes.Add(t)
            stack.Push(t)
            // call method in superclass to visit subtrees
            super.$(m.Name)(node)
            stack.Pop() 
    |]
    myVisitor.Members.Add(method)

// Compile unit and module creation
cu = CompileUnit()
mod = Boo.Lang.Compiler.Ast.Module(Name:"Module")
cu.Modules.Add(mod)

mod.Imports.Add(Import(Namespace:"System"))
mod.Imports.Add(Import(Namespace:"System.Windows.Forms"))
mod.Imports.Add(Import(Namespace:"Boo.Lang.Compiler.Ast"))
mod.Members.Add(myVisitor)

// Initialize compiler preferences
pipeline = Pipelines.CompileToMemory()
ctxt = CompilerContext(cu)

// Run the compiler
pipeline.Run(ctxt)

// Check the results
if(ctxt.GeneratedAssembly == null):
    for e in ctxt.Errors:
        print e
    Console.ReadLine()
    return    

// Create an instance of the new visitor and initialize it
visitorInstance as object = ctxt.GeneratedAssembly.CreateInstance("DynamicVisitor");
visitorType = ctxt.GeneratedAssembly.GetType("DynamicVisitor")
tStack = System.Collections.Stack()
tStack.Push(TreeNode("root"))
visitorType.GetField("stack").SetValue(visitorInstance, tStack);

// Parse a file an run the visitor
compileUnit = BooParser.ParseFile(argv[0])
compileUnit.Accept(visitorInstance)

//Initialize a form an show the results
frm = Form(Text: "AST content", Width: 800, Height: 600)
outerSplit = SplitContainer(Dock: DockStyle.Fill, Orientation: Orientation.Vertical)
innerSplit = SplitContainer(Dock: DockStyle.Fill, Orientation: Orientation.Horizontal)
definitionText = TextBox(Dock: DockStyle.Fill, Multiline: true, 
    ScrollBars: ScrollBars.Both, Font: Font("Courier New", 8.0))
xmlText = TextBox(Dock: DockStyle.Fill, Multiline: true, 
    ScrollBars: ScrollBars.Both, Font: Font("Courier New", 8.0))

tv = TreeView(Dock: DockStyle.Fill)

tv.AfterSelect += def (sender as object, e as TreeViewEventArgs):
    if e.Node.Tag != null:
        writer = StringWriter()
        BooPrinterVisitor(writer).Visit(e.Node.Tag as Node)
        definitionText.Text = writer.ToString()
        
        serializer = XmlSerializer(e.Node.Tag.GetType())
        writer = StringWriter()
        serializer.Serialize(writer, e.Node.Tag)
        xmlText.Text = writer.ToString()

tv.Nodes.Add(tStack.Pop() as TreeNode)
frm.Controls.Add(outerSplit)
outerSplit.Panel1.Controls.Add(tv)
outerSplit.Panel2.Controls.Add(innerSplit)
innerSplit.Panel1.Controls.Add(definitionText)
innerSplit.Panel2.Controls.Add(xmlText)
Application.Run(frm)

Some highlights:

• There is a BooPrinterVisitor class in Boo.Lang.Compiler.Ast.Visitors namespace, that converts AST to source code. Unfortunately this class doesn’t support quasiquotes, so passing a file with quasiquotes will result in exception.
• The file passed to the application doesn’t necessarily have to be compilation error free. It can contain macros, that are not yet defined. This way you can write your desired syntax, and then use this application to see how it is parsed. This should make macro implementation easier.

An example of IQuackFu usage in Boo

The IQuackFu interface lets you intercept calls to a duck type when called method or property doesn’t exist. You can use this to achieve many interesting things. In Boo’s examples there is a class for accessing XML data and also a class that allows dynamic inheritance. The IQuackFu interface has three methods:

• QuackInvoke(name as string, args as (object)) as object – intercepts method calls
• QuackSet(name as string, parameters as (object), value) as object – intercepts property setter calls
• QuackGet(name as string, parameters as (object)) as object – intercepts property getter calls

As you can see each method has a name argument, which contains a name of the called method or property. This name can be parsed and appropriate action can be taken. My example will be a simple class for accessing data in a database table. Methods called on this class should be in form of:

Get <table name> By <column 1> [And <column 2> And …] ( <value 1> [, <value 2>, …] )

The method name specifies which table will be queried and what columns will be used in the WHERE clause. Arguments of the method specify values for the filter. The method returns a DataSet. Here is the code:

import System
import System.Text.RegularExpressions
import System.Collections.Generic
import System.Data.SqlClient
import System.Data

class Repository(IQuackFu):
    
    def QuackInvoke(name as string, args as (object)) as object:

        match = /^Get(?<table>\w+)By(?<column>\w+?)(And(?<column>\w+?))*$/.Match(name)
        if match != null and match.Success:
            table = match.Groups["table"].Value
            
            params = List[of string]()
            for c as Capture in match.Groups["column"].Captures:
                params.Add(c.Value)
            
            if len(args) == len(params):
                return RunQuery(table, params.ToArray(), args)
            else:
                raise InvalidOperationException("Column count doesn't match parameter count")
        else:
            raise InvalidOperationException("Method name has incorrect format")
    
    private def RunQuery(table as string, params as (string), args as (object)):
        paramString = ""
        for i in range(len(params)):
            paramString += " and ${params[i]} = @p${i}"
        commandText = "select * from ${table} where (1 = 1)${paramString}";
        
        using connection = SqlConnection("<your connection string here>"):
            command = SqlCommand(commandText, connection)
            
            for i in range(len(args)):
                command.Parameters.AddWithValue("@p${i}", args[i])

            connection.Open()
            
            dataSet = DataSet()
            SqlDataAdapter(command).Fill(dataSet)
            return dataSet
    
    def QuackSet(name as string, parameters as (object), value) as object:
        pass
    
    def QuackGet(name as string, parameters as (object)) as object:
        pass
    

Sample usage of this class is:

repository = Repository()
customers = repository.GetCustomersByCountry("Germany") as DataSet
products = repository.GetProductsByUnitsInStockAndReorderLevel(0, 0) as DataSet

As you can see, the result of the method is casted to DataSet. Without this, the result would be of the duck type, which means its members would be resolved at runtime. While this may be OK, you should consider two things:

• Duck typing is approx. 160 times slower than static typing.
• There is a known issue with Boo 0.8.2 causing AmbiguousMatchException to be thrown when an overloaded indexer is accessed on a duck type. This means that accessing indexer of Tables collection of the DataSet class through duck typing will result in this exception.

Boo language with SharpDevelop

Recently I had urge to wander off the track laid by almighty Microsoft and take a peek into open source community. And there it is – the Boo language for CLI. It is announced as a “wrist friendly” language, which basically means that it has smooth syntax and other facilities that ease the hard life of a developer. The syntax is Python-like (or Ruby-like if you prefer), but the language itself is statically typed. It imitates dynamically typed language by type inference (where possible). The greatest power of Boo lies in extensibility of the language and the compiler, but let’s start at the beginning.

True programmers use the notepad, but lazy ones prefer to have some IDE. There is Boo support built into open source SharpDevelop IDE. You get project templates, syntax highlighting, debugger and NUnit integration for free.

 

This is no Visual Studio, but still impressive.

If you would like to learn about Boo, just visit it’s home page. As for this post I would like to bullet point some features that make programming in Boo more pleasant than C#:

• First class functions. No need to declare a class, even for entry point.
• Puts your code on a diet. It’s this:

  class Calculator:
      def Add(a as int, b as int):
          return a + b
  
  print Calculator().Add(1, 2)
  

  versus this:

  public class Calculator
  {
      public int Add(int a, int b)
      {
          return a + b;
      }
  }
  
  public static class Program
  {
      public static void Main()
      {
          Console.WriteLine(new Calculator().Add(1, 2));
      }
  }

• Builtin literals for arrays, lists and hashes (like Hashtable)

  myArray = (1, 2, 4)
  myList = [1, 2, "apple"]
  myHash = { "key1" : "value1", "key2" : "Value2" }
  
  print myArray
  print myList
  print myHash
  
  // outputs:
  // System.Int32[]
  // [1, 2, apple]
  // Boo.Lang.Hash

• Generators, which are basically expressions for defining a sequence based on condition. Those sequences are not stored in memory, but rather executed on demand (yeah, you can do this with LINQ too)

  squaresForEvenNumbers = i*i for i in range(10) if i % 2 == 0
  print join(squaresForEvenNumbers, ', ')
  fruits = ("apple", "bannana", "strawberry", "raspberry")
  berries = "Berry: " + fruit for fruit in fruits if fruit.Contains("berry")
  print join(berries, ', ')
  
  // outputs:
  // 0, 4, 16, 36, 64
  // Berry: strawberry, Berry: raspberry
  

• String interpolation (no more String.Format)

  name = "Marcin"
  print "Hello ${name}"
  

• Builtin literals for regular expressions.

  print /\d{2}-\d{3}/.IsMatch("12-333")
  

• Slicing

  numbers = (1, 2, 3, 4, 5)
  print join(numbers[1:3])
  name = "Marcin"
  print join(name[-3:])
  
  // outputs
  // 2 3
  // c i n
  

• Duck typing, which is what you will get with the dynamic keyword in C# 4. This means being able to resolve member names at runtime. But Boo also implements mechanism of missing methods (also present in Ruby for example). When a method is not found on object implementing IQuackFu interface, then a special method of this interface is called and the name of missing method along with its parameters are passed. Developer can implement some behavior basing on the method’s name or its parameters. I hope to cover this in more detail in future.
• Boo allows creating syntactic macros which you can use to extend language. While implementing a macro, developer has access to object tree representation of code (AST – abstract syntax tree) and is able to modify this tree. This opens a lot of possibilities. For examle Ayende Rahien uses this feature to create DSLs. Also you can build your own compiler steps – an example is to check the naming convenstions during compilation or automatically include assembly references for used types.

Hopefully I’ll be able to write more on Boo in future. For now I encourage you to explore it on your own.

How to get property name from lambda expression

Just a quick tip here. If you need a property name for reflection or any other purpose, the simplest solution is to pass it as a parameter of your method. This unfortunately has a serious disadvantage of not being influenced by automatic refactoring. Alternate way is to take advantage of lambda expressions and expression trees:

public void UseProperty<T, K>(Expression<Func<T, K>> propertySelector)
{
    if (propertySelector.Body.NodeType != ExpressionType.MemberAccess)
    {
        throw new ArgumentException(
            "A property selector expression has an incorrect format");
    }

    MemberExpression memberAccess = propertySelector.Body as MemberExpression;

    if (memberAccess.Member.MemberType != MemberTypes.Property)
    {
        throw new ArgumentException("A selected member is not a property");
    }

    string property = memberAccess.Member.Name;
    Console.WriteLine(property);
}

The usage:

var myClass = new MyClass();
myClass.UseProperty((Exception ex) => ex.Message);

Notice there is no need to explicitly provide parameter types as they are inferred from the lambda expression, but you have to explicitly type the lambda expression. If your class operates on a specific type, you can make it generic and move type declaration to the point, where an instance is created. This is useful if you have more methods using lambda to retrieve property name.

public class MyClass<T>
{
    public void UseProperty<K>(Expression<Func<T, K>> propertySelector)
    {
        // same as previously
    }
}

The usage:

var myClass = new MyClass<Exception>();
myClass.UseProperty(ex => ex.Message);

Hope this helps.

Some thoughts on LLBLGen

While there are many popular ORMs, the LLBLGen doesn’t get too much buzz on the blogs. Possibly because it is a commercial product and people rather use free tools if available. I think it is one of the first .NET ORMs on the market and it surely is a mature product. I had an opportunity to work a little with LLBLGen so I’d like to sum up some of my observations.

An overall impression I got was that LLBLGen is very ADO.NET-like. There’s no equivalent of session (or object context) unless explicitly specified, so the Identity Map pattern is not used by default, which is OK in most scenarios (and more intuitive in my opinion). Instead of session, you use a DataAccessAdapter class, which behaves like a smart connection to a database. There’s the EntityCollection class which is basically something like a DataSet – a data container, that tracks changes . There are typed lists which allow to create a custom view over a set of related entities.

The pros of LLBLGen are:

• Allows you to just get things done quickly. Maybe not in the best style, but still.
• Has a nice designer and a very sophisticated text templating engine with ORM oriented syntax. Take a look at this:

  /// <summary> 
  /// CTor which initializes the DTO with values from its corresponding entity 
  /// </summary> 
  /// <param name="entityInstance">The entity instance which holds the values for this DTO</param> 
  public <[CurrentEntityName]>DTO(<[CurrentEntityName]>Entity entityInstance)<[ If IsSubType ]> 
      : base(entityInstance)<[ EndIf]> 
  { 
      <[Foreach EntityField CrLf]> _<[CaseCamel EntityFieldName]> = 
          entityInstance.<[EntityFieldName]>;<[NextForeach]> 
  } 

  I consider this to be a nice example of DSL.
• Has an advanced LINQ support together with extensions allowing you to define prefetch paths on IQueryable<>
• Extensive predicate mechanism (Specification pattern) when not using LINQ
• Supports both adapter mode (the usual with entities loaded and saved using external object, adapter) and self-serviced mode(Active record pattern)
• Has some advanced features including auditing, authorization and own dependency injection, but presumably you will use specialized libraries for this aspects anyway.

While the cons are:

• Entities generated by default templates are cluttered with ORM related code and really heavyweight.
• The syntax imposed by runtime libraries is clumsy and awkward. An example:

  EntityCollection customers = new EntityCollection(new CustomerEntityFactory());
  DataAccessAdapter adapter = new DataAccessAdapter();
  adapter.FetchEntityCollection(customers, null);
  customers.Sort((int)CustomerFieldIndex.CompanyName, ListSortDirection.Descending);

  Fortunately this is remedied to some extent by usage of LINQ.
• Does not support lazy loading.
• While prefetching related entities, LLBLGen generates separate SELECT statement for each entity type instead of performing a join.
• While having a very nice templating engine and template designer, there is virtually no repository for community created templates. Sure, there is a forum section, but it is unstructured and you can browse posts from last year only!

Still, overall impression is good. I hope to get some comments on this :)