[antlr-interest] Re: Please help me with homogeneous versusheterogeneous trees!

[Alexey Demakov]

Terence,

I have to say again that heterogenous trees approach also allows to separate
tree structure descriptions and operations. Moreover, visitors approach is not unique
- there are other techniques of "external dispatching". Of course, they are more easy to use
if there is special notation and tool support, but tree grammars also are unusable without ANTLR :)
And heterogenous tree can expose homogenous interface, so heterogenous trees can be used in tree grammars :)

----- Original Message ----- 
From: "Terence Parr" <parrt at cs.usfca.edu>
To: "ANTLR Interest" <antlr-interest at antlr.org>
Sent: Sunday, July 31, 2005 12:36 PM
Subject: Re: [antlr-interest] Re: Please help me with homogeneous versusheterogeneous trees!
> 
> On Jul 30, 2005, at 5:20 AM, cflowers at mindspring.com wrote:
>
> > Thanks a ton for your response. I read with great interest the  
> > links you sent me. I can see how maintaining a compiler over a long  
> > term would be much easier with TreeDL.
> >
> > It is also clear that you vote strongly in favor of heterogeneous  
> > trees that name relationships. Can anyone who holds the opposite  
> > view share some thoughts? (I will search the archives later too,  
> > but right now the corporate firewall won't let me hit web pages  
> > that aren't from port 80).
> 
> Hi.   This article pretty much summarizes my experience and  
> intuition, which is not perfect but I think I've learned a trick or  
> two over the past 20 years building these suckers:
> 
> http://www.antlr.org/article/1100569809276/use.tree.grammars.tml
> 
> > I am not building a compiler. Rather, I envision a number of C#  
> > utilities, all of which might be based off of the same AST.
> 
> This will be a problem I'd say.  You'll need to build a new method in  
> each tree node object for each new utility, possibly screwing up the  

...or you can define separate visitor or visitor-like operation...

> other utilities.  Very poor separation in my opinion.  I like  

...and it will be separated from tree description...

> encapsulating all functionality for a tree walk in place rather than  
> over many many files and entangled with the walks for other utilities  

...operation description also will be in single file independent on
other operation definitions...

> or phases.  With a tree grammar, you'll never touch the tree  
> descriptions  and can't possibly mess up the other utilities.

...the same is true for heterogenous trees -
definition of new operation doesn't require to change tree description...

> Hetero trees are fine for one phase translations.  I think co-opting  
> the type system to enforce and describe structure is a nice trick but  
> it doesn't scale well per my arguments in the article.  For example,  
> the same tree structure can be walked by a tree parser in any target  
> language (for which you have a target) whereas using a type system  
> locks you into that language.  For example, C just doesn't have the  
> type system to handle what an OO language can do.

I see no problems with modelling of required OO features in C
and translation of heterogenous tree description to C.
There are the example - TreeCC tree description can be translated to C:
http://www.southern-storm.com.au/treecc_doc/treecc_toc.html

> In summary, Alexey is clearly a very smart guy and has a nice tool.   
> SableCC also uses this approach, written by another smart guy. :)   
> Using the type system is nice for many applications.  They are  
> obvious to the casual observer and work great for many simple  
> translation, 

I think, the extentions of Java and C# programming languages
with complicated translation to language itself are not simple examples :)

These tools are implemented using heterogenous trees described in TreeDL:
http://www.unitesk.com/products/jat/
http://www.unitesk.com/products/chase/
And Portable.NET C# translator implemented using heterogenous tree described in TreeCC:
http://www.southern-storm.com.au/portable_net.html

> though you have to write the tree recognizer by hand  (<shudder>).  

Tree walker can be generated from tree description.
It is needed to write only actions for affected node types.

> For larger problems, I hope over the next n years to  
> convince you that tree grammars are the way to recognize  
> structure. :)  Give me a chance to finish v3 and then watch the  
> torrent of doc/articles/papers.
> 
> Ter

But there are other ways :)

Regards,
Alexey

-----
Alexey Demakov
TreeDL: Tree Description Language: http://treedl.sourceforge.net
RedVerst Group: http://www.unitesk.com