% -*- Mode:TeX -*-
\chapter{Defining Compilers}
\label{defcompiler}

This chapter will describe a facility for the automatic composition of
compilers from component modules. The facility will take care of
managing which modules operate on an entire program and which operate
on a piece (\eg, procedure definition) at a time, compiler version
numbers, module interdependencies \etc. The goal is to make it easy to
splice experimental modules into the compiler, handle compiler
options, and the like. 

We will first describe the static structure of the compiler and its
components and then describe how they are glued together and exercised
dynamically. 

\section{Static Structure of the Compiler Substrate}
\subsection{Compiler Family}

There may be many compilers that share modules, data structures or
utilities of each other. In order to facilitate such sharing in a
consistent fashion, the substrate requires that compilers belong to a {\em
Compiler Family}\index{compiler family}. A compiler family is a pool of
resources that a group of compilers may share. The resources are one of the
following:

\begin{itemize}
\item A Data Structure.
\item A Compiler Option.
\item A Compiler Module.
\end{itemize}

It is important to understand the significance of defining a compiler
family. With a centralized place to look for compiler resources,
namely the compiler family, we can independently define resources that
belong to that family, and then build as many compilers as we like
that use one or more of those resources. For example, in the Id
Compiler Family (called {\tt id-compiler}), we have declared various
modules and options, and we use parse trees and dataflow graphs
(actually program graph and machine graph abstractions build on top of
dataflow graphs) as data structures. After this has been done, we can
group a string of modules together and form a Id compiler that
compiles from the editor into the TTDA target architecture, another
compiler may compile from files, yet another one from streams.
Similarly, a slightly different set of modules may be grouped together
to form a compiler for the Monsoon machine.


\subsubsection{Data Structure Representations and Levels (Units)}

The data structures of a family are the most important resources
around which the modules and the compilers are defined. The job of the
modules is to generate, process, and pass on the data structures of
the family. 

In order to obtain a useful handle on the various kinds of data structures
being passed around among the modules of a compiler family, and also to
ensure consistent glueing of modules that produce and consume that data
structure, a compiler family must be provided with a name of the data
structure representation. A {\em Representation}\index{representation} is
the name of such a data structure.  This can be viewed as the ``type'' of
the data structures flowing across a module boundary. A representation is
simply a class of data structure objects and is used to ensure consistent
glueing of modules. Several representation classes may, in fact, be
implemented using the same Lisp data structure objects. A
convenient example is the program graph and machine graph representations
in the Id Compiler family, both of which are abstractions built on top of
the Dataflow Graph data structure described later in this document.

A complete program may not be the best unit for independent property
maintenance and execution on a given execution vehicle. A complete program
would typically consist of several definitions, which may have embedded
procedures that may need to be lifted out, each procedure, in turn, may
need to be further subdivided into independently executable codeblocks. A
data structure representation can be used to represent a complete program
at one or more of these levels. A {\em level}\index{level}, therefore, is
the ``type'' of hierarchical clustering of the independent pieces of a
complete program. Each data structure representation also specifies the
names of all the levels it supports. The complete program can be specified
using the representation data structure at the highest level (usually
program level) supported by the representation, or equivalently, as lists
of representation objects at lower levels. As an example, consider
figure~\ref{rep-level}. The representation {\tt parse-tree} has three levels as
shown. A complete program is represented as either a single parse tree at
the {\tt program} level, or a list of parse trees each at the {\tt def}
level, or a list of list of parse trees each being at the {\tt procedure}
level. 

When there are multiple data structure representations in a family, as
is often the case, we also need to specify which levels of a
representation correspond to which levels of another representation,
so that it may be reasonable for a module to take input of one
representation level and produce output of an equivalent
representation level. An equivalence class of such representation and
level pairs is also called a {\em unit}\index{unit}. In the following
discussion and examples, we will use the term ``unit'' to refer to a
particular representation and level combination from its equivalent
class, or the class itself, interchangeably. 

