Implement "roles" into GHC.

Roles are a solution to the GeneralizedNewtypeDeriving type-safety
problem.

Roles were first described in the "Generative type abstraction" paper,
by Stephanie Weirich, Dimitrios Vytiniotis, Simon PJ, and Steve Zdancewic.
The implementation is a little different than that paper. For a quick
primer, check out Note [Roles] in Coercion. Also see
http://ghc.haskell.org/trac/ghc/wiki/Roles
and
http://ghc.haskell.org/trac/ghc/wiki/RolesImplementation
For a more formal treatment, check out docs/core-spec/core-spec.pdf.

This fixes Trac #1496, #4846, #7148.

7 files changed, 457 insertions, 67 deletions

diff --git a/docs/core-spec/CoreLint.ott b/docs/core-spec/CoreLint.ott
index c452877ad5..c2dba49612 100644
--- a/docs/core-spec/CoreLint.ott
+++ b/docs/core-spec/CoreLint.ott
@@ -1,3 +1,9 @@
+%%
+%% CoreLint.ott
+%%
+%% defines formal version of core typing rules
+%%
+%% See accompanying README file
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%  Static semantics  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -54,7 +60,7 @@ t = literalType lit
 G |-tm lit : t
 
 G |-tm e : s
-G |-co g : s ~#k t
+G |-co g : s ~Rep k t
 ------------------- :: Cast
 G |-tm e |> g : t
 
@@ -115,7 +121,7 @@ G |-ty t : k2
 ---------------------------------------------------- :: Case
 G |-tm case e as z_s return t of </ alti // i /> : t
 
-G |-co g : t1 ~#k t2
+G |-co g : t1 ~Nom k t2
 -------------------- :: Coercion
 G |-tm g : t1 ~#k t2
 
@@ -144,88 +150,101 @@ G |-ki k ok
 ---------------------------------------- :: TyVar
 G |-bnd alpha_k ok
 
-defn G  |- co g : t1 ~# k t2 ::  :: lintCoercion :: 'Co_'
+defn G  |- co g : t1 ~ R k t2 ::  :: lintCoercion :: 'Co_'
   {{ com Coercion typing, \coderef{coreSyn/CoreLint.lhs}{lintCoercion} }}
