GitLab

This patch embodies many, many changes to the contraint solver, which
make it simpler, more robust, and more beautiful.  But it has taken
me ages to get right. The forcing issue was some obscure programs
involving recursive dictionaries, but these eventually led to a
massive refactoring sweep.

Main changes are:
 * No more "frozen errors" in the monad.  Instead "insoluble
   constraints" are now part of the WantedConstraints type.

 * The WantedConstraint type is a product of bags, instead of (as
   before) a bag of sums.  This eliminates a good deal of tagging and
   untagging.

 * This same WantedConstraints data type is used
     - As the way that constraints are gathered
     - As a field of an implication constraint
     - As both argument and result of solveWanted
     - As the argument to reportUnsolved

 * We do not generate any evidence for Derived constraints. They are
   purely there to allow "impovement" by unifying unification
   variables.

 * In consequence, nothing is ever *rewritten* by a Derived
   constraint.  This removes, by construction, all the horrible
   potential recursive-dictionary loops that were making us tear our
   hair out.  No more isGoodRecEv search either. Hurrah!

 * We add the superclass Derived constraints during canonicalisation,
   after checking for duplicates.  So fewer superclass constraints
   are generated than before.

 * Skolem tc-tyvars no longer carry SkolemInfo.  Instead, the
   SkolemInfo lives in the GivenLoc of the Implication, where it
   can be tidied, zonked, and substituted nicely.  This alone is
   a major improvement.

 * Tidying is improved, so that we tend to get t1, t2, t3, rather
   than t1, t11, t111, etc

   Moreover, unification variables are always printed with a digit
   (thus a0, a1, etc), so that plain 'a' is available for a skolem
   arising from a type signature etc. In this way,
     (a) We quietly say which variables are unification variables,
         for those who know and care
     (b) Types tend to get printed as the user expects.  If he writes
             f :: a -> a
             f = ...blah...
         then types involving 'a' get printed with 'a', rather than
         some tidied variant.

 * There are significant improvements in error messages, notably
   in the "Cannot deduce X from Y" messages.

This major patch implements the new OutsideIn constraint solving
algorithm in the typecheker, following our JFP paper "Modular type
inference with local assumptions".  

Done with major help from Dimitrios Vytiniotis and Brent Yorgey.

The instances (and deriving declarations) have been taken from the ghc-syb
package.

Make idDetails and idInfo into proper functions, rather than record
fields, so that we can report more informatively if you use thenm on
a non-Id.

This biggish patch addresses Trac #2670.  The main effect is to make
record selectors into ordinary functions, whose unfoldings appear in
interface files, in contrast to their previous existence as magic
"implicit Ids".  This means that the usual machinery of optimisation,
analysis, and inlining applies to them, which was failing before when
the selector was somewhat complicated.  (Which it can be when
strictness annotations, unboxing annotations, and GADTs are involved.)

The change involves the following points

* Changes in Var.lhs to the representation of Var.  Now a LocalId can
  have an IdDetails as well as a GlobalId.  In particular, the
  information that an Id is a record selector is kept in the
  IdDetails.  While compiling the current module, the record selector
  *must* be a LocalId, so that it participates properly in compilation
  (free variables etc).

  This led me to change the (hidden) representation of Var, so that there
  is now only one constructor for Id, not two.

* The IdDetails is persisted into interface files, so that an
  importing module can see which Ids are records selectors.

* In TcTyClDecls, we generate the record-selector bindings in renamed,
  but not typechecked form.  In this way, we can get the typechecker
  to add all the types and so on, which is jolly helpful especially
  when GADTs or type families are involved.  Just like derived
  instance declarations.

  This is the big new chunk of 180 lines of code (much of which is
  commentary).  A call to the same function, mkAuxBinds, is needed in
  TcInstDcls for associated types.

* The typechecker therefore has to pin the correct IdDetails on to 
  the record selector, when it typechecks it.  There was a neat way
  to do this, by adding a new sort of signature to HsBinds.Sig, namely
  IdSig.  This contains an Id (with the correct Name, Type, and IdDetails);
  the type checker uses it as the binder for the final binding.  This
  worked out rather easily.

* Record selectors are no longer "implicit ids", which entails changes to
     IfaceSyn.ifaceDeclSubBndrs
     HscTypes.implicitTyThings
     TidyPgm.getImplicitBinds
  (These three functions must agree.)