\begin{fig}{rep-level}{A {\tt parse-tree} Representation of a program at various Levels.}
\begin{center}
$\begin{array}{c}
\mbox{{\bf Representation} : {\tt parse-tree}, {\bf Levels} : {\tt program}, {\tt def}, {\tt procedure}} \\[.1in]
\mbox{\tt program} \\
\Updownarrow \\
\mbox{\tt ( def$_{0}$ def$_{1}$ $\cdots$ )} \\
\Updownarrow \\
\mbox{\tt ( ( proc$_{00}$ proc$_{01}$ $\cdots$ ) ( proc$_{10}$ $\cdots$ ) $\cdots$ )}
\end{array}$
\end{center}
\end{fig}

\subsubsection{Declarations}

\lispdoc defcompiler-family family \clauses
        \repeatplus{\list{{\tt :representation} representation \repeatplus{level}}}
        \repeat{\list{{\tt :equivalence} \repeatplus{\list{representation level}}}} 
[Macro]

Defines a compiler family {\em family} along with its data structure
clauses.  Each {\tt :representation} clause defines a representation
named {\em representation} with the given level names.  The levels
appear in ascending order of size.  There must be at least one
representation clause having at least one level. The {\tt
:equivalence} clauses defines certain pairs of representation and
level to be equivalent. Errors are signalled if the system of
equivalences is not reasonable.

\subsubsection{Example of a Compiler Family}

As an example, consider the following compiler family declaration:

\begin{verbatim}
(defcompiler-family my-compiler-family
   (:representation parse-tree procedure def program)
   (:representation intermediate-form basicblock lambda lambdaset program)
   (:equivalence (parse-tree procedure) (intermediate-form lambda))
   (:equivalence (parse-tree def) (intermediate-form lambdaset))
   (:equivalence (parse-tree program) (intermediate-form program)))
\end{verbatim}

This family has two representations, {\tt parse-tree} and {\tt
intermediate-form}, along with their various levels. The equivalences of
levels into units is depicted in figure~\ref{family}.

\begin{fig}{family}{Representations, Levels, and Equivalences in {\tt
my-compiler-family}.}
\illustration{csg261-7}
\end{fig}

\subsection{Compiler Options}

An {\em Option} is a piece of external data that a module may use
during the course of its computation. This may be viewed as an
external parameter passed to the module from the environment under
which the module is invoked. Typically, an option may be used by one
or more modules, or by the particular compiler being constructed, and
therefore, is an independent resource of the compiler family. 

\subsubsection{Declarations}

\begin{lispdocs}
\lispdoc defcompiler-option name family \clauses
    \list{{\tt :type} type}
    \optgroup{\list{{\tt :how-defined} how-defined}}
    \optgroup{\list{{\tt :default} default}}
    \optgroup{\list{{\tt :mentioned-default} mentioned-default}}
    \optgroup{\list{{\tt :documentation} documentation-string}}
    \optgroup{\list{{\tt :importance} importance-number}}
[Macro]

\lispdoc *option-types* [Constant]
\end{lispdocs}

{\tt defcompiler-option} adds an option named {\em name} to the family
named {\em family}. The option must be one of the legal types. {\tt
*option-types*} denotes the set of recognized legal option types.  These
are {\tt :symbol}, {\tt :string}, {\tt :number}, {\tt :integer}, {\tt
:date}, {\tt :pathname}, {\tt :boolean}, {\tt :enumeration}, and {\tt
:stream}.

{\em how-defined}, if present, specifies how this option will be defined
in the argument list of the compiler in which it is included. The
possible values are {\tt :keyword} or {\tt :positional}. It defaults to
{\tt :keyword}. Keyword options must have a {\tt :default} clause which is
specified as {\em default}. The {\em documentation-string} describes the
option. The {\em importance-number} is a number between 0.0 and 1.0, and is
used to sort the options into an argument list of the compiler, from the
highest to the lowest. It defaults to 0.5.

\lispdoc option option-name [Macro]
Returns the current value of the option named {\em option-name}. This can
be used within the modules of the compiler to access the various options. 

\lispdoc option-exists-p option-name [Macro]
Returns a boolean value reflecting whether the option {\em option-name} is
a valid option for the current compiler or not.

\subsubsection{Example of a Compiler Option}

Here is an example of an option that may be used by a parser module of the
compiler. 

\begin{verbatim}
(defcompiler-option input-file my-compiler-family
  (:type :string)
  (:how-defined :positional)
  (:default *default-input-filename*)
  (:importance 1.0)
  (:documentation "Pathname of Source Program"))
\end{verbatim}

