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

[Andy Tripp]

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.

In my daily development, I spend almost 100% of my time thinking in terms of
"this chunk of C code becomes this chunk of Java", and almost zero on 
"What is
the (tree) structure of this code?"

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.

I didn't write this article to say that the rule-driven way is always 
better, I just tried to explain why I've found
it better for my application. Normally, I wouldn't even bother to spell 
out my thoughts like that, but when
someone as smart and knowledgable as Terence is doing things the other 
way, I'm never going to be able
to get rid of that nagging feeling that I'm just missing something and 
I've made a terrible mistake.

On one hand, when Terence says "your pattern matcher may never 
terminate", I can't help but assume he's right
and I just haven't yet noticed some fatal flaw. But on the other hand, 
an expert in computation complexity will
tell you "your traveling salesman algorithm may take forever", and you 
know right away that he's talking
about *in theory*, but you know full well that it works just fine *in 
practice*.

Anyway, I'm ranting again. The one thing that we can agree on is that 
I've finally setup my email client for
reading antlr-interest posts, so I hope my responses will not appear to 
be new threads all the time, and that's
a good thing.

Andy :)


Gregg Reynolds wrote:

> Andy Tripp wrote:
>
>>
> ...etc...
>
> Hi all,
>
> I'm relatively new to AntlrWorld, having (re)discovered it only a few 
> weeks ago, and then discovered StringTemplate, which has since 
> consumed most of my waking hours.
>
> I can't really follow the hairy details of this thread, but I think I 
> see an abstract pattern.  Please tell me if the following makes sense:
>
> The core issue is design strategy for language transformation.  If we 
> can think of a continuum of design options, then (possibly) we can put 
> the Antlr strategy on one end, and the (Jazillion?) on the other.
>
> (I'm being very schematic here; perhaps the actual workings of antlr 
> and jazillion don't fit the schema.  Please advise.)
>
> We can call the Antlr approach "source-driven transformation"; the 
> Jazillion approach "target-driven" transformation.
>
> By "source-driven", I mean that the process looks sth like:
>
>     a.  write grammar to parse source language
>     b.  generate source AST
>     c.  write (tree) transformation grammar that attaches actions to 
> (AST) productions, producing either:
>
>         c1.  a target AST that can then be run through other 
> transformers, in particular a pretty-printer; or
>         c2.  a text in the target language
>
> So in practice a source-driven strategy means writing code to feed 
> into a parser generator.  The driver will invoke the parser on a 
> source text.  Grammatical structure of the source text controls 
> processing.
>
> By "target-driven" I mean a process that looks something like:
>
>     For each element in the target language,
>
>         a.  write transformation logic mapping source elements to 
> target element
>         b.  write (or generate) a "rule", which is a little parser to 
> examine the source text for elements needed to generate said target 
> element; attach transformations from (a) to production in the grammar
>
> In practice a target-driven strategy means writing a set of rules 
> (functions) to be called in turn at each token in the source text.  
> I.e. Start with a target element and see if the corresponding source 
> production(s) match(es); or, try to find the appropriate target 
> element by testing various source productions.  Source language 
> structure controls processing within the driver itself.
>
> The source-driven approach embeds target generation code in a source 
> grammar; the target-driven approach embeds source-grammar in target 
> generation code.
>
> I hope that is somewhere in the ballpark; it's nice and clean so it 
> would be a shame if it was also stupid.  ;)  I think I understand how 
> antlr works pretty well, but I'm not sure about the Jazillion approach.
>
> If this schema is accurate/useful, then I would suggest building on 
> the paper "Why I don't Use..." to produce a more general consideration 
> of the pros and cons of the respective approaches.  Something like 
> *"Language Transformation Strategies: Source-Driven v. Target-Driven 
> in a Fight to the Death!"*  As it stands, the article is interesting 
> (though a bit hard to follow for somebody like me, w/out lots of 
> parsing experience), but it sometimes gives (me at least) the 
> impression of saying "my approach is better because, well, because I 
> like it more". That's not necessarily a bad thing, but I gather that 
> in large part that's because you find the one approach fits better 
> with the way you think about the problem, which doesn't imply that it 
> is a "better" approach.  I'd like to see a more dispassionate 
> consideration of the pros and cons.  The "mental model" one needs for 
> each strategy is obviously very important, but there are other 
> considerations: efficiency, maintainability, etc. - the usual suspects.
>
> And of course the overalln approach could be generalized, i.e. design 
> an abstract uber-language (cf. IDL).  Then you can write one 
> source->uberlang transformer per source lang, and one uberlang->target 
> transformer per target language.  I suppose somebody already does this 
> (or has decided it's impossible or impractical).
>
> thanks,
>
> gregg
>