* MkId.mkRecordSelectorId is deleted entirely, some 300+ lines (incl
  comments) of very error prone code.  Happy days.

* A TyCon no longer contains the list of record selectors: 
  algTcSelIds is gone

The renamer is unaffected, including the way that import and export of
record selectors is handled.

Other small things

* IfaceSyn.ifaceDeclSubBndrs had a fragile test for whether a data
  constructor had a wrapper.  I've replaced that with an explicit flag
  in the interface file. More robust I hope.

* I renamed isIdVar to isId, which touched a few otherwise-unrelated files.

  MERGE TO 6.10

re-recording to avoid new conflicts was too hard, so I just put it
all in one big patch :-(  (besides, some of the changes depended on
each other.)  Here are what the component patches were:

Fri Dec 28 11:02:55 EST 2007  Isaac Dupree <id@isaac.cedarswampstudios.org>
  * document BreakArray better

Fri Dec 28 11:39:22 EST 2007  Isaac Dupree <id@isaac.cedarswampstudios.org>
  * properly ifdef BreakArray for GHCI

Fri Jan  4 13:50:41 EST 2008  Isaac Dupree <id@isaac.cedarswampstudios.org>
  * change ifs on __GLASGOW_HASKELL__ to account for... (#1405)
  for it not being defined. I assume it being undefined implies
  a compiler with relatively modern libraries but without most
  unportable glasgow extensions.

Fri Jan  4 14:21:21 EST 2008  Isaac Dupree <id@isaac.cedarswampstudios.org>
  * MyEither-->EitherString to allow Haskell98 instance

Fri Jan  4 16:13:29 EST 2008  Isaac Dupree <id@isaac.cedarswampstudios.org>
  * re-portabilize Pretty, and corresponding changes

Fri Jan  4 17:19:55 EST 2008  Isaac Dupree <id@isaac.cedarswampstudios.org>
  * Augment FastTypes to be much more complete

Fri Jan  4 20:14:19 EST 2008  Isaac Dupree <id@isaac.cedarswampstudios.org>
  * use FastFunctions, cleanup FastString slightly

Fri Jan  4 21:00:22 EST 2008  Isaac Dupree <id@isaac.cedarswampstudios.org>
  * Massive de-"#", mostly Int# --> FastInt (#1405)

Fri Jan  4 21:02:49 EST 2008  Isaac Dupree <id@isaac.cedarswampstudios.org>
  * miscellaneous unnecessary-extension-removal

Sat Jan  5 19:30:13 EST 2008  Isaac Dupree <id@isaac.cedarswampstudios.org>
  * add FastFunctions

Older GHCs can't parse OPTIONS_GHC.
This also changes the URL referenced for the -w options from
WorkingConventions#Warnings to CodingStyle#Warnings for the compiler
modules.

This patch introduces type checking for type families of which associated
type synonyms are a special case. E.g.

        type family Sum n m

        type instance Sum Zero n = n
        type instance Sum (Succ n) m = Succ (Sum n m)

where

        data Zero       -- empty type
        data Succ n     -- empty type

In addition we support equational constraints of the form:

        ty1 ~ ty2

(where ty1 and ty2 are arbitrary tau types) in any context where
type class constraints are already allowed, e.g.

        data Equals a b where
                Equals :: a ~ b => Equals a b

The above two syntactical extensions are disabled by default. Enable
with the -XTypeFamilies flag.

For further documentation about the patch, see:

        * the master plan
          http://hackage.haskell.org/trac/ghc/wiki/TypeFunctions

        * the user-level documentation
          http://haskell.org/haskellwiki/GHC/Indexed_types

The patch is mostly backwards compatible, except for:

        * Some error messages have been changed slightly.

        * Type checking of GADTs now requires a bit more type declarations:
          not only should the type of a GADT case scrutinee be given, but also
          that of any identifiers used in the branches and the return type.

Please report any unexpected behavior and incomprehensible error message 
for existing code.

Contributors (code and/or ideas):
        Tom Schrijvers
        Manuel Chakravarty
        Simon Peyton-Jones
        Martin Sulzmann 
with special thanks to Roman Leshchinskiy

Now that coercion variables mention types, a type-lambda binder can
have free variables.  This patch adjusts the free-variable finder
to take account of this, by treating Ids and TyVars more uniformly.

In addition, I fixed a bug in the specialiser that was missing a 
free type variable in a binder.  And a bug in tyVarsOfInst that
was missing the type variables in the kinds of the quantified tyvars.

A type variable has a flag saying whether it is a *type* variable or
a *coercion* variable.  This patch adds assertions to check the flag.

And it adds fixes to places which were Wrong (and hence fired the
assertion)! 

Also removed isCoVar from Coercion, since it's done by Var.isCoVar.

This patch is a start on removing import lists and generally tidying
up the top of each module.  In addition to removing import lists:

   - Change DATA.IOREF -> Data.IORef etc.
   - Change List -> Data.List etc.
   - Remove $Id$
   - Update copyrights
   - Re-order imports to put non-GHC imports last
   - Remove some unused and duplicate imports

Mon Sep 18 16:50:18 EDT 2006  Manuel M T Chakravarty <chak@cse.unsw.edu.au>
  * fixing record selectors
  Sun Aug  6 19:56:29 EDT 2006  Manuel M T Chakravarty <chak@cse.unsw.edu.au>
    * fixing record selectors
    Fri Jul 28 10:24:28 EDT 2006  kevind@bu.edu
    - Bad conflict in tcIfaceDataAlt, at a place where the monster patch had a 
      conflict, too.  I have no idea what the right code is.  -=chak
  NB (at time of 2nd merge): previous conflict resolution was fine

Mon Sep 18 16:43:36 EDT 2006  Manuel M T Chakravarty <chak@cse.unsw.edu.au>
  * Comments only
  Sun Aug  6 17:18:44 EDT 2006  Manuel M T Chakravarty <chak@cse.unsw.edu.au>
    * Comments only
    Tue Jul 25 12:06:00 EDT 2006  simonpj@microsoft.com

Mon Sep 18 16:41:32 EDT 2006  Manuel M T Chakravarty <chak@cse.unsw.edu.au>
  * fix bugs, add boolean flag to identify coercion variables
  Sun Aug  6 17:04:02 EDT 2006  Manuel M T Chakravarty <chak@cse.unsw.edu.au>
    * fix bugs, add boolean flag to identify coercion variables
    Tue Jul 25 06:20:05 EDT 2006  kevind@bu.edu

Mon Sep 18 14:51:33 EDT 2006  Manuel M T Chakravarty <chak@cse.unsw.edu.au>
  * fix some coercion kind representation things, extend exprIsConApp_maybe to non-vanilla
  Sat Aug  5 21:48:21 EDT 2006  Manuel M T Chakravarty <chak@cse.unsw.edu.au>
    * fix some coercion kind representation things, extend exprIsConApp_maybe to non-vanilla
    Wed Jul 19 08:06:28 EDT 2006  kevind@bu.edu

Fri Aug  4 15:11:01 EDT 2006  Manuel M T Chakravarty <chak@cse.unsw.edu.au>
  * Massive patch for the first months work adding System FC to GHC #1
  Broken up massive patch -=chak
  Original log message:  
  This is (sadly) all done in one patch to avoid Darcs bugs.
  It's not complete work... more FC stuff to come.  A compiler
  using just this patch will fail dismally.

Most of the other users of the fptools build system have migrated to
Cabal, and with the move to darcs we can now flatten the source tree
without losing history, so here goes.

The main change is that the ghc/ subdir is gone, and most of what it
contained is now at the top level.  The build system now makes no
pretense at being multi-project, it is just the GHC build system.

No doubt this will break many things, and there will be a period of
instability while we fix the dependencies.  A straightforward build
should work, but I haven't yet fixed binary/source distributions.
Changes to the Building Guide will follow, too.

This very large commit adds impredicativity to GHC, plus
numerous other small things.
  
*** WARNING: I have compiled all the libraries, and
***	     a stage-2 compiler, and everything seems
***	     fine.  But don't grab this patch if you 
***	     can't tolerate a hiccup if something is
***	     broken.
  
The big picture is this:

a) GHC handles impredicative polymorphism, as described in the
   "Boxy types: type inference for higher-rank types and
   impredicativity" paper

b) GHC handles GADTs in the new simplified (and very sligtly less
   epxrssive) way described in the
   "Simple unification-based type inference for GADTs" paper

  