This defines a positionally specified string option with maximum importance (will
probably become the first argument of the compiler in which it is used).


\subsection{Compiler Modules}

A {\em Module} is an abstraction that packages up a particular phase of
compilation. It specifies the data structures that flow across its input
and output boundaries, their representations and levels, compiler options
that can be used to conditionalize the code inside the module, and points
to appropriate toplevel functions that initialize, trigger, and cleanup
that phase of compilation.

A module operates on instances of the data structures specified within a
compiler family.  When a module is provided with an object in a particular
representation at a particular level at its input boundary, it produces
another object at the same level in the same or equivalent representation
at its output boundary. A module may only have an output data structure
boundary, in which case, a fresh object is generated by the module and
placed at its output boundary each time the module is triggered. Such a
module is called a {\em generator}\index{generator module}. Conversely, a module
may only have an input data structure boundary, in which case, when an
object is placed at its input boundary, the module consumes it and does not
produce any output object. Such a module is called a {\em
collector}\index{collector module}. A module with both input and output data
structure boundaries specified is called an {\em
intermediary}\index{intermediary module}.

\subsubsection{Operating Levels of a Module and Level Marking}

Different modules may operate on different levels of the same or equivalent
representations. Operating at lower levels than the highest possible
level (\eg, {\tt program} level) permits incremental compilation of
the program. The program may be compiled definition by definition or
procedure by procedure, if the compiler modules have the capability to
operate at those levels. This reduces resource requirements of the
compiler and improves throughput, because the entire program need not
be available during the various phases of compilation. Examples of
such modules and their operation is described in section~\ref{cycling}.

When there are modules that work on levels other than the
highest level of a representation, it is necessary to figure out how to
group their output together to form higher levels. For example, a module
producing parse trees procedures must some how ``mark''\index{Marking a
level} the end of a def and a program in the sequence of procedures it
produces. Usually, this grouping is obtained by carrying through the same
grouping that existed on input to the module.  For example, suppose the
input to a module working at the {\tt basicblock} level is as follows:

\begin{verbatim}
 ( ( ( A B ) ( C ) ) ( ( D ) ) )
pr d p     p p   p d d p   p d pr
\end{verbatim}

Here, $A$, $B$, $C$, and $D$ are basic blocks. The grouping of basic blocks
into procedures is logically indicated by the ``p'' annotated parentheses;
the grouping of procedures into defs is indicated by the ``d'' annotated
parentheses, and the grouping of the whole program is indicated by the
``pr'' annotated parentheses.  Note that we invoke the module on a basic
block at a time, so the output will be $A'$, $B'$, $C'$, and $D'$
respectively for each of four calls we make to the module's function. The
substrate logic automatically inserts the ``p'', ``d'', and ``pr''
boundaries in a manner corresponding to their positions in the input to the
module, so that the output will look like:

\begin{verbatim}
 ( ( ( A' B' ) ( C' ) ) ( ( D' ) ) )
pr d p       p p    p d d p    p d pr
\end{verbatim}

But there are two situations where one cannot obtain this grouping information
just from looking at the module's input. These are,
\begin{enumerate}
\item If the very first module in the compiler (the generator) works at a
lower level than the whole program, then boundaries of its higher levels
cannot be automatically inferred.
\item If the output of a module is in a different representation than the input, and
there are levels in the output representation that have no corresponding
equivalent level in the input. 
\end{enumerate}
In both of these cases, the module must explicitly mark
the boundaries of levels that the system will not be able to figure out
from the input automatically.  In the first situation, the generator must mark all
higher levels than the level of its output; in the second situation, the module must
mark all levels that are both higher than its output and for which there is no
corresponding level in its input representation.

\subsubsection{Module {\em Before} and {\em After} Functions}

Another consequence of having modules operate at lower levels than the
highest program level is that global data structures used in a module
operating at lower levels need to be setup prior to invoking the module on
an object at that level. For this purpose, a module may specify functions
that will be invoked once at the appropriate higher level to setup and
cleanup such global data structures. These functions are called the {\em
before-function\/}s\index{before-function} and {\em
after-function\/}s\index{after-function}. 

