+-- | This is the data type that represents GHCs core intermediate language. Currently
+-- GHC uses System FC <http://research.microsoft.com/~simonpj/papers/ext-f/> for this purpose,
+-- which is closely related to the simpler and better known System F <http://en.wikipedia.org/wiki/System_F>.
+--
+-- We get from Haskell source to this Core language in a number of stages:
+--
+-- 1. The source code is parsed into an abstract syntax tree, which is represented
+-- by the data type 'HsExpr.HsExpr' with the names being 'RdrName.RdrNames'
+--
+-- 2. This syntax tree is /renamed/, which attaches a 'Unique.Unique' to every 'RdrName.RdrName'
+-- (yielding a 'Name.Name') to disambiguate identifiers which are lexically identical.
+-- For example, this program:
+--
+-- @
+-- f x = let f x = x + 1
+-- in f (x - 2)
+-- @
+--
+-- Would be renamed by having 'Unique's attached so it looked something like this:
+--
+-- @
+-- f_1 x_2 = let f_3 x_4 = x_4 + 1
+-- in f_3 (x_2 - 2)
+-- @
+--
+-- 3. The resulting syntax tree undergoes type checking (which also deals with instantiating
+-- type class arguments) to yield a 'HsExpr.HsExpr' type that has 'Id.Id' as it's names.
+--
+-- 4. Finally the syntax tree is /desugared/ from the expressive 'HsExpr.HsExpr' type into
+-- this 'Expr' type, which has far fewer constructors and hence is easier to perform
+-- optimization, analysis and code generation on.
+--
+-- The type parameter @b@ is for the type of binders in the expression tree.
+data Expr b
+ = Var Id -- ^ Variables
+ | Lit Literal -- ^ Primitive literals
+ | App (Expr b) (Arg b) -- ^ Applications: note that the argument may be a 'Type'.
+ --
+ -- See "CoreSyn#let_app_invariant" for another invariant
+ | Lam b (Expr b) -- ^ Lambda abstraction
+ | Let (Bind b) (Expr b) -- ^ Recursive and non recursive @let@s. Operationally
+ -- this corresponds to allocating a thunk for the things
+ -- bound and then executing the sub-expression.
+ --
+ -- #top_level_invariant#
+ -- #letrec_invariant#
+ --
+ -- The right hand sides of all top-level and recursive @let@s
+ -- /must/ be of lifted type (see "Type#type_classification" for
+ -- the meaning of /lifted/ vs. /unlifted/).
+ --
+ -- #let_app_invariant#
+ -- The right hand side of of a non-recursive 'Let' _and_ the argument of an 'App',
+ -- /may/ be of unlifted type, but only if the expression
+ -- is ok-for-speculation. This means that the let can be floated around
+ -- without difficulty. For example, this is OK:
+ --
+ -- > y::Int# = x +# 1#
+ --
+ -- But this is not, as it may affect termination if the expression is floated out:
+ --
+ -- > y::Int# = fac 4#
+ --
+ -- In this situation you should use @case@ rather than a @let@. The function
+ -- 'CoreUtils.needsCaseBinding' can help you determine which to generate, or
+ -- alternatively use 'MkCore.mkCoreLet' rather than this constructor directly,
+ -- which will generate a @case@ if necessary
+ --
+ -- #type_let#
+ -- We allow a /non-recursive/ let to bind a type variable, thus:
+ --
+ -- > Let (NonRec tv (Type ty)) body
+ --
+ -- This can be very convenient for postponing type substitutions until
+ -- the next run of the simplifier.
+ --
+ -- At the moment, the rest of the compiler only deals with type-let
+ -- in a Let expression, rather than at top level. We may want to revist
+ -- this choice.
+ | Case (Expr b) b Type [Alt b] -- ^ Case split. Operationally this corresponds to evaluating
+ -- the scrutinee (expression examined) to weak head normal form
+ -- and then examining at most one level of resulting constructor (i.e. you
+ -- cannot do nested pattern matching directly with this).
+ --
+ -- The binder gets bound to the value of the scrutinee,
+ -- and the 'Type' must be that of all the case alternatives
+ --
+ -- #case_invariants#
+ -- This is one of the more complicated elements of the Core language, and comes
+ -- with a number of restrictions:
+ --
+ -- The 'DEFAULT' case alternative must be first in the list, if it occurs at all.
+ --
+ -- The remaining cases are in order of increasing
+ -- tag (for 'DataAlts') or
+ -- lit (for 'LitAlts').
+ -- This makes finding the relevant constructor easy, and makes comparison easier too.
+ --
+ -- The list of alternatives must be exhaustive. An /exhaustive/ case
+ -- does not necessarily mention all constructors:
+ --
+ -- @
+ -- data Foo = Red | Green | Blue
+ -- ... case x of
+ -- Red -> True
+ -- other -> f (case x of
+ -- Green -> ...
+ -- Blue -> ... ) ...
+ -- @
+ --
+ -- The inner case does not need a @Red@ alternative, because @x@ can't be @Red@ at
+ -- that program point.
+ | Cast (Expr b) Coercion -- ^ Cast an expression to a particular type. This is used to implement @newtype@s
+ -- (a @newtype@ constructor or destructor just becomes a 'Cast' in Core) and GADTs.
+ | Note Note (Expr b) -- ^ Notes. These allow general information to be
+ -- added to expressions in the syntax tree
+ | Type Type -- ^ A type: this should only show up at the top
+ -- level of an Arg
+
+-- | Type synonym for expressions that occur in function argument positions.
+-- Only 'Arg' should contain a 'Type' at top level, general 'Expr' should not
+type Arg b = Expr b
+
+-- | A case split alternative. Consists of the constructor leading to the alternative,
+-- the variables bound from the constructor, and the expression to be executed given that binding.
+-- The default alternative is @(DEFAULT, [], rhs)@
+type Alt b = (AltCon, [b], Expr b)
+
+-- | A case alternative constructor (i.e. pattern match)
+data AltCon = DataAlt DataCon -- ^ A plain data constructor: @case e of { Foo x -> ... }@.
+ -- Invariant: the 'DataCon' is always from a @data@ type, and never from a @newtype@
+ | LitAlt Literal -- ^ A literal: @case e of { 1 -> ... }@
+ | DEFAULT -- ^ Trivial alternative: @case e of { _ -> ... }@
projects / ghc-hetmet.git / blobdiff