Simon's big boxy-type commit

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.

2 files changed, 24 insertions, 23 deletions

diff --git a/ghc/compiler/parser/Parser.y.pp b/ghc/compiler/parser/Parser.y.pp
index b4acb890eb..0a423f45df 100644
--- a/ghc/compiler/parser/Parser.y.pp
+++ b/ghc/compiler/parser/Parser.y.pp
@@ -774,7 +774,7 @@ gentype :: { LHsType RdrName }
         : btype                         { $1 }
         | btype qtyconop gentype        { LL $ HsOpTy $1 $2 $3 }
         | btype tyvarop  gentype  	{ LL $ HsOpTy $1 $2 $3 }
-	| btype '->' gentype		{ LL $ HsFunTy $1 $3 }
+ 	| btype '->' ctype		{ LL $ HsFunTy $1 $3 }
 
 btype :: { LHsType RdrName }
 	: btype atype			{ LL $ HsAppTy $1 $2 }
@@ -784,10 +784,10 @@ atype :: { LHsType RdrName }
 	: gtycon			{ L1 (HsTyVar (unLoc $1)) }
 	| tyvar				{ L1 (HsTyVar (unLoc $1)) }
 	| strict_mark atype		{ LL (HsBangTy (unLoc $1) $2) }
-	| '(' type ',' comma_types1 ')'	{ LL $ HsTupleTy Boxed  ($2:$4) }
+	| '(' ctype ',' comma_types1 ')'  { LL $ HsTupleTy Boxed  ($2:$4) }
 	| '(#' comma_types1 '#)'	{ LL $ HsTupleTy Unboxed $2     }
-	| '[' type ']'			{ LL $ HsListTy  $2 }
-	| '[:' type ':]'		{ LL $ HsPArrTy  $2 }
+	| '[' ctype ']'			{ LL $ HsListTy  $2 }
+	| '[:' ctype ':]'		{ LL $ HsPArrTy  $2 }
 	| '(' ctype ')'		        { LL $ HsParTy   $2 }
 	| '(' ctype '::' kind ')'	{ LL $ HsKindSig $2 $4 }
 -- Generics
@@ -809,8 +809,8 @@ comma_types0  :: { [LHsType RdrName] }
 	| {- empty -}			{ [] }
 
 comma_types1	:: { [LHsType RdrName] }
-	: type				{ [$1] }
-	| type  ',' comma_types1	{ $1 : $3 }
+	: ctype				{ [$1] }
+	| ctype  ',' comma_types1	{ $1 : $3 }
 
 tv_bndrs :: { [LHsTyVarBndr RdrName] }
 	 : tv_bndr tv_bndrs		{ $1 : $2 }
@@ -1260,7 +1260,7 @@ stmt  :: { LStmt RdrName }
   	| 'rec' stmtlist		{ LL $ mkRecStmt (unLoc $2) }
 
 qual  :: { LStmt RdrName }