The before and after functions may be used to setup and cleanup data
structures that need to be maintained at a level higher than the module's
operating level. Typically, such data structures dynamically accumulate
properties over multiple objects at the module's operating level. Using
representation example from the last section, for a module operating at the
{\tt def} level, we may setup a global data structure using a
before-function at the {\tt program} level. The module will accumulate/use
global properties in this data structure pertaining to each definition it
processes. An after-function at the {\tt program} level can then cleanup
the data structure when all the definitions have been processed.

\subsubsection{Declarations}

\lispdoc defcompiler-module name family \clauses
     \optgroup{\list{{\tt :input} representation level}}
     \optgroup{\list{{\tt :output} representation level}}
     \list{{\tt :function} function-name}
     \repeat{\list{{\tt :before-function} unit \optgroup{function-name}}}
     \repeat{\list{{\tt :after-function} unit \optgroup{function-name}}}
     \optgroup{\list{{\tt :levels-marked} \repeatplus{level}}}
     \optgroup{\list{{\tt :options} \repeatplus{option}}}
     \optgroup{\list{{\tt :wrapper-macro} macro-name}}
[Macro]

Defines a module {\em name} in the compiler family {\em family} along
with various clauses. At least one of {\tt :input} or {\tt :output} clauses
must be specified.  {\tt :function} clause must always be specified.  All
other clauses are optional.

{\tt :input} and {\tt :output} clauses specify the representation and the
level of the data structures that the module consumes and
produces respectively; if either is omitted, the module is assumed to be a
generator or collector, as appropriate.  The input and output
representation and levels must be equivalent, which means that they must
have been declared as such in the module's family. In addition, they must
satisfy glueing rules as described later in section~\ref{compiler}.

{\tt :function} clause specifies {\em function-name} to be the toplevel
function which implements the module. This is used to invoke the given
module with a data structure object of the input representation at the
specified input level, and must produce a data structure object of the
output representation at the output level.

{\tt :before-function} and {\tt :after-function} clauses may be used to
make the module aware of boundaries of levels higher than its input level.
The {\em function-name\/} specified in a {\tt :before-function} clause is
invoked before an object belonging to the given unit is passed on to the
module for processing. Similarly, the {\tt :after-function} clause specifies
the function to be invoked at the end of processing an object belonging to
the given unit. Unit may be of the form ({\em representation level})
where {\em representation} is the input representation and {\em level} is a
higher level than the module's input level. It could also be specified as
simply {\em level}, where the input representation is assumed.

Even though several {\tt :before-function} and {\tt :after-function}
clauses may be supplied, there should be atmost one {\tt :before-function}
or {\tt :after-function} clause per unit. For generator modules, atmost one
{\tt :before-function} and {\tt :after-function} clause is permitted, and
{\em unit} is omitted; those clauses refer to functions invoked before and
after the entire compilation.

{\tt :levels-marked} clause gives levels of the output representation
higher than the modules output level which the module function (main or
before or after) ``marks'' by calling {\tt mark-level}\index{mark-level}
when a boundary for that level is to be recorded.  

The {\tt :options} clause names compiler options required by the
module; they must have already been defined by {\tt
defcompiler-option}. Finally the {\tt :wrapper-macro} clause, if
present, sets up {\em macro-name} as a wrapper macro for the module
when it is used in a compiler. Such a wrapper can be used to set up a
dynamically scoped environment inside which the invocation of the
module is placed. We will describe these wrappers in more detail in
section~\ref{dynamic-env}. 

\lispdoc mark-level level-name \optional \list{when {\tt :before}}
[Function]

{\tt mark-level} may be called by module functions to record the boundaries
of the level {\em level-name}.  This level must be one of the levels of the
module's output representation.  For main functions of the modules, {\em
when} should be either {\tt :before} or {\tt :after}, indicating that the
separator is intended before or after the output produced by the module.
For before and after functions, {\em when} is ignored.

\subsubsection{Examples of Compiler Modules}

Below we present some examples of module declarations. We
will use the family and the option declarations given earlier.

\begin{verbatim}
(defcompiler-module def-parser my-compiler-family
  (:output parse-tree def)
  (:levels-marked program)
  (:before-function initialize-lexer-parser)
  (:function parse-def)
  (:wrapper-macro parser-wrapper)
  (:options input-file))

