ghc/compiler/types/TypeRep.lhs

   1 %
   2 % (c) The GRASP/AQUA Project, Glasgow University, 1998
   3 %
   4 \section[TypeRep]{Type - friends' interface}
   5
   6 \begin{code}
   7 module TypeRep (
   8         TyThing(..),
   9         Type(..), TyNote(..),           -- Representation visible
  10         PredType(..),                   -- to friends
  11
  12         Kind, ThetaType,                -- Synonyms
  13         TyVarSubst,
  14
  15         funTyCon,
  16
  17         -- Pretty-printing
  18         pprType, pprParendType,
  19         pprPred, pprTheta, pprThetaArrow, pprClassPred,
  20
  21         -- Re-export fromKind
  22         liftedTypeKind, unliftedTypeKind, openTypeKind,
  23         isLiftedTypeKind, isUnliftedTypeKind, isOpenTypeKind,
  24         mkArrowKind, mkArrowKinds,
  25         pprKind, pprParendKind
  26     ) where
  27
  28 #include "HsVersions.h"
  29
  30 import {-# SOURCE #-} DataCon( DataCon, dataConName )
  31
  32 -- friends:
  33 import Kind
  34 import Var        ( Id, TyVar, tyVarKind )
  35 import VarEnv     ( TyVarEnv )
  36 import VarSet     ( TyVarSet )
  37 import Name       ( Name, NamedThing(..), mkWiredInName )
  38 import OccName    ( mkOccFS, tcName )
  39 import BasicTypes ( IPName, tupleParens )
  40 import TyCon      ( TyCon, mkFunTyCon, tyConArity, tupleTyConBoxity, isTupleTyCon )
  41 import Class      ( Class )
  42
  43 -- others
  44 import PrelNames        ( gHC_PRIM, funTyConKey, listTyConKey, parrTyConKey, hasKey )
  45 import Outputable
  46 \end{code}
  47
  48 %************************************************************************
  49 %*                                                                      *
  50 \subsection{Type Classifications}
  51 %*                                                                      *
  52 %************************************************************************
  53
  54 A type is
  55
  56         *unboxed*       iff its representation is other than a pointer
  57                         Unboxed types are also unlifted.
  58
  59         *lifted*        A type is lifted iff it has bottom as an element.
  60                         Closures always have lifted types:  i.e. any
  61                         let-bound identifier in Core must have a lifted
  62                         type.  Operationally, a lifted object is one that
  63                         can be entered.
  64
  65                         Only lifted types may be unified with a type variable.
  66
  67         *algebraic*     A type with one or more constructors, whether declared
  68                         with "data" or "newtype".
  69                         An algebraic type is one that can be deconstructed
  70                         with a case expression.
  71                         *NOT* the same as lifted types,  because we also
  72                         include unboxed tuples in this classification.
  73
  74         *data*          A type declared with "data".  Also boxed tuples.
  75
  76         *primitive*     iff it is a built-in type that can't be expressed
  77                         in Haskell.
  78
  79 Currently, all primitive types are unlifted, but that's not necessarily
  80 the case.  (E.g. Int could be primitive.)
  81
  82 Some primitive types are unboxed, such as Int#, whereas some are boxed
  83 but unlifted (such as ByteArray#).  The only primitive types that we
  84 classify as algebraic are the unboxed tuples.
  85
  86 examples of type classifications:
  87
  88 Type            primitive       boxed           lifted          algebraic
  89 -----------------------------------------------------------------------------
  90 Int#,           Yes             No              No              No
  91 ByteArray#      Yes             Yes             No              No
  92 (# a, b #)      Yes             No              No              Yes
  93 (  a, b  )      No              Yes             Yes             Yes
  94 [a]             No              Yes             Yes             Yes
  95
  96
  97
  98         ----------------------
  99         A note about newtypes
 100         ----------------------
 101
 102 Consider
 103         newtype N = MkN Int
 104
 105 Then we want N to be represented as an Int, and that's what we arrange.
 106 The front end of the compiler [TcType.lhs] treats N as opaque,
 107 the back end treats it as transparent [Type.lhs].
 108
 109 There's a bit of a problem with recursive newtypes
 110         newtype P = MkP P
 111         newtype Q = MkQ (Q->Q)
 112
 113 Here the 'implicit expansion' we get from treating P and Q as transparent
 114 would give rise to infinite types, which in turn makes eqType diverge.
 115 Similarly splitForAllTys and splitFunTys can get into a loop.
 116
 117 Solution:
 118
 119 * Newtypes are always represented using NewTcApp, never as TyConApp.
 120
 121 * For non-recursive newtypes, P, treat P just like a type synonym after
 122   type-checking is done; i.e. it's opaque during type checking (functions
 123   from TcType) but transparent afterwards (functions from Type).
 124   "Treat P as a type synonym" means "all functions expand NewTcApps
 125   on the fly".
 126
 127   Applications of the data constructor P simply vanish:
 128         P x = x
 129
 130
 131 * For recursive newtypes Q, treat the Q and its representation as
 132   distinct right through the compiler.  Applications of the data consructor
 133   use a coerce:
 134         Q = \(x::Q->Q). coerce Q x
 135   They are rare, so who cares if they are a tiny bit less efficient.
 136
 137 The typechecker (TcTyDecls) identifies enough type construtors as 'recursive'
 138 to cut all loops.  The other members of the loop may be marked 'non-recursive'.
 139
 140
 141 %************************************************************************
 142 %*                                                                      *
 143 \subsection{The data type}
 144 %*                                                                      *
 145 %************************************************************************
 146
 147
 148 \begin{code}
 149 type TyVarSubst = TyVarEnv Type
 150
 151 data Type
 152   = TyVarTy TyVar
 153
 154   | AppTy
 155         Type            -- Function is *not* a TyConApp
 156         Type
 157
 158   | TyConApp            -- Application of a TyCon
 159         TyCon           -- *Invariant* saturated appliations of FunTyCon and
 160                         --      synonyms have their own constructors, below.
 161         [Type]          -- Might not be saturated.
 162
 163   | NewTcApp            -- Application of a NewType TyCon.   All newtype applications
 164         TyCon           -- show up like this until they are fed through newTypeRep,
 165                         -- which returns
 166                         --      * an ordinary TyConApp for non-saturated,
 167                         --       or recursive newtypes
 168                         --
 169                         --      * the representation type of the newtype for satuarted,
 170                         --        non-recursive ones
 171                         -- [But the result of a call to newTypeRep is always consumed
 172                         --  immediately; it never lives on in another type.  So in any
 173                         --  type, newtypes are always represented with NewTcApp.]
 174         [Type]          -- Might not be saturated.
 175
 176   | FunTy               -- Special case of TyConApp: TyConApp FunTyCon [t1,t2]
 177         Type
 178         Type
 179
 180   | ForAllTy            -- A polymorphic type
 181         TyVar
 182         Type
 183
 184   | PredTy              -- A high level source type
 185         PredType        -- ...can be expanded to a representation type...
 186
 187   | NoteTy              -- A type with a note attached
 188         TyNote
 189         Type            -- The expanded version
 190
 191 data TyNote
 192   = FTVNote TyVarSet    -- The free type variables of the noted expression
 193
 194   | SynNote Type        -- Used for type synonyms
 195                         -- The Type is always a TyConApp, and is the un-expanded form.
 196                         -- The type to which the note is attached is the expanded form.
 197 \end{code}
 198
 199 -------------------------------------
 200                 Source types
 201
 202 A type of the form
 203         PredTy p
 204 represents a value whose type is the Haskell predicate p,
 205 where a predicate is what occurs before the '=>' in a Haskell type.
 206 It can be expanded into its representation, but:
 207
 208         * The type checker must treat it as opaque
 209         * The rest of the compiler treats it as transparent
 210
 211 Consider these examples:
 212         f :: (Eq a) => a -> Int
 213         g :: (?x :: Int -> Int) => a -> Int
 214         h :: (r\l) => {r} => {l::Int | r}
 215
 216 Here the "Eq a" and "?x :: Int -> Int" and "r\l" are all called *predicates*
 217 Predicates are represented inside GHC by PredType:
 218
 219 \begin{code}
 220 data PredType
 221   = ClassP Class [Type]         -- Class predicate
 222   | IParam (IPName Name) Type   -- Implicit parameter
 223
 224 type ThetaType = [PredType]
 225 \end{code}
 226
 227 (We don't support TREX records yet, but the setup is designed
 228 to expand to allow them.)
 229
 230 A Haskell qualified type, such as that for f,g,h above, is
 231 represented using
 232         * a FunTy for the double arrow
 233         * with a PredTy as the function argument
 234
 235 The predicate really does turn into a real extra argument to the
 236 function.  If the argument has type (PredTy p) then the predicate p is
 237 represented by evidence (a dictionary, for example, of type (predRepTy p).
 238
 239
 240 %************************************************************************
 241 %*                                                                      *
 242                         TyThing
 243 %*                                                                      *
 244 %************************************************************************
 245
 246 Despite the fact that DataCon has to be imported via a hi-boot route,
 247 this module seems the right place for TyThing, because it's needed for
 248 funTyCon and all the types in TysPrim.
 249
 250 \begin{code}
 251 data TyThing = AnId     Id
 252              | ADataCon DataCon
 253              | ATyCon   TyCon
 254              | AClass   Class
 255
 256 instance Outputable TyThing where
 257   ppr (AnId   id)   = ptext SLIT("AnId")     <+> ppr id
 258   ppr (ATyCon tc)   = ptext SLIT("ATyCon")   <+> ppr tc
 259   ppr (AClass cl)   = ptext SLIT("AClass")   <+> ppr cl
 260   ppr (ADataCon dc) = ptext SLIT("ADataCon") <+> ppr (dataConName dc)
 261
 262 instance NamedThing TyThing where       -- Can't put this with the type
 263   getName (AnId id)     = getName id    -- decl, because the DataCon instance
 264   getName (ATyCon tc)   = getName tc    -- isn't visible there
 265   getName (AClass cl)   = getName cl
 266   getName (ADataCon dc) = dataConName dc
 267 \end{code}
 268
 269
 270 %************************************************************************
 271 %*                                                                      *
 272 \subsection{Wired-in type constructors
 273 %*                                                                      *
 274 %************************************************************************
 275
 276 We define a few wired-in type constructors here to avoid module knots
 277
 278 \begin{code}
 279 funTyCon = mkFunTyCon funTyConName (mkArrowKinds [argTypeKind, openTypeKind] liftedTypeKind)
 280         -- You might think that (->) should have type (?? -> ? -> *), and you'd be right
 281         -- But if we do that we get kind errors when saying
 282         --      instance Control.Arrow (->)
 283         -- becuase the expected kind is (*->*->*).  The trouble is that the
 284         -- expected/actual stuff in the unifier does not go contra-variant, whereas
 285         -- the kind sub-typing does.  Sigh.  It really only matters if you use (->) in
 286         -- a prefix way, thus:  (->) Int# Int#.  And this is unusual.
 287
 288 funTyConName = mkWiredInName gHC_PRIM
 289                         (mkOccFS tcName FSLIT("(->)"))
 290                         funTyConKey
 291                         Nothing                 -- No parent object
 292                         (ATyCon funTyCon)       -- Relevant TyCon
 293 \end{code}
 294
 295
 296 %************************************************************************
 297 %*                                                                      *
 298 \subsection{The external interface}
 299 %*                                                                      *
 300 %************************************************************************
 301
 302 @pprType@ is the standard @Type@ printer; the overloaded @ppr@ function is
 303 defined to use this.  @pprParendType@ is the same, except it puts
 304 parens around the type, except for the atomic cases.  @pprParendType@
 305 works just by setting the initial context precedence very high.
 306
 307 \begin{code}
 308 data Prec = TopPrec     -- No parens
 309           | FunPrec     -- Function args; no parens for tycon apps
 310           | TyConPrec   -- Tycon args; no parens for atomic
 311           deriving( Eq, Ord )
 312
 313 maybeParen :: Prec -> Prec -> SDoc -> SDoc
 314 maybeParen ctxt_prec inner_prec pretty
 315   | ctxt_prec < inner_prec = pretty
 316   | otherwise              = parens pretty
 317
 318 ------------------
 319 pprType, pprParendType :: Type -> SDoc
 320 pprType       ty = ppr_type TopPrec   ty
 321 pprParendType ty = ppr_type TyConPrec ty
 322
 323 ------------------
 324 pprPred :: PredType -> SDoc
 325 pprPred (ClassP cls tys) = pprClassPred cls tys
 326 pprPred (IParam ip ty)   = ppr ip <> dcolon <> pprType ty
 327
 328 pprClassPred :: Class -> [Type] -> SDoc
 329 pprClassPred clas tys = ppr clas <+> sep (map pprParendType tys)
 330
 331 pprTheta :: ThetaType -> SDoc
 332 pprTheta theta = parens (sep (punctuate comma (map pprPred theta)))
 333
 334 pprThetaArrow :: ThetaType -> SDoc
 335 pprThetaArrow theta
 336   | null theta = empty
 337   | otherwise  = parens (sep (punctuate comma (map pprPred theta))) <+> ptext SLIT("=>")
 338
 339 ------------------
 340 instance Outputable Type where
 341     ppr ty = pprType ty
 342
 343 instance Outputable PredType where
 344     ppr = pprPred
 345
 346 instance Outputable name => OutputableBndr (IPName name) where
 347     pprBndr _ n = ppr n -- Simple for now
 348
 349 ------------------
 350         -- OK, here's the main printer
 351
 352 ppr_type :: Prec -> Type -> SDoc
 353 ppr_type p (TyVarTy tv)               = ppr tv
 354 ppr_type p (PredTy pred)              = braces (ppr pred)
 355 ppr_type p (NoteTy (SynNote ty1) ty2) = ppr_type p ty1
 356 ppr_type p (NoteTy other         ty2) = ppr_type p ty2
 357
 358 ppr_type p (TyConApp tc tys) = ppr_tc_app p tc tys
 359 ppr_type p (NewTcApp tc tys) = ifPprDebug (ptext SLIT("<nt>")) <>
 360                                ppr_tc_app p tc tys
 361
 362 ppr_type p (AppTy t1 t2) = maybeParen p TyConPrec $
 363                            pprType t1 <+> ppr_type TyConPrec t2
 364
 365 ppr_type p (FunTy ty1 ty2)
 366   = -- We don't want to lose synonyms, so we mustn't use splitFunTys here.
 367     maybeParen p FunPrec $
 368     sep (ppr_type FunPrec ty1 : ppr_fun_tail ty2)
 369   where
 370     ppr_fun_tail (FunTy ty1 ty2) = (arrow <+> ppr_type FunPrec ty1) : ppr_fun_tail ty2
 371     ppr_fun_tail other_ty        = [arrow <+> pprType other_ty]
 372
 373 ppr_type p ty@(ForAllTy _ _)
 374   = maybeParen p FunPrec $
 375     sep [pprForAll tvs, pprThetaArrow ctxt, pprType tau]
 376   where
 377     (tvs,  rho) = split1 [] ty
 378     (ctxt, tau) = split2 [] rho
 379
 380     split1 tvs (ForAllTy tv ty)        = split1 (tv:tvs) ty
 381     split1 tvs (NoteTy (FTVNote _) ty) = split1 tvs ty
 382     split1 tvs ty                      = (reverse tvs, ty)
 383
 384     split2 ps (NoteTy (FTVNote _) arg   -- Rather a disgusting case
 385                `FunTy` res)           = split2 ps (arg `FunTy` res)
 386     split2 ps (PredTy p `FunTy` ty)   = split2 (p:ps) ty
 387     split2 ps (NoteTy (FTVNote _) ty) = split2 ps ty
 388     split2 ps ty                      = (reverse ps, ty)
 389
 390 ppr_tc_app :: Prec -> TyCon -> [Type] -> SDoc
 391 ppr_tc_app p tc []
 392   = ppr tc
 393 ppr_tc_app p tc [ty]
 394   | tc `hasKey` listTyConKey = brackets (pprType ty)
 395   | tc `hasKey` parrTyConKey = ptext SLIT("[:") <> pprType ty <> ptext SLIT(":]")
 396 ppr_tc_app p tc tys
 397   | isTupleTyCon tc && tyConArity tc == length tys
 398   = tupleParens (tupleTyConBoxity tc) (sep (punctuate comma (map pprType tys)))
 399   | otherwise
 400   = maybeParen p TyConPrec $
 401     ppr tc <+> sep (map (ppr_type TyConPrec) tys)
 402
 403 -------------------
 404 pprForAll tvs = ptext SLIT("forall") <+> sep (map pprTvBndr tvs) <> dot
 405
 406 pprTvBndr tv | isLiftedTypeKind kind = ppr tv
 407              | otherwise             = parens (ppr tv <+> dcolon <+> pprKind kind)
 408              where
 409                kind = tyVarKind tv
 410 \end{code}
 411