[Hugs-users] TypeCastery

[Anthony Clayden]

A typical consequence of combining FunDeps + Overlapping instances is that
you have to make the result parameter more general than it needs be, then
use a TypeCast constraint to improve it.

There's a classic example in the HList paper [*], Section 9 'A generic type
equality predicate'.

> class TypeEq x y b  | x y -> b
>
> instance TypeEq x x HTrue                   -- HTrue, HFalse are just two
datatypes
>
> instance (TypeCast HFalse b)
>                  => TypeEq x y b                    -- can't put TypeEq x
y HFalse

(And really all of the tricky type improvement in that paper boils down to
that technique, whether or not there's an explicit TypeEq test.)

The paper says the TypeEq solution is GHC-specific. That's true but .... I
wonder if they discussed their results with the Hugs team at the time,
because it's not needed drastic surgery to make Hugs do that. (Perhaps I
broke something, but if so it's going to take a convoluted example to find
it. I've built a routine that merges TRex records by matching label names,
with horrendous amounts of overlap and typecasting.)

The technique relies on TypeCast, which does use FunDeps to mutually
improve/unify its two parameters. Nowadays in GHC you'd use the (~)
constraint. TypeCast does use a complicated chain of "indirection"
superconstraints on instances, but does not use overlaps -- indeed there's
only a single instance for each of the classes involved. I'd been happily
using the version of TypeCast given in Appendix D 'Generic type unification
cont'd'. Then I re-read the paper, which claimed it didn't work in Hugs
[Section 9 'Reification of type unification']:

"The most generic implementation of TypeCast, which works for both Hugs and
GHC, is ... For this implementation to work, we need ... Otherwise, type
simplification will ... and thereby inline the unification." IOW
unification will be too 'eager'/too smart and see that we're trying to
evade the FunDep consistency rule.
"Alas, this implementation [Appendix D alternative] is specific to GHC; it
does not work in Hugs because of the peculiarities of that system with
regard to MPTCs and functional dependencies, ..."

I'm experiencing that the Section 9 implementation claimed to work in Hugs,
doesn't; and the Appendix D implementation claimed to not work in Hugs,
does. That's using the legitimate distro version of Hugs Sep2006. Possibly
Hugs changed after 2004 when the HList work was reported. (In Section 6 of
the paper "We give up on persuading Hugs." so I guess they didn't explore
further.)

That is, the Section 9 implementation exhibits the 'eager' type
unification, whether or not I declare TypeCast in a separate module and
"import it at a higher level in the module hierarchy" [Section 9]. That is,
if I'm doing that right: what does "separate compilation" mean in context
of Hugs? It's an interpreter not a compiler; it doesn't produce
executables/object code. Indeed if you import a library -- even one of the
standard Report-defined libraries, it goes and gets the library source and
compiles that alongside the client program. There's no Haskell
interface/.hi files that I can see(?)

Oh, and there's another advantage to avoiding separate compilation: Hugs
can see all the instances and their constraints (and instances of the
constraint classes) across all the modules. So no 'orphan instances' -- the
problems with which were amongst the reasons for Section 6 'Overlapping
banned'. "we do not want to depend on the doubtful future of overlapping
instances in general ... GHC's instance selection is lazy, whereas Hugs' is
eager".

This leads the paper on to "what's known as the Data.Typeable approach at
the type level". But the cure is worse than the disease! It's just not
scalable and not workable. So the version of HList that has persisted to
this day does use the combo of Fundeps + Overlaps, and despite the paper's
misgivings, that has persistently been stable in GHC. No "doubtful future"
after a dozen years.

To pick up a misrepresentation: "GHC's instance selection is lazy": no,
GHC's validation of overlapping instances is lazy; but its selection is
eager, too eager: it commits to an instance inside each module, ignoring
the possibility this module is imported into another with an overlapping
module which is a better fit. Whereas the alleged "Hugs' is eager" is also
opposite to the truth: Hugs' selection of an instance is delayed as much as
possible until it's sure there's only one fit (it can see all instances in
all imports). Validation of overlap is eager: instances (heads) must be in
strict substitution sequence. That's often a nuisance, but a price I'm
prepared to pay to get better coherence.

'Orphan instances' (and overlap thereof) are certainly a danger in GHC.
Avoiding them was part of the motivation for Closed Type Families to be
grouped in a single syntactic unit/in a single module. And yet GHC knows
how to defer instance selection if there's no unique/suitable instance
visible in a module. Why can't it do that everywhere? Or at least warn if
imports contain instances that are overlapped in a different module.

Then it seems to me:
* not only does GHC have a "bogus" implementation of the FunDep consistency
rule; but also
* GHC's implementation of Overlaps is broken.

Hugs' implementation of both is a lot more restrictive, and more coherent.
I'm not finding it prevents any programs. It does require I structure them
in specific ways.


AntC


[*] Strongly Typed Heterogeneous Collections 2004, Oleg Kiselyov, Ralf
Lämmel, Keean Schupke
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/hugs-users/attachments/20181004/7e1fbf3b/attachment.html>