But there are lots of smaller changes, and since it was pre-Darcs
they are not individually recorded.
  
Some things to watch out for:
  
c)   The story on lexically-scoped type variables has changed, as per
     my email.  I append the story below for completeness, but I 
     am still not happy with it, and it may change again.  In particular,
     the new story does not allow a pattern-bound scoped type variable
     to be wobbly, so (\(x::[a]) -> ...) is usually rejected.  This is
     more restrictive than before, and we might loosen up again.
  
d)   A consequence of adding impredicativity is that GHC is a bit less
     gung ho about converting automatically between
  	(ty1 -> forall a. ty2)    and    (forall a. ty1 -> ty2)
     In particular, you may need to eta-expand some functions to make
     typechecking work again.
   
     Furthermore, functions are now invariant in their argument types,
     rather than being contravariant.  Again, the main consequence is
     that you may occasionally need to eta-expand function arguments when
     using higher-rank polymorphism.
  

Please test, and let me know of any hiccups


Scoped type variables in GHC
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	January 2006

0) Terminology.
   
   A *pattern binding* is of the form
	pat = rhs

   A *function binding* is of the form
	f pat1 .. patn = rhs

   A binding of the formm
	var = rhs
   is treated as a (degenerate) *function binding*.


   A *declaration type signature* is a separate type signature for a
   let-bound or where-bound variable:
	f :: Int -> Int

   A *pattern type signature* is a signature in a pattern: 
	\(x::a) -> x
	f (x::a) = x

   A *result type signature* is a signature on the result of a
   function definition:
	f :: forall a. [a] -> a
	head (x:xs) :: a = x

   The form
	x :: a = rhs
   is treated as a (degnerate) function binding with a result
   type signature, not as a pattern binding.

