Kiama and Non-Tree Graphs

[Randall Schulz]

Hi,

This is a quick question about the following statement from this page of the Kiama documentation:

“… In most cases, the representation is a tree, but graphs are also possible.”

The question is this: Can Kiama effectively process arbitrary graphs? Specifically, can it process cyclic graphs? And if so, is cycle-breaking built in or something that the user must do?


Randall Schulz

[Tony Sloane]

Hi Randall,

Well, the answer (as in most topics) is “it depends”. There are two main cases:

* You have a graph data structure and you want to transform it. Kiama’s rewrite rules can be used for this but are basically a tree-focused paradigm, so essentially you would be traversing the graph using a tree subset of the graph relation (e.g., a spanning tree if you want to go to every node). There is a version of the rewriting library that memoises rewriting operations which makes it easy to generically traverse a graph without having to manually keep track of where you’ve been. The Scoobi project uses this approach to build an optimiser for their computation graphs.

* You have a graph data structure and you want to calculate some properties of nodes in that structure. The Kiama attribution library can be used for this. Normal attributes can compute on any structure as long as there are no cyclic dependencies between attribute equations. If you have a computation that is naturally cyclic, you can express it using Kiama’s circular attributes, as long as it converges. E.g., we have an example that shows how to do data flow analysis with circular attributes.

Does this clarify things enough?

cheers,

Tony

[Randall Schulz]

Thanks, Tony, that does answer my questions.

And sorry it took so long for me to acknowledge your answer–work intervened…


Randall