Add tuple sections as a new feature
[ghc.git] / compiler / types / TypeRep.lhs
1 %
2 % (c) The University of Glasgow 2006
3 % (c) The GRASP/AQUA Project, Glasgow University, 1998
4 %
5 \section[TypeRep]{Type - friends' interface}
6
7 \begin{code}
8 -- We expose the relevant stuff from this module via the Type module
9 {-# OPTIONS_HADDOCK hide #-}
10
11 module TypeRep (
12         TyThing(..), 
13         Type(..),
14         PredType(..),                   -- to friends
15         
16         Kind, ThetaType,                -- Synonyms
17
18         funTyCon, funTyConName,
19
20         -- Pretty-printing
21         pprType, pprParendType, pprTypeApp,
22         pprTyThing, pprTyThingCategory, 
23         pprPred, pprTheta, pprForAll, pprThetaArrow, pprClassPred,
24
25         -- Kinds
26         liftedTypeKind, unliftedTypeKind, openTypeKind,
27         argTypeKind, ubxTupleKind,
28         isLiftedTypeKindCon, isLiftedTypeKind,
29         mkArrowKind, mkArrowKinds, isCoercionKind,
30         coVarPred,
31
32         -- Kind constructors...
33         liftedTypeKindTyCon, openTypeKindTyCon, unliftedTypeKindTyCon,
34         argTypeKindTyCon, ubxTupleKindTyCon,
35
36         -- And their names
37         unliftedTypeKindTyConName, openTypeKindTyConName,
38         ubxTupleKindTyConName, argTypeKindTyConName,
39         liftedTypeKindTyConName,
40
41         -- Super Kinds
42         tySuperKind, coSuperKind,
43         isTySuperKind, isCoSuperKind,
44         tySuperKindTyCon, coSuperKindTyCon,
45         
46         pprKind, pprParendKind
47     ) where
48
49 #include "HsVersions.h"
50
51 import {-# SOURCE #-} DataCon( DataCon, dataConName )
52
53 -- friends:
54 import Var
55 import Name
56 import BasicTypes
57 import TyCon
58 import Class
59
60 -- others
61 import PrelNames
62 import Outputable
63 import FastString
64 \end{code}
65
66         ----------------------
67         A note about newtypes
68         ----------------------
69
70 Consider
71         newtype N = MkN Int
72
73 Then we want N to be represented as an Int, and that's what we arrange.
74 The front end of the compiler [TcType.lhs] treats N as opaque, 
75 the back end treats it as transparent [Type.lhs].
76
77 There's a bit of a problem with recursive newtypes
78         newtype P = MkP P
79         newtype Q = MkQ (Q->Q)
80
81 Here the 'implicit expansion' we get from treating P and Q as transparent
82 would give rise to infinite types, which in turn makes eqType diverge.
83 Similarly splitForAllTys and splitFunTys can get into a loop.  
84
85 Solution: 
86
87 * Newtypes are always represented using TyConApp.
88
89 * For non-recursive newtypes, P, treat P just like a type synonym after 
90   type-checking is done; i.e. it's opaque during type checking (functions
91   from TcType) but transparent afterwards (functions from Type).  
92   "Treat P as a type synonym" means "all functions expand NewTcApps 
93   on the fly".
94
95   Applications of the data constructor P simply vanish:
96         P x = x
97   
98
99 * For recursive newtypes Q, treat the Q and its representation as 
100   distinct right through the compiler.  Applications of the data consructor
101   use a coerce:
102         Q = \(x::Q->Q). coerce Q x
103   They are rare, so who cares if they are a tiny bit less efficient.
104
105 The typechecker (TcTyDecls) identifies enough type construtors as 'recursive'
106 to cut all loops.  The other members of the loop may be marked 'non-recursive'.
107
108
109 %************************************************************************
110 %*                                                                      *
111 \subsection{The data type}
112 %*                                                                      *
113 %************************************************************************
114
115
116 \begin{code}
117 -- | The key representation of types within the compiler
118 data Type
119   = TyVarTy TyVar       -- ^ Vanilla type variable
120
121   | AppTy
122         Type
123         Type            -- ^ Type application to something other than a 'TyCon'. Parameters:
124                         --
125                         --  1) Function: must /not/ be a 'TyConApp', must be another 'AppTy', or 'TyVarTy'
126                         --
127                         --  2) Argument type
128
129   | TyConApp
130         TyCon
131         [Type]          -- ^ Application of a 'TyCon', including newtypes /and/ synonyms.
132                         -- Invariant: saturated appliations of 'FunTyCon' must
133                         -- use 'FunTy' and saturated synonyms must use their own
134                         -- constructors. However, /unsaturated/ 'FunTyCon's do appear as 'TyConApp's.
135                         -- Parameters:
136                         --
137                         -- 1) Type constructor being applied to.
138                         --
139                         -- 2) Type arguments. Might not have enough type arguments here to saturate the constructor.
140                         -- Even type synonyms are not necessarily saturated; for example unsaturated type synonyms
141                         -- can appear as the right hand side of a type synonym.
142
143   | FunTy
144         Type
145         Type            -- ^ Special case of 'TyConApp': @TyConApp FunTyCon [t1, t2]@
146
147   | ForAllTy
148         TyVar
149         Type            -- ^ A polymorphic type
150
151   | PredTy
152         PredType        -- ^ The type of evidence for a type predictate.
153                         -- Note that a @PredTy (EqPred _ _)@ can appear only as the kind
154                         -- of a coercion variable; never as the argument or result
155                         -- of a 'FunTy' (unlike the 'PredType' constructors 'ClassP' or 'IParam')
156                         
157                         -- See Note [PredTy], and Note [Equality predicates]
158
159 -- | The key type representing kinds in the compiler.
160 -- Invariant: a kind is always in one of these forms:
161 --
162 -- > FunTy k1 k2
163 -- > TyConApp PrimTyCon [...]
164 -- > TyVar kv   -- (during inference only)
165 -- > ForAll ... -- (for top-level coercions)
166 type Kind = Type
167
168 -- | "Super kinds", used to help encode 'Kind's as types.
169 -- Invariant: a super kind is always of this form:
170 --
171 -- > TyConApp SuperKindTyCon ...
172 type SuperKind = Type
173 \end{code}
174
175 -------------------------------------
176                 Note [PredTy]
177
178 \begin{code}
179 -- | A type of the form @PredTy p@ represents a value whose type is
180 -- the Haskell predicate @p@, where a predicate is what occurs before 
181 -- the @=>@ in a Haskell type.
182 -- It can be expanded into its representation, but: 
183 --
184 -- * The type checker must treat it as opaque
185 --
186 -- * The rest of the compiler treats it as transparent
187 --
188 -- Consider these examples:
189 --
190 -- > f :: (Eq a) => a -> Int
191 -- > g :: (?x :: Int -> Int) => a -> Int
192 -- > h :: (r\l) => {r} => {l::Int | r}
193 --
194 -- Here the @Eq a@ and @?x :: Int -> Int@ and @r\l@ are all called \"predicates\"
195 data PredType 
196   = ClassP Class [Type]         -- ^ Class predicate e.g. @Eq a@
197   | IParam (IPName Name) Type   -- ^ Implicit parameter e.g. @?x :: Int@
198   | EqPred Type Type            -- ^ Equality predicate e.g @ty1 ~ ty2@
199
200 -- | A collection of 'PredType's
201 type ThetaType = [PredType]
202 \end{code}
203
204 (We don't support TREX records yet, but the setup is designed
205 to expand to allow them.)
206
207 A Haskell qualified type, such as that for f,g,h above, is
208 represented using 
209         * a FunTy for the double arrow
210         * with a PredTy as the function argument
211
212 The predicate really does turn into a real extra argument to the
213 function.  If the argument has type (PredTy p) then the predicate p is
214 represented by evidence (a dictionary, for example, of type (predRepTy p).
215
216 Note [Equality predicates]
217 ~~~~~~~~~~~~~~~~~~~~~~~~~~
218         forall a b. (a ~ S b) => a -> b
219 could be represented by
220         ForAllTy a (ForAllTy b (FunTy (PredTy (EqPred a (S b))) ...))
221 OR
222         ForAllTy a (ForAllTy b (ForAllTy (c::PredTy (EqPred a (S b))) ...))
223
224 The latter is what we do.  (Unlike for class and implicit parameter
225 constraints, which do use FunTy.)
226
227 Reason:
228         * FunTy is always a *value* function
229         * ForAllTy is discarded at runtime
230
231 We often need to make a "wildcard" (c::PredTy..).  We always use the same
232 name (wildCoVarName), since it's not mentioned.
233
234
235 %************************************************************************
236 %*                                                                      *
237                         TyThing
238 %*                                                                      *
239 %************************************************************************
240
241 Despite the fact that DataCon has to be imported via a hi-boot route, 
242 this module seems the right place for TyThing, because it's needed for
243 funTyCon and all the types in TysPrim.
244
245 \begin{code}
246 -- | A typecheckable-thing, essentially anything that has a name
247 data TyThing = AnId     Id
248              | ADataCon DataCon
249              | ATyCon   TyCon
250              | AClass   Class
251
252 instance Outputable TyThing where 
253   ppr = pprTyThing
254
255 pprTyThing :: TyThing -> SDoc
256 pprTyThing thing = pprTyThingCategory thing <+> quotes (ppr (getName thing))
257
258 pprTyThingCategory :: TyThing -> SDoc
259 pprTyThingCategory (ATyCon _)   = ptext (sLit "Type constructor")
260 pprTyThingCategory (AClass _)   = ptext (sLit "Class")
261 pprTyThingCategory (AnId   _)   = ptext (sLit "Identifier")
262 pprTyThingCategory (ADataCon _) = ptext (sLit "Data constructor")
263
264 instance NamedThing TyThing where       -- Can't put this with the type
265   getName (AnId id)     = getName id    -- decl, because the DataCon instance
266   getName (ATyCon tc)   = getName tc    -- isn't visible there
267   getName (AClass cl)   = getName cl
268   getName (ADataCon dc) = dataConName dc
269 \end{code}
270
271
272 %************************************************************************
273 %*                                                                      *
274                 Wired-in type constructors
275 %*                                                                      *
276 %************************************************************************
277
278 We define a few wired-in type constructors here to avoid module knots
279
280 \begin{code}
281 --------------------------
282 -- First the TyCons...
283
284 -- | See "Type#kind_subtyping" for details of the distinction between the 'Kind' 'TyCon's
285 funTyCon, tySuperKindTyCon, coSuperKindTyCon, liftedTypeKindTyCon,
286       openTypeKindTyCon, unliftedTypeKindTyCon,
287       ubxTupleKindTyCon, argTypeKindTyCon
288    :: TyCon
289 funTyConName, tySuperKindTyConName, coSuperKindTyConName, liftedTypeKindTyConName,
290       openTypeKindTyConName, unliftedTypeKindTyConName,
291       ubxTupleKindTyConName, argTypeKindTyConName
292    :: Name
293
294 funTyCon = mkFunTyCon funTyConName (mkArrowKinds [argTypeKind, openTypeKind] liftedTypeKind)
295         -- You might think that (->) should have type (?? -> ? -> *), and you'd be right
296         -- But if we do that we get kind errors when saying
297         --      instance Control.Arrow (->)
298         -- becuase the expected kind is (*->*->*).  The trouble is that the
299         -- expected/actual stuff in the unifier does not go contra-variant, whereas
300         -- the kind sub-typing does.  Sigh.  It really only matters if you use (->) in
301         -- a prefix way, thus:  (->) Int# Int#.  And this is unusual.
302
303
304 tySuperKindTyCon     = mkSuperKindTyCon tySuperKindTyConName
305 coSuperKindTyCon     = mkSuperKindTyCon coSuperKindTyConName
306
307 liftedTypeKindTyCon   = mkKindTyCon liftedTypeKindTyConName
308 openTypeKindTyCon     = mkKindTyCon openTypeKindTyConName
309 unliftedTypeKindTyCon = mkKindTyCon unliftedTypeKindTyConName
310 ubxTupleKindTyCon     = mkKindTyCon ubxTupleKindTyConName
311 argTypeKindTyCon      = mkKindTyCon argTypeKindTyConName
312
313 mkKindTyCon :: Name -> TyCon
314 mkKindTyCon name = mkVoidPrimTyCon name tySuperKind 0
315
316 --------------------------
317 -- ... and now their names
318
319 tySuperKindTyConName      = mkPrimTyConName (fsLit "BOX") tySuperKindTyConKey tySuperKindTyCon
320 coSuperKindTyConName      = mkPrimTyConName (fsLit "COERCION") coSuperKindTyConKey coSuperKindTyCon
321 liftedTypeKindTyConName   = mkPrimTyConName (fsLit "*") liftedTypeKindTyConKey liftedTypeKindTyCon
322 openTypeKindTyConName     = mkPrimTyConName (fsLit "?") openTypeKindTyConKey openTypeKindTyCon
323 unliftedTypeKindTyConName = mkPrimTyConName (fsLit "#") unliftedTypeKindTyConKey unliftedTypeKindTyCon
324 ubxTupleKindTyConName     = mkPrimTyConName (fsLit "(#)") ubxTupleKindTyConKey ubxTupleKindTyCon
325 argTypeKindTyConName      = mkPrimTyConName (fsLit "??") argTypeKindTyConKey argTypeKindTyCon
326 funTyConName              = mkPrimTyConName (fsLit "(->)") funTyConKey funTyCon
327
328 mkPrimTyConName :: FastString -> Unique -> TyCon -> Name
329 mkPrimTyConName occ key tycon = mkWiredInName gHC_PRIM (mkTcOccFS occ) 
330                                               key 
331                                               (ATyCon tycon)
332                                               BuiltInSyntax
333         -- All of the super kinds and kinds are defined in Prim and use BuiltInSyntax,
334         -- because they are never in scope in the source
335
336 ------------------
337 -- We also need Kinds and SuperKinds, locally and in TyCon
338
339 kindTyConType :: TyCon -> Type
340 kindTyConType kind = TyConApp kind []
341
342 -- | See "Type#kind_subtyping" for details of the distinction between these 'Kind's
343 liftedTypeKind, unliftedTypeKind, openTypeKind, argTypeKind, ubxTupleKind :: Kind
344
345 liftedTypeKind   = kindTyConType liftedTypeKindTyCon
346 unliftedTypeKind = kindTyConType unliftedTypeKindTyCon
347 openTypeKind     = kindTyConType openTypeKindTyCon
348 argTypeKind      = kindTyConType argTypeKindTyCon
349 ubxTupleKind     = kindTyConType ubxTupleKindTyCon
350
351 -- | Given two kinds @k1@ and @k2@, creates the 'Kind' @k1 -> k2@
352 mkArrowKind :: Kind -> Kind -> Kind
353 mkArrowKind k1 k2 = FunTy k1 k2
354
355 -- | Iterated application of 'mkArrowKind'
356 mkArrowKinds :: [Kind] -> Kind -> Kind
357 mkArrowKinds arg_kinds result_kind = foldr mkArrowKind result_kind arg_kinds
358
359 tySuperKind, coSuperKind :: SuperKind
360 tySuperKind = kindTyConType tySuperKindTyCon 
361 coSuperKind = kindTyConType coSuperKindTyCon 
362
363 isTySuperKind :: SuperKind -> Bool
364 isTySuperKind (TyConApp kc []) = kc `hasKey` tySuperKindTyConKey
365 isTySuperKind _                = False
366
367 isCoSuperKind :: SuperKind -> Bool
368 isCoSuperKind (TyConApp kc []) = kc `hasKey` coSuperKindTyConKey
369 isCoSuperKind _                = False
370
371 -------------------
372 -- Lastly we need a few functions on Kinds
373
374 isLiftedTypeKindCon :: TyCon -> Bool
375 isLiftedTypeKindCon tc    = tc `hasKey` liftedTypeKindTyConKey
376
377 isLiftedTypeKind :: Kind -> Bool
378 isLiftedTypeKind (TyConApp tc []) = isLiftedTypeKindCon tc
379 isLiftedTypeKind _                = False
380
381 isCoercionKind :: Kind -> Bool
382 -- All coercions are of form (ty1 ~ ty2)
383 -- This function is here rather than in Coercion, 
384 -- because it's used in a knot-tied way to enforce invariants in Var
385 isCoercionKind (PredTy (EqPred {})) = True
386 isCoercionKind _                    = False
387
388 coVarPred :: CoVar -> PredType
389 coVarPred tv
390   = ASSERT( isCoVar tv )
391     case tyVarKind tv of
392         PredTy eq -> eq
393         other     -> pprPanic "coVarPred" (ppr tv $$ ppr other)
394 \end{code}
395
396
397
398 %************************************************************************
399 %*                                                                      *
400 \subsection{The external interface}
401 %*                                                                      *
402 %************************************************************************
403
404 @pprType@ is the standard @Type@ printer; the overloaded @ppr@ function is
405 defined to use this.  @pprParendType@ is the same, except it puts
406 parens around the type, except for the atomic cases.  @pprParendType@
407 works just by setting the initial context precedence very high.
408
409 \begin{code}
410 data Prec = TopPrec     -- No parens
411           | FunPrec     -- Function args; no parens for tycon apps
412           | TyConPrec   -- Tycon args; no parens for atomic
413           deriving( Eq, Ord )
414
415 maybeParen :: Prec -> Prec -> SDoc -> SDoc
416 maybeParen ctxt_prec inner_prec pretty
417   | ctxt_prec < inner_prec = pretty
418   | otherwise              = parens pretty
419
420 ------------------
421 pprType, pprParendType :: Type -> SDoc
422 pprType       ty = ppr_type TopPrec   ty
423 pprParendType ty = ppr_type TyConPrec ty
424
425 pprTypeApp :: NamedThing a => a -> [Type] -> SDoc
426 -- The first arg is the tycon, or sometimes class
427 -- Print infix if the tycon/class looks like an operator
428 pprTypeApp tc tys = ppr_type_app TopPrec (getName tc) tys
429
430 ------------------
431 pprPred :: PredType -> SDoc
432 pprPred (ClassP cls tys) = pprClassPred cls tys
433 pprPred (IParam ip ty)   = ppr ip <> dcolon <> pprType ty
434 pprPred (EqPred ty1 ty2) = sep [ppr ty1, nest 2 (ptext (sLit "~")), ppr ty2]
435
436 pprClassPred :: Class -> [Type] -> SDoc
437 pprClassPred clas tys = ppr_type_app TopPrec (getName clas) tys
438
439 pprTheta :: ThetaType -> SDoc
440 pprTheta theta = parens (sep (punctuate comma (map pprPred theta)))
441
442 pprThetaArrow :: ThetaType -> SDoc
443 pprThetaArrow theta 
444   | null theta = empty
445   | otherwise  = parens (sep (punctuate comma (map pprPred theta))) <+> ptext (sLit "=>")
446
447 ------------------
448 instance Outputable Type where
449     ppr ty = pprType ty
450
451 instance Outputable PredType where
452     ppr = pprPred
453
454 instance Outputable name => OutputableBndr (IPName name) where
455     pprBndr _ n = ppr n -- Simple for now
456
457 ------------------
458         -- OK, here's the main printer
459
460 pprKind, pprParendKind :: Kind -> SDoc
461 pprKind = pprType
462 pprParendKind = pprParendType
463
464 ppr_type :: Prec -> Type -> SDoc
465 ppr_type _ (TyVarTy tv)         -- Note [Infix type variables]
466   | isSymOcc (getOccName tv)  = parens (ppr tv)
467   | otherwise                 = ppr tv
468 ppr_type _ (PredTy pred)      = ifPprDebug (ptext (sLit "<pred>")) <> (ppr pred)
469 ppr_type p (TyConApp tc tys)  = ppr_tc_app p tc tys
470
471 ppr_type p (AppTy t1 t2) = maybeParen p TyConPrec $
472                            pprType t1 <+> ppr_type TyConPrec t2
473
474 ppr_type p ty@(ForAllTy _ _)       = ppr_forall_type p ty
475 ppr_type p ty@(FunTy (PredTy _) _) = ppr_forall_type p ty
476
477 ppr_type p (FunTy ty1 ty2)
478   = -- We don't want to lose synonyms, so we mustn't use splitFunTys here.
479     maybeParen p FunPrec $
480     sep (ppr_type FunPrec ty1 : ppr_fun_tail ty2)
481   where
482     ppr_fun_tail (FunTy ty1 ty2) = (arrow <+> ppr_type FunPrec ty1) : ppr_fun_tail ty2
483     ppr_fun_tail other_ty        = [arrow <+> pprType other_ty]
484
485 ppr_forall_type :: Prec -> Type -> SDoc
486 ppr_forall_type p ty
487   = maybeParen p FunPrec $
488     sep [pprForAll tvs, pprThetaArrow ctxt, pprType tau]
489   where
490     (tvs,  rho) = split1 [] ty
491     (ctxt, tau) = split2 [] rho
492
493     -- We need to be extra careful here as equality constraints will occur as
494     -- type variables with an equality kind.  So, while collecting quantified
495     -- variables, we separate the coercion variables out and turn them into
496     -- equality predicates.
497     split1 tvs (ForAllTy tv ty) 
498       | not (isCoVar tv)     = split1 (tv:tvs) ty
499     split1 tvs ty            = (reverse tvs, ty)
500  
501     split2 ps (PredTy p `FunTy` ty) = split2 (p:ps) ty
502     split2 ps (ForAllTy tv ty) 
503         | isCoVar tv                = split2 (coVarPred tv : ps) ty
504     split2 ps ty                    = (reverse ps, ty)
505
506 ppr_tc_app :: Prec -> TyCon -> [Type] -> SDoc
507 ppr_tc_app _ tc []
508   = ppr_tc tc
509 ppr_tc_app _ tc [ty]
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 "??")
517
518 ppr_tc_app p tc tys
519   | isTupleTyCon tc && tyConArity tc == length tys
520   = tupleParens (tupleTyConBoxity tc) (sep (punctuate comma (map pprType tys)))
521   | otherwise
522   = ppr_type_app p (getName tc) tys
523
524 ppr_type_app :: Prec -> Name -> [Type] -> SDoc
525 -- Used for classes as well as types; that's why it's separate from ppr_tc_app
526 ppr_type_app p tc tys
527   | is_sym_occ          -- Print infix if possible
528   , [ty1,ty2] <- tys    -- We know nothing of precedence though
529   = maybeParen p FunPrec (sep [ppr_type FunPrec ty1, 
530                                pprInfixVar True (ppr tc) <+> ppr_type FunPrec ty2])
531   | otherwise
532   = maybeParen p TyConPrec (hang (pprPrefixVar is_sym_occ (ppr tc))
533                                2 (sep (map pprParendType tys)))
534   where
535     is_sym_occ = isSymOcc (getOccName tc)
536
537 ppr_tc :: TyCon -> SDoc -- No brackets for SymOcc
538 ppr_tc tc 
539   = pp_nt_debug <> ppr tc
540   where
541    pp_nt_debug | isNewTyCon tc = ifPprDebug (if isRecursiveTyCon tc 
542                                              then ptext (sLit "<recnt>")
543                                              else ptext (sLit "<nt>"))
544                | otherwise     = empty
545
546 -------------------
547 pprForAll :: [TyVar] -> SDoc
548 pprForAll []  = empty
549 pprForAll tvs = ptext (sLit "forall") <+> sep (map pprTvBndr tvs) <> dot
550
551 pprTvBndr :: TyVar -> SDoc
552 pprTvBndr tv | isLiftedTypeKind kind = ppr tv
553              | otherwise             = parens (ppr tv <+> dcolon <+> pprKind kind)
554              where
555                kind = tyVarKind tv
556 \end{code}
557
558 Note [Infix type variables]
559 ~~~~~~~~~~~~~~~~~~~~~~~~~~~
560 In Haskell 98 you can say
561
562    f :: (a ~> b) -> b
563
564 and the (~>) is considered a type variable.  However, the type
565 pretty-printer in this module will just see (a ~> b) as
566
567    App (App (TyVarTy "~>") (TyVarTy "a")) (TyVarTy "b")
568
569 So it'll print the type in prefix form.  To avoid confusion we must
570 remember to parenthesise the operator, thus
571
572    (~>) a b -> b
573
574 See Trac #2766.
575
576
577
578