1) The main invariants:

     A) A lexically-scoped type variable always names a (rigid)
 	type variable (not an arbitrary type).  THIS IS A CHANGE.
        Previously, a scoped type variable named an arbitrary *type*.

     B) A type signature always describes a rigid type (since
	its free (scoped) type variables name rigid type variables).
	This is also a change, a consequence of (A).

     C) Distinct lexically-scoped type variables name distinct
	rigid type variables.  This choice is open; 

2) Scoping

2(a) If a declaration type signature has an explicit forall, those type
   variables are brought into scope in the right hand side of the 
   corresponding binding (plus, for function bindings, the patterns on
   the LHS).  
	f :: forall a. a -> [a]
	f (x::a) = [x :: a, x]
   Both occurences of 'a' in the second line are bound by 
   the 'forall a' in the first line

   A declaration type signature *without* an explicit top-level forall
   is implicitly quantified over all the type variables that are
   mentioned in the type but not already in scope.  GHC's current
   rule is that this implicit quantification does *not* bring into scope
   any new scoped type variables.
	f :: a -> a
	f x = ...('a' is not in scope here)...
   This gives compatibility with Haskell 98

2(b) A pattern type signature implicitly brings into scope any type
   variables mentioned in the type that are not already into scope.
   These are called *pattern-bound type variables*.
	g :: a -> a -> [a]
	g (x::a) (y::a) = [y :: a, x]
   The pattern type signature (x::a) brings 'a' into scope.
   The 'a' in the pattern (y::a) is bound, as is the occurrence on 
   the RHS.  

   A pattern type siganture is the only way you can bring existentials 
   into scope.
	data T where
	  MkT :: forall a. a -> (a->Int) -> T

	f x = case x of
		MkT (x::a) f -> f (x::a)

2a) QUESTION
	class C a where
	  op :: forall b. b->a->a

	instance C (T p q) where
	  op = <rhs>
    Clearly p,q are in scope in <rhs>, but is 'b'?  Not at the moment.
    Nor can you add a type signature for op in the instance decl.
    You'd have to say this:
	instance C (T p q) where
	  op = let op' :: forall b. ...
	           op' = <rhs>
	       in op'

