[antlr-interest] Type discovery for operator overloading?

[Gavin Lambert]

At 14:40 14/06/2008, C. Mundi wrote:
>Now in my calculus, multiplication over pairs of one integer and 
>one string is commutative.  So my tree-walker has to recognize 
>the equivalence of
>
>      ^( MULTIPLY STRING INTEGER )
>
>and
>
>      ^( MULTIPLY INTEGER STRING )
>
>But it seems to me that simply overloading the "left-multiply" 
>method for both strings and integers is wholly inadequate, 
>because the multiplication must take into account not only the 
>type of the left-argument, but also the type of the 
>right-argument, to determine what to do and what type to 
>return.  This is evident from the fact that 2*3 and 2*'foo' 
>return entirely different types, but 2*'foo' and 'foo'*2 return 
>the same type (and value in this case).
>
>How does one approach this?  It seems to me that the answer lies 
>in the translation output, not in ANTLR itself.  Nonetheless, I 
>am hoping that perhaps ANTLR provides some tools to support such 
>situations.  I was thinking LL(2) with a semantic predicate 
>peeking ahead to determine the type of the second operand.  Am I 
>on the right track here?  Or should I go back to monkey finishing 
>school?

Generally speaking, when writing a tree grammar rule you put the 
action to be executed at the end of the rule.  This means that it 
has already seen both terms in the AST, so there's no lookahead 
involved here.  You merely need some way to identify the type of 
each term (which is trivial in the above case, and only slightly 
more complicated in the cases where the terms can be 
sub-ASTs/expressions).

Of course, this approach only works for a strongly typed language 
(ie. one where variables are typed, so that you can statically 
determine whether a given variable name contains a string or an 
integer).  If your language is dynamically typed then you'll have 
to have your runtime multiplication operation work out what types 
its arguments are and how to deal with them accordingly.