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, pprTyThingCategory,
  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    ( mkOccNameFS, tcName, parenSymOcc )
  37 import BasicTypes ( IPName, tupleParens )
  38 import TyCon      ( TyCon, mkFunTyCon, tyConArity, tupleTyConBoxity, isTupleTyCon, isRecursiveTyCon, isNewTyCon )
  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 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
 152         Type            -- It must be another AppTy, or TyVarTy
 153                         -- (or NoteTy of these)
 154
 155   | TyConApp            -- Application of a TyCon, including newtypes *and* synonyms
 156         TyCon           --  *Invariant* saturated appliations of FunTyCon and
 157                         --      synonyms have their own constructors, below.
 158                         -- However, *unsaturated* FunTyCons do appear as TyConApps.
 159                         --
 160         [Type]          -- Might not be saturated.
 161                         -- Even type synonyms are not necessarily saturated;
 162                         -- for example unsaturated type synonyms can appear as the
 163                         -- RHS of a type synonym.
 164
 165   | FunTy               -- Special case of TyConApp: TyConApp FunTyCon [t1,t2]
 166         Type
 167         Type
 168
 169   | ForAllTy            -- A polymorphic type
 170         TyVar
 171         Type
 172
 173   | PredTy              -- A high level source type
 174         PredType        -- ...can be expanded to a representation type...
 175
 176   | NoteTy              -- A type with a note attached
 177         TyNote
 178         Type            -- The expanded version
 179
 180 data TyNote = FTVNote TyVarSet  -- The free type variables of the noted expression
 181 \end{code}
 182
 183 -------------------------------------
 184                 Source types
 185
 186 A type of the form
 187         PredTy p
 188 represents a value whose type is the Haskell predicate p,
 189 where a predicate is what occurs before the '=>' in a Haskell type.
 190 It can be expanded into its representation, but:
 191
 192         * The type checker must treat it as opaque
 193         * The rest of the compiler treats it as transparent
 194
 195 Consider these examples:
 196         f :: (Eq a) => a -> Int
 197         g :: (?x :: Int -> Int) => a -> Int
 198         h :: (r\l) => {r} => {l::Int | r}
 199
 200 Here the "Eq a" and "?x :: Int -> Int" and "r\l" are all called *predicates*
 201 Predicates are represented inside GHC by PredType:
 202
 203 \begin{code}
 204 data PredType
 205   = ClassP Class [Type]         -- Class predicate
 206   | IParam (IPName Name) Type   -- Implicit parameter
 207
 208 type ThetaType = [PredType]
 209 \end{code}
 210
 211 (We don't support TREX records yet, but the setup is designed
 212 to expand to allow them.)
 213
 214 A Haskell qualified type, such as that for f,g,h above, is
 215 represented using
 216         * a FunTy for the double arrow
 217         * with a PredTy as the function argument
 218
 219 The predicate really does turn into a real extra argument to the
 220 function.  If the argument has type (PredTy p) then the predicate p is
 221 represented by evidence (a dictionary, for example, of type (predRepTy p).
 222
 223
 224 %************************************************************************
 225 %*                                                                      *
 226                         TyThing
 227 %*                                                                      *
 228 %************************************************************************
 229
 230 Despite the fact that DataCon has to be imported via a hi-boot route,
 231 this module seems the right place for TyThing, because it's needed for
 232 funTyCon and all the types in TysPrim.
 233
 234 \begin{code}
 235 data TyThing = AnId     Id
 236              | ADataCon DataCon
 237              | ATyCon   TyCon
 238              | AClass   Class
 239
 240 instance Outputable TyThing where
 241   ppr thing = pprTyThingCategory thing <+> quotes (ppr (getName thing))
 242
 243 pprTyThingCategory :: TyThing -> SDoc
 244 pprTyThingCategory (ATyCon _)   = ptext SLIT("Type constructor")
 245 pprTyThingCategory (AClass _)   = ptext SLIT("Class")
 246 pprTyThingCategory (AnId   _)   = ptext SLIT("Identifier")
 247 pprTyThingCategory (ADataCon _) = ptext SLIT("Data constructor")
 248
 249 instance NamedThing TyThing where       -- Can't put this with the type
 250   getName (AnId id)     = getName id    -- decl, because the DataCon instance
 251   getName (ATyCon tc)   = getName tc    -- isn't visible there
 252   getName (AClass cl)   = getName cl
 253   getName (ADataCon dc) = dataConName dc
 254 \end{code}
 255
 256
 257 %************************************************************************
 258 %*                                                                      *
 259 \subsection{Wired-in type constructors
 260 %*                                                                      *
 261 %************************************************************************
 262
 263 We define a few wired-in type constructors here to avoid module knots
 264
 265 \begin{code}
 266 funTyCon = mkFunTyCon funTyConName (mkArrowKinds [argTypeKind, openTypeKind] liftedTypeKind)
 267         -- You might think that (->) should have type (?? -> ? -> *), and you'd be right
 268         -- But if we do that we get kind errors when saying
 269         --      instance Control.Arrow (->)
 270         -- becuase the expected kind is (*->*->*).  The trouble is that the
 271         -- expected/actual stuff in the unifier does not go contra-variant, whereas
 272         -- the kind sub-typing does.  Sigh.  It really only matters if you use (->) in
 273         -- a prefix way, thus:  (->) Int# Int#.  And this is unusual.
 274
 275 funTyConName = mkWiredInName gHC_PRIM
 276                         (mkOccNameFS tcName FSLIT("(->)"))
 277                         funTyConKey
 278                         Nothing                 -- No parent object
 279                         (ATyCon funTyCon)       -- Relevant TyCon
 280                         BuiltInSyntax
 281 \end{code}
 282
 283
 284 %************************************************************************
 285 %*                                                                      *
 286 \subsection{The external interface}
 287 %*                                                                      *
 288 %************************************************************************
 289
 290 @pprType@ is the standard @Type@ printer; the overloaded @ppr@ function is
 291 defined to use this.  @pprParendType@ is the same, except it puts
 292 parens around the type, except for the atomic cases.  @pprParendType@
 293 works just by setting the initial context precedence very high.
 294
 295 \begin{code}
 296 data Prec = TopPrec     -- No parens
 297           | FunPrec     -- Function args; no parens for tycon apps
 298           | TyConPrec   -- Tycon args; no parens for atomic
 299           deriving( Eq, Ord )
 300
 301 maybeParen :: Prec -> Prec -> SDoc -> SDoc
 302 maybeParen ctxt_prec inner_prec pretty
 303   | ctxt_prec < inner_prec = pretty
 304   | otherwise              = parens pretty
 305
 306 ------------------
 307 pprType, pprParendType :: Type -> SDoc
 308 pprType       ty = ppr_type TopPrec   ty
 309 pprParendType ty = ppr_type TyConPrec ty
 310
 311 ------------------
 312 pprPred :: PredType -> SDoc
 313 pprPred (ClassP cls tys) = pprClassPred cls tys
 314 pprPred (IParam ip ty)   = ppr ip <> dcolon <> pprType ty
 315
 316 pprClassPred :: Class -> [Type] -> SDoc
 317 pprClassPred clas tys = parenSymOcc (getOccName clas) (ppr clas)
 318                         <+> sep (map pprParendType tys)
 319
 320 pprTheta :: ThetaType -> SDoc
 321 pprTheta theta = parens (sep (punctuate comma (map pprPred theta)))
 322
 323 pprThetaArrow :: ThetaType -> SDoc
 324 pprThetaArrow theta
 325   | null theta = empty
 326   | otherwise  = parens (sep (punctuate comma (map pprPred theta))) <+> ptext SLIT("=>")
 327
 328 ------------------
 329 instance Outputable Type where
 330     ppr ty = pprType ty
 331
 332 instance Outputable PredType where
 333     ppr = pprPred
 334
 335 instance Outputable name => OutputableBndr (IPName name) where
 336     pprBndr _ n = ppr n -- Simple for now
 337
 338 ------------------
 339         -- OK, here's the main printer
 340
 341 ppr_type :: Prec -> Type -> SDoc
 342 ppr_type p (TyVarTy tv)       = ppr tv
 343 ppr_type p (PredTy pred)      = braces (ppr pred)
 344 ppr_type p (NoteTy other ty2) = ppr_type p ty2
 345 ppr_type p (TyConApp tc tys)  = ppr_tc_app p tc tys
 346
 347 ppr_type p (AppTy t1 t2) = maybeParen p TyConPrec $
 348                            pprType t1 <+> ppr_type TyConPrec t2
 349
 350 ppr_type p ty@(ForAllTy _ _)       = ppr_forall_type p ty
 351 ppr_type p ty@(FunTy (PredTy _) _) = ppr_forall_type p ty
 352
 353 ppr_type p (FunTy ty1 ty2)
 354   = -- We don't want to lose synonyms, so we mustn't use splitFunTys here.
 355     maybeParen p FunPrec $
 356     sep (ppr_type FunPrec ty1 : ppr_fun_tail ty2)
 357   where
 358     ppr_fun_tail (FunTy ty1 ty2) = (arrow <+> ppr_type FunPrec ty1) : ppr_fun_tail ty2
 359     ppr_fun_tail other_ty        = [arrow <+> pprType other_ty]
 360
 361 ppr_forall_type :: Prec -> Type -> SDoc
 362 ppr_forall_type p ty
 363   = maybeParen p FunPrec $
 364     sep [pprForAll tvs, pprThetaArrow ctxt, pprType tau]
 365   where
 366     (tvs,  rho) = split1 [] ty
 367     (ctxt, tau) = split2 [] rho
 368
 369     split1 tvs (ForAllTy tv ty) = split1 (tv:tvs) ty
 370     split1 tvs (NoteTy _ ty)    = split1 tvs ty
 371     split1 tvs ty               = (reverse tvs, ty)
 372
 373     split2 ps (NoteTy _ arg     -- Rather a disgusting case
 374                `FunTy` res)           = split2 ps (arg `FunTy` res)
 375     split2 ps (PredTy p `FunTy` ty)   = split2 (p:ps) ty
 376     split2 ps (NoteTy _ ty)           = split2 ps ty
 377     split2 ps ty                      = (reverse ps, ty)
 378
 379 ppr_tc_app :: Prec -> TyCon -> [Type] -> SDoc
 380 ppr_tc_app p tc []
 381   = ppr_tc tc
 382 ppr_tc_app p tc [ty]
 383   | tc `hasKey` listTyConKey = brackets (pprType ty)
 384   | tc `hasKey` parrTyConKey = ptext SLIT("[:") <> pprType ty <> ptext SLIT(":]")
 385 ppr_tc_app p tc tys
 386   | isTupleTyCon tc && tyConArity tc == length tys
 387   = tupleParens (tupleTyConBoxity tc) (sep (punctuate comma (map pprType tys)))
 388   | otherwise
 389   = maybeParen p TyConPrec $
 390     ppr_tc tc <+> sep (map (ppr_type TyConPrec) tys)
 391
 392 ppr_tc :: TyCon -> SDoc
 393 ppr_tc tc = parenSymOcc (getOccName tc) (pp_nt_debug <> ppr tc)
 394   where
 395    pp_nt_debug | isNewTyCon tc = ifPprDebug (if isRecursiveTyCon tc
 396                                              then ptext SLIT("<recnt>")
 397                                              else ptext SLIT("<nt>"))
 398                | otherwise     = empty
 399
 400 -------------------
 401 pprForAll []  = empty
 402 pprForAll tvs = ptext SLIT("forall") <+> sep (map pprTvBndr tvs) <> dot
 403
 404 pprTvBndr tv | isLiftedTypeKind kind = ppr tv
 405              | otherwise             = parens (ppr tv <+> dcolon <+> pprKind kind)
 406              where
 407                kind = tyVarKind tv
 408 \end{code}
 409