TypeCastery

Next Topic
 
classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

TypeCastery

AntC
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

_______________________________________________
Hugs-Users mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/hugs-users
Reply | Threaded
Open this post in threaded view
|

~ Swansong [was: TypeCastery]

AntC
(More from the annals of oh-so-easy in yacc.)

On Thu, 4 Oct 2018 at 12:45 AM, Anthony Clayden <[hidden email]> wrote:
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.

... TypeCast, which does use FunDeps to mutually improve/unify its two parameters. Nowadays in GHC you'd use the (~) constraint.

I got so fed up writing out TypeCast constraints; and I'm so used to writing infix (~) in GHC, I implemented (~) in Hugs. This is hard-coded syntax in constraints; I've not implemented type operators. (Mark you, it's also hard-coded in GHC, because (~) is a reserved symbol.)

This needed only changes to the yacc syntax. From that I insisted that "~" is a legitimate name for a class. There is a downside that equality constraints are printed with the '~' prefix -- because all class names are prefix.

To be clear: this is not as powerful or well-integrated as (~) in GHC. You still need at the term level to explicitly cast.

Then I got so fed up writing out explicit typeCast calls ..., I picked up the postfix operators idea
and invented a postfix operator (~::) to do the job.
Trailing double-colon says I'm doing something typeful; tilde connects it to the equality constraint.

Then here's the classic, compiled in Hugs, also exhibiting the FunDeps + Overlaps combo

class TypeEq t t' r  | t t' -> r  where
  typeEq :: t -> t' -> r

instance TypeEq t t TTrue  where
  typeEq _ _ = TTrue

instance (TFalse ~ f) => TypeEq t t' f  where
  typeEq _ _ = (TFalse ~::)      -- without explicit cast, complains type is not general enough


AntC

_______________________________________________
Hugs-Users mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/hugs-users