%%% Front End Modules,
%%% Id Compiler Documentation
%%%
%%% Andy Shaw
%%% Wed Feb 13 15:17:29 EST 1991
%%%

\chapter{Front End Modules}

\section{Introduction}

Unlike some compilers which generate low-level code directly, the Id
compiler uses parse-trees as one of its intermediate representations for
programs.  More detailed documentation about the parse-tree data structure
can be found in \cite{DFCS}.  The front end of the Id compiler is the group
of modules which operates on the parse-tree representation.

\begin{figure}[h]
\begin{center}
\fbox{\it 
\begin{tabular}{c}
Id Source File\\
$\downarrow$ \\
{\tt file-parser} or {\tt stream-parser}\\
$\downarrow$\\
{\tt pre-scope-analysis-desugaring}\\
$\downarrow$\\
{\tt scope-analysis}\\
$\downarrow$\\
{\tt type-checking}\\
$\downarrow$\\
{\tt overloading-translation}\\
$\downarrow$\\
{\tt lambda-lift}\\
$\downarrow$\\
{\it Id Compiler Middle End}
\end{tabular}
}
\caption{Structure of Current Id Compiler Front End (3/18/91)}
\label{fig: front-end}
\end{center}
\end{figure}

%%%
%%%  The Module Descriptions
%%%
%%%
\section{The Modules}

Each module description briefly describes some high-level characteristic of
the module, including:

\begin{description}
\item[Module:] The {\tt defcompiler} module definition.
\item[Options:] A description of the module's options.
\item[Description:] A declarative description of the module's effect on the
parse tree.
\item[Strategy:] The algorithms used by the module.
\item[Author:]  Primary person responsible for coding.
\item[Caveats:] Known limitations, warnings, points of interest, etc.
\end{description}

Each module in the front end of the compiler reads or modifies a number of
global data structures in addition to its explicit parse-tree argument and
result.  The following entries, for each module, provide information about
its usage of global data structures:

\begin{description}
\item[Parse-Tree Properties:] Parse-tree node properties.
\item[Parse-Tree Slots:] Parse-tree node slots.
\end{description}

Not each module has all the entries filled in.  If a module is the first to
define an entry in a global structure or is the exclusive user of an entry
then the entry's name is in {\bf boldface} followed by a description.
Otherwise, just the name is listed.

%%%
%%% File Parser and Stream Parser
%%%
\subsection{Parsing}

\paragraph{Module:}
\begin{verbatim}
(defcompiler-module file-parser id-compiler
  (:output parse-tree def)
  (:levels-marked program)
  (:before-function initialize-lexical-analyzer-for-file)
  (:function parse-def)
  (:wrapper-macro file-parser-wrapper)
  (:options input-file))

(defcompiler-module stream-parser id-compiler
  (:output parse-tree def)
  (:levels-marked program)
  (:before-function initialize-lexical-analyzer-for-stream)
  (:function parse-def)
  (:wrapper-macro stream-parser-wrapper)
  (:options input-stream initial-character
            initial-line initial-column input-stream-truename))
\end{verbatim}

\paragraph{Options:}
\begin{itemize}
\item {\tt input-file} is the filename of the Id file to be compiled.  This
is a positional argument which has the highest importance (meaning that
this argument will appear first in the argument list of the compile
function).  This option is only used for file-compiles.

\item {\tt input-stream} is the stream that is passed to the compiler.
This is a positional argument which also has the highest importance.  (This
argument will also appear first in the argument list of the compile
function.  However, there is no conflict with the {\tt input-file} option,
because only one of these two options is ever specified for any compile
function.)  This option is only used for editor-compiles.

\item {\tt initial-character} is the initial setting for the counter
that the parser uses to keep track of where each lexeme comes from in the
editor buffer.  Eventually, this information is used for error messages and
source debugging information.  This option is only used for
editor-compiles, and the editor calculates the character offset from the
beginning of the buffer.  (For file-compiles, the character counter is
automatically set to 0, so there is no need for an option.)