(defcompiler-module def-xform my-compiler-family
  (:input parse-tree procedure)
  (:output intermediate-form lambda)
  (:function xform-def)
  (:before-function program xform-before-program)
  (:after-function program xform-after-program))

(defcompiler-module program-printer my-compiler-family
  (:input intermediate-form program)
  (:function print-program))
\end{verbatim}

We have defined three modules. {\tt def-parser} is a generator that
generates parse trees at the {\tt def} level. In order to inform the
rest of the modules when the program level has finished, it will mark the
{\tt program} level during its execution when the end of the input file has
reached. The before function is run before the entire compilation and it
will be used to initialize global data structures used across the whole
program. The wrapper macro, in this case, may be used to open the input
file accessed via the compiler option {\tt input-file} given in the last
section. 

The {\tt def-xform} module converts a parse tree procedure into a
intermediate-form lambda. It uses before and after function at the program
level to setup and cleanup its internal global data structures. 

Finally, the {\tt program-printer} module is a collector that prints the
entire program at once. 

\subsection{Compilers}
\label{compiler}

With all the resources in hand, it is now possible to start building
compilers. A {\em Compiler} is a sequence of modules, the first of which
must be a generator and the last one must be a collector, all the others
are intermediaries. Each of the internal boundaries between pairs of
modules is provided with a glueing mechanism that takes care of the
representations and the levels of data structures that flow through them.
The first module must obtain its input specially from a source code stream,
which is usually an editor buffer or a file.  Similarly, the last module
must output object code specially into an object code stream which is
typically a file or a special stream into the loader. Therefore, in the
compiler substrate, we do not worry about these overall input and output
streams, and leave their specification upto the modules that handle them
which may use compiler options to specify them.

Each module must follow the following glueing rules.
\begin{enumerate}
\item A module's input level must be equivalent\footnote{Either both
should have the same representation and level or they must have been
declared as equivalent in the corresponding compiler family.} to its
output level. Its input representation can be different from its
output representation, in which case the module acts like a translator for
the program from its input data structure representation to its output
data structure representation. 

\item A module's output representation must match the subsequent
module's input representation. But, a module's output level can be
different from the input level of the subsequent module. The substrate
takes care of such mismatch of levels by appropriately queuing up objects
collected from a previous module and grouping them into a level acceptable
to the subsequent module. 
\end{enumerate}
Apart from the sequence of modules, a compiler also specifies what
options are being used by the compiler. These are a union of all the
options used by its component modules and any other specifically
declared within the compiler declaration.

\subsubsection{Declarations}

\lispdoc defcompiler name family \clauses
         \optgroup{\list{{\tt :wrapper-macro} macro-name}}
         \optgroup{\list{{\tt :message-hook} hook-name}}
         \optgroup{\list{{\tt :options} \repeatplus{option}}}
         \optgroup{\list{{\tt :lambda-list} \repeat{argument}}}
         \optgroup{\list{{\tt :option-default} option default}}
         \body{modules}
[Macro]

Defines a compiler {\em name} belonging to the compiler family {\em
family} with the given sequence of modules. The restrictions on
modules (generator, intermediary, ..., collector; matching representations)
are enforced. The various optional clauses are used in building the
toplevel compiler invocation function. 

{\tt :wrapper-macro} clause supplies a macro name for the entire compiler
to be wrapped into. {\tt :message-hook} clause allows the hook function
{\em hook-name} to be invoked whenever the compiler generates a message.
More will be said about error messages later. 

{\tt :options} clause specifies what options are to be included in the
compiler apart from those that are used by the modules of the compiler.
{\tt :option-default} permits changing the default of the specified option
for the purpose of this compiler. {\tt :lambda-list} permits the
specification of a LISP-like lambda list for the compiler invocation
function. The list is checked for the presence and proper specification of
the options of the declared compiler. 

\subsubsection{Example Compiler}

We continue with our examples of {\tt my-compiler-family}.

\begin{verbatim}
(defcompiler-option log-file my-compiler-family
  (:type :stream)
  (:how-defined :keyword)
  (:default *trace-output*)
  (:importance .2))

(defcompiler my-compiler my-compiler-family
             ((:wrapper-macro my-compiler-wrapper)
              (:message-hook my-compiler-message-hook)
              (:options log-file)
              (:option-default log-file *log-file*))
  def-parser
  def-xform
  program-printer)
