Re: Call by pattern parsing

myg@gate.net (Mark Grosberg) writes:
>Some languages (especially functional languages) use a function calling
>scheme calling "call by pattern" where, rather than naming a function
>and having it use a strict syntax, the PROGRAMMER (not the language)
>defines the syntax.


The particular examples you give are of operator overloading, which blurs
the issue a little. In languages such as C++ and Ada, the associativities
and precedences of overloaded operators do not change. In addition, new
syntax may not be pulled from out of the sky in these languages, so the
only problem to be addressed is deciding which instance of an overloaded
operator to use (I'll come back to this).


>This seems simple enough, but the problem I had when coding my
>algorithm is basically what to do about precedence and associativity
>[...]


Some languages, as you say, allow completely new operators to be invented.
My knowledge of Prolog is sketchy at best, but I believe it has this
facility; it also allows precedences and associativities to be changed.
Haskell permits both of these, and supports polymorphism and overloading.


If you don't supply associativity and precedence information when defining
a new infix operator in Haskell, ``sensible defaults'' are used. Parsing
these new operators is made easier by two features of the language:


1. Infix operators must consist entirely of ``graphic characters''
        such as ``+'', ``&'', and so on.


3 +|& 5


2. You can use ordinary functions (of arity two or greater) as infix
        operators, but they must be enclosed by backtick characters.


a `foo` b


In addition, there is a small number (10) of possible precedences, so if
you're using a yacc-style parser generator, you can write rules for all
the different fixity/precedence combinations without much trouble and have
your lexer ``recognise'' user-defined operators appropriately to fire the
correct rule in each case.


Prolog has a far larger number (10,000) of precedences for the programmer
to choose from, so the above approach is unsuitable. In this case, you
can just parse expressions with all infix operators treated as if they
have the same precedence and fixity, and build a parse tree in this
manner. Once you're done parsing the expression, you go over the tree and
change its shape using the associativity and fixity information you have
for each operator. This technique can be applied whenever you have a
total ordering on the set of possible operator precedences (e.g. where
precedences are specified numerically), and is used by the Glasgow Haskell
Compiler.


As far as choosing an instance of an overloaded operator or function to
use is concerned, separate compilation can make it harder for compilers to
tell whether specialised instances of functions are either available for
use, or in need of generation.


C++ has a set of baroque type coercion rules which are applied, so the a
specific instance of an overloaded function can always be chosen at
compile time. You miss out on run-time sloth, at the price of being
bitten by unexpected coercions if you aren't suitably careful while
writing your C++ code.


Haskell compilers use a suitably specialised instance of a function at
compile time whenever such is known to exist, and otherwise use the
generic version of the function (if *that* exists). Compilers for other
modular languages with support for polymorphism and overloading presumably
do the same thing.


<b (e&oe)


--
Bryan O'Sullivan u nas est tolko odyeen yagnyonok seychas.
Computing Science Department email: bos@cyclic.com, bos@dcs.gla.ac.uk
University of Glasgow web.gunge: http://www.scrg.cs.tcd.ie/~bos
--

Return to the comp.compilers page.
Search the comp.compilers archives again.