\item {\tt initial-line} is similar to the {\tt initial-character}
option, except that this is the line offset from the beginning of the
buffer.

\item {\tt initial-column} is similar to the previous two options, except
that this is the column offset from the current line.

\item {\tt input-stream-truename} is only used for editor-compiles.  This
is the truename of the file which is associated with the buffer in which
the region or definition is being compiled.
\end{itemize}

\paragraph{Description:}
Only one of these two modules ({\tt file-parser} and {\tt stream-parser})
are used, depending upon whether we are compiling a file or an editor
buffer.  {\tt file-parser} reads from a file stream, and {\tt
stream-parser} reads from an editor stream.

The two modules are similar: they read the parser tables generated by PAGEN
and parse the input stream.  The {\it only} function of these modules is to
produce parse-trees from Id source.

\paragraph{Strategy:} The parser is a LALR(1) parser.  More information
about parsing can be found in \cite{Aho86a}.

The chapter on PAGEN describes how to change the grammar of the language.
Both {\tt file-parser} and {\tt stream-parser} are just interpreters for
the parser tables generated by PAGEN.


\paragraph{Author:} Ken Traub, May 1986

%\paragraph{Caveats:}

%%%
%%% Pre-scope-analysis-desugaring
%%%
\subsection{Desugaring}

\paragraph{Module:}
\begin{verbatim}
(defcompiler-module pre-scope-analysis-desugaring id-compiler
  (:input parse-tree def)
  (:output parse-tree def)
  (:options loop-bound-mode)
  (:function pre-scope-analysis-desugar-def))
\end{verbatim}

\paragraph{Options:}
\begin{itemize}
\item {\tt loop-bound-mode} selects whether {\tt for} loops will be bounded
or unbounded.  This option is set to either {\tt :bounded-for-loops} or
{\tt :unbounded-for-loops}.  If the option is set to {\tt
:bounded-for-loops}, then the compiler will generate the bounded loop
schema, which has slightly more overhead than the unbounded loop schema.

The default is {\tt :unbounded-for-loops}.
\end{itemize}

\paragraph{Description:} Several types of desugaring are done in this 
module:
\begin{enumerate}
\item List comprehensions, array comprehensions, accumulator
comprehensions, and stream comprehensions are translated into loops.

\item Array literals are desugared into either a while loop or a list of
assignments, depending upon whether its bounds are known at compile time.

\item Managers are desugared to abstract types.

\item Multi-clause {\tt def}'s are desugared to case statements.

\item Lambda's ({\tt fun}'s) are desugared to be internal {\tt def}'s
(which are eventually lifted to the top-level by the lambda lifting
module).

\item {\tt for} loops are transformed into {\tt while} loops.

\end{enumerate}

\paragraph{Strategy:} Recursively descend the parse tree.  When you find
a pattern that matches one that you wish to desugar, cut and paste that
pattern.

\paragraph{Author:} Ken Traub, January 1987

%\paragraph{Caveats:}

%%%
%%% Scope-analysis
%%%
\subsection{Scope Analysis}

\paragraph{Module:}
\begin{verbatim}
(defcompiler-module scope-analysis id-compiler
  (:input parse-tree program)
  (:output parse-tree program)
  (:function scope-analyze-program))
\end{verbatim}

\paragraph{Description:} {\tt variable} objects are added to parse tree
nodes relating valriable definitions and their uses (def-use information).
This analysis is done using the attribute grammar which is described in
more detail in \cite{DFCS}.  More information about attribute grammars can
be found in \cite{Aho86a} and in the previous chapter.

\paragraph{Strategy:}

To compute def-use information, a synthesized pt-node attribute is defined
for the definition point of each variable use, and an inherited attribute
is defined for the use point of each variable definition.  Each node is
then touched to calculate the value of each attribute variable.

The type inference system also uses attribute grammars to calculate the
types.  

\paragraph{Author:} Ken Traub, January 1987

%\paragraph{Caveats:}  Attribute grammars are an elegant way to describe some
%attribute computation.  However, not all attributes can be easily expressed
%with attribute grammars.  Certainly, the def-use information is the 