-  {{ tex [[G]] \labeledjudge{co} [[g]] : [[t1]] \mathop{\sim_{\#}^{[[k]]} } [[t2]] }}
+  {{ tex [[G]] \labeledjudge{co} [[g]] : [[t1]] \mathop{\sim_{[[R]]}^{[[k]]} } [[t2]] }}
 by
 
 G |-ty t : k
 ---------------------- :: Refl
-G |-co <t> : t ~#k t
+G |-co <t>_R : t ~R k t
 
-G |-co g1 : s1 ~#k1 t1
-G |-co g2 : s2 ~#k2 t2
+G |-co g1 : s1 ~R k1 t1
+G |-co g2 : s2 ~R k2 t2
 G |-arrow k1 -> k2 : k
 ------------------------- :: TyConAppCoFunTy
-G |-co (->) g1 g2 : (s1 -> s2) ~#k (t1 -> t2)
+G |-co (->)_R g1 g2 : (s1 -> s2) ~R k (t1 -> t2)
 
 T /= (->)
-</ G |-co gi : si ~#ki ti // i />
+</ Ri // i /> = tyConRolesX R T
+</ G |-co gi : si ~Ri ki ti // i />
 G |-app </ (si : ki) // i /> : tyConKind T ~> k
 --------------------------------- :: TyConAppCo
-G |-co T </ gi // i /> : T </ si // i />  ~#k T </ ti // i />
+G |-co T_R </ gi // i /> : T </ si // i />  ~R k T </ ti // i />
 
-G |-co g1 : s1 ~#k1 t1
-G |-co g2 : s2 ~#k2 t2
+G |-co g1 : s1 ~R k1 t1
+G |-co g2 : s2 ~Nom k2 t2
 G |-app (s2 : k2) : k1 ~> k
 --------------------- :: AppCo
-G |-co g1 g2 : (s1 s2) ~#k (t1 t2)
+G |-co g1 g2 : (s1 s2) ~R k (t1 t2)
+
+G |-co g1 : s1 ~Ph k1 t1
+G |-co g2 : s2 ~Ph k2 t2
+G |-app (s2 : k2) : k1 ~> k
+--------------------- :: AppCoPhantom
+G |-co g1 g2 : (s1 s2) ~Ph k (t1 t2)
 
 G |-ki k1 ok
-G, z_k1 |-co g : s ~#k2 t
+G, z_k1 |-co g : s ~R k2 t
 --------------------------- :: ForAllCo
-G |-co forall z_k1. g : (forall z_k1.s) ~#k2 (forall z_k1.t)
+G |-co forall z_k1. g : (forall z_k1.s) ~R k2 (forall z_k1.t)
 
 z_(t ~#BOX t) elt G
 ----------------------- :: CoVarCoBox
-G |-co z_(t ~#BOX t) : t ~#BOX t
+G |-co z_(t ~#BOX t) : t ~Nom BOX t
 
 z_(s ~#k t) elt G
 k /= BOX
------------------------ :: CoVarCo
-G |-co z_(s ~#k t) : s ~#k t
+----------------------- :: CoVarCoNom
+G |-co z_(s ~#k t) : s ~Nom k t
+
+z_(s ~R#k t) elt G
+k /= BOX
+----------------------- :: CoVarCoRepr
+G |-co z_(s ~R#k t) : s ~Rep k t
 
 G |-ty t1 : k
------------------------------ :: UnsafeCo
-G |-co t1 ==>! t2 : t1 ~#k t2
+----------------------------- :: UnivCo
+G |-co t1 ==>!_R t2 : t1 ~R k t2
 
-G |-co g : t1 ~#k t2
+G |-co g : t1 ~R k t2
 ------------------------- :: SymCo
-G |-co sym g : t2 ~#k t1
+G |-co sym g : t2 ~R k t1
 
-G |-co g1 : t1 ~#k t2
-G |-co g2 : t2 ~#k t3
+G |-co g1 : t1 ~R k t2
+G |-co g2 : t2 ~R k t3
 ----------------------- :: TransCo
-G |-co g1 ; g2 : t1 ~#k t3
+G |-co g1 ; g2 : t1 ~R k t3
 
-G |-co g : (T </ sj // j />) ~#k (T </ tj // j />)
+G |-co g : (T </ sj // j />) ~R k (T </ tj // j />)
 length </ sj // j /> = length </ tj // j />
 i < length </ sj // j />
 G |-ty si : k
+R' = (tyConRolesX R T)[i]
 ---------------------- :: NthCo
-G |-co nth i g : si ~#k ti
+G |-co nth i g : si ~R' k ti
 
-G |-co g : (s1 s2) ~#k (t1 t2)
+G |-co g : (s1 s2) ~Nom k' (t1 t2)
 G |-ty s1 : k
 ----------------------- :: LRCoLeft
-G |-co Left g : s1 ~#k t1
+G |-co Left g : s1 ~Nom k t1
 
-G |-co g : (s1 s2) ~#k (t1 t2)
+G |-co g : (s1 s2) ~Nom k' (t1 t2)
 G |-ty s2 : k
 ----------------------- :: LRCoRight
-G |-co Right g : s2 ~#k t2
+G |-co Right g : s2 ~Nom k t2
 
-G |-co g : forall m.s ~#k forall n.t
+G |-co g : forall m.s ~R k forall n.t
 G |-ty t0 : k0
 m = z_k1
 k0 <: k1
 --------------------- :: InstCo
-G |-co g t0 : s[m |-> t0] ~#k t[n |-> t0]
+G |-co g t0 : s[m |-> t0] ~R k t[n |-> t0]
 
-C = T </ axBranchkk // kk />
+C = T_R0 </ axBranchkk // kk />
 0 <= ind < length </ axBranchkk // kk />
-forall </ ni // i />. (</ s1j // j /> ~> t1) = (</ axBranchkk // kk />)[ind]
-</ G |-co gi : s'i ~#k'i t'i // i />
+forall </ ni_Ri // i />. (</ s1j // j /> ~> t1) = (</ axBranchkk // kk />)[ind]
+</ G |-co gi : s'i ~Ri k'i t'i // i />
 </ substi @ // i /> = inits(</ [ ni |-> s'i ] // i />)
 </ ni = zi_ki // i />
 </ k'i <: substi(ki) // i />
@@ -234,7 +253,76 @@ no_conflict(C, </ s2j // j />, ind, ind-1)
 t2 = t1 </ [ni |-> t'i] // i />
 G |-ty t2 : k
 ------------------------------------------------------ :: AxiomInstCo
-G |-co C ind </ gi // i /> : T </ s2j // j /> ~#k t2
+G |-co C ind </ gi // i /> : T </ s2j // j /> ~R0 k t2
+
+defn validRoles T ::  :: checkValidRoles :: 'Cvr_'
+  {{ com Type constructor role validity, \coderef{typecheck/TcTyClsDecls.lhs}{checkValidRoles} }}
+by  
+
+</ Ki // i /> = tyConDataCons T
+</ Rj // j /> = tyConRoles T
+</ validDcRoles </ Rj // j /> Ki // i />
+------------------------------------ :: DataCons
+validRoles T
+
+defn validDcRoles </ Raa // aa /> K :: :: check_dc_roles :: 'Cdr_'
+  {{ com Data constructor role validity, \coderef{typecheck/TcTyClsDecls.lhs}{check\_dc\_roles} }}
+by
+
+forall </ naa // aa />. forall </ mbb // bb />. </ tcc // cc /> @ -> T </ naa // aa /> = dataConRepType K
+</ </ naa : Raa // aa />, </ mbb : Nom // bb /> |- tcc : Rep // cc />
+--------------------------------- :: Args
+validDcRoles </ Raa // aa /> K
+
+defn O |- t : R  ::   :: check_ty_roles :: 'Ctr_'
+  {{ com Type role validity, \coderef{typecheck/TcTyClsDecls.lhs}{check\_ty\_roles} }}
+  {{ tex [[O]] \labeledjudge{ctr} [[t]] : [[R]] }}
+by
+
+O(n) = R'
+R' <= R
+---------- :: TyVarTy
+O |- n : R
+
+</ Ri // i /> = tyConRoles T
+</ Ri elt { Nom, Rep } => O |- ti : Ri // i />
+-------------------------- :: TyConAppRep
+O |- T </ ti // i /> : Rep
+
+</ O |- ti : Nom // i />
+--------------------------- :: TyConAppNom
+O |- T </ ti // i /> : Nom
+
+O |- t1 : R
+O |- t2 : Nom
+-------------------------- :: AppTy
+O |- t1 t2 : R
+
+O |- t1 : R
+O |- t2 : R
+------------------- :: FunTy
+O |- t1 -> t2 : R
+
+O, n : Nom |- t : R
+--------------------- :: ForAllTy
+O |- forall n. t : R
+
+------------------ :: LitTy
+O |- lit : R
+
+defn R1 <= R2 ::  :: ltRole :: 'Rlt_'
+  {{ com Sub-role relation, \coderef{types/Coercion.lhs}{ltRole} }}
+  {{ tex [[R1]] \leq [[R2]] }}
+by
+
+-------- :: Nominal
+Nom <= R
+
+-------- :: Phantom
+R <= Ph
+
+------- :: Refl
+R <= R 
 
 defn G |- ki k ok ::  :: lintKind :: 'K_'
   {{ com Kind validity, \coderef{coreSyn/CoreLint.lhs}{lintKind} }}
@@ -410,24 +498,24 @@ by
 ------------------------------------------------ :: NoBranch
 no_conflict(C, </ si // i/>, ind, -1)
 
-C = T </ axBranchkk // kk />
-forall </ ni // i />. (</ tj // j /> ~> t') = (</ axBranchkk // kk />)[ind2]
+C = T_R </ axBranchkk // kk />
+forall </ ni_Ri // i />. (</ tj // j /> ~> t') = (</ axBranchkk // kk />)[ind2]
 apart(</ sj // j />, </ tj // j />)
 no_conflict(C, </ sj // j />, ind1, ind2-1)
 ------------------------------------------------ :: Incompat
 no_conflict(C, </ sj // j />, ind1, ind2)
 
-C = T </ axBranchkk // kk />
-forall </ ni // i />. (</ tj // j /> ~> s) = (</ axBranchkk // kk />)[ind1]
-forall </ n'i // i />. (</ t'j // j /> ~> s') = (</ axBranchkk // kk />)[ind2]
+C = T_R </ axBranchkk // kk />
+forall </ ni_Ri // i />. (</ tj // j /> ~> s) = (</ axBranchkk // kk />)[ind1]
+forall </ n'i_R'i // i />. (</ t'j // j /> ~> s') = (</ axBranchkk // kk />)[ind2]
 apart(</ tj // j />, </ t'j // j />)
 no_conflict(C, </ sj // j />, ind1, ind2-1)
 ------------------------------------------- :: CompatApart
 no_conflict(C, </ sj // j />, ind1, ind2)
 
-C = T </ axBranchkk // kk />
-forall </ ni // i />. (</ tj // j /> ~> s) = (</ axBranchkk // kk />)[ind1]
-forall </ n'i // i />. (</ t'j // j /> ~> s') = (</ axBranchkk // kk />)[ind2]
+C = T_R </ axBranchkk // kk />
+forall </ ni_Ri // i />. (</ tj // j /> ~> s) = (</ axBranchkk // kk />)[ind1]
+forall </ n'i_R'i // i />. (</ t'j // j /> ~> s') = (</ axBranchkk // kk />)[ind2]
 unify(</ tj // j />, </ t'j // j />) = subst
 subst(s) = subst(s')
 ----------------------------------------- :: CompatCoincident
diff --git a/docs/core-spec/CoreSyn.ott b/docs/core-spec/CoreSyn.ott
index e6fae08956..ca060f2f72 100644
--- a/docs/core-spec/CoreSyn.ott
+++ b/docs/core-spec/CoreSyn.ott
@@ -1,3 +1,9 @@
+%%
+%% CoreSyn.ott
+%%
+%% defines formal version of core syntax
+%%
+%% See accompanying README file
 
 embed {{ tex-preamble
   \newcommand{\coderef}[2]{\ghcfile{#1}:\texttt{#2}%
@@ -93,6 +99,8 @@ t {{ tex \tau }}, k {{ tex \kappa }}, s {{ tex \sigma }}
   | tyConKind T             :: M :: tyConKind     {{ com \coderef{types/TyCon.lhs}{tyConKind} }}
   | t1 ~# k t2              :: M :: unliftedEq    {{ com Metanotation for coercion types }}
     {{ tex [[t1]] \mathop{\sim_{\#}^{[[k]]} } [[t2]] }}
+  | t1 ~R# k t2             :: M :: unliftedREq   {{ com Metanotation for coercion types }}
+    {{ tex [[t1]] \mathop{\sim_{\mathsf{R}\#}^{[[k]]} } [[t2]] }}
   | literalType t           :: M :: literalType   {{ com \coderef{basicTypes/Literal.lhs}{literalType} }}
   | ( t )                   :: M :: parens        {{ com Parentheses }}
   | t [ n |-> s ]           :: M :: TySubst       {{ com Type substitution }}
@@ -106,14 +114,14 @@ t {{ tex \tau }}, k {{ tex \kappa }}, s {{ tex \sigma }}
 %% COERCIONS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
 g {{ tex \gamma }} :: 'Coercion_' ::= {{ com Coercions, \coderef{types/Coercion.lhs}{Coercion} }}
-  | < t >                   ::   :: Refl          {{ com Reflexivity }}
-    {{ tex \langle [[t]] \rangle }}
-  | T </ gi // i />         ::   :: TyConAppCo    {{ com Type constructor application }}
+  | < t > _ R               ::   :: Refl          {{ com Reflexivity }}
+    {{ tex {\langle [[t]] \rangle}_{[[R]]} }}
+  | T RA  </ gi // i />     ::   :: TyConAppCo    {{ com Type constructor application }}
   | g1 g2                   ::   :: AppCo         {{ com Application }}
   | forall n . g            ::   :: ForAllCo      {{ com Polymorphism }}
   | n                       ::   :: CoVarCo       {{ com Variable }}
   | C ind </ gj // j />     ::   :: AxiomInstCo   {{ com Axiom application }}
-  | t1 ==>! t2              ::   :: UnsafeCo      {{ com Unsafe coercion }}
+  | t1 ==>! RA t2           ::   :: UnivCo        {{ com Universal coercion }}
   | sym g                   ::   :: SymCo         {{ com Symmetry }}
   | g1 ; g2                 ::   :: TransCo       {{ com Transitivity }}
   | nth I g                 ::   :: NthCo         {{ com Projection (0-indexed) }}
@@ -128,12 +136,21 @@ LorR :: 'LeftOrRight_' ::= {{ com left or right deconstructor, \coderef{types/Co
   | Right            ::   :: CRight               {{ com Right projection }}
 
 C :: 'CoAxiom_' ::= {{ com Axioms, \coderef{types/TyCon.lhs}{CoAxiom} }}
-  | T </ axBranchi // ; // i />    ::   :: CoAxiom  {{ com Axiom }}
+  | T RA </ axBranchi // ; // i /> ::   :: CoAxiom  {{ com Axiom }}
   | ( C )                          :: M :: Parens   {{ com Parentheses }}
 
+R {{ tex \rho }} :: 'Role_' ::= {{ com Roles, \coderef{types/CoAxiom.lhs}{Role} }}
+  | Nom              ::   :: Nominal              {{ com Nominal }}
+    {{ tex \mathsf{N} }}
+  | Rep              ::   :: Representational     {{ com Representational }}
+    {{ tex \mathsf{R} }}
+  | Ph               ::   :: Phantom              {{ com Phantom }}
+    {{ tex \mathsf{P} }}
+  | role_list [ i ]  :: M :: RoleListIndex        {{ com Look up in list }}
+
 axBranch, b :: 'CoAxBranch_' ::= {{ com Axiom branches, \coderef{types/TyCon.lhs}{CoAxBranch} }}
-  | forall </ ni // i /> . ( </ tj // j /> ~> s )  ::   :: CoAxBranch  {{ com Axiom branch }}
-  | ( </ axBranchi // i /> ) [ ind ]               :: M :: lookup      {{ com List lookup }}
+  | forall </ ni RAi // i /> . ( </ tj // j /> ~> s )  ::   :: CoAxBranch  {{ com Axiom branch }}
+  | ( </ axBranchi // i /> ) [ ind ]                   :: M :: lookup      {{ com List lookup }}
 
 %% TYCONS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
@@ -149,13 +166,14 @@ T :: 'TyCon_' ::= {{ com Type constructors, \coderef{types/TyCon.lhs}{TyCon} }}
   | dataConTyCon K :: M :: dataConTyCon    {{ com TyCon extracted from DataCon }}
 
 H :: 'PrimTyCon_' ::= {{ com Primitive type constructors, \coderef{prelude/TysPrim.lhs}{} }}
-  | Int#         ::   :: intPrimTyCon           {{ com Unboxed Int }}
-  | ( ~# )       ::   :: eqPrimTyCon            {{ com Unboxed equality }}
-  | BOX          ::   :: superKindTyCon         {{ com Sort of kinds }}
-  | *            ::   :: liftedTypeKindTyCon    {{ com Kind of lifted types }}
-  | #            ::   :: unliftedTypeKindTyCon  {{ com Kind of unlifted types }}
-  | OpenKind     ::   :: openTypeKindTyCon      {{ com Either $*$ or $\#$ }}
-  | Constraint   ::   :: constraintTyCon        {{ com Constraint }}
+  | Int#         ::   :: intPrimTyCon           {{ com Unboxed Int (\texttt{intPrimTyCon}) }}
+  | ( ~# )       ::   :: eqPrimTyCon            {{ com Unboxed equality (\texttt{eqPrimTyCon}) }}
+  | ( ~R# )      ::   :: eqReprPrimTyCon        {{ com Unboxed representational equality (\texttt{eqReprPrimTyCon}) }}
+  | BOX          ::   :: superKindTyCon         {{ com Sort of kinds (\texttt{superKindTyCon}) }}
+  | *            ::   :: liftedTypeKindTyCon    {{ com Kind of lifted types (\texttt{liftedTypeKindTyCon}) }}
+  | #            ::   :: unliftedTypeKindTyCon  {{ com Kind of unlifted types (\texttt{unliftedTypeKindTyCon}) }}
+  | OpenKind     ::   :: openTypeKindTyCon      {{ com Either $*$ or $\#$ (\texttt{openTypeKindTyCon}) }}
+  | Constraint   ::   :: constraintTyCon        {{ com Constraint (\texttt{constraintTyCon}) }}
 
 %% CONTEXTS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
@@ -164,6 +182,10 @@ G {{ tex \Gamma }} :: 'LintM_Bindings_' ::= {{ com List of bindings, \coderef{co
   | </ Gi // , // i />       ::   :: Concat    {{ com Context concatenation }}
   | vars_of binding          :: M :: VarsOf    {{ com \coderef{coreSyn/CoreSyn.lhs}{bindersOf} }}
 
+O {{ tex \Omega }} :: 'VarEnv_Role_' ::= {{ com Mapping from type variables to roles }}
+  | </ ni : Ri // i />       ::   :: List      {{ com List of bindings }}
+  | O1 , O2                  :: M :: Concat    {{ com Concatenate two lists }}
+
 S {{ tex \Sigma }} :: 'St_' ::= {{ com Runtime store }}
   | [ n |-> e ]            ::   :: Binding  {{ com Single binding }}
   | </ Si // , // i />     ::   :: Concat   {{ com Store concatentation }}
@@ -201,6 +223,17 @@ ind, I {{ tex i }} :: 'Ind_' ::= {{ com Indices, numbers }}
 type_list :: 'TypeList_' ::= {{ com List of types }}
   | </ si // i />     ::   :: List
 
+RA {{ tex {\!\!\!{}_{\rho} } }} :: 'RoleAnnot_' ::= {{ com Role annotation }}
+  | _ R                    :: M :: annotation
+  {{ tex {}_{[[R]]} }}
+
+role_list :: 'RoleList_' ::= {{ com List of roles }}
+  | </ Ri // , // i />     ::   :: List
+  | tyConRolesX R T        :: M :: tyConRolesX
+  | tyConRoles T           :: M :: tyConRoles
+  | ( role_list )          :: M :: Parens
+  | { role_list }          :: M :: Braces
+
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%  Terminals  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -226,6 +259,7 @@ terminals :: 'terminals_' ::=
   | BOX          ::   :: BOX              {{ tex \Box }}
   | Int#         ::   :: int_hash         {{ tex {\textsf{Int} }_{\#} }}
   | ~#           ::   :: eq_hash          {{ tex \mathop{ {\sim}_{\#} } }}
+  | ~R#          ::   :: eq_repr_hash     {{ tex \mathop{ {\sim}_{\mathsf{R}\#} } }}
   | OpenKind     ::   :: OpenKind         {{ tex \textsf{OpenKind} }}
   | ok           ::   :: ok               {{ tex \textsf{ ok} }}
   | no_duplicates ::  :: no_duplicates    {{ tex \textsf{no\_duplicates } }}
@@ -257,6 +291,11 @@ terminals :: 'terminals_' ::=
   | no_conflict  ::   :: no_conflict      {{ tex \textsf{no\_conflict} }}
   | apart        ::   :: apart            {{ tex \textsf{apart} }}
   | unify        ::   :: unify            {{ tex \textsf{unify} }}
+  | tyConRolesX  ::   :: tyConRolesX      {{ tex \textsf{tyConRolesX} }}
+  | tyConRoles   ::   :: tyConRoles       {{ tex \textsf{tyConRoles} }}
+  | tyConDataCons ::  :: tyConDataCons    {{ tex \textsf{tyConDataCons} }}
+  | validRoles   ::   :: validRoles       {{ tex \textsf{validRoles} }}
+  | validDcRoles ::   :: validDcRoles     {{ tex \textsf{validDcRoles} }}
   | -->          ::   :: steps            {{ tex \longrightarrow }}
   | coercionKind ::   :: coercionKind     {{ tex \textsf{coercionKind} }}
 
@@ -303,6 +342,14 @@ formula :: 'formula_' ::=
   | C1 = C2                            ::   :: axiom_rewrite
   | apart ( </ ti // i /> , </ sj // j /> ) :: :: apart
   | unify ( </ ti // i /> , </ sj // j /> ) = subst :: :: unify
+  | role_list1 = role_list2            ::   :: eq_role_list
+  | R1 /= R2                           ::   :: role_neq
+  | R1 = R2                            ::   :: eq_role
+  | </ Ki // i /> = tyConDataCons T    ::   :: tyConDataCons
+  | O ( n ) = R                        ::   :: role_lookup
+  | R elt role_list                    ::   :: role_elt
+  | formula1 => formula2               ::   :: implication
+    {{ tex [[formula1]] \implies [[formula2]] }}
   | alt1 = alt2                        ::   :: alt_rewrite
   | e1 = e2                            ::   :: e_rewrite
   | no other case matches              ::   :: no_other_case
@@ -336,4 +383,6 @@ Subst_TmMapping <= Type_TySubstListPost
 
 Expr_Type <= formula_e_rewrite
 
+Coercion_TyConAppCo <= Coercion_AppCo
+
 Expr_Coercion <= Subst_TmMapping
diff --git a/docs/core-spec/OpSem.ott b/docs/core-spec/OpSem.ott
index 53e1f288a9..1c21ada0ec 100644
--- a/docs/core-spec/OpSem.ott
+++ b/docs/core-spec/OpSem.ott
@@ -83,7 +83,7 @@ S |- case e as n return t of </ alti // i /> --> u[n |-> e]
 
 T </ taa // aa /> ~#k T </ t'aa // aa /> = coercionKind g
 forall </ alphaaa_kaa // aa />. forall </ betabb_k'bb // bb />. </ t1cc // cc /> @-> T </ alphaaa_kaa // aa /> = dataConRepType K
-</ e'cc = ecc |> (t1cc @ </ [alphaaa_kaa |-> nth aa g] // aa /> </ [betabb_k'bb |-> <sbb>] // bb />) // cc />
+</ e'cc = ecc |> (t1cc @ </ [alphaaa_kaa |-> nth aa g] // aa /> </ [betabb_k'bb |-> <sbb>_Nom] // bb />) // cc />
 --------------------------- :: CasePush
 S |- case (K </ taa // aa /> </ sbb // bb /> </ ecc // cc />) |> g as n return t2 of </ alti // i /> --> case K </ t'aa // aa /> </ sbb // bb /> </ e'cc // cc /> as n return t2 of </ alti // i />
 
diff --git a/docs/core-spec/README b/docs/core-spec/README
index e193955490..1fb304d261 100644
--- a/docs/core-spec/README
+++ b/docs/core-spec/README
@@ -64,7 +64,7 @@ your notation to LaTeX. Three different homs are used:
   help disambiguate otherwise-ambiguous parses. Getting these right is hard,
   so if you have trouble, you're not alone.
 
-- In one place, it was necessary to use an @ symbol to disambiguate parses. The
+- In a few places, it is necessary to use an @ symbol to disambiguate parses. The
   @ symbol is not typeset and is used solely for disambiguation. Feel free to use
   it if necessary to disambiguate other parses.
 
diff --git a/docs/core-spec/core-spec.mng b/docs/core-spec/core-spec.mng
index 246be067fc..2e8134c7a1 100644
--- a/docs/core-spec/core-spec.mng
+++ b/docs/core-spec/core-spec.mng
@@ -7,6 +7,7 @@
 \usepackage{xcolor}
 \usepackage{fullpage}
 \usepackage{multirow}
+\usepackage{url}
 
 \newcommand{\ghcfile}[1]{\textsl{#1}}
 \newcommand{\arraylabel}[1]{\multicolumn{2}{l}{\!\!\!\!\!\!\!\!\!\text{\underline{#1}:}}}
@@ -19,7 +20,7 @@
 \setlength{\parindent}{0in}
 \setlength{\parskip}{1ex}
 
-\newcommand{\gram}[1]{\ottgrammartabular{#1\ottinterrule}}
+\newcommand{\gram}[1]{\ottgrammartabular{#1\ottafterlastrule}}
 
 \begin{document}
 
@@ -148,13 +149,21 @@ a term-level literal, but we are ignoring this distinction here.
 
 Invariants on coercions:
 \begin{itemize}
-\item $[[<t1 t2>]]$ is used; never $[[<t1> <t2>]]$.
-\item If $[[<T>]]$ is applied to some coercions, at least one of which is not
-reflexive, use $[[T </ gi // i />]]$, never $[[<T> g1 g2]] \ldots$.
-\item The $[[T]]$ in $[[T </gi//i/>]]$ is never a type synonym, though it could
+\item $[[<t1 t2>_R]]$ is used; never $[[<t1>_R <t2>_Nom]]$.
+\item If $[[<T>_R]]$ is applied to some coercions, at least one of which is not
+reflexive, use $[[T_R </ gi // i />]]$, never $[[<T>_R g1 g2]] \ldots$.
+\item The $[[T]]$ in $[[T_R </gi//i/>]]$ is never a type synonym, though it could
 be a type function.
 \end{itemize}
 
+Roles label what equality relation a coercion is a witness of. Nominal equality
+means that two types are identical (have the same name); representational equality
+means that two types have the same representation (introduced by newtypes); and
+phantom equality includes all types. See \url{http://ghc.haskell.org/trac/ghc/wiki/Roles}
+for more background.
+
+\gram{\ottR}
+
 Is it a left projection or a right projection?
 
 \gram{\ottLorR}
@@ -285,12 +294,22 @@ a dead id and for one-tuples. These checks are omitted here.
 
 \subsection{Coercion typing}
 
+In the coercion typing judgment, the $\#$ marks are left off the equality
+operators to reduce clutter. This is not actually inconsistent, because
+the GHC function that implements this check, \texttt{lintCoercion}, actually
+returns four separate values (the kind, the two types, and the role), not
+a type with head $[[(~#)]]$ or $[[(~R#)]]$. Note that the difference between
+these two forms of equality is interpreted in the rules \ottdrulename{Co\_CoVarCoNom}
+and \ottdrulename{Co\_CoVarCoRepr}.
+
 \ottdefnlintCoercion{}
 
 In \ottdrulename{Co\_AxiomInstCo}, the use of $[[inits]]$ creates substitutions from
 the first $i$ mappings in $[[ </ [ni |-> si] // i /> ]]$. This has the effect of 
 folding the substitution over the kinds for kind-checking.
 
+See Section~\ref{sec:tyconroles} for more information about $[[tyConRolesX]]$.
+
 \subsection{Name consistency}
 
 There are two very similar checks for names, one declared as a local function:
@@ -327,6 +346,31 @@ There are two very similar checks for names, one declared as a local function:
 
 \ottdefnisSubKind{}
 
+\subsection{Roles}
+\label{sec:tyconroles}
+
+During type-checking, role inference is carried out, assigning roles to the
+arguments of every type constructor. The function $[[tyConRoles]]$ extracts these
+roles. Also used in other judgments is $[[tyConRolesX]]$, which is the same as
+$[[tyConRoles]]$, but with an arbitrary number of $[[Nom]]$ at the end, to account
+for potential oversaturation.
+
+The checks encoded in the following
+judgments are run from \coderef{typecheck/TcTyClsDecls.lhs}{checkValidTyCon}
+when \texttt{-dcore-lint} is set.
+
+\ottdefncheckValidRoles{}
+
+\ottdefncheckXXdcXXroles{}
+
+In the following judgment, the role $[[R]]$ is an \emph{input}, not an output.
+
+\ottdefncheckXXtyXXroles{}
+
+These judgments depend on a sub-role relation:
+
+\ottdefnltRole{}
+
 \subsection{Branched axiom conflict checking}
 \label{sec:no_conflict}
 
diff --git a/docs/core-spec/core-spec.pdf b/docs/core-spec/core-spec.pdf
index 180d9bed78..cb21286abb 100644
--- a/docs/core-spec/core-spec.pdf
+++ b/docs/core-spec/core-spec.pdf
diff --git a/docs/users_guide/glasgow_exts.xml b/docs/users_guide/glasgow_exts.xml
index f972a4bd56..8111a81e63 100644
--- a/docs/users_guide/glasgow_exts.xml
+++ b/docs/users_guide/glasgow_exts.xml
@@ -3525,7 +3525,7 @@ dictionary, only slower!
 </para>
 
 
-<sect3> <title> Generalising the deriving clause </title>
+<sect3 id="generalized-newtype-deriving"> <title> Generalising the deriving clause </title>
 <para>
 GHC now permits such instances to be derived instead,
 using the flag <option>-XGeneralizedNewtypeDeriving</option>,
@@ -3646,6 +3646,8 @@ where
 		derive these classes for a newtype, but it happens in the usual way, not
 		via this new mechanism.
 </para></listitem>
+<listitem><para>
+  The role of the last parameter of each of the <literal>ci</literal> is <emphasis>not</emphasis> <literal>N</literal>. (See <xref linkend="roles"/>.)</para></listitem>
 </itemizedlist>
 Then, for each <literal>ci</literal>, the derived instance
 declaration is:
@@ -10707,7 +10709,214 @@ Jose Pedro Magalhaes, Atze Dijkstra, Johan Jeuring, and Andres Loeh.
 
 </sect1>
 
+<sect1 id="roles">
+<title>Roles
+<indexterm><primary>roles</primary></indexterm>
+</title>
+
+<para>
+Using <option>-XGeneralizedNewtypeDeriving</option> (<xref
+linkend="generalized-newtype-deriving" />), a programmer can take existing
+instances of classes and "lift" these into instances of that class for a
+newtype. However, this is not always safe. For example, consider the following:
+</para>
+
+<programlisting>
+  newtype Age = MkAge { unAge :: Int }
+
+  type family Inspect x
+  type instance Inspect Age = Int
+  type instance Inspect Int = Bool
+
+  class BadIdea a where
+    bad :: a -> Inspect a
+
+  instance BadIdea Int where
+    bad = (> 0)
+
+  deriving instance BadIdea Age    -- not allowed!
+</programlisting>
+
+<para>
+If the derived instance were allowed, what would the type of its method
+<literal>bad</literal> be? It would seem to be <literal>Age -> Inspect
+Age</literal>, which is equivalent to <literal>Age -> Int</literal>, according
+to the type family <literal>Inspect</literal>. Yet, if we simply adapt the
+implementation from the instance for <literal>Int</literal>, the implementation
+for <literal>bad</literal> produces a <literal>Bool</literal>, and we have trouble.
+</para>
+
+<para>
+The way to identify such situations is to have <emphasis>roles</emphasis> assigned
+to type variables of datatypes, classes, and type synonyms.</para>
+
+<para>
+Roles as implemented in GHC are a from a simplified version of the work
+described in <ulink
+url="http://www.seas.upenn.edu/~sweirich/papers/popl163af-weirich.pdf">Generative
+type abstraction and type-level computation</ulink>, published at POPL 2011.</para>
+
+<sect2>
+<title>Nominal, Representational, and Phantom</title>
+
+<para>The goal of the roles system is to track when two types have the same
+underlying representation. In the example above, <literal>Age</literal> and
+<literal>Int</literal> have the same representation. But, the corresponding
+instances of <literal>BadIdea</literal> would <emphasis>not</emphasis> have
+the same representation, because the types of the implementations of
+<literal>bad</literal> would be different.</para>
+
+<para>Suppose we have two uses of a type constructor, each applied to the same
+parameters except for one difference. (For example, <literal>T Age Bool
+c</literal> and <literal>T Int Bool c</literal> for some type
+<literal>T</literal>.) The role of a type parameter says what we need to
+know about the two differing type arguments in order to know that the two
+outer types have the same representation (in the example, what must be true
+about <literal>Age</literal> and <literal>Int</literal> in order to show that
+<literal>T Age Bool c</literal> has the same representation as <literal>
+T Int Bool c</literal>).</para>
+
+<para>GHC supports three different roles for type parameters: nominal,
+representational, and phantom. If a type parameter has a nominal (N) role,
+then the two types that differ must not actually differ at all: they must be
+identical (after type family reduction). If a type parameter has a
+representational (R) role, then the two types must have the same
+representation. (If <literal>T</literal>'s first parameter's role is R, then
+<literal>T Age Bool c</literal> and <literal>T Int Bool c</literal> would have
+the same representation, because <literal>Age</literal> and <literal>Int</literal>
+have the same representation.) If a type parameter has a phantom (P) role,
+then we need no further information.</para>
+
+<para>Here are some examples:</para>
+
+<programlisting>
+  data Simple a = MkSimple a          -- a has role R
+
+  type family F
+  type instance F Int = Bool
+  type instance F Age = Char
+
+  data Complex a = MkComplex (F a)    -- a has role N
+
+  data Phant a = MkPhant Bool         -- a has role P
+</programlisting>
+
+<para>The type <literal>Simple</literal> has its parameter at role R, which is
+generally the most common case. <literal>Simple Age</literal> would have the same
+representation as <literal>Simple Int</literal>. The type <literal>Complex</literal>,
+on the other hand, has its parameter at role N, because <literal>Simple Age</literal>
+and <literal>Simple Int</literal> are <emphasis>not</emphasis> the same. Lastly,
+<literal>Phant Age</literal> and <literal>Phant Bool</literal> have the same
+representation, even though <literal>Age</literal> and <literal>Bool</literal>
+are unrelated.</para>
+
+</sect2>
+
+<sect2>
+<title>Role inference</title>
+
+<para>
+What role should a given type parameter should have? GHC performs role
+inference to determine the correct role for every parameter. It starts with a
+few base facts: <literal>(->)</literal> has two R parameters;
+<literal>(~)</literal> has two N parameters; all type families' parameters are
+N; and all GADT-like parameters are N. Then, these facts are propagated to all
+places where these types are used. By defaulting parameters to role P, any
+parameters unused in the right-hand side (or used only in other types in P
+positions) will be P. Whenever a parameter is used in an R position (that is,
+used as a type argument to a constructor whose corresponding variable is at
+role R), we raise its role from P to R. Similarly, when a parameter is used in
+an N position, its role is upgraded to N. We never downgrade a role from N to
+P or R, or from R to P. In this way, we infer the most-general role for each
+parameter.
+</para>
+
+<para>There is one particularly tricky case that should be explained:</para>
+
+<programlisting>
+  data Tricky a b = MkTricky (a b)
+</programlisting>
+
+<para>What should <literal>Tricky</literal>'s roles be? At first blush, it would
+seem that both <literal>a</literal> and <literal>b</literal> should be at role R,
+since both are used in the right-hand side and neither is involved in a type family.
+However, this would be wrong, as the following example shows:</para>
 
+<programlisting>
+  data Nom a = MkNom (F a)   -- type family F from example above
+</programlisting>
+
+<para>Is <literal>Tricky Nom Age</literal> representationally equal to
+<literal>Tricky Nom Int</literal>? No! The former stores a <literal>Char</literal>
+and the latter stores a <literal>Bool</literal>. The solution to this is
+to require all parameters to type variables to have role N. Thus, GHC would
+infer role R for <literal>a</literal> but role N for <literal>b</literal>.</para>
+
+</sect2>
+
+<sect2>
+<title>Role annotations
+<indexterm><primary>-XRoleAnnotations</primary></indexterm>
+</title>
+
+<para>
+Sometimes the programmer wants to constrain the inference process. For
+example, the base library contains the following definition:
+</para>
+
+<programlisting>
+  data Ptr a = Ptr Addr#
+</programlisting>
+
+<para>
+The idea is that <literal>a</literal> should really be an R parameter, but
+role inference assigns it to P. This makes some level of sense: a pointer to
+an <literal>Int</literal> really is representationally the same as a pointer
+to a <literal>Bool</literal>. But, that's not at all how we want to use
+<literal>Ptr</literal>s! So, we want to be able to say</para>
+
+<programlisting>
+  data Ptr a@R = Ptr Addr#
+</programlisting>
+
+<para>
+The <literal>@R</literal> (enabled with <option>-XRoleAnnotations</option>) annotation forces the
+parameter a to be at role R, not role P. GHC then checks
+the user-supplied roles to make sure they don't break any promises. It would
+be bad, for example, if the user could make <literal>BadIdea</literal>'s role be R.
+</para>
+
+<para>The other place where role annotations may be necessary are in
+<literal>hs-boot</literal> files (<xref linkend="mutual-recursion"/>), where
+the right-hand sides of definitions can be omitted. As usual, the
+types/classes declared in an <literal>hs-boot</literal> file must match up
+with the definitions in the <literal>hs</literal> file, including down to the
+roles. The default role is R in <literal>hs-boot</literal> files,
+corresponding to the common use case.</para>
+
+<para>
+Role annotations are allowed on type variables in data, newtype, class,
+and type declarations. They are not allowed on type/data family
+declarations or in explicit foralls in function type signatures.
+The syntax for a role annotation is an <literal>@</literal> sign followed
+by one of <literal>N</literal>, <literal>R</literal>, or <literal>P</literal>,
+directly following a type variable. If the type variable has an explicit
+kind annotation, the role annotation goes after the kind annotation, outside
+the parentheses. Here are some examples:</para>
+
+<programlisting>
+  data T1 a b@P = MkT1 a     -- b is not used; annotation is fine but unnecessary
+  data T2 a b@P = MkT2 b     -- ERROR: b is used and cannot be P
+  data T3 a b@N = MkT3 a     -- OK: N is higher than necessary, but safe
+  data T4 (a :: * -> *)@N = MkT4 (a Int)    -- OK, but N is higher than necessary
+  class C a@R b where ...    -- OK
+  type X a@N = ...           -- OK
+  type family F a@R          -- ERROR: annotations not allowed on family declarations
+</programlisting>
+
+</sect2>
+
+</sect1>
 
 <!-- Emacs stuff:
      ;;; Local Variables: ***