relaxed instance rules spec (was: the MPTC Dilemma(pleasesolve))

Ross Paterson ross at
Sat Mar 4 19:52:00 EST 2006

On Sat, Mar 04, 2006 at 10:32:58PM -0000, Claus Reinke wrote:
> >On Thu, Mar 02, 2006 at 12:03:59PM -0000, Claus Reinke wrote:
> >>The way I interpret FDs implies that they introduce a systematic space
> >>leak into the inference process: if any stage in the inference uses *any*
> >>constraint with a class which is subject to an FD, that results in an 
> >>additional bit of information about that class' FD. and we *cannot*
> >>throw that bit of information away unless we know that we will
> >>never need to refer to it in the remainder of the inference chain.
> >
> >But with the current system you can throw it away, because it's implied
> >by the FDs on the classes in the context.  A system where that was
> >not the case would be significantly more complex than the current FDs,
> >which I think disqualifies it for Haskell'.
> I'm not sure what FD system you are referring to here? in the CHR
> representation of FDs (which seems to be the only candidate for 
> Haskell'), you _cannot_ throw this information away, and the 
> potential of doing so accounts for the majority of confluence
> violations in the paper "understanding FDs via CHRs": if you simplify 
> a constraint before using it for propagation, you end up missing
> some improvements and you may not be able to rejoin the diverging 
> deductions.
> that's what I was referring to: there shouldn't be any confluence
> problems with the original code (type classes w FDs), but there are
> confluence problems with the CHRs used to represent that code!

I think we're applying different value judgements to the same data.
The CHR implementation faithfully reflects Mark Jones's original rules
(section 6.2 of his paper, plus context reduction as inherited from
Haskell 98).  Martin is trying to relax Mark's restrictions on the form of
instances while keeping those rules working (confluent and terminating).
You think the problem is the context reduction rule, which should be
changed to retain FD information.  Fair enough, but I disagree, for the
reason I gave.

More information about the Haskell-prime mailing list