%%%
%%% Type-Checking
%%%
\subsection{Type Inference and Checking}

\paragraph{Module:}
\begin{verbatim}
(defcompiler-module type-checking id-compiler
  (:input parse-tree program)
  (:output parse-tree program)
  (:function type-check-program)
  (:options type-check))
\end{verbatim}

\paragraph{Options:}
\begin{itemize}
\item {\tt type-check} determines whether the compiler will type infer and
type check.  If this option is set to {\tt t}, then the compiler will infer
and check the types of the program; if this option is set to {\tt nil},
then the parse tree will pass through this module without alteration.

The default is {\tt t}.
\end{itemize}

\paragraph{Description:}  The type-inference system determines the type of
each variable and function.  A more detailed description of the
type-inference system can be found in Shail Aditya's Master's thesis
\cite{Gupta90}.  The type-inference system is based upon the Hindley/Milner
type-inference system used in ML, and has been extended to work with
separate compilation.  A clear exposition of the Hindley/Milner
type-inference algorithm can be found in \cite{Damas82}.

\paragraph{Strategy:}  

\paragraph{Author:} Shail Aditya, July 1988

\paragraph{Caveats:}  The type-inference module has the same limitations
that the Hindley-Milner system has.  It has exponential complexity, and
limits the polymorphism of let-block assigned variables.

In addition, in order to resolve the type of certain functions, sometimes
separate compilation will not work appropriately.  Although information is
preserved between separate compilations, if that information changes, then
enough context must be compiled in order to resolve the types of the
changed functions.

%%%
%%% Overloading-translations
%%%
\subsection{Overloading Resolution}

\paragraph{Module:}
\begin{verbatim}
(defcompiler-module overloading-translation id-compiler
  (:input parse-tree program)
  (:output parse-tree program)
  (:function translate-overloaded-program))
\end{verbatim}

\paragraph{Description:} Most of the work for this module is actually done
in the {\tt type-checking} module.  This module takes the information
deduced in the {\tt type-checking} module and cuts and pastes parse tree
nodes so that each overloaded operator is transformed into the correct type
instance of that operator.

After this module, each operator has an unambiguous type.  For example, all
{\tt+} operators will be translated to either {\tt plus\~float} or {\tt
plus\~int}.  If the operator cannot be resolved, an error message is
printed.

\paragraph{Strategy:}  With the type information calculated in the
{\tt type-checking} module, the context of each overloaded operator
resolves the type of the operator.  Each node is visited, and if that node
is an overloaded operator, the type of the operator is looked up from
information calculated in the {\tt type-checking} module and that operator
is replaced with the correct type instance of the operator.

\paragraph{Author:} Shail Aditya Gupta, July 1990

\paragraph{Caveats:} The {\tt overloading-translation} module does not have
much more functionality than the {\tt type-checking} module.  These two
modules are separate because the {\tt type-checking} module does not do any
cut and paste on the parse tree, and {\tt overloading-translation} only
does cut and paste.  In the future, this module may be incorporated into
the type-checking module.

%%%
%%% Lambda-lift
%%%
\subsection{Lambda Lifting}

\paragraph{Module:}
\begin{verbatim}
(defcompiler-module lambda-lift id-compiler
  (:input parse-tree def)
  (:output parse-tree def)
  (:function lambda-lift-def))
\end{verbatim}

\paragraph{Description:} Nested {\tt def}'s are lifted to the outermost
scope, making every function definition a top-level function.  Extra
arguments are added to the previously internal function definition to pass
along variables that the internal function references from its lexical
scope.

\paragraph{Strategy:} The algorithm for lambda lifting is taken from 
\cite{Augustsson84}.

\paragraph{Author:} Ken Traub, October 1986

\paragraph{Caveats:}  Lambda lifting is implemented to support nested
function definitions.  Scheme and Lisp use environments in order to support
nested function definitions.  It is not clear that lambda lifting is more
efficient than environments.  Perhaps we should do an environment-based
implemention in order to clarify the various issues involved in the
relative efficiency of these two implementations.
