2 % (c) The University of Glasgow 2006
3 % (c) The GRASP/AQUA Project, Glasgow University, 1998
5 \section[TypeRep]{Type - friends' interface}
10 Type(..), TyNote(..), -- Representation visible
11 PredType(..), -- to friends
13 Kind, ThetaType, -- Synonyms
18 pprType, pprParendType, pprTypeApp,
20 pprPred, pprTheta, pprForAll, pprThetaArrow, pprClassPred,
23 liftedTypeKind, unliftedTypeKind, openTypeKind,
24 argTypeKind, ubxTupleKind,
25 isLiftedTypeKindCon, isLiftedTypeKind,
26 mkArrowKind, mkArrowKinds, isCoercionKind,
28 -- Kind constructors...
29 liftedTypeKindTyCon, openTypeKindTyCon, unliftedTypeKindTyCon,
30 argTypeKindTyCon, ubxTupleKindTyCon,
33 unliftedTypeKindTyConName, openTypeKindTyConName,
34 ubxTupleKindTyConName, argTypeKindTyConName,
35 liftedTypeKindTyConName,
38 tySuperKind, coSuperKind,
39 isTySuperKind, isCoSuperKind,
40 tySuperKindTyCon, coSuperKindTyCon,
42 pprKind, pprParendKind
45 #include "HsVersions.h"
47 import {-# SOURCE #-} DataCon( DataCon, dataConName )
63 %************************************************************************
65 \subsection{Type Classifications}
67 %************************************************************************
71 *unboxed* iff its representation is other than a pointer
72 Unboxed types are also unlifted.
74 *lifted* A type is lifted iff it has bottom as an element.
75 Closures always have lifted types: i.e. any
76 let-bound identifier in Core must have a lifted
77 type. Operationally, a lifted object is one that
80 Only lifted types may be unified with a type variable.
82 *algebraic* A type with one or more constructors, whether declared
83 with "data" or "newtype".
84 An algebraic type is one that can be deconstructed
85 with a case expression.
86 *NOT* the same as lifted types, because we also
87 include unboxed tuples in this classification.
89 *data* A type declared with "data". Also boxed tuples.
91 *primitive* iff it is a built-in type that can't be expressed
94 Currently, all primitive types are unlifted, but that's not necessarily
95 the case. (E.g. Int could be primitive.)
97 Some primitive types are unboxed, such as Int#, whereas some are boxed
98 but unlifted (such as ByteArray#). The only primitive types that we
99 classify as algebraic are the unboxed tuples.
101 examples of type classifications:
103 Type primitive boxed lifted algebraic
104 -----------------------------------------------------------------------------
106 ByteArray# Yes Yes No No
107 (# a, b #) Yes No No Yes
108 ( a, b ) No Yes Yes Yes
113 ----------------------
114 A note about newtypes
115 ----------------------
120 Then we want N to be represented as an Int, and that's what we arrange.
121 The front end of the compiler [TcType.lhs] treats N as opaque,
122 the back end treats it as transparent [Type.lhs].
124 There's a bit of a problem with recursive newtypes
126 newtype Q = MkQ (Q->Q)
128 Here the 'implicit expansion' we get from treating P and Q as transparent
129 would give rise to infinite types, which in turn makes eqType diverge.
130 Similarly splitForAllTys and splitFunTys can get into a loop.
134 * Newtypes are always represented using TyConApp.
136 * For non-recursive newtypes, P, treat P just like a type synonym after
137 type-checking is done; i.e. it's opaque during type checking (functions
138 from TcType) but transparent afterwards (functions from Type).
139 "Treat P as a type synonym" means "all functions expand NewTcApps
142 Applications of the data constructor P simply vanish:
146 * For recursive newtypes Q, treat the Q and its representation as
147 distinct right through the compiler. Applications of the data consructor
149 Q = \(x::Q->Q). coerce Q x
150 They are rare, so who cares if they are a tiny bit less efficient.
152 The typechecker (TcTyDecls) identifies enough type construtors as 'recursive'
153 to cut all loops. The other members of the loop may be marked 'non-recursive'.
156 %************************************************************************
158 \subsection{The data type}
160 %************************************************************************
168 Type -- Function is *not* a TyConApp
169 Type -- It must be another AppTy, or TyVarTy
170 -- (or NoteTy of these)
172 | TyConApp -- Application of a TyCon, including newtypes *and* synonyms
173 TyCon -- *Invariant* saturated appliations of FunTyCon and
174 -- synonyms have their own constructors, below.
175 -- However, *unsaturated* FunTyCons do appear as TyConApps.
177 [Type] -- Might not be saturated.
178 -- Even type synonyms are not necessarily saturated;
179 -- for example unsaturated type synonyms can appear as the
180 -- RHS of a type synonym.
182 | FunTy -- Special case of TyConApp: TyConApp FunTyCon [t1,t2]
186 | ForAllTy -- A polymorphic type
190 | PredTy -- The type of evidence for a type predictate
191 PredType -- See Note [PredTy], and Note [Equality predicates]
192 -- NB: A PredTy (EqPred _ _) can appear only as the kind
193 -- of a coercion variable; never as the argument or result
194 -- of a FunTy (unlike ClassP, IParam)
196 | NoteTy -- A type with a note attached
198 Type -- The expanded version
200 type Kind = Type -- Invariant: a kind is always
202 -- or TyConApp PrimTyCon [...]
203 -- or TyVar kv (during inference only)
204 -- or ForAll ... (for top-level coercions)
206 type SuperKind = Type -- Invariant: a super kind is always
207 -- TyConApp SuperKindTyCon ...
209 data TyNote = FTVNote TyVarSet -- The free type variables of the noted expression
212 -------------------------------------
217 represents a value whose type is the Haskell predicate p,
218 where a predicate is what occurs before the '=>' in a Haskell type.
219 It can be expanded into its representation, but:
221 * The type checker must treat it as opaque
222 * The rest of the compiler treats it as transparent
224 Consider these examples:
225 f :: (Eq a) => a -> Int
226 g :: (?x :: Int -> Int) => a -> Int
227 h :: (r\l) => {r} => {l::Int | r}
229 Here the "Eq a" and "?x :: Int -> Int" and "r\l" are all called *predicates*
230 Predicates are represented inside GHC by PredType:
234 = ClassP Class [Type] -- Class predicate
235 | IParam (IPName Name) Type -- Implicit parameter
236 | EqPred Type Type -- Equality predicate (ty1 ~ ty2)
238 type ThetaType = [PredType]
241 (We don't support TREX records yet, but the setup is designed
242 to expand to allow them.)
244 A Haskell qualified type, such as that for f,g,h above, is
246 * a FunTy for the double arrow
247 * with a PredTy as the function argument
249 The predicate really does turn into a real extra argument to the
250 function. If the argument has type (PredTy p) then the predicate p is
251 represented by evidence (a dictionary, for example, of type (predRepTy p).
253 Note [Equality predicates]
254 ~~~~~~~~~~~~~~~~~~~~~~~~~~
255 forall a b. (a ~ S b) => a -> b
256 could be represented by
257 ForAllTy a (ForAllTy b (FunTy (PredTy (EqPred a (S b))) ...))
259 ForAllTy a (ForAllTy b (ForAllTy (c::PredTy (EqPred a (S b))) ...))
261 The latter is what we do. (Unlike for class and implicit parameter
262 constraints, which do use FunTy.)
265 * FunTy is always a *value* function
266 * ForAllTy is discarded at runtime
268 We often need to make a "wildcard" (c::PredTy..). We always use the same
269 name (wildCoVarName), since it's not mentioned.
272 %************************************************************************
276 %************************************************************************
278 Despite the fact that DataCon has to be imported via a hi-boot route,
279 this module seems the right place for TyThing, because it's needed for
280 funTyCon and all the types in TysPrim.
283 data TyThing = AnId Id
288 instance Outputable TyThing where
289 ppr thing = pprTyThingCategory thing <+> quotes (ppr (getName thing))
291 pprTyThingCategory :: TyThing -> SDoc
292 pprTyThingCategory (ATyCon _) = ptext SLIT("Type constructor")
293 pprTyThingCategory (AClass _) = ptext SLIT("Class")
294 pprTyThingCategory (AnId _) = ptext SLIT("Identifier")
295 pprTyThingCategory (ADataCon _) = ptext SLIT("Data constructor")
297 instance NamedThing TyThing where -- Can't put this with the type
298 getName (AnId id) = getName id -- decl, because the DataCon instance
299 getName (ATyCon tc) = getName tc -- isn't visible there
300 getName (AClass cl) = getName cl
301 getName (ADataCon dc) = dataConName dc
305 %************************************************************************
307 Wired-in type constructors
309 %************************************************************************
311 We define a few wired-in type constructors here to avoid module knots
314 --------------------------
315 -- First the TyCons...
317 funTyCon = mkFunTyCon funTyConName (mkArrowKinds [argTypeKind, openTypeKind] liftedTypeKind)
318 -- You might think that (->) should have type (?? -> ? -> *), and you'd be right
319 -- But if we do that we get kind errors when saying
320 -- instance Control.Arrow (->)
321 -- becuase the expected kind is (*->*->*). The trouble is that the
322 -- expected/actual stuff in the unifier does not go contra-variant, whereas
323 -- the kind sub-typing does. Sigh. It really only matters if you use (->) in
324 -- a prefix way, thus: (->) Int# Int#. And this is unusual.
327 tySuperKindTyCon = mkSuperKindTyCon tySuperKindTyConName
328 coSuperKindTyCon = mkSuperKindTyCon coSuperKindTyConName
330 liftedTypeKindTyCon = mkKindTyCon liftedTypeKindTyConName
331 openTypeKindTyCon = mkKindTyCon openTypeKindTyConName
332 unliftedTypeKindTyCon = mkKindTyCon unliftedTypeKindTyConName
333 ubxTupleKindTyCon = mkKindTyCon ubxTupleKindTyConName
334 argTypeKindTyCon = mkKindTyCon argTypeKindTyConName
336 mkKindTyCon :: Name -> TyCon
337 mkKindTyCon name = mkVoidPrimTyCon name tySuperKind 0
339 --------------------------
340 -- ... and now their names
342 tySuperKindTyConName = mkPrimTyConName FSLIT("BOX") tySuperKindTyConKey tySuperKindTyCon
343 coSuperKindTyConName = mkPrimTyConName FSLIT("COERCION") coSuperKindTyConKey coSuperKindTyCon
344 liftedTypeKindTyConName = mkPrimTyConName FSLIT("*") liftedTypeKindTyConKey liftedTypeKindTyCon
345 openTypeKindTyConName = mkPrimTyConName FSLIT("?") openTypeKindTyConKey openTypeKindTyCon
346 unliftedTypeKindTyConName = mkPrimTyConName FSLIT("#") unliftedTypeKindTyConKey unliftedTypeKindTyCon
347 ubxTupleKindTyConName = mkPrimTyConName FSLIT("(#)") ubxTupleKindTyConKey ubxTupleKindTyCon
348 argTypeKindTyConName = mkPrimTyConName FSLIT("??") argTypeKindTyConKey argTypeKindTyCon
349 funTyConName = mkPrimTyConName FSLIT("(->)") funTyConKey funTyCon
351 mkPrimTyConName occ key tycon = mkWiredInName gHC_PRIM (mkOccNameFS tcName occ)
355 -- All of the super kinds and kinds are defined in Prim and use BuiltInSyntax,
356 -- because they are never in scope in the source
359 -- We also need Kinds and SuperKinds, locally and in TyCon
361 kindTyConType :: TyCon -> Type
362 kindTyConType kind = TyConApp kind []
364 liftedTypeKind = kindTyConType liftedTypeKindTyCon
365 unliftedTypeKind = kindTyConType unliftedTypeKindTyCon
366 openTypeKind = kindTyConType openTypeKindTyCon
367 argTypeKind = kindTyConType argTypeKindTyCon
368 ubxTupleKind = kindTyConType ubxTupleKindTyCon
370 mkArrowKind :: Kind -> Kind -> Kind
371 mkArrowKind k1 k2 = FunTy k1 k2
373 mkArrowKinds :: [Kind] -> Kind -> Kind
374 mkArrowKinds arg_kinds result_kind = foldr mkArrowKind result_kind arg_kinds
376 tySuperKind, coSuperKind :: SuperKind
377 tySuperKind = kindTyConType tySuperKindTyCon
378 coSuperKind = kindTyConType coSuperKindTyCon
380 isTySuperKind (NoteTy _ ty) = isTySuperKind ty
381 isTySuperKind (TyConApp kc []) = kc `hasKey` tySuperKindTyConKey
382 isTySuperKind other = False
384 isCoSuperKind :: SuperKind -> Bool
385 isCoSuperKind (NoteTy _ ty) = isCoSuperKind ty
386 isCoSuperKind (TyConApp kc []) = kc `hasKey` coSuperKindTyConKey
387 isCoSuperKind other = False
390 -- Lastly we need a few functions on Kinds
392 isLiftedTypeKindCon tc = tc `hasKey` liftedTypeKindTyConKey
394 isLiftedTypeKind :: Kind -> Bool
395 isLiftedTypeKind (TyConApp tc []) = isLiftedTypeKindCon tc
396 isLiftedTypeKind other = False
398 isCoercionKind :: Kind -> Bool
399 -- All coercions are of form (ty1 ~ ty2)
400 -- This function is here rather than in Coercion,
401 -- because it's used in a knot-tied way to enforce invariants in Var
402 isCoercionKind (NoteTy _ k) = isCoercionKind k
403 isCoercionKind (PredTy (EqPred {})) = True
404 isCoercionKind other = False
409 %************************************************************************
411 \subsection{The external interface}
413 %************************************************************************
415 @pprType@ is the standard @Type@ printer; the overloaded @ppr@ function is
416 defined to use this. @pprParendType@ is the same, except it puts
417 parens around the type, except for the atomic cases. @pprParendType@
418 works just by setting the initial context precedence very high.
421 data Prec = TopPrec -- No parens
422 | FunPrec -- Function args; no parens for tycon apps
423 | TyConPrec -- Tycon args; no parens for atomic
426 maybeParen :: Prec -> Prec -> SDoc -> SDoc
427 maybeParen ctxt_prec inner_prec pretty
428 | ctxt_prec < inner_prec = pretty
429 | otherwise = parens pretty
432 pprType, pprParendType :: Type -> SDoc
433 pprType ty = ppr_type TopPrec ty
434 pprParendType ty = ppr_type TyConPrec ty
436 pprTypeApp :: NamedThing a => a -> SDoc -> [Type] -> SDoc
437 -- The first arg is the tycon; it's used to arrange printing infix
438 -- if it looks like an operator
439 -- Second arg is the pretty-printed tycon
440 pprTypeApp tc pp_tc tys = ppr_type_app TopPrec (getName tc) pp_tc tys
443 pprPred :: PredType -> SDoc
444 pprPred (ClassP cls tys) = pprClassPred cls tys
445 pprPred (IParam ip ty) = ppr ip <> dcolon <> pprType ty
446 pprPred (EqPred ty1 ty2) = sep [ppr ty1, nest 2 (ptext SLIT("~")), ppr ty2]
447 pprClassPred :: Class -> [Type] -> SDoc
448 pprClassPred clas tys = ppr_type_app TopPrec (getName clas) (ppr clas) tys
450 pprTheta :: ThetaType -> SDoc
451 pprTheta theta = parens (sep (punctuate comma (map pprPred theta)))
453 pprThetaArrow :: ThetaType -> SDoc
456 | otherwise = parens (sep (punctuate comma (map pprPred theta))) <+> ptext SLIT("=>")
459 instance Outputable Type where
462 instance Outputable PredType where
465 instance Outputable name => OutputableBndr (IPName name) where
466 pprBndr _ n = ppr n -- Simple for now
469 -- OK, here's the main printer
472 pprParendKind = pprParendType
474 ppr_type :: Prec -> Type -> SDoc
475 ppr_type p (TyVarTy tv) = ppr tv
476 ppr_type p (PredTy pred) = ifPprDebug (ptext SLIT("<pred>")) <> (ppr pred)
477 ppr_type p (NoteTy other ty2) = ppr_type p ty2
478 ppr_type p (TyConApp tc tys) = ppr_tc_app p tc tys
480 ppr_type p (AppTy t1 t2) = maybeParen p TyConPrec $
481 pprType t1 <+> ppr_type TyConPrec t2
483 ppr_type p ty@(ForAllTy _ _) = ppr_forall_type p ty
484 ppr_type p ty@(FunTy (PredTy _) _) = ppr_forall_type p ty
486 ppr_type p (FunTy ty1 ty2)
487 = -- We don't want to lose synonyms, so we mustn't use splitFunTys here.
488 maybeParen p FunPrec $
489 sep (ppr_type FunPrec ty1 : ppr_fun_tail ty2)
491 ppr_fun_tail (FunTy ty1 ty2) = (arrow <+> ppr_type FunPrec ty1) : ppr_fun_tail ty2
492 ppr_fun_tail other_ty = [arrow <+> pprType other_ty]
494 ppr_forall_type :: Prec -> Type -> SDoc
496 = maybeParen p FunPrec $
497 sep [pprForAll tvs, pprThetaArrow ctxt, pprType tau]
499 (tvs, rho) = split1 [] ty
500 (ctxt, tau) = split2 [] rho
502 split1 tvs (ForAllTy tv ty) = split1 (tv:tvs) ty
503 split1 tvs (NoteTy _ ty) = split1 tvs ty
504 split1 tvs ty = (reverse tvs, ty)
506 split2 ps (NoteTy _ arg -- Rather a disgusting case
507 `FunTy` res) = split2 ps (arg `FunTy` res)
508 split2 ps (PredTy p `FunTy` ty) = split2 (p:ps) ty
509 split2 ps (NoteTy _ ty) = split2 ps ty
510 split2 ps ty = (reverse ps, ty)
512 ppr_tc_app :: Prec -> TyCon -> [Type] -> SDoc
516 | tc `hasKey` listTyConKey = brackets (pprType ty)
517 | tc `hasKey` parrTyConKey = ptext SLIT("[:") <> pprType ty <> ptext SLIT(":]")
518 | tc `hasKey` liftedTypeKindTyConKey = ptext SLIT("*")
519 | tc `hasKey` unliftedTypeKindTyConKey = ptext SLIT("#")
520 | tc `hasKey` openTypeKindTyConKey = ptext SLIT("(?)")
521 | tc `hasKey` ubxTupleKindTyConKey = ptext SLIT("(#)")
522 | tc `hasKey` argTypeKindTyConKey = ptext SLIT("??")
525 | isTupleTyCon tc && tyConArity tc == length tys
526 = tupleParens (tupleTyConBoxity tc) (sep (punctuate comma (map pprType tys)))
528 = ppr_type_app p (getName tc) (ppr_naked_tc tc) tys
530 ppr_type_app :: Prec -> Name -> SDoc -> [Type] -> SDoc
531 ppr_type_app p tc pp_tc tys
532 | is_sym_occ -- Print infix if possible
533 , [ty1,ty2] <- tys -- We know nothing of precedence though
534 = maybeParen p FunPrec (sep [ppr_type FunPrec ty1,
535 pp_tc <+> ppr_type FunPrec ty2])
537 = maybeParen p TyConPrec (hang paren_tc 2 (sep (map pprParendType tys)))
539 is_sym_occ = isSymOcc (getOccName tc)
540 paren_tc | is_sym_occ = parens pp_tc
543 ppr_tc :: TyCon -> SDoc
544 ppr_tc tc = parenSymOcc (getOccName tc) (ppr_naked_tc tc)
546 ppr_naked_tc :: TyCon -> SDoc -- No brackets for SymOcc
548 = pp_nt_debug <> ppr tc
550 pp_nt_debug | isNewTyCon tc = ifPprDebug (if isRecursiveTyCon tc
551 then ptext SLIT("<recnt>")
552 else ptext SLIT("<nt>"))
557 pprForAll tvs = ptext SLIT("forall") <+> sep (map pprTvBndr tvs) <> dot
559 pprTvBndr tv | isLiftedTypeKind kind = ppr tv
560 | otherwise = parens (ppr tv <+> dcolon <+> pprKind kind)