2 % (c) The GRASP/AQUA Project, Glasgow University, 1998
4 \section[TypeRep]{Type - friends' interface}
8 Type(..), TyNote(..), PredType(..), UsageAnn(..), -- Representation visible to friends
10 Kind, ThetaType, RhoType, TauType, SigmaType, -- Synonyms
13 superKind, superBoxity, -- KX and BX respectively
14 boxedBoxity, unboxedBoxity, -- :: BX
16 typeCon, -- :: BX -> KX
17 boxedTypeKind, unboxedTypeKind, openTypeKind, -- :: KX
18 mkArrowKind, mkArrowKinds, -- :: KX -> KX -> KX
23 #include "HsVersions.h"
26 import Var ( TyVar, UVar )
30 import Name ( Name, mkGlobalName, mkKindOccFS, tcName )
31 import OccName ( mkOccFS, tcName )
32 import TyCon ( TyCon, KindCon,
33 mkFunTyCon, mkKindCon, mkSuperKindCon,
35 import Class ( Class )
38 import SrcLoc ( builtinSrcLoc )
39 import PrelNames ( pREL_GHC, kindConKey, boxityConKey, boxedConKey,
40 unboxedConKey, typeConKey, anyBoxConKey, funTyConName
44 %************************************************************************
46 \subsection{Type Classifications}
48 %************************************************************************
52 *unboxed* iff its representation is other than a pointer
53 Unboxed types cannot instantiate a type variable.
54 Unboxed types are always unlifted.
56 *lifted* A type is lifted iff it has bottom as an element.
57 Closures always have lifted types: i.e. any
58 let-bound identifier in Core must have a lifted
59 type. Operationally, a lifted object is one that
61 (NOTE: previously "pointed").
63 *algebraic* A type with one or more constructors, whether declared
64 with "data" or "newtype".
65 An algebraic type is one that can be deconstructed
66 with a case expression.
67 *NOT* the same as lifted types, because we also
68 include unboxed tuples in this classification.
70 *data* A type declared with "data". Also boxed tuples.
72 *primitive* iff it is a built-in type that can't be expressed
75 Currently, all primitive types are unlifted, but that's not necessarily
76 the case. (E.g. Int could be primitive.)
78 Some primitive types are unboxed, such as Int#, whereas some are boxed
79 but unlifted (such as ByteArray#). The only primitive types that we
80 classify as algebraic are the unboxed tuples.
82 examples of type classifications:
84 Type primitive boxed lifted algebraic
85 -----------------------------------------------------------------------------
87 ByteArray# Yes Yes No No
88 (# a, b #) Yes No No Yes
89 ( a, b ) No Yes Yes Yes
92 %************************************************************************
94 \subsection{The data type}
96 %************************************************************************
100 type SuperKind = Type
103 type TyVarSubst = TyVarEnv Type
109 Type -- Function is *not* a TyConApp
112 | TyConApp -- Application of a TyCon
113 TyCon -- *Invariant* saturated appliations of FunTyCon and
114 -- synonyms have their own constructors, below.
115 [Type] -- Might not be saturated.
117 | FunTy -- Special case of TyConApp: TyConApp FunTyCon [t1,t2]
121 | ForAllTy -- A polymorphic type
125 | PredTy -- A Haskell predicate
128 | NoteTy -- A type with a note attached
130 Type -- The expanded version
133 = SynNote Type -- The unexpanded version of the type synonym; always a TyConApp
134 | FTVNote TyVarSet -- The free type variables of the noted expression
135 | UsgNote UsageAnn -- The usage annotation at this node
136 | UsgForAll UVar -- Annotation variable binder
139 = UsOnce -- Used at most once
140 | UsMany -- Used possibly many times (no info; this annotation can be omitted)
141 | UsVar UVar -- Annotation is variable (unbound OK only inside analysis)
144 type ThetaType = [PredType]
147 type SigmaType = Type
151 -------------------------------------
154 Consider these examples:
155 f :: (Eq a) => a -> Int
156 g :: (?x :: Int -> Int) => a -> Int
157 h :: (r\l) => {r} => {l::Int | r}
159 Here the "Eq a" and "?x :: Int -> Int" and "r\l" are all called *predicates*
160 Predicates are represented inside GHC by PredType:
163 data PredType = Class Class [Type]
167 (We don't support TREX records yet, but the setup is designed
168 to expand to allow them.)
170 A Haskell qualified type, such as that for f,g,h above, is
172 * a FunTy for the double arrow
173 * with a PredTy as the function argument
175 The predicate really does turn into a real extra argument to the
176 function. If the argument has type (PredTy p) then the predicate p is
177 represented by evidence (a dictionary, for example, of type (predRepTy p).
180 %************************************************************************
184 %************************************************************************
188 kind :: KX = kind -> kind
189 | Type boxity -- (Type *) is printed as just *
190 -- (Type #) is printed as just #
192 | OpenKind -- Can be boxed or unboxed
195 | kv -- A kind variable; *only* happens during kind checking
197 boxity :: BX = * -- Boxed
199 | bv -- A boxity variable; *only* happens during kind checking
201 There's a little subtyping at the kind level:
202 forall b. Type b <: OpenKind
204 That is, a type of kind (Type b) is OK in a context requiring an OpenKind
206 OpenKind, written '?', is used as the kind for certain type variables,
209 1. The universally quantified type variable(s) for special built-in
210 things like error :: forall (a::?). String -> a.
211 Here, the 'a' can be instantiated to a boxed or unboxed type.
213 2. Kind '?' is also used when the typechecker needs to create a fresh
214 type variable, one that may very well later be unified with a type.
215 For example, suppose f::a, and we see an application (f x). Then a
216 must be a function type, so we unify a with (b->c). But what kind
217 are b and c? They can be boxed or unboxed types, so we give them kind '?'.
219 When the type checker generalises over a bunch of type variables, it
220 makes any that still have kind '?' into kind '*'. So kind '?' is never
221 present in an inferred type.
225 mk_kind_name key str = mkGlobalName key pREL_GHC (mkKindOccFS tcName str) builtinSrcLoc
226 -- mk_kind_name is a bit of a hack
227 -- The LocalDef means that we print the name without
228 -- a qualifier, which is what we want for these kinds.
229 -- It's used for both Kinds and Boxities
232 ------------------------------------------
233 Define KX, the type of a kind
234 BX, the type of a boxity
237 superKind :: SuperKind -- KX, the type of all kinds
238 superKindName = mk_kind_name kindConKey SLIT("KX")
239 superKind = TyConApp (mkSuperKindCon superKindName) []
241 superBoxity :: SuperKind -- BX, the type of all boxities
242 superBoxityName = mk_kind_name boxityConKey SLIT("BX")
243 superBoxity = TyConApp (mkSuperKindCon superBoxityName) []
246 ------------------------------------------
247 Define boxities: @*@ and @#@
250 boxedBoxity, unboxedBoxity :: Kind -- :: BX
252 boxedConName = mk_kind_name boxedConKey SLIT("*")
253 boxedBoxity = TyConApp (mkKindCon boxedConName superBoxity) []
255 unboxedConName = mk_kind_name unboxedConKey SLIT("#")
256 unboxedBoxity = TyConApp (mkKindCon unboxedConName superBoxity) []
259 ------------------------------------------
260 Define kinds: Type, Type *, Type #, and OpenKind
263 typeCon :: KindCon -- :: BX -> KX
264 typeConName = mk_kind_name typeConKey SLIT("Type")
265 typeCon = mkKindCon typeConName (superBoxity `FunTy` superKind)
267 boxedTypeKind, unboxedTypeKind, openTypeKind :: Kind -- Of superkind superKind
269 boxedTypeKind = TyConApp typeCon [boxedBoxity]
270 unboxedTypeKind = TyConApp typeCon [unboxedBoxity]
272 openKindConName = mk_kind_name anyBoxConKey SLIT("?")
273 openKindCon = mkKindCon openKindConName superKind
274 openTypeKind = TyConApp openKindCon []
277 ------------------------------------------
281 mkArrowKind :: Kind -> Kind -> Kind
282 mkArrowKind k1 k2 = k1 `FunTy` k2
284 mkArrowKinds :: [Kind] -> Kind -> Kind
285 mkArrowKinds arg_kinds result_kind = foldr mkArrowKind result_kind arg_kinds
289 %************************************************************************
291 \subsection{Wired-in type constructors
293 %************************************************************************
295 We define a few wired-in type constructors here to avoid module knots
298 funTyCon = mkFunTyCon funTyConName (mkArrowKinds [boxedTypeKind, boxedTypeKind] boxedTypeKind)