\end{verbatim}

The option {\tt log-file} indicates a stream where the compiler may send
log messages. It is defined using a keyword with a low importance. 

The compiler definition specifies a wrapper macro which may be used to set
up the lexical environment of the whole compiler. It may also be used to
open the log file for output. The specified message hook function will use
this log file to record messages from the compiler. The {\tt log-file}
option and its overriding default are specified with the compiler
declaration since they do not pertain to any specific module. Finally, we
have the three modules glued together. Note from their earlier definitions
that their input and output representations and levels satisfy the glueing
rules. The top-level function generated by the above macro will be called
{\tt my-compiler} and it will have arguments specified by the various
options present in the above compiler declaration and the declarations of
its component modules. In this case, {\tt my-compiler} will have two
arguments, {\tt input-file} option used by the first module generates a
positional argument, and the {\tt log-file} option generates a keyword
argument.

\section{Dynamic Control Structure of the Compiler Substrate}

In this section, we will describe how the various pieces of a compiler as
defined in the last section are made to operate dynamically in conjunction.
Both the dynamic environment of a compiler and the scheduling of its 
various modules are controlled by the substrate.

\subsection{The Dynamic Environment of a Compiler}
\label{dynamic-env}
The compiler substrate is responsible for setting up the dynamic
environment under which each module of a compiler is invoked. This is
achieved using the declared wrapper macros of the compiler and the
individual modules, as well as other dynamic environment initializations
described below, inside which an invocation to cycle the compiler is placed.

The definition of a compiler using the above macro {\tt defcompiler}
generates a LISP function by the given name and its argument list is
generated using the options and clause specifications. This function glues
the specified modules in the given order. There are several wrappers and
variable bindings that are set up during this glueing and it is worthwhile
mentioning some of them. 

The outermost wrapper is the code that computes and sets the options. Code
to generate default values is used for an unspecified option. Next, an
error catching wrapper catches unrecoverable user errors as well as
compiler bugs that would abort the compilation and may otherwise throw the
user into the LISP debugger. Inside this the compiler message hook is set
up and the declared compiler wrapper is applied. Errors and messages are
described separately in chapter~\ref{MiscChapter}. Finally, the individual
module wrappers are applied nested from the wrapper of the first module to
the last. Inside all these wrappers lies the call to invoke the compiler. 

\subsection{Cycling the Compiler}
\label{cycling}
The substrate also controls to a first degree the scheduling of the
individual modules of a compiler. The overall scheduling order of the
modules is chosen to be depth-first incremental, which means that the
individual units of source code will be cycled through the sequence of
modules as far down as possible from the front-end to the back-end before
another unit of source code is pushed into the front end. But this
depth-first scheduling strategy must obey the operating levels of
individual modules, which gives it enough flexibility to simulate any
combination of depth-first and breadth-first schedule. 

\subsubsection{Declarations}

\lispdoc current-module-name [Function]
Returns the name of the currently executing module. 

\subsubsection{A Complete Example}

To make things clearer, we will walk through an example compiler as defined
below. 

\begin{verbatim}
(defcompiler-family family1
  (:representation rep1 def program))

(defcompiler-module def-parser family1
  (:output rep1 def)
  (:levels-marked program)
  (:before-function print-before-compile)
  (:after-function print-after-compile)
  (:function parse-def))

(defvar *asdf* 0)
(defun print-before-compile () (format t "~&Printing before compile"))
(defun print-after-compile () (format t "~&Printing after compile"))

