--- /dev/null
+<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
+<html>
+ <head>
+ <META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=ISO-8859-1">
+ <title>The GHC Commentary - Sugar Free: From Haskell To Core</title>
+ </head>
+
+ <body BGCOLOR="FFFFFF">
+ <h1>The GHC Commentary - Sugar Free: From Haskell To Core</h1>
+ <p>
+ Up until after type checking, GHC keeps the source program in an
+ abstract representation of Haskell source without removing any of the
+ syntactic sugar (such as, list comprehensions) that could easily be
+ represented by more primitive Haskell. This complicates part of the
+ front-end considerably as the abstract syntax of Haskell (as exported by
+ the module <a
+ href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/hsSyn/HsSyn.lhs"><code>HsSyn</code></a>)
+ is much more complex than a simplified representation close to, say, the
+ <a href="http://haskell.org/onlinereport/intro.html#sect1.2">Haskell
+ Kernel</a> would be. However, having a representation that is as close
+ as possible to the surface syntax simplifies the generation of clear
+ error messages. As GHC (quite in contrast to "conventional" compilers)
+ prints code fragments as part of error messages, the choice of
+ representation is especially important.
+ <p>
+ Nonetheless, as soon as the input has passed all static checks, it is
+ transformed into GHC's principal intermediate language that goes by the
+ name of <em>Core</em> and whose representation is exported by the
+ module <a
+ href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/coreSyn/CoreSyn.lhs"><code>CoreSyn</code></a>.
+ All following compiler phases, except code generation operate on Core.
+ Due to Andrew Tolmach's effort, there is also an <a
+ href="http://www.haskell.org/ghc/docs/papers/core.ps.gz">external
+ representation for Core.</a>
+ <p>
+ The conversion of the compiled module from <code>HsSyn</code> into that
+ of <code>CoreSyn</code> is performed by a phase called the
+ <em>desugarer</em>, which is located in
+ <a
+ href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/deSugar/"><code>fptools/ghc/compiler/deSugar/</code></a>.
+ It's operation is detailed in the following.
+ </p>
+
+ <h2>Auxilliary Functions</h2>
+ <p>
+ The modules <a
+ href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/deSugar/DsMonad.lhs"><code>DsMonad<code></a>
+ defines the desugarer monad (of type <code>DsM</code>) which maintains
+ the environment needed for desugaring. In particular, it encapsulates a
+ unique supply for generating new variables, a map to lookup standard
+ names (such as functions from the prelude), a source location for error
+ messages, and a pool to collect warning messages generated during
+ desugaring. Initialisation of the environment happens in the function <a
+ href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/deSugar/Desugar.lhs"><code>Desugar</code></a><code>.desugar</code>,
+ which is also the main entry point into the desugarer.
+ <p>
+ The generation of Core code often involves the use of standard functions
+ for which proper identifiers (i.e., values of type <code>Id</code> that
+ actually refer to the definition in the right Prelude) need to be
+ obtained. This is supported by the function
+ <code>DsMonad.dsLookupGlobalValue :: Name -> DsM Id</code>.
+
+ <h2>Pattern Matching</h2>
+ <p>
+ Nested pattern matching with guards and everything is translated into
+ the simple, flat case expressions of Core by the following modules:
+ <dl>
+ <dt><a
+ href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/deSugar/Match.lhs"><code>Match</code></a>:
+ <dd>This modules contains the main pattern-matching compiler in the form
+ of a function called <code>match</code>. There is some documentation
+ as to how <code>match</code> works contained in the module itself.
+ Generally, the implemented algorithm is similar to the one described
+ in Phil Wadler's Chapter ? of Simon Peyton Jones' <em>The
+ Implementation of Functional Programming Languages</em>.
+ <code>Match</code> exports a couple of functions with not really
+ intuitive names. In particular, it exports <code>match</code>,
+ <code>matchWrapper</code>, <code>matchExport</code>, and
+ <code>matchSimply</code>. The function <code>match</code>, which is
+ the main work horse, is only used by the other matching modules. The
+ function <code>matchExport</code> - despite it's name - is merely used
+ internally in <code>Match</code> and handles warning messages (see
+ below for more details). The actual interface to the outside is
+ <code>matchWrapper</code>, which converts the output of the type
+ checker into the form needed by the pattern matching compiler (i.e., a
+ list of <code>EquationInfo</code>). Similar in function to
+ <code>matchWrapper</code> is <code>matchSimply</code>, which provides
+ an interface for the case where a single expression is to be matched
+ against a single pattern (as, for example, is the case in bindings in
+ a <code>do</code> expression).
+ <dt><a
+ href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/deSugar/MatchCon.lhs"><code>MatchCon</code></a>:
+ <dd>This module generates code for a set of alternative constructor
+ patterns that belong to a single type by means of the routine
+ <code>matchConFamily</code>. More precisely, the routine gets a set
+ of equations where the left-most pattern of each equation is a
+ constructor pattern with a head symbol from the same type as that of
+ all the other equations. A Core case expression is generated that
+ distinguihes between all these constructors. The routine is clever
+ enough to generate a sparse case expression and to add a catch-all
+ default case only when needed (i.e., if the case expression isn't
+ exhaustive already). There is also an explanation at the start of the
+ modules.
+ <dt><a
+ href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/deSugar/MatchLit.lhs"><code>MatchLit</code></a>:
+ <dd>Generates code for a set of alternative literal patterns by means of
+ the routine <code>matchLiterals</code>. The principle is similar to
+ that of <code>matchConFamily</code>, but all left-most patterns are
+ literals of the same type.
+ <dt><a
+ href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/deSugar/DsUtils.lhs"><code>DsUtils</code></a>:
+ <dd>This module provides a set of auxilliary definitions as well as the
+ data types <code>EquationInfo</code> and <code>MatchResult</code> that
+ form the input and output, respectively, of the pattern matching
+ compiler.
+ <dt><a
+ href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/deSugar/Check.lhs"><code>Check</code></a>:
+ <dd>This module does not really contribute the compiling pattern
+ matching, but it inspects sets of equations to find whether there are
+ any overlapping patterns or non-exhaustive pattern sets. This task is
+ implemented by the function <code>check</code>, which returns a list of
+ patterns that are part of a non-exhaustive case distinction as well as a
+ set of equation labels that can be reached during execution of the code;
+ thus, the remaining equations are shadowed due to overlapping patterns.
+ The function <code>check</code> is invoked and its result converted into
+ suitable warning messages by the function <code>Match.matchExport</code>
+ (which is a wrapper for <code>Match.match</code>).
+ </dl>
+ <p>
+ The central function <code>match</code>, given a set of equations,
+ proceeds in a number of steps:
+ <ol>
+ <li>It starts by desugaring the left-most pattern of each equation using
+ the function <code>tidy1</code> (indirectly via
+ <code>tidyEqnInfo</code>). During this process, non-elementary
+ pattern (e.g., those using explicit list syntax <code>[x, y, ...,
+ z]</code>) are converted to a standard constructor pattern and also
+ irrefutable pattern are removed.
+ <li>Then, a process called <em>unmixing</em> clusters the equations into
+ blocks (without re-ordering them), such that the left-most pattern of
+ all equations in a block are either all variables, all literals, or
+ all constructors.
+ <li>Each block is, then, compiled by <code>matchUnmixedEqns</code>,
+ which forwards the handling of literal pattern blocks to
+ <code>MatchLit.matchLiterals</code>, of constructor pattern blocks to
+ <code>MatchCon.matchConFamily</code>, and hands variable pattern
+ blocks back to <code>match</code>.
+ </ol>
+
+ <p><hr><small>
+<!-- hhmts start -->
+Last modified: Wed Jan 16 23:40:16 EST 2002
+<!-- hhmts end -->
+ </small>
+ </body>
+</html>
projects / ghc-hetmet.git / commitdiff