Kiama is a Scala library for language processing including attribute grammars, term rewriting, abstract state machines and pretty printing.

This is a major release cross-published for both Scala 2.10 and 2.11. It’s been a while and there are lots of changes, so these notes are crazy long.

Since June 2015, Kiama has been based at Bitbucket instead of Google code. Please raise issues on the Bitbucket site.

Breaking changes

Enhancements

Fixes

Other

What happened to Attributable?

In Kiama 1.x you could use abstract syntax trees reflexively by accessing fields such as parent, next or isRoot. These fields were provided by the Attributable trait that you had to mix in to your AST classes. You also had to call initTree on the root of your AST to setup these fields before you tried to use them.

Kiama 2.x changes this aspect of the library quite a bit, so we devote some space here to describing the migration path. The Kiama examples have all been updated so you can consult them for more detail.

In a nutshell, Attributable and initTree no longer exist. Instead, you can use a mechanism called tree relations to achieve a similar goal. A key property of the new approach is that the relations exist outside your AST so that no modification of the AST classes is necessary. Thus, you can now do full attribution of structures that come from elsewhere for which mixing in Attributable would have been impossible.

Since Attributable no longer exists, the accompanying n->a notation for evaluating an attribute a on a node n has also gone. Instead, just use the normal function call notation a(n).

Attribution that doesn’t need to access the tree reflexively (i.e., doesn’t useparent, isRoot, etc.) can be written as before.

If you want the equivalent of the parent, isRoot, etc fields of 1.x in 2.x you need to create a Tree object for your AST. Suppose that you have a tree rooted at a node root that you wish to attribute. You create the Tree for this structure as follows:

import org.bitbucket.inkytonik.kiama.relation.Tree
val tree = new Tree(root)

The Tree object traverses the structure to set up relations that give reflective access to the structure. E.g., tree.parent is a relation that relates each node to its parent (if there is one).

The easiest way to use the relations such as tree.parent is via pattern matching. Suppose that you want to write a depth attribute whose value is zero if the node is the root of the tree (i.e., has no parent) and one more than its parent’s value otherwise. Assuming you have access to a relevant Tree via the variable tree you can define the attribute as follows:

val depth =
  attr {
    case tree.parent(p) =>
      depth(p) + 1
    case _ =>
      0
  }

The first case will only succeed if the matched node has a parent and it will bind p to that parent node for use in the recursive call. If the first case fails, then there is no parent and we use the default case for the root of the tree.

Each relation also comes with a pair method that enables you to match on both parts of a relational tuple at the same time. For example, the following case uses the tree.next relation to match if the current node is an assignment statement node and the next one at the same level is a while loop statement node:

case tree.next.pair(_ : AsgnStmt, _ : WhileStmt) =>

Of course, patterns can be nested so very powerful matching up and down trees can be expressed using these relations.

The tree relation approach brings a disciplined approach to programs that combine attribution and rewriting. In Kiama 1.x you had to be very careful if you rewrote an AST and then wanted to perform attribution on it. Because the old and new ASTs could share nodes, it was not always clear what the appropriate value of an attribute should be. E.g., imagine that the depth of a node changes. The safest way out was to clear the attribute values before computing any in the new AST, which was a brute force solution and didn’t allow you to go back and access attributes on the old AST.

In Kiama 2.x you are forced to use a Tree value to access the AST structure (other than children). Hence you can have a Tree for the old AST and another one for the new AST and can perform well-defined attribution on either whenever you want. In a future version of Kiama we plan to support some form of incremental computation of attributes where Tree relations overlap.

To make rewriting a little easier than before, it is no longer necessary to clone nodes when rewriting to avoid creating sharing in the rewritten tree. Just create the sharing and move on. If later you decide to perform some sharing-sensitive attribution on the AST that contains shared nodes, the Tree that you create will clone nodes as necessary to avoid sharing in the relations.

For more information on how to use tree relations, please consult the Kiama 2.x examples. In particular, the semantic analysis modules of the compiler examples (e.g., MiniJava and Oberon-0) show how reusable collections of attribute definitions can be defined.