On Sat, Jan 14, 2012 at 12:52 AM, Simon Peyton-Jones
<simonpj@microsoft.com> wrote:
Complexities of (Plan B)
~~~~~~~~~~~~~~~~~~~~~~~~
Proposal (Plan B) sounds innocent enough. But I promise you, it isn't.
There has ben some mention of the "left-to-right" bias of Frege type
inference engine; indeed the wohle explanation of which programs are
accepted and which are rejected, inherently involves an understanding
of the type inference algorithm. This is a Very Bad Thing when the
type inference algorithm gets complicated, and GHC's is certainly
complicated.
Here's an example:
type family F a b
data instance F Int [a] = Mk { f :: Int }
g :: F Int b -> ()
h :: F a [Bool] -> ()
k x = (g x, x.f, h x)
Consider type inference on k. Initially we know nothing about the
type of x.
* From the application (g x) we learn that x's type has
shape (F Int <something>).
* From the application (h x) we learn that x's type has
shape (F <something else> [Bool])
* Hence x's type must be (F Int [Bool])
* And hence, using the data family we can see which field
f is intended.
Notice that
a) Neither left to right nor right to left would suffice
b) There is significant interaction with type/data families
(and I can give you more examples with classes and GADTs)
c) In passing we note that it is totally unclear how (Plan A)
would deal with data families
This looks like a swamp. In a simple Hindley-Milner typed language
you might get away with some informal heuristics, but Haskell is far
too complicated.
I rarely use Haskell's complex type machinery (and must admit to very little understanding of it). So before dismissing this as difficult to resolve in the face of a complex type system, For the complex type system I would like to figure out.
* I am assuming that it is always possible to add a type annotation. Is there extra complexity to the annotation, or can we just annotate the record or top-level function?
* which parts of Haskell's complex type sytem will require type annotations for Frege-style records.
* does using a library that uses complex machinery under the hood but tries to limit the complexity of types exposed to the user end up infecting the user's code with respect to difficulty in resolving records.
What makes the Haskell's type system great is first and foremost typeclasses. And this is as complex as the vast majority of code gets. It doesn't sound that bad to have an implementation that works very well for the vast majority of code but requires using type annotations or normal verbose name-spacing for those few parts that are already using verbose name spacing.
- When you have SORF, you don't really need anything else
The blocking issues are described on
http://hackage.haskell.org/trac/ghc/wiki/Records/OverloadedRecordFields
a) "Representation hiding" (look for that heading)
b) "Record update" (ditto), most especially for records whose
fields have polymorphic types
If we fix these we can move forward.
So essentially records are stalled again :(
I will keep trying to see if I can figure something out.