GitLab

The previous names were not informative at all, and now we have
named kinds like Constraint and datatype promotion to kind, so
we might as well name these too.

I tried to update some comments to the new names, but certainly
many references to the old names remain.

This big patch implements a kind-polymorphic core for GHC. The current
implementation focuses on making sure that all kind-monomorphic programs still
work in the new core; it is not yet guaranteed that kind-polymorphic programs
(using the new -XPolyKinds flag) will work.

For more information, see http://haskell.org/haskellwiki/GHC/Kinds

We only use it for "compiler" sources, i.e. not for libraries.
Many modules have a -fno-warn-tabs kludge for now.

Basically as documented in http://hackage.haskell.org/trac/ghc/wiki/KindFact,
this patch adds a new kind Constraint such that:

  Show :: * -> Constraint
  (?x::Int) :: Constraint
  (Int ~ a) :: Constraint

And you can write *any* type with kind Constraint to the left of (=>):
even if that type is a type synonym, type variable, indexed type or so on.

The following (somewhat related) changes are also made:
 1. We now box equality evidence. This is required because we want
    to give (Int ~ a) the *lifted* kind Constraint
 2. For similar reasons, implicit parameters can now only be of
    a lifted kind. (?x::Int#) => ty is now ruled out
 3. Implicit parameter constraints are now allowed in superclasses
    and instance contexts (this just falls out as OK with the new
    constraint solver)

Internally the following major changes were made:
 1. There is now no PredTy in the Type data type. Instead
    GHC checks the kind of a type to figure out if it is a predicate
 2. There is now no AClass TyThing: we represent classes as TyThings
    just as a ATyCon (classes had TyCons anyway)
 3. What used to be (~) is now pretty-printed as (~#). The box
    constructor EqBox :: (a ~# b) -> (a ~ b)
 4. The type LCoercion is used internally in the constraint solver
    and type checker to represent coercions with free variables
    of type (a ~ b) rather than (a ~# b)

These turn out to be a useful special case of splitTyConApp_maybe.

A refactoring only; no change in behaviour

This addresses Trac #5345, but only partially.  Fundamentally STG Lint
is impossible, because unsafeCoerce# can randomise all the types.

This patch does a bit of fiddle faddling in StgLint which makes it
a bit better, but it's a losing battle. Trac #5345 works though, FWIW.

A "lifting substitition" takes a *type* to a *coercion*, using a
substitution that takes a *type variable* to a *coercion*.  We were
using a CvSubst for this purpose, which was an awkward exception: in
every other use of CvSubst, type variables map only to types.

Turned out that Coercion.liftCoSubst is quite a small function, so I
rewrote it with a special substitution type Coercion.LiftCoSubst, just
for that purpose.  In doing so I found that the function itself was
bizarrely over-complicated ... a direct result of mis-using CvSubst.

So this patch makes it all simpler, faster, and easier to understand.
No bugs fixed though!

When floating a case outwards we must be careful to clone
the binders, since their scope is widening.

Plus lots of tidying up.

* Fix bugs in the packing and unpacking of data
  constructors with equality predicates in their types

* Remove PredCo altogether; instead, coercions between predicated
  types (like  (Eq a, [a]~b) => blah) are treated as if they
  were precisely their underlying representation type
       Eq a -> ((~) [a] b) -> blah
  in this case

* Similarly, Type.coreView no longer treats equality
  predciates specially.

* Implement the cast-of-coercion optimisation in
  Simplify.simplCoercionF

Numerous other small bug-fixes and refactorings.

Annoyingly, OptCoercion had Windows line endings, and this
patch switches to Unix, so it looks as if every line has changed.

See the paper "Practical aspects of evidence based compilation in System FC"

* Coercion becomes a data type, distinct from Type

* Coercions become value-level things, rather than type-level things,
  (although the value is zero bits wide, like the State token)
  A consequence is that a coerion abstraction increases the arity by 1
  (just like a dictionary abstraction)

* There is a new constructor in CoreExpr, namely Coercion, to inject
  coercions into terms

plus a false ASSERT failure

This dumps a (one-line) listing of the size of the Core program,
just after tidying

In particular there is much less fiddly skolemisation now
Things are not *quite* right (break001 and 006 still fail), 
but they are *much* better than before.

We weren't gathering the type variables free in the kind
of a coercion binder!

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.

After rumination, yet again, on the subject of arity calculation,
I have redone what an ArityType is (it's purely internal to the
CoreArity module), and documented it better.  The result should
fix #3959, and I hope the related #3961, #3983.

There is lots of new documentation: in particular
 * Note [ArityType]  
   describes the new datatype for arity info

 * Note [State hack and bottoming functions] 
   says how bottoming functions are dealt with, particularly
   covering catch# and Trac #3959

I also found I had to be careful not to eta-expand single-method
class constructors; see Note [Newtype classes and eta expansion].
I think this part could be done better, but it works ok.

I was experimenting with making coercions opaque to
arity.  I think this is ultimately the right thing to do
but I've left the functionality unchanged for now.

The main purpose of this patch is to add a bunch of new rules
to the coercion optimiser.  They are documented in the (revised)
Appendix of the System FC paper.  

Some code has moved about:

- OptCoercion is now a separate module, mainly because it
  now uses tcMatchTy, which is defined in Unify, so OptCoercion
  must live higehr up in the hierarchy

- Functions that manipulate Kinds has moved from 
  Type.lhs to Coercion.lhs.  Reason: the function typeKind
  now needs to call coercionKind.  And in any case, a Kind is
  a flavour of Type, so it builds on top of Type; indeed Coercions
  and Kinds are both flavours of Type.

  This change required fiddling with a number of imports, hence
  the one-line changes to otherwise-unrelated modules

- The representation of CoTyCons in TyCon has changed.   Instead of
  an extensional representation (a kind checker) there is now an
  intensional representation (namely TyCon.CoTyConDesc).  This was
  needed for one of the new coercion optimisations.

* Fix a bug that meant that 
     (right (inst (forall tv.co) ty)) 
  wasn't getting optimised.  This showed up in the
  compiled code for ByteCodeItbls

* Add a substitution to optCoercion, so that it simultaneously
  substitutes and optimises.  Both call sites wanted this, and
  optCoercion itself can use it, so it seems a win all round.

In CSE we were getting lots of apprarently-unequal expressions with
the same hash code.  In fact they were perfectly equal -- but we were
using a cheap-and-cheerful equality tests for CoreExpr that said False
for any lambda expression!

This patch adds a proper equality test for Core, with alpha-renaming.
It's easy to do, and will avoid silly cases of CSE failing to fire.

We should get less of this:
  WARNING: file compiler/simplCore/CSE.lhs line 326
  extendCSEnv: long list, length 18
from a compiler built with -DDEBUG

* Core Lint now does full checking of kinds and coercion terms
  which picks up kind errors in coercions that were previously
  simply not checked for

* Coercion.lhs now provides optCoercion which optimises coercion
  terms.  It implements all of Dimitrios's rules

* The constructors for coercion terms now make no attempt to be
  "smart"; instead we rely solely on the coercion optimiser

* CoercionTyCons in TyCon.lhs always had a "custom" kinding rule
  (the coKindFun field of CoercionTyCon) but its type was not 
  clever enough to do both 
     (a) *figure out the result kind*, assuming the whole thing
         is well-kinded in the first place
     (b) *check* the kinds of everything, failing gracefully if
         they aren't right. 
  We need (b) for the new CoreLint stuff. The field now has type
        CoTyConKindChecker
  which does the job nicely.

In preparation for implementing the PushC rule for coercion-swizzling
in the Simplifier, I had to inmplement the three new decomposition
operators for coercions, which I've called csel1, csel2, and cselR.

     co :: ((s1~t1) => r1) ~ ((s2~t2) => r2)
     ---------------------------------------
              csel1 co :: s1~s2

and similarly csel2, cselR.

On the way I fixed the coercionKind function for types of form
          (s1~t2) => r2
which currently are expressed as a forall type.  

And I refactored quite a bit to help myself understand what is
going on.

Type synonyms that don't mention one of their type parameters on the 
RHS are a pain in the neck.  This patch fixes a long-standing bug (that
simply has not appeared before) in that exprType could return a type
mentioning an existentially-quantified variable (in one of those ignored
argument positions).

See CoreUtils Note [Existential variables and silly type synonyms]

The fix is not entirely beautiful, but it works, and is very localised.

This is a fix to 
  Tue Mar  3 17:42:58 GMT 2009  simonpj@microsoft.com
    * Fix Trac #3066: checking argument types in foreign calls
which I embarassingly got wrong.

Have to be careful when expanding recursive newtypes.

Pls merge.

  MERGE TO 6.10

  MERGE TO 6.10