3) A pattern-bound type variable is allowed only if the pattern's
   expected type is rigid.  Otherwise we don't know exactly *which*
   skolem the scoped type variable should be bound to, and that means
   we can't do GADT refinement.  This is invariant (A), and it is a 
   big change from the current situation.

	f (x::a) = x	-- NO; pattern type is wobbly
	
	g1 :: b -> b
	g1 (x::b) = x	-- YES, because the pattern type is rigid

	g2 :: b -> b
	g2 (x::c) = x	-- YES, same reason

	h :: forall b. b -> b
	h (x::b) = x	-- YES, but the inner b is bound

	k :: forall b. b -> b
	k (x::c) = x	-- NO, it can't be both b and c

3a) You cannot give different names for the same type variable in the same scope
    (Invariant (C)):

	f1 :: p -> p -> p		-- NO; because 'a' and 'b' would be
	f1 (x::a) (y::b) = (x::a)	--     bound to the same type variable

	f2 :: p -> p -> p		-- OK; 'a' is bound to the type variable
	f2 (x::a) (y::a) = (x::a)	--     over which f2 is quantified
					-- NB: 'p' is not lexically scoped

	f3 :: forall p. p -> p -> p	-- NO: 'p' is now scoped, and is bound to
	f3 (x::a) (y::a) = (x::a)	--     to the same type varialble as 'a'

	f4 :: forall p. p -> p -> p	-- OK: 'p' is now scoped, and its occurences
	f4 (x::p) (y::p) = (x::p)	--     in the patterns are bound by the forall


3b) You can give a different name to the same type variable in different
    disjoint scopes, just as you can (if you want) give diferent names to 
    the same value parameter

	g :: a -> Bool -> Maybe a
	g (x::p) True  = Just x  :: Maybe p
	g (y::q) False = Nothing :: Maybe q

3c) Scoped type variables respect alpha renaming. For example, 
    function f2 from (3a) above could also be written:
	f2' :: p -> p -> p
	f2' (x::b) (y::b) = x::b
   where the scoped type variable is called 'b' instead of 'a'.


4) Result type signatures obey the same rules as pattern types signatures.
   In particular, they can bind a type variable only if the result type is rigid

	f x :: a = x	-- NO

	g :: b -> b
	g x :: b = x	-- YES; binds b in rhs

5) A *pattern type signature* in a *pattern binding* cannot bind a 
   scoped type variable

	(x::a, y) = ...		-- Legal only if 'a' is already in scope

   Reason: in type checking, the "expected type" of the LHS pattern is
   always wobbly, so we can't bind a rigid type variable.  (The exception
   would be for an existential type variable, but existentials are not
   allowed in pattern bindings either.)
 
   Even this is illegal
	f :: forall a. a -> a
	f x = let ((y::b)::a, z) = ... 
	      in 
   Here it looks as if 'b' might get a rigid binding; but you can't bind
   it to the same skolem as a.

6) Explicitly-forall'd type variables in the *declaration type signature(s)*
   for a *pattern binding* do not scope AT ALL.

	x :: forall a. a->a	  -- NO; the forall a does 
	Just (x::a->a) = Just id  --     not scope at all

	y :: forall a. a->a
	Just y = Just (id :: a->a)  -- NO; same reason

   THIS IS A CHANGE, but one I bet that very few people will notice.
   Here's why:

	strange :: forall b. (b->b,b->b)
	strange = (id,id)

	x1 :: forall a. a->a
	y1 :: forall b. b->b
	(x1,y1) = strange

    This is legal Haskell 98 (modulo the forall). If both 'a' and 'b'
    both scoped over the RHS, they'd get unified and so cannot stand
    for distinct type variables. One could *imagine* allowing this:
   
	x2 :: forall a. a->a
	y2 :: forall a. a->a
	(x2,y2) = strange

    using the very same type variable 'a' in both signatures, so that
    a single 'a' scopes over the RHS.  That seems defensible, but odd,
    because though there are two type signatures, they introduce just
    *one* scoped type variable, a.

7) Possible extension.  We might consider allowing
	\(x :: [ _ ]) -> <expr>
    where "_" is a wild card, to mean "x has type list of something", without
    naming the something.

WARNING: this is a big commit.  You might want 
	to wait a few days before updating, in case I've 
	broken something.

	However, if any of the changes are what you wanted,
	please check it out and test!

This commit does three main things:

