ghc/docs/add_to_compiler/core-syntax.verb

   1 %************************************************************************
   2 %*                                                                      *
   3 \section{Core syntax, and transformations on it}
   4 \label{sec:core-syntax}
   5 %*                                                                      *
   6 %************************************************************************
   7
   8 The @CoreSyntax@ datatype is intended to be the {\em lingua franca} of
   9 the back end of the compiler; a summary is shown in
  10 Figure~\ref{fig:core-syntax}.
  11 \input{core-summary-fig}
  12 As you can see, the Core syntax is a simple
  13 functional language.
  14
  15 \subsection{Second-order polymorphic lambda calculus}
  16 \label{sec:second-order}
  17
  18 Core syntax is essentially the second-order polymorphic lambda
  19 calculus.  This is reflected in the fact that Core expressions can be
  20 {\em type applications} or {\em type abstractions} (the types in
  21 question are represented as @UniTypes@, of course).\footnote{An
  22 interesting point: there are Core-syntax programs that cannot be
  23 written in Haskell!  Core syntax
  24 is the {\em more expressive} language.  One could imagine writing a
  25 front end (parser, etc.) for a richer programming language and still
  26 being able to use this compiler's back-end machinery without change.}
  27
  28 Having explicit type application and abstraction (NB: added by
  29 the typechecker during translation) gives us a uniform,
  30 well-understood, non-{\em ad hoc} way to express the types of
  31 Core expressions.  Given that variables (i.e., @Ids@) and other
  32 basic entities have their types memoised in them, it is then easy to
  33 work out the type of {\em any Core expression}.  For example, in the
  34 expression\ToDo{example here}
  35 \begin{verbatim}
  36 ... <example to be supplied> ...
  37 \end{verbatim}
  38 @a@ is a type variable, @(<???>)@ is a type application, and, assuming
  39 the type of @??@ is $some\ math\ mode\ here...$, then the type of the
  40 expression is @...@.
  41
  42 The truly great thing about using the second-order polymorphic lambda
  43 calculus is that it is {\em easy to preserve types
  44 in the face of transformation passes}, however drastic their mangling
  45 of the original program.
  46
  47 \ToDo{example here}
  48
  49 \subsection{Parameterised and annotated Core syntax}
  50 \label{sec:parameterised-core}
  51
  52 As we saw with the ``abstract syntax'' (in
  53 Section~\ref{sec:AbsSyntax}), the Core syntax is also {\em
  54 parameterised}, this time with respect to binders and bound-variables
  55 (or ``bindees'').  The definition of a Core expression
  56 begins\srcloc{coreSyn/CoreSyn.lhs}:
  57 \begin{mytightcode}
  58 data CoreExpr binder bindee
  59      = CoVar        bindee
  60      | CoLit        CoreLiteral
  61      ...
  62 type PlainCoreBinder = Id
  63 type PlainCoreBindee = Id
  64 type PlainCoreExpr = CoreExpr PlainCoreBinder PlainCoreBindee\end{mytightcode}
  65 Most back-end passes use the parameterisation shown above, namely
  66 @PlainCoreExprs@\srcloc{coreSyn/PlainCore.lhs}, parameterised on @Id@
  67 for both binders and bindees.
  68
  69 An example of a pass that uses a different parameterisation is
  70 occurrence analysis\srcloc{simplCore/OccurAnal.lhs}, which gathers
  71 up info about the {\em occurrences} of bound variables.  It uses:
  72 \begin{mytightcode}
  73 data BinderInfo     {\dcd\rm-- various things to record about binders...}
  74 type TaggedBinder   tag = (Id, tag)
  75 type TaggedCoreExpr tag = CoreExpr (TaggedBinder tag) Id
  76
  77 substAnalyseExpr :: PlainCoreExpr -> TaggedCoreExpr BinderInfo\end{mytightcode}
  78 The pass's expression-mangling function then has the unsurprising type
  79 shown above.
  80
  81 Core syntax has a ``twin'' datatype that is also sometimes useful:
  82 {\em annotated} Core syntax\srcloc{coreSyn/AnnCoreSyn.lhs}. This is a
  83 datatype identical in form to Core syntax, but such that every
  84 ``node'' of a Core expression can be annotated with some information
  85 of your choice.  As an example, the type of a pass that attaches a
  86 @Set@ of free variables to every subexpression in a Core expression
  87 might be\srcloc{coreSyn/FreeVars.lhs}:
  88 \begin{mytightcode}
  89 freeVars :: PlainCoreExpr -> AnnCoreExpr Id Id (Set Id)
  90         {\dcd\rm-- parameterised on binders, bindees, and annotation}\end{mytightcode}
  91
  92 \subsection{Unboxing and other Core syntax details}
  93 \label{sec:unboxing}
  94
  95 One facet of the Core syntax summary in Figure~\ref{fig:core-syntax}
  96 that may have caught your eye is the separation of case-alternatives
  97 into those for boxed entities (ordinary data constructors) and unboxed
  98 entities (real machine-level things).  The ``literals'' and
  99 ``primitives'' mentioned there are also machine-level constructs.  It
 100 is for this reason that all applications of constructors and
 101 primitives are {\em saturated}; what use, for example, is
 102 a machine-level addition if you do not
 103 have two arguments to feed to it?  (Most machines do not offer curried
 104 arithmetic in their hardware.)
 105
 106 The handling of unboxed values in the back end of the compiler follows
 107 the design described in the Peyton Jones/Launchbury paper on the
 108 subject \cite{peyton-jones91b}.  You, the enthusiastic optimiser, only
 109 need to be aware that this is the ``level of discourse.''  You will
 110 also probably want to be sure that your optimisations can take full
 111 advantage of the explicitness of the unboxery.
 112
 113 \subsection{``Core Lint''---your dear friend}
 114 \label{sec:core-lint}
 115
 116 ToDo ToDo
 117
 118 % \subsection{STG syntax}
 119 % \label{sec:stg-syntax}
 120 %
 121 % As mentioned earlier, the compiler converts Core syntax into ``STG
 122 % syntax'' (named for the Spineless Tagless G-machine) before finally
 123 % making its move into the dark world we call ``Abstract~C''.
 124 %
 125 % Figure~\ref{fig:stg-syntax} shows the STG syntax,
 126 % \input{stg-summary-fig}
 127 % mainly so that you can compare it with Core syntax.  (It is at least
 128 % conceivable that you might to perform your optimisation pass at this
 129 % level.)
 130 %
 131 % STG syntax is a truly austere functional language.  In places where
 132 % Core syntax allows "exprs", STG syntax insists on "vars"---everything
 133 % has been flattened out.  Type information (abstractions and
 134 % applications) have been thrown overboard.  Other than that, STG syntax
 135 % is the ``same'' as Core syntax, with some extra non-essential
 136 % annotations on bindings: update flags and free-variable information.
 137 %
 138 % You will want to consult the revised Spineless Tagless G-machine paper
 139 % \cite{peyton-jones92a} if you wish to spend any time in the STG world.