[m-dev.] `highly ambiguous overloading' ??

[Fergus Henderson]

On 19-Mar-2001, Ralph Becket <rbeck at microsoft.com> wrote:
> > From: Fergus Henderson [mailto:fjh at cs.mu.OZ.AU] 
> > Sent: 16 March 2001 21:59
> > 
> > The compiler type-checks things left-to-right, and does 
> > breadth-first search to resolve ambiguities.  If you have a 
> > whole bunch of unifications with an overloaded name like `no' 
> > (which is used both in `bool' and in `maybe(T)'), and nothing 
> > to resolve the ambiguity, then the current implementation 
> > uses up 2^N time and space.  For N > 5 you will get a 
> > warning.  Here N = 6.
> 
> Is there a document or comment somewhere explaining the decision
> to use breadth first?

It's mentioned briefly in my draft thesis ;-)

The main reason for using breadth-first search is that it leads to
better diagnostics.  Breadth-first search means that the compiler
type-checks things left-to-right, considering all the possibilities
with regards to overloading as it goes, so that it reports an error
at the first point in the clause where the types become inconsistent.

Peter Stuckey has proposed an alternative algorithm which avoids the
exponential complexity in most cases (it's not possible to do it in
polynomial time in the general case, at least not unless P=NP).
This algorithm treats type checking as constraint solving, and
solves the constraints by delaying disjunctive constraints (overloading),
and using constraint propagation to eliminate them where possible;
the algorithm only resorts to searching as a last resort, if there
are disjunctive constraints remaining at the end which can't be
eliminated by constraint propagation.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
                                    |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------