|Version 23 (modified by simonpj, 2 years ago) (diff)|
The data type Type and its friends
GHC compiles a typed programming language, and GHC's intermediate language is explicitly typed. So the data type that GHC uses to represent types is of central importance.
The single data type Type is used to represent
- Types (possibly of higher kind); e.g. [Int], Maybe
- Kinds (which classify types and coercions); e.g. (* -> *), T :=: [Int]. See Commentary/Compiler/Kinds
- Sorts (which classify types); e.g. TY, CO
GHC's use of coercions and equality constraints is important enough to deserve its own page.
The module TypeRep exposes the representation because a few other modules (Type, TcType, Unify, etc) work directly on its representation. However, you should not lightly pattern-match on Type; it is meant to be an abstract type. Instead, try to use functions defined by Type, TcType etc.
Views of types
Even when considering only types (not kinds, sorts, coercions) you need to know that GHC uses a single data type for types, even though there are two different "views".
- The "typechecker view" (or "source view") regards the type as a Haskell type, complete with implicit parameters, class constraints, and the like. For example:
forall a. (Eq a, %x::Int) => a -> Int
- The "core view" regards the type as a Core-language type, where class and implicit parameter constraints are treated as function arguments:
forall a. Eq a -> Int -> a -> Int
These two "views" are supported by a family of functions operating over that view:
- compiler/types/TypeRep.lhs: here is where Type is defined.
- compiler/types/Type.lhs: core-view utility functions over Type.
- compiler/typecheck/TcType.lhs: source-view utility functions over Type.
The "view" functions are shallow, not deep---a view function just looks at the root of the tree representing the type. For example, part of the coreView function (compiler/types/Type.lhs) looks like this:
coreView :: Type -> Maybe Type coreView (PredTy p) = Just (predTypeRep p) coreView (NoteTy _ ty) = Just ty coreView other = Nothing
Notice that in the NoteTy case, coreView does not call itself. Now, clients of the view look like this:
splitFunTy_maybe :: Type -> Maybe (Type,Type) splitFunTy_maybe ty | Just ty' <- coreView ty = splitFunTy_maybe ty' splitFunTy_maybe (FunTy t1 t2) = Just (t1,t2) splitFunTy_maybe other = Nothing
Notice the first line, which uses the view, and recurses when the view 'fires'. Since coreView is non-recursive, GHC will inline it, and the optimiser will ultimately produce something like:
splitFunTy_maybe :: Type -> Maybe (Type,Type) splitFunTy_maybe (PredTy p) = splitFunTy_maybe (predTypeRep p) splitFunTy_maybe (NoteTy _ ty) = splitFunTy_maybe ty splitFunTy_maybe (FunTy t1 t2) = Just (t1,t2) splitFunTy_maybe other = Nothing
The representation of Type
Here, then is the representation of types (see compiler/types/TypeRep.lhs for more details):
type TyVar = Var data Type = TyVarTy TyVar -- Type variable | AppTy Type Type -- Application | TyConApp TyCon [Type] -- Type constructor application | FunTy Type Type -- Arrow type | ForAllTy Var Type -- Polymorphic type | LitTy TyLit -- Type literals data TyLit = NumTyLit Integer -- A number | StrTyLit FastString -- A string
Invariant: if the head of a type application is a TyCon, GHC always uses the TyConApp constructor, not AppTy. This invariant is maintained internally by 'smart constructors'. A similar invariant applies to FunTy; TyConApp is never used with an arrow type.
Type variables are represented by the TyVar constructor of the data type Var.
In Haskell we write
f :: forall a. Num a => a -> a
but in Core the => is represented by an ordinary FunTy. So f's type looks like this:
ForAllTy a (TyConApp num [TyVarTy a] `FunTy` TyVarTy a `FunTy` TyVarTy a) where a :: TyVar num :: TyCOn
Nevertheless, we can tell when a function argument is actually a predicate (and hence should be displayed with =>, etc), using
isPredTy :: Type -> Bool
The various forms of predicate can be extracted thus:
classifyPredType :: Type -> PredTree data PredTree = ClassPred Class [Type] -- Class predicates e.g. (Num a) | EqPred Type Type -- Equality predicates e.g. (a ~ b) | TuplePred [PredType] -- Tuples of predicates e.g. (Num a, a~b) | IrredPred PredType -- Higher order predicates e.g. (c a)
These functions are defined in module Type.
GHC uses the following nomenclature for types:
- A type is unboxed iff its representation is other than a pointer. Unboxed types are also unlifted.
- A type is lifted iff it has bottom as an element. Closures always have lifted types: i.e. any let-bound identifier in Core must have a lifted type. Operationally, a lifted object is one that can be entered. Only lifted types may be unified with a type variable.
- A type declared with data. Also boxed tuples.
- An algebraic data type is a data type with one or more constructors, whether declared with data or newtype. An algebraic type is one that can be deconstructed with a case expression. "Algebraic" is NOT the same as "lifted", because unboxed tuples count as "algebraic".
- a type is primitive iff it is a built-in type that can't be expressed in Haskell. Currently, all primitive types are unlifted, but that's not necessarily the case. (E.g. Int could be primitive.)
Some primitive types are unboxed, such as Int#, whereas some are boxed but unlifted (such as ByteArray#). The only primitive types that we classify as algebraic are the unboxed tuples.
Examples of type classifications:
|(# a, b #)||Yes||No||No||Yes|
|( a, b )||No||Yes||Yes||Yes|