Changes between Version 7 and Version 8 of Commentary/Compiler/TypeType


Ignore:
Timestamp:
Oct 4, 2006 9:49:05 PM (9 years ago)
Author:
simonpj
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • Commentary/Compiler/TypeType

    v7 v8  
    55GHC's compiles a typed programming lanuage, and GHC's intermediate language is explicitly typed.  So the data type that GHC uses to represent types is of central importance.
    66
    7 The first thing to realise is that GHC uses a ''single'' data type for types, even though there are two different "views". 
     7The single data type {{{Type}}} is used to represent
     8 * Types (possibly of higher kind); e.g. `[Int]`, `Maybe`
     9 * Coercions; e.g. `trans (sym g) h`
     10 * Kinds (which classify types and coercions); e.g. `(* -> *)`, `T :=: [Int]`
     11 * Sorts (which classify types); e.g. `TY`, `CO`
     12
     13GHC's use of [wiki:Commentary/Compiler/FC coercions and equality constraints] is important enough to deserve its own page.
     14
     15The module {{{TypeRep}}} exposes the representation becauese 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.
     16
     17== Views of types ==
     18
     19Even 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". 
    820 * The "typechecker view" (or "source view") regards the type as a Haskell type, complete with implicit parameters, class constraints, and the like.  For example:
    921{{{
     
    1931 * [[GhcFile(compiler/types/Type.lhs)]]: core-view utility functions over {{{Type}}}.
    2032 * [[GhcFile(compiler/typecheck/TcType.lhs)]]: source-view utility functions over {{{Type}}}.
    21 The "view" functions are ''shallow'', not deep---a view function just looks at the root of the tree representing the type.  This leads to a nice programming idiom in which a case can be guarded by {{Just t' <- coreView t}}, which unfortunately the margin of this Wiki is too small to contain.
    2233
    23 The module {{{TypeRep}}} exposes the representation becauese 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.
     34The "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 ([[GhcFile(compiler/types/Type]]) looks like this:
     35{{{
     36  coreView :: Type -> Maybe Type
     37  coreView (PredTy p)    = Just (predTypeRep p)
     38  coreView (NoteTy _ ty) = Just ty
     39  coreView other         = Nothing
     40}}}
     41Notice that in the `NoteTy` case, `coreView` does not call itself.  Now, clients of the view look like this:
     42{{{
     43  splitFunTy_maybe :: Type -> Maybe (Type,Type)
     44  splitFunTy_maybe ty | Just ty' <- coreView ty = splitFunTy_maybe ty'
     45  splitFunTy_maybe (FunTy t1 t2) = Just (t1,t2)
     46  splitFunTy_maybe other         = Nothing
     47}}}
     48Notice 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 somethign like:
     49{{{
     50  splitFunTy_maybe :: Type -> Maybe (Type,Type)
     51  splitFunTy_maybe (PredTy p) = splitFunTy_maybe (predTypeRep p)
     52  splitFunTy_maybe (NoteTy _ ty) = splitFunTy_maybe ty
     53  splitFunTy_maybe (FunTy t1 t2) = Just (t1,t2)
     54  splitFunTy_maybe other         = Nothing
     55}}}
     56Neat, huh?
    2457
    25 The single data type {{{Type}}} is used to represent
    26  * Types (possibly of higher kind); e.g. `[Int]`, `Maybe`
    27  * Coercions; e.g. `trans (sym g) h`
    28  * Kinds (which classify types and coercions); e.g. `(* -> *)`, `T :=: [Int]`
    29  * Sorts (which classify types); e.g. `TY`, `CO`
    3058
    31 GHC's use of [wiki:Commentary/Compiler/FC coercions and equality constraints] is important enough to deserve its own page.
    3259
    3360== The representation of {{{Type}}} ==