(defun parse-def ()
  (let ((data (incf *asdf*)))
    (when (zerop (mod data 5))
      (mark-level 'program :after))
    (format t "~&Parsing def ~a" data)
    data))

(defcompiler-module program-xform family1
  (:input rep1 program)
  (:output rep1 program)
  (:function xform-program))

(defun xform-program (program)
  (format t "~&Xforming program ~a" program)
  program)

(defcompiler-module def-analyser family1
    (:input rep1 def)
    (:output rep1 def)
    (:before-function program print-before-program)
    (:after-function program print-after-program)
    (:function analyse-def))

(defun print-before-program ()
  (format t "~&Print before program in ~a" (current-module-name)))
(defun print-after-program ()
  (format t "~&Print after program in ~a" (current-module-name)))

(defun analyse-def (def)
  (format t "~&Analysing def ~a" def)
  def)

(defcompiler-module def-printer family1
  (:input rep1 def)
  (:function print-def)
  (:before-function program print-before-program)
  (:after-function program print-after-program))

(defun print-def (def)
  (format t "~&Printing def ~a" def))

(defcompiler compiler1 family1 ()
    def-parser
    program-xform
    def-analyser
    def-printer)
\end{verbatim}

\begin{fig}{comp-struct}{Structure of the Compiler {\tt compiler1}.}
\illustration{csg261-8}
\end{fig}

The internal structure of the compiler {\tt compiler1} is pictorially
depicted in figure~\ref{comp-struct}. It consists of four modules whose
operating levels are as defined. Module {\tt def-parser} is a generator
generating {\tt def}s (which are actually simply integers!). Note that
since {\tt def-parser} operates at a lower level than the highest {\tt
program} level, it must mark the end of a {\tt program} after emitting
a certain number of {\tt def}s. We simply choose to do so after every
5 definitions emitted. 

The {\tt def}s emitted by the {\tt def-parser} module have to be
collected by the substrate to form a {\tt program} and fed to the next
module {\tt program-xform} because that operates at the {\tt program}
level.  Modules {\tt def-analyser} and {\tt def-printer} operate at
the {\tt def} level, therefore, the program emitted out from the {\tt
program-xform} module needs to be split into {\tt def}s and supplied
to them definition by definition.  Finally, the module {\tt
def-printer} is a collector operating at the {\tt def} level.  The
substrate inserts the virtual FIFO queues between the modules so that
different operating levels can be matched.

A call to run the compiler {\tt compiler1} produces the following output.

\begin{verbatim}
        > (compiler1)
        Printing before compile
        Parsing def 1
        Parsing def 2
        Parsing def 3
        Parsing def 4
        Parsing def 5
        Xforming program (1 2 3 4 5)
        Print before program in DEF-ANALYSER
        Analysing def 1
        Print before program in DEF-PRINTER
        Printing def 1
        Analysing def 2
        Printing def 2
        Analysing def 3
        Printing def 3
        Analysing def 4
        Printing def 4
        Analysing def 5
        Printing def 5
        Print after program in DEF-ANALYSER
        Print after program in DEF-PRINTER
        Printing after compile
        NIL
        > 
\end{verbatim}

We discuss the various phases below.
\begin{enumerate}
\item First, the before function of the generator module {\tt def-parser}
is executed before the entire compilation. 
\item Now the compiler enters a loop to execute modules in a depth-first
fashion. Since there is nothing to do, the generator is triggered. 
\item The generator produces a definition, but since module {\tt program-xform}
requires the complete program, this definition will just accumulate in the
input FIFO queue of module {\tt program-xform} until the complete program
is available.
\item The generator must mark the end of the program, since there is no
other way of knowing it. It will presumable do so after the end of its
input file or stream. Once the last definition has been generated and the end
of the program has been marked,  the
substrate has enough objects in the queue to invoke the module {\tt program-xform} on
the complete program. Note that, when a module operates at a
higher level than its previous modules, it is not scheduled until all the
objects comprising its operating level have been accumulated. This effectively
amounts to a breadth-first scheduling of that module.
\item When module {\tt program-xform} is done, it places the complete program on
its output queue. At this point, a program level  before-function for
module {\tt def-analyser} will be executed. The substrate now attempts to push the
objects in the queue as far down into the compiler as possible. As soon as
the first definition crosses the module {\tt def-analyser}, it can be
passed to the module {\tt def-printer}, since that operates on the def level as well. Of course,
before the module {\tt def-printer} starts processing the first definition
its program level before-function will be executed.
\item Definitions residing at the output queue of the module {\tt program-xform} will
be pushed through modules {\tt def-analyser} and {\tt def-printer} one by one
until all of them are done. 
\item Note that the after functions of the modules are executed when the
appropriate level boundary passes through the module\footnote{There is a
slight difference between the scheduling of the after function and the
corresponding before functions with respect to the scheduling of the
intervening modules, as it may be evident from the given
example. Whether this is a bug or a feature, it is not clear.}. 
\item Finally, the after function of the generator is executed after the
whole compilation. 
\end{enumerate}


