[antlr-interest] Re: Source-driven v. Target-driven xforms (was Re: New article on StringTemplates and Treewalkers)

[Andy Tripp]

Gregg Reynolds wrote:

> Andy Tripp wrote:
>
>> Hi Gregg,
>>
>> Yes, very good description of the issue.
>> Generally, I think of it  as "tree driven" vs. "rule driven" rather 
>> than "source-driven"
>> and "target driven". In "tree driven", the  source language grammar 
>> drives the design.
>> In rule-driven, the  design is a sequential application of rules.
>>
>
> Understandable, but as I mentioned in my other post, "rule" is 
> ambiguous, so this terminology might be troublesome for people not so 
> familiar with parsing or your approach.  In ParserWorld, "rule" is 
> commonly a synonym for "grammatical production" (which may have 
> attached actions) (and it could be a tree grammar production), but in 
> JazillionTown it means specifically a function that does a little 
> parsing and then some actions.  I think that will be confusing for 
> your readers.  Unfortunately I can't think of a better term at the 
> moment.

Yea, "rule" is probably confusing to many. Some use the term "term 
rewriting" too.
Also, I don't think of my "rule" as doing "a little parsing and them 
some actions", I think of it as
"a mapping of an input pattern to a replacement pattern". That's how you 
start to think when you've got hundreds of
little things like:

sprintf(stderr, --> printf(

...and you have to think like that, because in fact the thing you're 
matching on may not even be "parseable" - it's not a valid
C construct on it's own, and you can't build an AST from it!

>
> Howsabout "target-centered rule-driven" v. "source-centered 
> tree-driven"?  Oh boy!  Acronyms: TCRD v. SCTD!  ;)
>
> A Jazillion "rule" is analogous to an antlr "rule" turned inside out, 
> and vice-versa, no?
>
> But "tree-driven" makes sense to me, since it creates and uses ASTs, 
> whereas Jazillion doesn't.
>
>>
>> When I started with the tree-driven approach and using ANTLR to do 
>> tranformation, I felt completely bogged down in
>> AST structure and found myself constantly thinking about *how* to do 
>> things rather than what needed
>> to be done.
>>
> Well, that's where I have to hold my tongue, since it's all 
> theoretical to me.  But as a general issue, I wonder how much of that 
> is attributable to Antlr's meta-language, by which I mean the English 
> language used to document the works.  After all, anybody who can read 
> C and understand C code must be parsing it, and therefore must have a 
> structured model of the code rattling around in the skull: a tree, if 
> not an AST.  If one sees "if (x=1)", one can surely see that "x=1" is 
> an expression, and that it is composed of a variable, etc.  Which 
> amounts to a tree, even if one doesn't use tree language (parent, 
> child, root, etc.) to talk about it.

I never care too much about the theory, only how things work out in 
practice. Even if people do generally picture some
tree-like structure when they read C code, I think the tree structure is 
often "wrong". That's why we often write
"if (x=5)" so often, even in writing Java. If we where good at picturing 
ASTs, we would know that the child of an IF node
must be boolean type and that the ASSIGNMENT operator returns a type 
that matches it's children, which is "int" here.

>
> In any case, I think you've put your finger on a very important point, 
> namely that  even if the AST-based approach has advantages, it may 
> require the fabled "paradigm shift", and let's face it, most people 
> coding to deadline don't have the luxury - it takes time, and there's 
> always the risk that the new paradigm won't deliver.  

Yes, though I would call it a "mindset shift" for developers to stop 
thinking in terms of "snippets of code" and start thinking in terms of
"AST tree structures". ANTLR gurus already made that shift many years 
ago, and are good at making shifts like that. I guess I'm not.

> So then the question is, can the AST approach be explained in a 
> metalanguage that is closer to the way most programmers ordinarily 
> think?  By the same token, can we come up with a meta-language for 
> your approach that connects it with the implied parse tree/AST?  Hmm.  
> (If you can't tell, I'm actually much more interested in the 
> expressiveness of language and metalanguage than I am in actual 
> software. ;)

TXL (among others) has a nice language that lets you specify tree 
transforms. In fact, I guess XSLT does that too.

>
>
> -gregg
>