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
18 pprType, pprParendType,
19 pprPred, pprTheta, pprThetaArrow, pprClassPred,
22 liftedTypeKind, unliftedTypeKind, openTypeKind,
23 isLiftedTypeKind, isUnliftedTypeKind, isOpenTypeKind,
24 mkArrowKind, mkArrowKinds,
25 pprKind, pprParendKind
28 #include "HsVersions.h"
30 import {-# SOURCE #-} DataCon( DataCon, dataConName )
34 import Var ( Id, TyVar, tyVarKind )
35 import VarEnv ( TyVarEnv )
36 import VarSet ( TyVarSet )
37 import Name ( Name, NamedThing(..), BuiltInSyntax(..), mkWiredInName )
38 import OccName ( mkOccFS, tcName )
39 import BasicTypes ( IPName, tupleParens )
40 import TyCon ( TyCon, mkFunTyCon, tyConArity, tupleTyConBoxity, isTupleTyCon, isRecursiveTyCon )
41 import Class ( Class )
44 import PrelNames ( gHC_PRIM, funTyConKey, listTyConKey, parrTyConKey, hasKey )
48 %************************************************************************
50 \subsection{Type Classifications}
52 %************************************************************************
56 *unboxed* iff its representation is other than a pointer
57 Unboxed types are also unlifted.
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
65 Only lifted types may be unified with a type variable.
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.
74 *data* A type declared with "data". Also boxed tuples.
76 *primitive* iff it is a built-in type that can't be expressed
79 Currently, all primitive types are unlifted, but that's not necessarily
80 the case. (E.g. Int could be primitive.)
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.
86 examples of type classifications:
88 Type primitive boxed lifted algebraic
89 -----------------------------------------------------------------------------
91 ByteArray# Yes Yes No No
92 (# a, b #) Yes No No Yes
93 ( a, b ) No Yes Yes Yes
98 ----------------------
100 ----------------------
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].
109 There's a bit of a problem with recursive newtypes
111 newtype Q = MkQ (Q->Q)
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.
119 * Newtypes are always represented using NewTcApp, never as TyConApp.
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
127 Applications of the data constructor P simply vanish:
131 * For recursive newtypes Q, treat the Q and its representation as
132 distinct right through the compiler. Applications of the data consructor
134 Q = \(x::Q->Q). coerce Q x
135 They are rare, so who cares if they are a tiny bit less efficient.
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'.
141 %************************************************************************
143 \subsection{The data type}
145 %************************************************************************
149 type TyVarSubst = TyVarEnv Type
155 Type -- Function is *not* a TyConApp
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.
163 | NewTcApp -- Application of a NewType TyCon. All newtype applications
164 TyCon -- show up like this until they are fed through newTypeRep,
166 -- * an ordinary TyConApp for non-saturated,
167 -- or recursive newtypes
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.
176 | FunTy -- Special case of TyConApp: TyConApp FunTyCon [t1,t2]
180 | ForAllTy -- A polymorphic type
184 | PredTy -- A high level source type
185 PredType -- ...can be expanded to a representation type...
187 | NoteTy -- A type with a note attached
189 Type -- The expanded version
192 = FTVNote TyVarSet -- The free type variables of the noted expression
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.
199 -------------------------------------
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:
208 * The type checker must treat it as opaque
209 * The rest of the compiler treats it as transparent
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}
216 Here the "Eq a" and "?x :: Int -> Int" and "r\l" are all called *predicates*
217 Predicates are represented inside GHC by PredType:
221 = ClassP Class [Type] -- Class predicate
222 | IParam (IPName Name) Type -- Implicit parameter
224 type ThetaType = [PredType]
227 (We don't support TREX records yet, but the setup is designed
228 to expand to allow them.)
230 A Haskell qualified type, such as that for f,g,h above, is
232 * a FunTy for the double arrow
233 * with a PredTy as the function argument
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).
240 %************************************************************************
244 %************************************************************************
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.
251 data TyThing = AnId Id
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)
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
270 %************************************************************************
272 \subsection{Wired-in type constructors
274 %************************************************************************
276 We define a few wired-in type constructors here to avoid module knots
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.
288 funTyConName = mkWiredInName gHC_PRIM
289 (mkOccFS tcName FSLIT("(->)"))
291 Nothing -- No parent object
292 (ATyCon funTyCon) -- Relevant TyCon
297 %************************************************************************
299 \subsection{The external interface}
301 %************************************************************************
303 @pprType@ is the standard @Type@ printer; the overloaded @ppr@ function is
304 defined to use this. @pprParendType@ is the same, except it puts
305 parens around the type, except for the atomic cases. @pprParendType@
306 works just by setting the initial context precedence very high.
309 data Prec = TopPrec -- No parens
310 | FunPrec -- Function args; no parens for tycon apps
311 | TyConPrec -- Tycon args; no parens for atomic
314 maybeParen :: Prec -> Prec -> SDoc -> SDoc
315 maybeParen ctxt_prec inner_prec pretty
316 | ctxt_prec < inner_prec = pretty
317 | otherwise = parens pretty
320 pprType, pprParendType :: Type -> SDoc
321 pprType ty = ppr_type TopPrec ty
322 pprParendType ty = ppr_type TyConPrec ty
325 pprPred :: PredType -> SDoc
326 pprPred (ClassP cls tys) = pprClassPred cls tys
327 pprPred (IParam ip ty) = ppr ip <> dcolon <> pprType ty
329 pprClassPred :: Class -> [Type] -> SDoc
330 pprClassPred clas tys = ppr clas <+> sep (map pprParendType tys)
332 pprTheta :: ThetaType -> SDoc
333 pprTheta theta = parens (sep (punctuate comma (map pprPred theta)))
335 pprThetaArrow :: ThetaType -> SDoc
338 | otherwise = parens (sep (punctuate comma (map pprPred theta))) <+> ptext SLIT("=>")
341 instance Outputable Type where
344 instance Outputable PredType where
347 instance Outputable name => OutputableBndr (IPName name) where
348 pprBndr _ n = ppr n -- Simple for now
351 -- OK, here's the main printer
353 ppr_type :: Prec -> Type -> SDoc
354 ppr_type p (TyVarTy tv) = ppr tv
355 ppr_type p (PredTy pred) = braces (ppr pred)
356 ppr_type p (NoteTy (SynNote ty1) ty2) = ppr_type p ty1
357 ppr_type p (NoteTy other ty2) = ppr_type p ty2
359 ppr_type p (TyConApp tc tys) = ppr_tc_app p tc tys
360 ppr_type p (NewTcApp tc tys) = ifPprDebug (if isRecursiveTyCon tc
361 then ptext SLIT("<recnt>")
362 else ptext SLIT("<nt>")
366 ppr_type p (AppTy t1 t2) = maybeParen p TyConPrec $
367 pprType t1 <+> ppr_type TyConPrec t2
369 ppr_type p (FunTy ty1 ty2)
370 = -- We don't want to lose synonyms, so we mustn't use splitFunTys here.
371 maybeParen p FunPrec $
372 sep (ppr_type FunPrec ty1 : ppr_fun_tail ty2)
374 ppr_fun_tail (FunTy ty1 ty2) = (arrow <+> ppr_type FunPrec ty1) : ppr_fun_tail ty2
375 ppr_fun_tail other_ty = [arrow <+> pprType other_ty]
377 ppr_type p ty@(ForAllTy _ _)
378 = maybeParen p FunPrec $
379 sep [pprForAll tvs, pprThetaArrow ctxt, pprType tau]
381 (tvs, rho) = split1 [] ty
382 (ctxt, tau) = split2 [] rho
384 split1 tvs (ForAllTy tv ty) = split1 (tv:tvs) ty
385 split1 tvs (NoteTy (FTVNote _) ty) = split1 tvs ty
386 split1 tvs ty = (reverse tvs, ty)
388 split2 ps (NoteTy (FTVNote _) arg -- Rather a disgusting case
389 `FunTy` res) = split2 ps (arg `FunTy` res)
390 split2 ps (PredTy p `FunTy` ty) = split2 (p:ps) ty
391 split2 ps (NoteTy (FTVNote _) ty) = split2 ps ty
392 split2 ps ty = (reverse ps, ty)
394 ppr_tc_app :: Prec -> TyCon -> [Type] -> SDoc
398 | tc `hasKey` listTyConKey = brackets (pprType ty)
399 | tc `hasKey` parrTyConKey = ptext SLIT("[:") <> pprType ty <> ptext SLIT(":]")
401 | isTupleTyCon tc && tyConArity tc == length tys
402 = tupleParens (tupleTyConBoxity tc) (sep (punctuate comma (map pprType tys)))
404 = maybeParen p TyConPrec $
405 ppr tc <+> sep (map (ppr_type TyConPrec) tys)
408 pprForAll tvs = ptext SLIT("forall") <+> sep (map pprTvBndr tvs) <> dot
410 pprTvBndr tv | isLiftedTypeKind kind = ppr tv
411 | otherwise = parens (ppr tv <+> dcolon <+> pprKind kind)