2 % (c) The GRASP/AQUA Project, Glasgow University, 1998
4 \section[TypeRep]{Type - friends' interface}
9 Type(..), TyNote(..), -- Representation visible
10 PredType(..), -- to friends
12 Kind, ThetaType, -- Synonyms
17 pprType, pprParendType, pprTyThingCategory,
18 pprPred, pprTheta, pprThetaArrow, pprClassPred,
21 liftedTypeKind, unliftedTypeKind, openTypeKind,
22 argTypeKind, ubxTupleKind,
23 isLiftedTypeKindCon, isLiftedTypeKind,
24 mkArrowKind, mkArrowKinds,
26 -- Kind constructors...
27 liftedTypeKindTyCon, openTypeKindTyCon, unliftedTypeKindTyCon,
28 argTypeKindTyCon, ubxTupleKindTyCon,
31 unliftedTypeKindTyConName, openTypeKindTyConName,
32 ubxTupleKindTyConName, argTypeKindTyConName,
33 liftedTypeKindTyConName,
36 tySuperKind, coSuperKind,
37 isTySuperKind, isCoSuperKind,
38 tySuperKindTyCon, coSuperKindTyCon,
40 pprKind, pprParendKind
43 #include "HsVersions.h"
45 import {-# SOURCE #-} DataCon( DataCon, dataConName )
48 import Var ( Var, Id, TyVar, tyVarKind )
49 import VarSet ( TyVarSet )
50 import Name ( Name, NamedThing(..), BuiltInSyntax(..), mkWiredInName )
51 import OccName ( mkOccNameFS, tcName, parenSymOcc )
52 import BasicTypes ( IPName, tupleParens )
53 import TyCon ( TyCon, mkFunTyCon, tyConArity, tupleTyConBoxity, isTupleTyCon,
54 isRecursiveTyCon, isNewTyCon, mkVoidPrimTyCon,
56 import Class ( Class )
59 import PrelNames ( gHC_PRIM, funTyConKey, tySuperKindTyConKey,
60 coSuperKindTyConKey, liftedTypeKindTyConKey,
61 openTypeKindTyConKey, unliftedTypeKindTyConKey,
62 ubxTupleKindTyConKey, argTypeKindTyConKey, listTyConKey,
63 parrTyConKey, hasKey )
67 %************************************************************************
69 \subsection{Type Classifications}
71 %************************************************************************
75 *unboxed* iff its representation is other than a pointer
76 Unboxed types are also unlifted.
78 *lifted* A type is lifted iff it has bottom as an element.
79 Closures always have lifted types: i.e. any
80 let-bound identifier in Core must have a lifted
81 type. Operationally, a lifted object is one that
84 Only lifted types may be unified with a type variable.
86 *algebraic* A type with one or more constructors, whether declared
87 with "data" or "newtype".
88 An algebraic type is one that can be deconstructed
89 with a case expression.
90 *NOT* the same as lifted types, because we also
91 include unboxed tuples in this classification.
93 *data* A type declared with "data". Also boxed tuples.
95 *primitive* iff it is a built-in type that can't be expressed
98 Currently, all primitive types are unlifted, but that's not necessarily
99 the case. (E.g. Int could be primitive.)
101 Some primitive types are unboxed, such as Int#, whereas some are boxed
102 but unlifted (such as ByteArray#). The only primitive types that we
103 classify as algebraic are the unboxed tuples.
105 examples of type classifications:
107 Type primitive boxed lifted algebraic
108 -----------------------------------------------------------------------------
110 ByteArray# Yes Yes No No
111 (# a, b #) Yes No No Yes
112 ( a, b ) No Yes Yes Yes
117 ----------------------
118 A note about newtypes
119 ----------------------
124 Then we want N to be represented as an Int, and that's what we arrange.
125 The front end of the compiler [TcType.lhs] treats N as opaque,
126 the back end treats it as transparent [Type.lhs].
128 There's a bit of a problem with recursive newtypes
130 newtype Q = MkQ (Q->Q)
132 Here the 'implicit expansion' we get from treating P and Q as transparent
133 would give rise to infinite types, which in turn makes eqType diverge.
134 Similarly splitForAllTys and splitFunTys can get into a loop.
138 * Newtypes are always represented using TyConApp.
140 * For non-recursive newtypes, P, treat P just like a type synonym after
141 type-checking is done; i.e. it's opaque during type checking (functions
142 from TcType) but transparent afterwards (functions from Type).
143 "Treat P as a type synonym" means "all functions expand NewTcApps
146 Applications of the data constructor P simply vanish:
150 * For recursive newtypes Q, treat the Q and its representation as
151 distinct right through the compiler. Applications of the data consructor
153 Q = \(x::Q->Q). coerce Q x
154 They are rare, so who cares if they are a tiny bit less efficient.
156 The typechecker (TcTyDecls) identifies enough type construtors as 'recursive'
157 to cut all loops. The other members of the loop may be marked 'non-recursive'.
160 %************************************************************************
162 \subsection{The data type}
164 %************************************************************************
172 Type -- Function is *not* a TyConApp
173 Type -- It must be another AppTy, or TyVarTy
174 -- (or NoteTy of these)
176 | TyConApp -- Application of a TyCon, including newtypes *and* synonyms
177 TyCon -- *Invariant* saturated appliations of FunTyCon and
178 -- synonyms have their own constructors, below.
179 -- However, *unsaturated* FunTyCons do appear as TyConApps.
181 [Type] -- Might not be saturated.
182 -- Even type synonyms are not necessarily saturated;
183 -- for example unsaturated type synonyms can appear as the
184 -- RHS of a type synonym.
186 | FunTy -- Special case of TyConApp: TyConApp FunTyCon [t1,t2]
190 | ForAllTy -- A polymorphic type
194 | PredTy -- The type of evidence for a type predictate
195 PredType -- See Note [PredTy], and Note [Equality predicates]
196 -- NB: A PredTy (EqPred _ _) can appear only as the kind
197 -- of a coercion variable; never as the argument or result
198 -- of a FunTy (unlike ClassP, IParam)
200 | NoteTy -- A type with a note attached
202 Type -- The expanded version
204 type Kind = Type -- Invariant: a kind is always
206 -- or TyConApp PrimTyCon [...]
207 -- or TyVar kv (during inference only)
208 -- or ForAll ... (for top-level coercions)
210 type SuperKind = Type -- Invariant: a super kind is always
211 -- TyConApp SuperKindTyCon ...
213 data TyNote = FTVNote TyVarSet -- The free type variables of the noted expression
216 -------------------------------------
221 represents a value whose type is the Haskell predicate p,
222 where a predicate is what occurs before the '=>' in a Haskell type.
223 It can be expanded into its representation, but:
225 * The type checker must treat it as opaque
226 * The rest of the compiler treats it as transparent
228 Consider these examples:
229 f :: (Eq a) => a -> Int
230 g :: (?x :: Int -> Int) => a -> Int
231 h :: (r\l) => {r} => {l::Int | r}
233 Here the "Eq a" and "?x :: Int -> Int" and "r\l" are all called *predicates*
234 Predicates are represented inside GHC by PredType:
238 = ClassP Class [Type] -- Class predicate
239 | IParam (IPName Name) Type -- Implicit parameter
240 | EqPred Type Type -- Equality predicate (ty1 :=: ty2)
242 type ThetaType = [PredType]
245 (We don't support TREX records yet, but the setup is designed
246 to expand to allow them.)
248 A Haskell qualified type, such as that for f,g,h above, is
250 * a FunTy for the double arrow
251 * with a PredTy as the function argument
253 The predicate really does turn into a real extra argument to the
254 function. If the argument has type (PredTy p) then the predicate p is
255 represented by evidence (a dictionary, for example, of type (predRepTy p).
257 Note [Equality predicates]
258 ~~~~~~~~~~~~~~~~~~~~~~~~~~
259 forall a b. (a :=: S b) => a -> b
260 could be represented by
261 ForAllTy a (ForAllTy b (FunTy (PredTy (EqPred a (S b))) ...))
263 ForAllTy a (ForAllTy b (ForAllTy (c::PredTy (EqPred a (S b))) ...))
265 The latter is what we do. (Unlike for class and implicit parameter
266 constraints, which do use FunTy.)
269 * FunTy is always a *value* function
270 * ForAllTy is discarded at runtime
272 We often need to make a "wildcard" (c::PredTy..). We always use the same
273 name (wildCoVarName), since it's not mentioned.
276 %************************************************************************
280 %************************************************************************
282 Despite the fact that DataCon has to be imported via a hi-boot route,
283 this module seems the right place for TyThing, because it's needed for
284 funTyCon and all the types in TysPrim.
287 data TyThing = AnId Id
292 instance Outputable TyThing where
293 ppr thing = pprTyThingCategory thing <+> quotes (ppr (getName thing))
295 pprTyThingCategory :: TyThing -> SDoc
296 pprTyThingCategory (ATyCon _) = ptext SLIT("Type constructor")
297 pprTyThingCategory (AClass _) = ptext SLIT("Class")
298 pprTyThingCategory (AnId _) = ptext SLIT("Identifier")
299 pprTyThingCategory (ADataCon _) = ptext SLIT("Data constructor")
301 instance NamedThing TyThing where -- Can't put this with the type
302 getName (AnId id) = getName id -- decl, because the DataCon instance
303 getName (ATyCon tc) = getName tc -- isn't visible there
304 getName (AClass cl) = getName cl
305 getName (ADataCon dc) = dataConName dc
309 %************************************************************************
311 Wired-in type constructors
313 %************************************************************************
315 We define a few wired-in type constructors here to avoid module knots
318 --------------------------
319 -- First the TyCons...
321 funTyCon = mkFunTyCon funTyConName (mkArrowKinds [argTypeKind, openTypeKind] liftedTypeKind)
322 -- You might think that (->) should have type (?? -> ? -> *), and you'd be right
323 -- But if we do that we get kind errors when saying
324 -- instance Control.Arrow (->)
325 -- becuase the expected kind is (*->*->*). The trouble is that the
326 -- expected/actual stuff in the unifier does not go contra-variant, whereas
327 -- the kind sub-typing does. Sigh. It really only matters if you use (->) in
328 -- a prefix way, thus: (->) Int# Int#. And this is unusual.
331 tySuperKindTyCon = mkSuperKindTyCon tySuperKindTyConName
332 coSuperKindTyCon = mkSuperKindTyCon coSuperKindTyConName
334 liftedTypeKindTyCon = mkKindTyCon liftedTypeKindTyConName
335 openTypeKindTyCon = mkKindTyCon openTypeKindTyConName
336 unliftedTypeKindTyCon = mkKindTyCon unliftedTypeKindTyConName
337 ubxTupleKindTyCon = mkKindTyCon ubxTupleKindTyConName
338 argTypeKindTyCon = mkKindTyCon argTypeKindTyConName
340 mkKindTyCon :: Name -> TyCon
341 mkKindTyCon name = mkVoidPrimTyCon name tySuperKind 0
343 --------------------------
344 -- ... and now their names
346 tySuperKindTyConName = mkPrimTyConName FSLIT("BOX") tySuperKindTyConKey tySuperKindTyCon
347 coSuperKindTyConName = mkPrimTyConName FSLIT("COERCION") coSuperKindTyConKey coSuperKindTyCon
348 liftedTypeKindTyConName = mkPrimTyConName FSLIT("*") liftedTypeKindTyConKey liftedTypeKindTyCon
349 openTypeKindTyConName = mkPrimTyConName FSLIT("?") openTypeKindTyConKey openTypeKindTyCon
350 unliftedTypeKindTyConName = mkPrimTyConName FSLIT("#") unliftedTypeKindTyConKey unliftedTypeKindTyCon
351 ubxTupleKindTyConName = mkPrimTyConName FSLIT("(#)") ubxTupleKindTyConKey ubxTupleKindTyCon
352 argTypeKindTyConName = mkPrimTyConName FSLIT("??") argTypeKindTyConKey argTypeKindTyCon
353 funTyConName = mkPrimTyConName FSLIT("(->)") funTyConKey funTyCon
355 mkPrimTyConName occ key tycon = mkWiredInName gHC_PRIM (mkOccNameFS tcName occ)
357 Nothing -- No parent object
360 -- All of the super kinds and kinds are defined in Prim and use BuiltInSyntax,
361 -- because they are never in scope in the source
364 -- We also need Kinds and SuperKinds, locally and in TyCon
366 kindTyConType :: TyCon -> Type
367 kindTyConType kind = TyConApp kind []
369 liftedTypeKind = kindTyConType liftedTypeKindTyCon
370 unliftedTypeKind = kindTyConType unliftedTypeKindTyCon
371 openTypeKind = kindTyConType openTypeKindTyCon
372 argTypeKind = kindTyConType argTypeKindTyCon
373 ubxTupleKind = kindTyConType ubxTupleKindTyCon
375 mkArrowKind :: Kind -> Kind -> Kind
376 mkArrowKind k1 k2 = FunTy k1 k2
378 mkArrowKinds :: [Kind] -> Kind -> Kind
379 mkArrowKinds arg_kinds result_kind = foldr mkArrowKind result_kind arg_kinds
381 tySuperKind, coSuperKind :: SuperKind
382 tySuperKind = kindTyConType tySuperKindTyCon
383 coSuperKind = kindTyConType coSuperKindTyCon
385 isTySuperKind (NoteTy _ ty) = isTySuperKind ty
386 isTySuperKind (TyConApp kc []) = kc `hasKey` tySuperKindTyConKey
387 isTySuperKind other = False
389 isCoSuperKind :: SuperKind -> Bool
390 isCoSuperKind (NoteTy _ ty) = isCoSuperKind ty
391 isCoSuperKind (TyConApp kc []) = kc `hasKey` coSuperKindTyConKey
392 isCoSuperKind other = False
395 -- lastly we need a few functions on Kinds
397 isLiftedTypeKindCon tc = tc `hasKey` liftedTypeKindTyConKey
399 isLiftedTypeKind (TyConApp tc []) = isLiftedTypeKindCon tc
400 isLiftedTypeKind other = False
407 %************************************************************************
409 \subsection{The external interface}
411 %************************************************************************
413 @pprType@ is the standard @Type@ printer; the overloaded @ppr@ function is
414 defined to use this. @pprParendType@ is the same, except it puts
415 parens around the type, except for the atomic cases. @pprParendType@
416 works just by setting the initial context precedence very high.
419 data Prec = TopPrec -- No parens
420 | FunPrec -- Function args; no parens for tycon apps
421 | TyConPrec -- Tycon args; no parens for atomic
424 maybeParen :: Prec -> Prec -> SDoc -> SDoc
425 maybeParen ctxt_prec inner_prec pretty
426 | ctxt_prec < inner_prec = pretty
427 | otherwise = parens pretty
430 pprType, pprParendType :: Type -> SDoc
431 pprType ty = ppr_type TopPrec ty
432 pprParendType ty = ppr_type TyConPrec ty
435 pprPred :: PredType -> SDoc
436 pprPred (ClassP cls tys) = pprClassPred cls tys
437 pprPred (IParam ip ty) = ppr ip <> dcolon <> pprType ty
438 pprPred (EqPred ty1 ty2) = sep [ppr ty1, nest 2 (ptext SLIT(":=:")), ppr ty2]
440 pprClassPred :: Class -> [Type] -> SDoc
441 pprClassPred clas tys = parenSymOcc (getOccName clas) (ppr clas)
442 <+> sep (map pprParendType tys)
444 pprTheta :: ThetaType -> SDoc
445 pprTheta theta = parens (sep (punctuate comma (map pprPred theta)))
447 pprThetaArrow :: ThetaType -> SDoc
450 | otherwise = parens (sep (punctuate comma (map pprPred theta))) <+> ptext SLIT("=>")
453 instance Outputable Type where
456 instance Outputable PredType where
459 instance Outputable name => OutputableBndr (IPName name) where
460 pprBndr _ n = ppr n -- Simple for now
463 -- OK, here's the main printer
466 pprParendKind = pprParendType
468 ppr_type :: Prec -> Type -> SDoc
469 ppr_type p (TyVarTy tv) = ppr tv
470 ppr_type p (PredTy pred) = braces (ppr pred)
471 ppr_type p (NoteTy other ty2) = ppr_type p ty2
472 ppr_type p (TyConApp tc tys) = ppr_tc_app p tc tys
474 ppr_type p (AppTy t1 t2) = maybeParen p TyConPrec $
475 pprType t1 <+> ppr_type TyConPrec t2
477 ppr_type p ty@(ForAllTy _ _) = ppr_forall_type p ty
478 ppr_type p ty@(FunTy (PredTy _) _) = ppr_forall_type p ty
480 ppr_type p (FunTy ty1 ty2)
481 = -- We don't want to lose synonyms, so we mustn't use splitFunTys here.
482 maybeParen p FunPrec $
483 sep (ppr_type FunPrec ty1 : ppr_fun_tail ty2)
485 ppr_fun_tail (FunTy ty1 ty2) = (arrow <+> ppr_type FunPrec ty1) : ppr_fun_tail ty2
486 ppr_fun_tail other_ty = [arrow <+> pprType other_ty]
488 ppr_forall_type :: Prec -> Type -> SDoc
490 = maybeParen p FunPrec $
491 sep [pprForAll tvs, pprThetaArrow ctxt, pprType tau]
493 (tvs, rho) = split1 [] ty
494 (ctxt, tau) = split2 [] rho
496 split1 tvs (ForAllTy tv ty) = split1 (tv:tvs) ty
497 split1 tvs (NoteTy _ ty) = split1 tvs ty
498 split1 tvs ty = (reverse tvs, ty)
500 split2 ps (NoteTy _ arg -- Rather a disgusting case
501 `FunTy` res) = split2 ps (arg `FunTy` res)
502 split2 ps (PredTy p `FunTy` ty) = split2 (p:ps) ty
503 split2 ps (NoteTy _ ty) = split2 ps ty
504 split2 ps ty = (reverse ps, ty)
506 ppr_tc_app :: Prec -> TyCon -> [Type] -> SDoc
510 | tc `hasKey` listTyConKey = brackets (pprType ty)
511 | tc `hasKey` parrTyConKey = ptext SLIT("[:") <> pprType ty <> ptext SLIT(":]")
512 | tc `hasKey` liftedTypeKindTyConKey = ptext SLIT("*")
513 | tc `hasKey` unliftedTypeKindTyConKey = ptext SLIT("#")
514 | tc `hasKey` openTypeKindTyConKey = ptext SLIT("(?)")
515 | tc `hasKey` ubxTupleKindTyConKey = ptext SLIT("(#)")
516 | tc `hasKey` argTypeKindTyConKey = ptext SLIT("??")
519 | isTupleTyCon tc && tyConArity tc == length tys
520 = tupleParens (tupleTyConBoxity tc) (sep (punctuate comma (map pprType tys)))
522 = maybeParen p TyConPrec $
523 ppr_tc tc <+> sep (map (ppr_type TyConPrec) tys)
525 ppr_tc :: TyCon -> SDoc
526 ppr_tc tc = parenSymOcc (getOccName tc) (pp_nt_debug <> ppr tc)
528 pp_nt_debug | isNewTyCon tc = ifPprDebug (if isRecursiveTyCon tc
529 then ptext SLIT("<recnt>")
530 else ptext SLIT("<nt>"))
535 pprForAll tvs = ptext SLIT("forall") <+> sep (map pprTvBndr tvs) <> dot
537 pprTvBndr tv | isLiftedTypeKind kind = ppr tv
538 | otherwise = parens (ppr tv <+> dcolon <+> pprKind kind)