-	: infixexp '<-' exp		{% checkPattern $1 >>= \p ->
+	: exp '<-' exp			{% checkPattern $1 >>= \p ->
 					   return (LL $ mkBindStmt p $3) }
 	| exp				{ L1 $ mkExprStmt $1 }
   	| 'let' binds			{ LL $ LetStmt (unLoc $2) }
diff --git a/ghc/compiler/parser/RdrHsSyn.lhs b/ghc/compiler/parser/RdrHsSyn.lhs
index a955791412..75229a88c2 100644
--- a/ghc/compiler/parser/RdrHsSyn.lhs
+++ b/ghc/compiler/parser/RdrHsSyn.lhs
@@ -126,8 +126,8 @@ extractGenericPatTyVars :: LHsBinds RdrName -> [Located RdrName]
 extractGenericPatTyVars binds
   = nubBy eqLocated (foldrBag get [] binds)
   where
-    get (L _ (FunBind _ _ (MatchGroup ms _) _)) acc = foldr (get_m.unLoc) acc ms
-    get other	    			        acc = acc
+    get (L _ (FunBind { fun_matches = MatchGroup ms _ })) acc = foldr (get_m.unLoc) acc ms
+    get other	 	   			          acc = acc
 
     get_m (Match (L _ (TypePat ty) : _) _ _) acc = extract_lty ty acc
     get_m other			       		   acc = acc
@@ -231,15 +231,15 @@ getMonoBind :: LHsBind RdrName -> [LHsDecl RdrName]
 --
 -- No AndMonoBinds or EmptyMonoBinds here; just single equations
 
-getMonoBind (L loc (FunBind lf@(L _ f) inf (MatchGroup mtchs _) _)) binds
+getMonoBind (L loc bind@(FunBind { fun_id = L _ f, fun_matches = MatchGroup mtchs _ })) binds
   | has_args mtchs
   = go mtchs loc binds
   where
-    go mtchs1 loc1 (L loc2 (ValD (FunBind f2 inf2 (MatchGroup mtchs2 _) _)) : binds)
-	| f == unLoc f2 = go (mtchs2++mtchs1) loc binds
+    go mtchs1 loc1 (L loc2 (ValD (FunBind { fun_id = L _ f2, fun_matches = MatchGroup mtchs2 _ })) : binds)
+	| f == f2 = go (mtchs2++mtchs1) loc binds
 	where loc = combineSrcSpans loc1 loc2
     go mtchs1 loc binds
-	= (L loc (FunBind lf inf (mkMatchGroup (reverse mtchs1)) placeHolderNames), binds)
+	= (L loc (bind { fun_matches = mkMatchGroup (reverse mtchs1) }), binds)
 	-- Reverse the final matches, to get it back in the right order
 
 getMonoBind bind binds = (bind, binds)
@@ -583,14 +583,15 @@ checkValDef
 	-> P (HsBind RdrName)
 
 checkValDef lhs opt_sig (L rhs_span grhss)
-  | Just (f,inf,es)  <- isFunLhs lhs []
+  | Just (f,inf,es)  <- isFunLhs lhs
   = if isQual (unLoc f)
 	then parseError (getLoc f) ("Qualified name in function definition: "  ++ 
 					showRdrName (unLoc f))
 	else do ps <- checkPatterns es
 		let match_span = combineSrcSpans (getLoc lhs) rhs_span
 		    matches    = mkMatchGroup [L match_span (Match ps opt_sig grhss)]
-		return (FunBind f inf matches  placeHolderNames)
+		return (FunBind { fun_id = f, fun_infix = inf, fun_matches = matches,
+				  fun_co_fn = idCoercion, bind_fvs = placeHolderNames })
 	-- The span of the match covers the entire equation.  
 	-- That isn't quite right, but it'll do for now.
   | otherwise = do
@@ -634,23 +635,23 @@ mkGadtDecl name ty = ConDecl
 
 -- A variable binding is parsed as a FunBind.
 
-isFunLhs :: LHsExpr RdrName -> [LHsExpr RdrName]
+isFunLhs :: LHsExpr RdrName
   -> Maybe (Located RdrName, Bool, [LHsExpr RdrName])
-isFunLhs (L loc e) = isFunLhs' loc e
+isFunLhs e = go e []
  where
-   isFunLhs' loc (HsVar f) es 
+   go (L loc (HsVar f)) es 
 	| not (isRdrDataCon f)	 	= Just (L loc f, False, es)
-   isFunLhs' loc (HsApp f e) es 	= isFunLhs f (e:es)
-   isFunLhs' loc (HsPar e)   es@(_:_) 	= isFunLhs e es
-   isFunLhs' loc (OpApp l (L loc' (HsVar op)) fix r) es
+   go (L _ (HsApp f e)) es 	 = go f (e:es)
+   go (L _ (HsPar e))   es@(_:_) = go e es
+   go (L loc (OpApp l (L loc' (HsVar op)) fix r)) es
 	| not (isRdrDataCon op) = Just (L loc' op, True, (l:r:es))
 	| otherwise		= 
-		case isFunLhs l es of
+		case go l es of
 		    Just (op', True, j : k : es') ->
 		      Just (op', True, 
 			    j : L loc (OpApp k (L loc' (HsVar op)) fix r) : es')
 		    _ -> Nothing
-   isFunLhs' _ _ _ = Nothing
+   go _ _ = Nothing
 
 ---------------------------------------------------------------------------
 -- Miscellaneous utilities