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