1. A re-organisation of the way that GHC handles bindings in HsSyn.
   This has been a bit of a mess for quite a while.  The key new
   types are

	-- Bindings for a let or where clause
	data HsLocalBinds id
	  = HsValBinds (HsValBinds id)
	  | HsIPBinds  (HsIPBinds id)
	  | EmptyLocalBinds

	-- Value bindings (not implicit parameters)
	data HsValBinds id
	  = ValBindsIn  -- Before typechecking
		(LHsBinds id) [LSig id]	-- Not dependency analysed
					-- Recursive by default

	  | ValBindsOut	-- After typechecking
		[(RecFlag, LHsBinds id)]-- Dependency analysed

2. Implement Mark Jones's idea of increasing polymoprhism
   by using type signatures to cut the strongly-connected components
   of a recursive group.  As a consequence, GHC no longer insists
   on the contexts of the type signatures of a recursive group
   being identical.

   This drove a significant change: the renamer no longer does dependency
   analysis.  Instead, it attaches a free-variable set to each binding,
   so that the type checker can do the dep anal.  Reason: the typechecker
   needs to do *two* analyses:
	one to find the true mutually-recursive groups
		(which we need so we can build the right CoreSyn)
	one to find the groups in which to typecheck, taking
		account of type signatures

3. Implement non-ground SPECIALISE pragmas, as promised, and as
   requested by Remi and Ross.  Certainly, this should fix the 
   current problem with GHC, namely that if you have
	g :: Eq a => a -> b -> b
   then you can now specialise thus
	SPECIALISE g :: Int -> b -> b
    (This didn't use to work.)

   However, it goes further than that.  For example:
	f :: (Eq a, Ix b) => a -> b -> b
   then you can make a partial specialisation
	SPECIALISE f :: (Eq a) => a -> Int -> Int

    In principle, you can specialise f to *any* type that is
    "less polymorphic" (in the sense of subsumption) than f's 
    actual type.  Such as
	SPECIALISE f :: Eq a => [a] -> Int -> Int
    But I haven't tested that.

    I implemented this by doing the specialisation in the typechecker
    and desugarer, rather than leaving around the strange SpecPragmaIds,
    for the specialiser to find.  Indeed, SpecPragmaIds have vanished 
    altogether (hooray).

    Pragmas in general are handled more tidily.  There's a new
    data type HsBinds.Prag, which lives in an AbsBinds, and carries
    pragma info from the typechecker to the desugarer.


Smaller things

- The loop in the renamer goes via RnExpr, instead of RnSource.
  (That makes it more like the type checker.)

- I fixed the thing that was causing 'check_tc' warnings to be 
  emitted.

Reset the export flag for the new bindings in LiberateCase

------------------------------------------
	Keep-alive set and Template Haskell quotes
	------------------------------------------

a) Template Haskell quotes should be able to mention top-leve
   things without resorting to lifting.  Example

	module Foo( foo ) where
	  f x = x
	  foo = [| f 4 |]

   Here the reference to 'f' is ok; no need to 'lift' it.
   The relevant changes are in TcExpr.tcId

b) However, we must take care not to discard the binding for f,
   so we add it to the 'keep-alive' set for the module.  I've
   now made this into (another) mutable bucket, tcg_keep, 
   in the TcGblEnv

c) That in turn led me to look at the handling of orphan rules;
   as a result I made IdCoreRule into its own data type, which
   has simle but non-local ramifications

------------------------------------
	Add Generalised Algebraic Data Types
	------------------------------------

This rather big commit adds support for GADTs.  For example,

    data Term a where
 	  Lit :: Int -> Term Int
	  App :: Term (a->b) -> Term a -> Term b
	  If  :: Term Bool -> Term a -> Term a
	  ..etc..

    eval :: Term a -> a
    eval (Lit i) = i
    eval (App a b) = eval a (eval b)
    eval (If p q r) | eval p    = eval q
    		    | otherwise = eval r


Lots and lots of of related changes throughout the compiler to make
this fit nicely.

One important change, only loosely related to GADTs, is that skolem
constants in the typechecker are genuinely immutable and constant, so
we often get better error messages from the type checker.  See
TcType.TcTyVarDetails.

There's a new module types/Unify.lhs, which has purely-functional
unification and matching for Type. This is used both in the typechecker
(for type refinement of GADTs) and in Core Lint (also for type refinement).

Comments only

Fix globaliseId wibble which was killing ghci