Tree Transformation Techniques

Randall,
One place to mine for this sort of thing is the whole generic functional programming cottage industry, with Scrap-Your-Boilerplate (aka SYB) as a paradigmatic example. There are a bunch of these frameworks in Haskell, now. Porting one of them over to Scala shouldn't be difficult. Iirc, Tony Morris was working on one of these and for all i know it might already live in scalaz.
Here's another hare-brained scheme that has worked for me. Your mileage may vary. i often describe my data structures as a grammar, using BNFC. From this description you can generate a Java parser. The abstract syntax tree classes of that output ends up being a good first stab at a Java representation of the data structure. Further, BNFC autogenerates a good chunk of the visitor pattern stuff. You can target a huge number of languages, including Haskell -- sadly no Scala, yet. But, because you can target Java all of that is available in Scala. Then you can mix and match with  the generated visitor pattern code and some generic functional programming approaches.
As a toy example, the following BNFC grammar
Leaf . TreeStructure ::= IdentTree . TreeStructure ::= "{" TreeStructure "|" TreeStructure "}"
will generate a (Java-or-C#-or-Haskell-or-OCaml-or...-based) parser for a language that allows you to write things like
{ phred | { weasley | { harry | potter } } }
The data structures for the abstract syntax will provide a container to manipulate binary trees. If you generated the Java parser, you can access these structures and the visitor stuff from Scala. A side benefit of this is that you get a little DSL that provides a test framework for driving your data structures.
Here you can see a little sample Scala+Lift app of a compositional model for Graphs that i did using this technique. i wrapper the REPL for the DSL that comes for free in a Lift-web-app. 
Best wishes,
--greg

On Thu, Mar 19, 2009 at 1:15 PM, Randall R Schulz <rschulz@sonic.net> wrote:

Hi,

I'm working on a Scala reimplementation of a large system in which
transformation of tree structures are ubiquitous. In the existing
system, I wrote visit and transform drivers that performed the
traversal of the trees, invoked the proper methods on the visitor or
transformer instances that held the code for each particular analysis
or transform and, for transformations, built the transformed result.
I've gotten the impression that this is not the ideal model for this
sort of task in functional languages.

What sort of techniques, idioms, patterns, libraries, etc. should I be
looking at for such algorithms?


Randall Schulz

--
L.G. Meredith
Managing Partner
Biosimilarity LLC
806 55th St NE
Seattle, WA 98105

+1 206.650.3740

http://biosimilarity.blogspot.com

On Thursday March 19 2009, Meredith Gregory wrote:
> Randall,

Thanks for the ideas and the pointers.

> One place to mine for this sort of thing is the whole generic
> functional programming cottage industry, with Scrap-Your-Boilerplate
> (aka SYB) as a paradigmatic example. ...
>
> Here's another hare-brained scheme that has worked for me. ...
>
> ...
>
> The data structures for the abstract syntax will provide a container
> to manipulate binary trees. If you generated the Java parser, you can
> access these structures and the visitor stuff from Scala. A side
> benefit of this is that you get a little DSL that provides a test
> framework for driving your data structures.

I have a first cut at the types that comprise the trees, though they're
far from cast in stone.

I do have a requirement of being able to read and write multiple
external language forms, so I have to modularize the parsers and
printers. I also need multiple formatting styles ("pretty-printed,"
flat, etc.) even within a given output language. So the whole I/O side
is a separate and somewhat complicated matter. The I/O side does not
exist at all, so far, since I'm just getting the core types in place
now.

I also need to be able to handle multiple run-time representations of
some of the key structures depending on which kind of special
techniques are used when operating on these trees (in fact, one common
representation is the so-called "flatterm" representation that
facilitates access in trie-like discrimination trees and is not a tree
at all, though it captures all the structure of the tree form it
encodes).

> Here you can
> see a little sample Scala+Lift app of a compositional model for
> Graphs that i did using this technique. i wrapper the REPL for the
> DSL that comes for free in a Lift-web-app.

Any chance that's deployed somewhere? I'm aware of Lift, but haven't
worked with it, nor have I used Maven, though I suppose that blissful
state will not last a lot longer...

> Best wishes,
>
> --greg

Thanks again.

Randall Schulz

Randall,

Thanks for your response. It gives me food for thought. i wonder about data structure representations such as trie-based representations or incidence matrices for graphs and how they become reconciled with ADTs. Intuition suggests that a good accounting of such representations will uncover interesting functors, making it possible to generate, if only partially, some of these less language-theoretic representations; but that doesn't help you in the short term, i suppose. ;-(

As for playing around with the GraphL widget, on a *nix box (with svn and maven installed) you should just be able to do the following

> svn co http://svn.biosimilarity.com/src/opn/GraphL/trunk GraphL
...
> mvn compile jetty:run
...

(If you try it and that doesn't work, please let me know.)

Installing svn and mvn are relatively painless experiences. On a mac with macports it's

> sudo port install subversion
...
> sudo port install maven2
...

Alternatively, you can just download install packages for all the major archtectures from the subversion and maven websites.

i've blogged about the motivations behind GraphL here. That entry also discusses some of the installation and use.

Best wishes,

--greg

On Thu, Mar 19, 2009 at 5:24 PM, Randall R Schulz <rschulz@sonic.net> wrote:

On Thursday March 19 2009, Meredith Gregory wrote:
> Randall,

Thanks for the ideas and the pointers.

> One place to mine for this sort of thing is the whole generic
> functional programming cottage industry, with Scrap-Your-Boilerplate
> (aka SYB) as a paradigmatic example. ...
>
> Here's another hare-brained scheme that has worked for me. ...
>
> ...
>
> The data structures for the abstract syntax will provide a container
> to manipulate binary trees. If you generated the Java parser, you can
> access these structures and the visitor stuff from Scala. A side
> benefit of this is that you get a little DSL that provides a test
> framework for driving your data structures.

I have a first cut at the types that comprise the trees, though they're
far from cast in stone.

I do have a requirement of being able to read and write multiple
external language forms, so I have to modularize the parsers and
printers. I also need multiple formatting styles ("pretty-printed,"
flat, etc.) even within a given output language. So the whole I/O side
is a separate and somewhat complicated matter. The I/O side does not
exist at all, so far, since I'm just getting the core types in place
now.

I also need to be able to handle multiple run-time representations of
some of the key structures depending on which kind of special
techniques are used when operating on these trees (in fact, one common
representation is the so-called "flatterm" representation that
facilitates access in trie-like discrimination trees and is not a tree
at all, though it captures all the structure of the tree form it
encodes).


> Here <http://svn.biosimilarity.com/src/open/GraphL/trunk/> you can
> see a little sample Scala+Lift app of a compositional model for
> Graphs that i did using this technique. i wrapper the REPL for the
> DSL that comes for free in a Lift-web-app.

Any chance that's deployed somewhere? I'm aware of Lift, but haven't
worked with it, nor have I used Maven, though I suppose that blissful
state will not last a lot longer...


> Best wishes,
>
> --greg


Thanks again.

Randall Schulz

--
L.G. Meredith
Managing Partner
Biosimilarity LLC
806 55th St NE
Seattle, WA 98105

+1 206.650.3740

http://biosimilarity.blogspot.com

Hi Randall,

> I'm working on a Scala reimplementation of a large system in which
> transformation of tree structures are ubiquitous. In the existing
> system, I wrote visit and transform drivers that performed the
> traversal of the trees, invoked the proper methods on the visitor or
> transformer instances that held the code for each particular analysis
> or transform and, for transformations, built the transformed result.
> I've gotten the impression that this is not the ideal model for this
> sort of task in functional languages.
>
> What sort of techniques, idioms, patterns, libraries, etc. should I be
> looking at for such algorithms?

Greg Meredith mentioned the scrap-your-boilerplate line of work. A
related approach is embodied in term rewriting systems, two prominent
examples of which are ASF+SDF and Stratego. In these systems, tree
transformation are expressed as rewrite rules. In Stratego there is
a logical separation between the basic rewrite rules and the strategies
that are used to decide how to apply the rules to a given tree. This
approach has given rise to the term strategic programming.

The Kiama library that I am developing has a DSL version of the Stratego
approach embedded in Scala. I expect to make a public release in the
next few weeks, but in the meantime I'd be happy to talk about your
application to see if Kiama might be useful to you.

As a simple example, here is how you might express an arithmetic
expression simplification in Kiama:

def simplify : Exp => Exp =
rewrite (everywheretd (rule {
case Sub (x, y) => simplify (Add (x, Neg (y)))
case Add (x, y) if x == y => Mul (Num (2), x)
}))

everywheretd is an example of a strategy, in this case applying the
rule at every node in the tree.

A general description of Kiama as of last year can be found in the
following paper:

http://www.labri.fr/perso/reveille/DSPD/2008/papers/7.pdf

regards,
Tony

thank you for the paper link!

Am 25.03.2009 um 09:39 schrieb Tony Sloane:

> Hi Randall,
>
>> I'm working on a Scala reimplementation of a large system in which
>> transformation of tree structures are ubiquitous. In the existing
>> system, I wrote visit and transform drivers that performed the
>> traversal of the trees, invoked the proper methods on the visitor or
>> transformer instances that held the code for each particular analysis
>> or transform and, for transformations, built the transformed result.
>> I've gotten the impression that this is not the ideal model for this
>> sort of task in functional languages.
>>
>> What sort of techniques, idioms, patterns, libraries, etc. should
>> I be
>> looking at for such algorithms?
>
> Greg Meredith mentioned the scrap-your-boilerplate line of work. A
> related approach is embodied in term rewriting systems, two prominent
> examples of which are ASF+SDF and Stratego. In these systems, tree
> transformation are expressed as rewrite rules. In Stratego there is
> a logical separation between the basic rewrite rules and the
> strategies
> that are used to decide how to apply the rules to a given tree. This
> approach has given rise to the term strategic programming.
>
> The Kiama library that I am developing has a DSL version of the
> Stratego
> approach embedded in Scala. I expect to make a public release in the
> next few weeks, but in the meantime I'd be happy to talk about your
> application to see if Kiama might be useful to you.
>
> As a simple example, here is how you might express an arithmetic
> expression simplification in Kiama:
>
> def simplify : Exp => Exp =
> rewrite (everywheretd (rule {
> case Sub (x, y) => simplify (Add (x, Neg (y)))
> case Add (x, y) if x == y => Mul (Num (2), x)
> }))
>
> everywheretd is an example of a strategy, in this case applying the
> rule at every node in the tree.
>
> A general description of Kiama as of last year can be found in the
> following paper:
>
> http://www.labri.fr/perso/reveille/DSPD/2008/papers/7.pdf
>
> regards,
> Tony
>
>

On Wednesday March 25 2009, Tony Sloane wrote:
> Hi Randall,

Thanks for the information on Kiama.

> > I'm working on a Scala reimplementation of a large system in which
> > transformation of tree structures are ubiquitous. ...
> >
> > What sort of techniques, idioms, patterns, libraries, etc. should I
> > be looking at for such algorithms?
>
> Greg Meredith mentioned the scrap-your-boilerplate line of work. A
> related approach is embodied in term rewriting systems, two prominent
> examples of which are ASF+SDF and Stratego. In these systems, tree
> transformation are expressed as rewrite rules. In Stratego there is
> a logical separation between the basic rewrite rules and the
> strategies that are used to decide how to apply the rules to a given
> tree. This approach has given rise to the term strategic
> programming.

I'm familiar with those, though I haven't used them. In the Java project
that is a predecessor to my current work, I've worked a bit with Tom
(based on the references in your paper, I gather you're familiar with
it). But I ended up using it only in one restricted set of transforms.
It was a lot of work to write its equivalent of extractors and
constructors needed because Java doesn't have the underpinning to
support algebraic types that Scala does.

It is also the case that I've learned a lot about term rewriting systems
since then and now feel much more comfortable with those concepts.

> The Kiama library that I am developing has a DSL version of the
> Stratego approach embedded in Scala. ...
>
> As a simple example, here is how you might express an arithmetic
> expression simplification in Kiama:
>
> def simplify : Exp => Exp =
> rewrite (everywheretd (rule {
> case Sub (x, y) => simplify (Add (x, Neg (y)))
> case Add (x, y) if x == y => Mul (Num (2), x)
> }))
>
> everywheretd is an example of a strategy, in this case applying the
> rule at every node in the tree.

Basically, what I'm looking for is a library that abstracts the control
mechanisms and common "bookkeeping" of tree transformations. It looks
like your strategies are these mechanisms. If you have a more detailed
paper than the summary you mention below or user documentation, I'd
love to read that.

> A general description of Kiama as of last year can be found in the
> following paper:
>
> http://www.labri.fr/perso/reveille/DSPD/2008/papers/7.pdf

Somehow that paper was already entered into my library, on the 19th of
this month. Was it referred to earlier in this thread, or did I find it
myself? I did some Web searching using terms like "Scala functional
tree transformation" and such.

> regards,
> Tony

Randall Schulz

On 25/03/2009, at 12:56 PM, Randall R Schulz wrote:

> On Wednesday March 25 2009, Tony Sloane wrote:
>
>> Greg Meredith mentioned the scrap-your-boilerplate line of work. A
>> related approach is embodied in term rewriting systems, two prominent
>> examples of which are ASF+SDF and Stratego. In these systems, tree
>> transformation are expressed as rewrite rules. In Stratego there is
>> a logical separation between the basic rewrite rules and the
>> strategies that are used to decide how to apply the rules to a given
>> tree. This approach has given rise to the term strategic
>> programming.
>
> I'm familiar with those, though I haven't used them. In the Java
> project
> that is a predecessor to my current work, I've worked a bit with Tom
> (based on the references in your paper, I gather you're familiar with
> it). But I ended up using it only in one restricted set of transforms.
> It was a lot of work to write its equivalent of extractors and
> constructors needed because Java doesn't have the underpinning to
> support algebraic types that Scala does.

Yes, Tom is quite nice, but I agree that Scala is a much better fit
than Java for the scaffolding that rewriting needs.

>> The Kiama library that I am developing has a DSL version of the
>> Stratego approach embedded in Scala. ...
>>
>> As a simple example, here is how you might express an arithmetic
>> expression simplification in Kiama:
>>
>> def simplify : Exp => Exp =
>> rewrite (everywheretd (rule {
>> case Sub (x, y) => simplify (Add (x, Neg (y)))
>> case Add (x, y) if x == y => Mul (Num (2), x)
>> }))
>>
>> everywheretd is an example of a strategy, in this case applying the
>> rule at every node in the tree.
>
> Basically, what I'm looking for is a library that abstracts the
> control
> mechanisms and common "bookkeeping" of tree transformations. It looks
> like your strategies are these mechanisms. If you have a more detailed
> paper than the summary you mention below or user documentation, I'd
> love to read that.

A Kiama user manual is under construction and, unfortunately, doesn't
yet contain a section on the rewriting library. For the most part,
the Stratego papers can be used as a reference since we follow that
design pretty closely. I would recommend the following paper as a
good overview to the Stratego approach for people wanting one:

http://swerl.tudelft.nl/twiki/pub/Main/TechnicalReports/TUD-SERG-2008-01...

For Kiama itself, the API doc is at:

https://plrg.science.mq.edu.au/kiama/bin/doc/api/

Look at the kiama.rewriting.Rewriter trait for the bits we are
discussing here.

The main Kiama project site is:

http://plrg.science.mq.edu.au/projects/show/kiama

Kiama is only now going public and we are still tidying quite a bit of
code, documentation and examples for the first official public release
that I expect to make in the next few weeks. If you want to try it
anyway, the cutting edge is available from our Mercurial repository.
See the project wiki for details on how to get it.

For guidance on usage, the best bet at the moment is to grab the code
and look at the tests and examples. I'm very interested in feedback
of course.

>> A general description of Kiama as of last year can be found in the
>> following paper:
>>
>> http://www.labri.fr/perso/reveille/DSPD/2008/papers/7.pdf
>
> Somehow that paper was already entered into my library, on the 19th of
> this month. Was it referred to earlier in this thread, or did I find
> it
> myself? I did some Web searching using terms like "Scala functional
> tree transformation" and such.

I'm not sure. I think it was mentioned by me a while ago, but not
recently.

Scala people may also be interested in the paper "A Pure Object-
Oriented Embedding of Attribute Grammars" that will be presented at
the Workshop on Language Descriptions, Tools and Applications this
coming weekend. It describes the tree annotation portion of Kiama's
library. You can download the LDTA pre-proceedings from:

http://ldta.info/ldta2009proceedings.pdf

cheers,
Tony

On Wednesday March 25 2009, Tony Sloane wrote:
> ...
> >
> > Basically, what I'm looking for is a library that abstracts the
> > control mechanisms and common "bookkeeping" of tree transformations.
> > It looks like your strategies are these mechanisms. ...
>
> A Kiama user manual is under construction and, unfortunately, doesn't
> yet contain a section on the rewriting library. ... I would recommend
> the following paper as a good overview to the Stratego approach for
> people wanting one:
>
>
>
> For Kiama itself, the API doc is at:
>
> https://plrg.science.mq.edu.au/kiama/bin/doc/api/
>
> Look at the kiama.rewriting.Rewriter trait for the bits we are
> discussing here.
>
> The main Kiama project site is:
>
> http://plrg.science.mq.edu.au/projects/show/kiama
>
> Kiama is only now going public and we are still tidying quite a bit
> of code, documentation and examples for the first official public
> release ...
>
> For guidance on usage, the best bet at the moment is to grab the code
> and look at the tests and examples. I'm very interested in feedback
> of course.

Mercurial, eh? I guess one more version management client won't break
this camel's back.

> ...
>
> Scala people may also be interested in the paper "A Pure Object-
> Oriented Embedding of Attribute Grammars" that will be presented at
> the Workshop on Language Descriptions, Tools and Applications this
> coming weekend. It describes the tree annotation portion of Kiama's
> library. You can download the LDTA pre-proceedings from:
>
> http://ldta.info/ldta2009proceedings.pdf

Thank you very much for all this information. It looks pretty
interesting. Between Scala itself and tools like these, we may yet get
computing in everyday practice on a sound footing!

> cheers,
> Tony

Randall Schulz

On 25/03/2009, at 6:21 PM, Randall R Schulz wrote:

> ...
> Mercurial, eh? I guess one more version management client won't break
> this camel's back.

Sorry about that. It just felt right...

> ...
> Thank you very much for all this information. It looks pretty
> interesting. Between Scala itself and tools like these, we may yet get
> computing in everyday practice on a sound footing!

Yeah, hopefully it all helps.

cheers,
Tony

as a paradigmatic example. 

I'm sorry for being awfully pedantic but this sounds very bad. "Paradigmatic example" literally means "exemplary example", i.e. an "example-like" example, probably not what you meant to say...

Jim,

Many thanks for the feedback. Where i come from paradigmatic connotes best representative of a class of patterns -- where best means most fitting or illustrative. On the other hand exemplary connotes worthy of imitation due to excellence. Further, a quick google search illustrates that 'paradigmatic example' is used with great regularity in common parlance and scholarly texts. So, while it may sound bad to some ears, to a great many it conveys a specific and useful meaning.

Best wishes,

--greg

On Wed, Mar 25, 2009 at 3:30 PM, Jim Andreou <jim.andreou@gmail.com> wrote:

as a paradigmatic example. 

I'm sorry for being awfully pedantic but this sounds very bad. "Paradigmatic example" literally means "exemplary example", i.e. an "example-like" example, probably not what you meant to say...

--
L.G. Meredith
Managing Partner
Biosimilarity LLC
806 55th St NE
Seattle, WA 98105

+1 206.650.3740

http://biosimilarity.blogspot.com