%To discuss:
% Pragmas - how to define pragmas, etc...
% Exsyms - describe the general idea behind exsyms, etc...



\chapter{General Structure of the Compiler}

\section{Introduction and Motivation}

At first glance, the Id compiler seems to be an impenetrable piece of
software.  The fledgling compiler hacker can be easily intimidated by
the number of modules and by the sheer size of the program's source
code.  Nevertheless, the Id compiler was conceived as an experimental
tool, and consequently, one of its design goals was to make it easy to
modify and to adapt. In order to enjoy the benefits of this design
goal, it is important to understand the high level organization of the
compiler, as well as its high level structuring facilities.  This
chapter provides a top-down description\footnote{This chapter should
be regarded as a tutorial in its scope and depth. While it introduces
many new concepts, it does not attempt to provide a definitive
treatment of these. Alternative references are provided for readers
interested in more detail.} of the structure of the Id compiler, and
it will introduce several of the important software engineering
concepts that make the compiler a flexible tool.

At this point, it is important to make one clarification. Although we have
been referring to {\em the\/} Id compiler, there are actually many Id
compilers!  Some Id compilers compile Id source files to TTDA object files
while other Id compilers compile regions of Id code in editor buffers to
Monsoon object files.  The reason why there are many Id compilers is that
Id compilers are built on top of the Dataflow Compiler Substrate (DFCS)
\cite{DFCS}. DFCS is a collection of data structures and abstractions that
provide the general functionality for writing compilers for a dataflow
language. In the framework provided by DFCS, a compiler is composed of a
collection of {\em modules\/} and of a top-level procedure that
``supervises the passing of control from module to module''
\cite{DFCS}.\footnote{Since the top level structure of an Id compiler is
defined by using the facilities provided by DFCS, this chapter will
parallel much of the discussion found in Chapter 2 of the DFCS reference
document \cite{DFCS}.  However, this chapter takes a {\em top-down\/}
approach, while the DFCS document is organized in a {\em bottom-up\/}
fashion. In addition, this chapter will give specific examples of the use
of DFCS in the context of building or modifying an Id compiler.}

Thus, a compiler in the DFCS framework is really a very flexible software
system.  One can add modules to a compiler to implement new functionality
or one can eliminate modules that become superfluous. Instead of building
one monolithic compiler to handle different cases of input and output
formats, optimizations levels, etc\ldots, one can build many different
compilers using DFCS. More importantly, each of these compilers is separate
from others already defined. This prevents separate software development
efforts from interfering with each other.

\section{Defining a Compiler}

So let's plunge right in. This section presents the DFCS macros used to
define an Id compiler. It also presents a sample definition of a compiler
as well as examples on how to modify the definition to add functionality.
For a more detailed description of {\tt defcompiler}, refer to \cite{DFCS}.

\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]

This macro defines a compiler {\em name\/} belonging to the compiler family
{\em family\/}. The compiler is composed of the given sequence of modules
{\em modules\/}. The various optional clauses are used to build the
top-level function that invokes this particular compiler.

The {\tt :wrapper-macro} clause supplies the name of a ``wrapper''
macro for the whole compiler. A wrapper macro provides a lexical
``enclosure'' for the invocation of the compiler. The {\tt
:message-hook} clause provides the name of a function {\em
hook-name\/} that is called whenever the compiler generates a message.
This hook allows the compiler writer to customize the generation of
messages depending on the compiler. The {\tt :options} clause
specifies a set of options that can be set to alter the behavior of
the compiler on a particular invocation. Compiler options will be
discussed later. The {\tt :option-default} clause allows the default
values of options to be changed for this particular compiler. The {\tt
:lambda-list} clause permits the specification of a LISP-like lambda
list for the top-level function that invokes the compiler. If this
clause is omitted, the {\tt defcompiler} macro will generate a default
lambda list using rules discussed later.

Figure \ref{defcompiler} shows the definition\footnote{For expository
purposes, this definition has been shortened somewhat. However, it
retains the key features a typical use of {\tt defcompiler}.} of a
typical compiler.As its name implies, this particular compiler, {\tt
monsoon-id-compile-file}, compiles Id source files into Monsoon object
code.  The compiler belongs to the {\tt id-compiler} family. Notice
that only some of the optional clauses of the {\tt defcompiler} macro
are included. This compiler uses a wrapper macro and defines the
compiler option {\tt libraries}. Figure \ref{compiler-wrapper} shows
the code for the wrapper macro.

\begin{figure}
\begin{verbatim}
        (defcompiler monsoon-id-compile-file
                     id-compiler
                ((:wrapper-macro id-monsoon-compile-file-wrapper)
                 (:options libraries))
          file-parser                   ; Beginning of front end.
          pre-scope-analysis-desugaring 
          scope-analysis             
          type-checking                 ; Type inference module.
          overloading-translation       
          lambda-lift                   ; Lambda lifting module.
          generate-program-graph        ; Beginning of middle end.
          manager-synchronization       
          constant-propagation          ; Optimizations
          call-substitution             ; 
          fetch-elimination             ;
          simple-fetch-elimination      ;
          dead-code-elimination         ;
          cse-and-hoisting              ;
          circulate-structures          ;
          constant-propagation          ;
          synchronize-release           ;
          partial-evaluation            ;
          constant-propagation          ;
          dead-code-elimination         ;
          thunk-splitting               ;
          inlinable-definitions         ;
          loop-constant-propagation     ;
          code-blocks                
          signals-and-triggers       
          generate-ets-graph            ; Beginning of back end.
          peephole
          add-fanouts                
          merge-merges                
          expand-system-functions     
          merge-merges
          assign-fp-offsets          
          add-successor-constraints  
          assign-ip-offsets          
          file-assemble-monsoon-graph   ; Assemble and produce object code.
         )
\end{verbatim}
\caption{Definition of an Id compiler}
\label{defcompiler}
\end{figure}

\begin{figure}
\begin{verbatim}
      (defmacro id-monsoon-compile-file-wrapper (&body body)
        `(let* ((*current-compilation-exsym-table* (make-exsym-table))
                (*the-copyright-notice* nil)
                (start-time (get-universal-time)))
            (format t "~&The Id Monsoon Compiler, Version 1.0.~
                   ~&~A" (get 'id-compiler :copyright-notice))
            (monsoon-id-compile-file-exsym-table-prolog)
            ,@body
            (monsoon-id-compile-file-exsym-table-epilog)
            (format t "~&~%Compiled ~d procedure~P,~
                        ~%  in ~d seconds"
                (- (get-universal-time) start-time) )))
\end{verbatim}
\caption{Compiler Wrapper Macro}
\label{compiler-wrapper}
\end{figure}

A list of module names follows the list of clauses in the definition of this Id
compiler. The name of a module usually reveals its function. For example, the
first module of this compiler is the {\tt file-parser} module. The purpose of
this module, as we'll see later on, is to read an Id source code file and to
produce a parse tree from it. The module following the parser, the {\tt
pre-scope-analysis-desugaring} module, receives a parse tree as input an
replaces parts of the parse tree with semantically equivalent constructs.
Notice that the type of the output of one module must match the type of the
input of the following module. The {\tt defcompiler} macro makes sure that the
different representation of the Id program used by different modules match, as
control is passed from module to module.

That's all there is to defining the top-level structure of an Id
compiler. With the proper collection of modules, any particular type
of dataflow compiler, whether for Id for some other language, can be
implemented. The following section describes how modules are defined
and implemented.

\section{Defining a Module}

As we saw in the previous section, an Id compiler is composed of a
sequence of modules. While the {\tt defcompiler} macro takes care of
connecting modules and building the top-level Lisp function that
invokes the compiler, it is the compiler modules that actually do the
work. According to the DFCS reference document, a compiler module
``packages up a particular phase of compilation.'' In Figure
\ref{defcompiler}, we saw that there was a single parser module, some graph
generation modules, several optimization modules, and finally a single
assembler module.  Each of these is a separate phase of the
compilation of an Id program, and each is implemented by a distinct
module.  In order to define a module, we must use one more DFCS
facility: the {\tt defcompiler-module} macro.

\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]

The {\tt defcompiler-module} macro really defines the external
interface of a module to the rest of the compiler. The {\tt :input}
clause informally describes the ``type'' of input data structure which
the module expects. The type of this data structure is described by a
{\em representation\/} and a {\em level\/}; these two concepts will be
addressed later. Similarly, the {\tt :output} clause describes the
type of the output data structure of the module. In order to maintain
the correct composability of modules, the types of the {\tt :input}
and {\tt :output} data structures must be ``equivalent'' in a manner
described below. The {\tt defcompiler} macro checks this property and
signals an error if the equivalence is not maintained.

The {\tt :function} clause names the top-level Lisp function that
implements the module. The {\tt :before-function} and {\tt
:after-function} clauses provide hooks to setup and cleanup functions
which are called before and after the invocation of the module.

The {\tt :levels-marked} clause provides some rather subtle
functionality which is beyond the scope of this document. Interested
readers are referred to \cite{DFCS}.

The {\tt :options} clause specifies the compiler options used by this
module. These options should have been defined using the {\tt
defcompiler-option} macro, which will be described in Section
\ref{section-defcompiler-option}. Finally, the {\tt :wrapper-macro} clause names the
macro {\em macro-name\/} as the wrapper for this module.

\subsection{Families, Representations, and Levels}

Modules generate, transform, and pass on data structures. In order to
be able to describe the interface of a module, we must be able to name
these data structures. A {\em representation\/} is exactly that: a
name for a data structure. Informally, a representation can be viewed
as the type of a data structure. For example, the compiler uses two
representations of programs as graphs during compilation: these are program
graphs and machine graphs.  Although these are different abstractions,
they both happen to be implemented using the dataflow-graph data
structure provided by DFCS.

However, as we mentioned in the previous section, the input and output
interfaces of a module are described by a representation and a {\em
level\/}. Often, the complete representation of a program may be too
unwieldy for a particular module to process. For example, a module
performing an optimization on loops does not need to know the
structure of the whole program. Therefore, it becomes important to
describe the program in a hierarchical manner. A level is exactly
this: a name for a level in the hierarchical representation of a
program. For example, an Id program is described using the following
levels: a program is composed of definitions, each of which is
composed of some procedures. Finally, each procedure is implemented by
one or more code-blocks. Figure \ref{levels} shows an Id program and
its hierarchical representation.

\begin{figure}
\illustration{top-level-prog-hierarchy}
\caption{Hierarchical Representation of a Program}
\label{levels}
\end{figure}

A representation must also describe the levels that it supports. For
example, a {\tt parse-tree} supports the {\tt program}, the {\tt def},
and the {\tt procedure} levels. Similarly, the {\tt program-graph}
representation supports these three levels plus the {\tt code-block}
level. Since we have different data structures supporting the same
levels, it becomes important to describe how they correspond to each
other. We use the {\tt defcompiler-family} macro to describe these
relationships.

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

The {\tt :representation} clauses declare the different program
representations used in this compiler family. The format for these
clauses includes the name of the representation followed by the names
of the levels it supports, from smallest to largest. The {\tt
:equivalence} clauses establish equivalence classes among different
representations.  These equivalence classes, known as {\em units\/},
are used by the {\tt defcompiler} macro when checking the connectivity
of modules: the condition that must be met is that the output of one
module must be in the same unit as the input of the next module.

Figure \ref{defcompiler-family} shows the definition of the Id
compiler family. Notice that the definition describes three
representations for Id programs: the {\tt parse-tree} representation,
the {\tt program-graph} representation, and the {\tt machine-graph}
representation. Different parts of the compiler use the different
representations of the program to facilitate their work. Moreover, the
definition of the Id compiler family also describes four units, one
for programs, one for definitions, one for procedures, and one for
codeblocks.

\begin{figure}
\begin{verbatim}
(defcompiler-family id-compiler
  (:representation parse-tree procedure def program)
  (:representation program-graph code-block procedure def program)
  (:representation machine-graph code-block procedure def program)
  (:equivalence (parse-tree program)
                (program-graph program)
                (machine-graph program))
  (:equivalence (parse-tree def)
                (program-graph def)
                (machine-graph def))
  (:equivalence (parse-tree procedure)
                (program-graph procedure)
                (machine-graph procedure))
  (:equivalence (program-graph code-block)
                (machine-graph code-block)))
\end{verbatim}
\caption{Id Compiler Family Definition}
\label{defcompiler-family}
\end{figure}

The real purpose of compiler families, however, is to implement the
mechanism of sharing.  Modularity without sharing amounts to
reinventing the wheel for every new software project. The association
of data structures, modules, and options with a compiler family allows
the sharing of these resources among the different compilers of the
family. For example, an Id compiler that compiles Id source files
shares most of its internal data structures and modules with an Id
compiler that compiles source code from Id editor buffers. Without the
sharing facilities provided by compiler families, each of these two
compilers would have to replicate substantial amounts of code.

Currently, the Id compiler family is the only compiler family defined
at MIT. However, other users of DFCS have defined compiler families
for languages such as Fortran.

\subsection{Cycling the Compiler}

The discussion of representations and levels naturally leads one to
ask the question: how does the compiler control the level at which a
particular module receives its input? After all, the user {\em
declares\/} that a module will operate at a certain level, yet apart
from equality between levels---as defined by the {\tt defcompiler}
macro---the user makes no explicit conversion between levels and
representations. The answer to this question is known as {\em
cycling\/}.

As we have seen, the definition of the Id compiler family includes a
description of the hierarchical representation of programs. If we
think of a representation at a certain level as a set whose elements
are representations at a lower levels, then we can see that the
compiler can automatically insert code to convert between different
levels.  This cycling code would consist of code to mapping over the
elements of the set. For example, the {\tt lambda-lift} module
produces the {\tt parse-tree} representation at the {\tt def} level
while the module the follows it, {\tt generate-program-graph}, expects
its {\tt parse-tree} input at the {\tt procedure} level. In this case,
the compiler would cycle the {\tt generate-program-graph} module over
each of the procedures contained in each of the definitions produced
by the {\tt lambda-lift} module. 

The opposite case arises when the module that occurs earlier in the
compilation process produces a data structure that is at a lower level
than that required by the following module. In this case, the compiler
needs to {\em collect\/} the output of the earlier module into a data
structure at the higher level so that it can be passed on the later
module.

Readers interested in more details should consult the DFCS reference
document \cite{DFCS}.

\subsection{Some Compiler Modules}

A module can be classified as a member of one of four different
classes of modules, according to inputs and outputs. The first type of
module is the {\bf generator} module. This module does not include an
{\tt :input} clause in its definition, and it is the first module of
the compiler. There is only one generator module in a compiler. Figure
\ref{generator-module} shows the definition of a file parser module for a
file-based Id compiler.

\begin{figure}
\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))
\end{verbatim}
\caption{A Generator Module}
\label{generator-module}
\end{figure}

The second class of modules is the {\bf standard} module class. This
type of module receives its input at a certain representation and
level and produces its output in the same representation and level.
Modules that implement optimizations epitomize this class of modules
since they typically perform some local analysis and perform small
changes to their input. Figure \ref{standard-module} shows the
definition of a module that performs the call-substitution
optimization on {\tt program-graphs} at the {\tt code-block} level.

\begin{figure}
\begin{verbatim}
(defcompiler-module call-substitution id-compiler
  (:input program-graph code-block)
  (:output program-graph code-block)
  (:options call-substitution)
  (:function cs-code-block))
\end{verbatim}
\caption{A Standard Module}
\label{standard-module}
\end{figure}

The third class of modules is the {\bf translator} module class.
Translator modules take input at one representation and level and
produce output in another representation, but at the same
level.\footnote{Remember that conversions between levels are done
automatically by the compiler. Therefore a module cannot change the
vary the level of its input and output representations.} These modules
mark the places where different parts of the compiler begin. For
example, the parse-tree representation is used in the front-end of the
compiler, program graphs are used in the middle-end, and machine
graphs are used in the back end. The modules that appear on the
boundaries of the conceptual ``ends'' of the compiler are translator
modules.

\begin{figure}
\begin{verbatim}
(defcompiler-module generate-machine-graph id-compiler
  (:input program-graph code-block)
  (:output machine-graph code-block)
  (:function gmg-dataflow-graph))
\end{verbatim}
\caption{A Translator Module}
\label{translator-module}
\end{figure}

Figure \ref{collector-module} contains a {\bf collector} module. A
collector module simply receives input. It produces no output apart
that will pass to the rest of the compiler. A collector module is
typically the last module of a compiler and produces a file or a
stream of object code.

\begin{figure}
\begin{verbatim}
(defcompiler-module assemble-monsoon-graph id-compiler
  (:input machine-graph code-block)
  (:wrapper-macro monsoon-assembler-wrapper)
  (:function assemble-monsoon-graph))
\end{verbatim}
\caption{A Collector Module}
\label{collector-module}
\end{figure}

\subsection{Example: Adding a New Module}
 
Let's say we want to instrument our compiler so that it displays the
intermediate representation of the program in a graphics window. A
module such as this is useful when debugging the output of an
optimization module, for example. 

Due to the modular nature of the compiler, a module such as this is
simple to add.  Let's assume the task of our module is to display
program graphs (rather than machine graphs) since most of the
optimizations of the compiler at done with this program
representation. Assume that the top-level function of our graph
display module is called {\tt display-program-graph}. Also, assume
that we want to display graphs at the {\tt code-block} level so that
the graphs do not become too large. Figure \ref{new-module} shows a
possible definition for this new compiler module.

\begin{figure}
\begin{verbatim}
(defcompiler-module display-graph id-compiler
   (:input program-graph code-block)
   (:output program-graph code-block)
   (:function display-program-graph)
   (:options reverse-video)
   (:wrapper-macro display-graph-wrapper))
\end{verbatim}
\caption{Definition of a New Module}
\label{new-module}
\end{figure}

Notice that we specify the inputs and outputs to be the same
representation and level. After all, this module simply displays
graphs and does not modify them. Next, the {\tt :function} clause
specifies the name of the top-level function that implements this
module, {\tt display-program-graph}. The {\tt :options} clause
declares that this module makes use of the {\tt reverse-video} option
(which should have been defined already). Finally, the {\tt
:wrapper-macro} clause contains the name of the wrapper macro for this
module.

Figure \ref{new-module-wrapper} shows a possible wrapper macro for
this module. If the compiler is operating under the X Window System,
for example, this wrapper macro takes care of opening a display
connection and a top-level window.

\begin{figure}
\begin{verbatim}
(defmacro display-graph-wrapper (&body body)
   `(let* ((*display* (OPEN-DISPLAY ``vinod:0''))
	   (*screen* (first (DISPLAY-ROOTS *display*)))
	   (*gcontext* (CREATE-GCONTEXT :drawable (SCREEN-ROOT *screen*)
			                :foreground (SCREEN-BLACK-PIXEL *screen*)
				        :background (SCREEN-WHITE-PIXEL *screen*)
				        :font font))
           (*top-level-window* (CREATE-WINDOW :parent (SCREEN-ROOT *screen*)
					      :class :input-output
					      :x 0
					      :y 0
					      :width 500
					      :height 500
					      :border-width 5
					      :background (SCREEN-WHITE-PIXEL *screen*)
					  )))
	,@body))
\end{verbatim}
\caption{Wrapper for New Module}
\label{new-module-wrapper}
\end{figure}

\section{Compiler Options}
\label{section-defcompiler-option}
Options are additional compiler resources---shared by all compilers of
a given family---that modules may use during their computations.
Typically, options augment the environment in which a module operates.
The {\tt defcompiler-option} macro is used to define compiler options.

\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}

This macro adds the option {\em name} to the compiler family {\em
family}. The {\tt :type} of the option must be one of the types
defined by {\tt *option-types*}. These types are typically {\tt
:symbol}, {\tt :string}, {\tt :number}, {\tt :integer}, {\tt :date},
{\tt :pathname}, {\tt :boolean}, {\tt :enumeration}, and {\tt
:stream}. The {\tt :how-defined} clause specifies how the option is
going to be defined when the lambda-list of the top-level function to
invoke the compiler is constructed. The two possible values are {\tt
:keyword} or {\tt :positional}. If the option is specified to be a
{\tt :keyword} option, then it must also have a {\tt :default} value
{\em default}. The {\tt :documentation} clause specifies a string to
describe the option. Finally, the {\tt :importance} clause specifies a
number between 0.0 and 1.0 that is used to sort the options when the
lambda-list of the top-level function is constructed.

In the previous section, for example, we declared that the {\tt
display-graph} compiler module used the {\tt reverse-video} option. A
possible definition for this option is shown in Figure
\ref{defcompiler-option}. 

In order to access the value of a compiler option within a module, we
use the {\tt option} macro. In order to determine whether or not an
option is valid for the current compiler, we use the {\tt
option-exists-p} macro.
\begin{lispdocs}
\lispdoc option option-name [Macro]

\lispdoc option-exists-p option-name [Macro]
\end{lispdocs}

\begin{figure}
\begin{verbatim}
(defcompiler-option reverse-video id-compiler
   (:type boolean)
   (:how-defined :positional)
   (:default nil)
   (:documentation ``This options defines whether or not graphics are
                     displayed in reverse video'')
   (:importance 0.3))
\end{verbatim}
\caption{Definition of the {\tt reverse-video} Option}
\label{defcompiler-option}
\end{figure}

\section{Target Options}

Target options are used to set the value of variables that depend on
the target architecture for which the compiler is compiling. These
options do not use the {\tt defcompiler-option} machinery defined by
DFCS and described in the previous section. In particular, target
options are not associated with a particular compiler family. Rather,
they are defined and set with the following forms:

\begin{lispdocs}
\lispdoc define-target-option name variable
	\body{alist} 
[Macro]

\lispdoc set-target target [Function]
\end{lispdocs}

The {\tt define-target-option} macro defines the target-option {\em name}
and the variable {\em variable} to hold the value of this target option.
The body of the macro, {\em alist}, is an association list of targets and
values. Figure \ref{target-option} shows an example definition of a target
option.

\begin{figure}
\begin{verbatim}
(define-target-option Id-Compiler-Float-Format *Float-format*
   (:ttda 'single-float)
   (:monsoon 'double-float))
\end{verbatim}
\caption{Definition of a Target Option}
\label{target-option}
\end{figure}

The {\tt set-target} function sets all the options defined for a
particular target to their appropriate values. In the example above,
{\tt (set-target :monsoon)} would set the value of {\tt
*Float-format*} to {\tt 'double-float}. The target options mechanism
is really a tool that allows the compiler writer, specially those
working on the back-end of the compiler, to write code that depends on
the details of the target architecture in a reasonably portable manner.

\section{Pragmas}
While the Id compiler performs extensive optimizations on programs,
there are certain situations which it cannot detect; control over
these optimizations is left to the Id programmer. Currently, the
compiler allows the Id programmer to control the way in which certain
loops are compiled, in order to reduce overhead, and to ``insert
suggestions\ldots to the compiler to generate code that releases or
reuses data structure storage''\cite{Nikhil90}. The compiler provides
a mechanism to define and implement these pragmatic annotations of
programs (known as pragmas) in a straightforward way. 
\begin{lispdocs}
\lispdoc define-definition-pragma keywords arglist properties
	\body{body}
[Macro]

\lispdoc define-block-pragma keywords arglist properties
	\body{body}
[Macro]

\lispdoc define-toplevel-pragma keywords arglist properties
	\body{body}
[Macro]
\end{lispdocs}
There are three different kinds of pragmas supported by the Id
compiler: definition pragmas, block pragmas, and toplevel pragmas.
Definition pragmas apply only to the definition of the function, and
they occur between the formal parameters and the "=" of a definition.
Several definition pragmas can appear together; they are simply
enclosed in braces. For example, the {\tt @inlineonly} pragma is a
definition pragma. Figure \ref{defpragma} contains the definition of
this pragma, whose purpose is to allow the Id programmer to declare
that the Id procedure being defined should always be inlined in its
callers' code.

\begin{figure}
\begin{verbatim}
(define-definition-pragma :inlineonly (name pragma dataflow-graph place) ()
  (declare (ignore name pragma place))
  (exsym-put *current-procedure-name* :inline-only t *current-compilation-exsym-table*)
  (setf (dataflow-graph-get dataflow-graph :inline-only) 't)
  (setf (dataflow-graph-get dataflow-graph :inlinablep) 't))
\end{verbatim}
\caption{A Definition Pragma}
\label{defpragma}
\end{figure}

Block pragmas are found in bindings lists. They apply to the region of
the program within the braces that enclose the pragma's binding list.
A pragma in a loop binding list, for example, applies to the predicate
of the loop and to the FINALLY expression of the loop. The {\tt
@release} is a block pragma which allows the programmer to specify that the
storage for a data structure should be released (reused) upon
termination of the current control region.\footnote{A control region
is simply a region of the program, such as a procedure body, loop iteration,
or conditional expression, for which the compiler detects
termination.} Figure \ref{blockpragma} illustrates the definition of
{\tt @release}.

\begin{figure}
\begin{verbatim}
(define-block-pragma :release process-release-pragma (:expression-variables-free T))
\end{verbatim}
\caption{A Block Pragma}
\label{blockpragma}
\end{figure}

The final type of pragma is the toplevel pragma. These pragmas affect
the global behavior of the compiler; they are not associated with a
particular definition or binding list. The{\tt @include} pragma is an
example of a toplevel pragma. {\tt @include} tells the compiler to
include the exsym information (see Section \ref{exsym}) for a
particular file during the current compilation. The inclusion of exsym
information allows certain optimizations to be performed since the
compiler has more information available. Figure \ref{toplevelpragma}
shows the defintion of {\tt @include}.

\begin{figure}
\begin{verbatim}
(define-toplevel-pragma :include (name expression place) 
                        (:processing-module pre-scope-analysis-desugaring)
  (declare (ignore name))
  (if (null expression)
      (message :warning place
	       "INCLUDE pragma requires a string expression.")
      (grammarcase expression
	(:string
	  (let ((file (parse-library-filename (unslashify (ptnode-value expression)))))
	    (let ((exsym-table (file-exsym-table file t)))
	      (when exsym-table
		(pushnew exsym-table (cdr *exsym-search-path*))))))
	(otherwise
	  (message :warning place
		   "INCLUDE pragma requires a string expression."))))
  nil)
\end{verbatim}
\caption{A Toplevel Pragma}
\label{toplevelpragma}
\end{figure}

The development of new pragmas requires a deep understanding of the
compiler; the reader should not be alarmed if the topic seems
confusing at first.

\section{Exsyms}
\label{exsym}
The Id compiler supports separate compilation of functions. In order
to be able to support this feature, the compiler must maintain a
database of information about top-level symbols. Each entry in this
database is known as an {\em exsym}\footnote{The term exsym comes from
EXternal SYMbol.}\footnote{The material in this section is also
covered in Chapter 5 of \cite{DFCS}.}

\subsection{Exsym Properties}
Exsym entries store information about top-level symbols in {\em
properties}.  An exsym for a top-level function, for example, contains
information such as the type signature of the function, the arity of
the function, and whether or not the function is ``inlinable''.  In
order to access a property from an exsym entry, the following
functions are used.

\begin{lispdocs}
\lispdoc exsym-get symbol indicator search-path [Function]

\lispdoc exsym-put symbol indicator value exsym-table [Function]
\end{lispdocs}

The {\tt exsym-get} function retrieves the property {\em indicator\/}
from the exsym entry for {\em symbol\/}. It searches for the exsym
entry in the set of exsym tables indicated by {\em search-path\/}.
For example, if one wanted to find the arity of the function {\tt foo}, one
would use the following form:
\begin{verbatim}
            (exsym-get :foo :arity *exsym-search-path*)
\end{verbatim}
The {\tt exsym-put} function inserts a property value in an exsym
entry. For example, if the compiler was processing a function of
two arguments named {\tt bar}, it would eventually use the following
form to insert the arity of {\tt bar} into the exsym database.
\begin{verbatim}
            (exsym-put :bar :arity 2 *exsym-search-path*)
\end{verbatim}

Exsym properties are defined using {\tt define-exsym-property}.

\lispdoc define-exsym-property indicator \clauses 
        \list{{\tt :consistency-predicate} pred}
        \optgroup{\list{{\tt :consistency-encoder} encoder}}
        \optgroup{\list{{\tt :consistency-printer} printer}}
        [Macro]

This macro defines the property {\em indicator}. This property can be
placed in exsym entries using {\tt exsym-put}. The {\tt
:consistency-predicate} clause is necessary. It specifies the name of
a predicate that checks the consistency of this property. The next
section introduces the concept of consistency checking, which uses
these predicates. The last two clauses, {\tt :consistency-encoder} and
{\tt :consistency-printer} are optional. 

The following functions manipulate individual exsyms.
\begin{lispdocs}
\lispdoc install-exsym exsym exsym-table [Function]

\lispdoc find-exsym symbol search-path [Function]

\lispdoc exsym-exists-p symbol exsym-table-or-search-path [Function]

\lispdoc exsym-clear symbol search-path [Function]

\lispdoc copy-exsym exsym [Function]
\end{lispdocs}
The function {\tt install-exsym} stores {\em exsym\/} into {\em
exsym-table\/} under the name {\tt (exsym-name {\em exsym})}. {\tt
Find-exsym} finds the exsym for {\em symbol\/} in {\em search-path\/}.
An exsym search path is simply a list of exsym tables.  {\tt
Exsym-exists-p} is a predicate which returns {\tt t} if an exsym for
{\em symbol\/} exists in {\em exsym-table-or-search-path}. Finally,
{\tt copy-exsym} returns a copy of {\em exsym}.

The following functions manipulate collections of exsyms (exsym tables).
\begin{lispdocs}
\lispdoc make-exsym-table [Function]

\lispdoc map-exsym-table function exsym-table [Function]
\end{lispdocs}
{\tt Make-exsym-table} constructs a new, empty exsym table. Exsym
tables essentially implement a mapping from keyword symbols
(representing top-level Id identifiers) to exsym structures. {\tt
Map-exsym-table} applies {\em function\/} to each entry in {\em
exsym-table}. The function is called for its side-effects, and it is
passed the {\em name} of the exsym and the {\em exsym\/} structure
itself as arguments.

\subsection{Assumptions}
Exsym tables store not only properties about identifiers but also {\em
assumptions\/} about properties. Any time the compiler uses an exsym
property of one identifier to compile code for another identifier, it
records an assumption in the ``assumer's'' exsym. For example, if in
the course of compiling function {\tt foo}, the compiler encounters a
reference to function {\tt bar}, it looks up the {\tt :arity}
property in {\tt bar}'s exsym in order to determine whether or not to
compile a general application or a direct
application.\footnote{General applications involve building a closure;
they are used when the arity of a function is unknown or when the
function application is a partial one. Direct applications are
compiled when the arity of a function is known and satisfied. Direct
applications are more efficient than general applications since they
do not build closures!} The compiler records an assumption in {\tt
foo}'s exsym about {\tt bar}'s arity. This record of assumptions is
then used by the consistency checking functions to determine whether
or not the functions that were compiled separately were compiled with
a consistent set of assumptions about each other.

The following functions implement the assumption and consistency
checking mechanisms of exsyms.
\begin{lispdocs}
\lispdoc exsym-assume assumer assumer-table assumee assumee-indicator
assumee-search-path [Function]

\lispdoc exsym-assume-value assumer assumer-table assumee assumee-indicator
assumee-search-path assumee-value [Function]

\lispdoc consistency-summary root-exsym-names search-path [Function]

\lispdoc describe-consistency root-exsym-names search-path [Function]
\end{lispdocs}
The {\tt exsym-assume} and {\tt exsym-assume-value} functions are used
to record assumptions into exsyms. Following the example above, the 
form below would record an assumption about {\tt bar}'s arity in
{\tt foo}'s exsym.
\begin{verbatim}
       (exsym-assume :foo exsym-table-1 :bar :arity *exsym-search-path*)
\end{verbatim}
Notice that an exsym for the assumee must exist; otherwise,
the value of the property (the arity, in this example) could not be
determined. The difference between {\tt exsym-assume} and {\tt
exsym-assume-value} is that the latter allows for the assumed value to
be provided directly. This obviates the need for the assumee to have
an exsym.

The consistency checking functions determine whether the assumptions
recorded in the exsym table are consistent with each other. As an
example of an inconsistency, suppose that {\tt bar} gets recompiled,
after {\tt foo} has been compiled, so that it takes one more argument
than it did before. If a direct application of {\tt bar} was compiled
into {\tt foo}, due to the value of {\tt bar}'s {\tt :arity} property
at the time {\tt foo} was compiled, the resulting state of the
compiled code in the machine would be incorrect! If foo were to be
executed, the new version of {\tt bar} would not receive enough
arguments! When called with the appropriate ``root'' set of exsyms,
the {\tt consistency-summary} function would detect this problem and
would report it. The {\tt consistency-summary} applies the consistency
predicate, specified when the exsym property was defined, to the
assumed value stored in the assumer's exsym and to the actual value,
stored in the assumee's exsym. If these values fail to pass the
consistency predicate's test, {\tt consistency-summary} records them
and returns them as part of its result.

The {\tt describe-consistency} function prints a detailed description
of the inconsistencies found by {\em consistency-summary}, using the
consistency printers defined with each exsym property.

Typically, execution managers call {\tt consistency-summary} before
executing functions to ensure that no error will occur due to separate
compilation problems. 

\section{User Features}
The following sections discuss features of the compiler that are more
``user oriented'' than ``compiler-writer oriented''. They are included
here because they should form part of the reader's mental model for
the Id compiler.

\subsection{Incremental Compilation}
\label{sep_compilation}
Traditional compilers operate in a batch-oriented manner: the user
``submits'' a program to the compiler, the compiler attempts to
compile the program, and finally, the compiler produces object code,
assuming there were no syntax or type errors in the source program.
While the Id Compiler can operate in this way, it can also operate
{\em interactively\/} and {\em incrementally}. Incremental compilation
allows the user to compile a program in small pieces until a complete
program is compiled. In the case where a particular function needs to
be recompiled, the user need only recompile {\em that\/} function. The
work done to compile all the other functions in the program does not
need to be repeated uselessly. 

When compiling incrementally, the Id compiler may take its input from
an editor buffer, for example. By selecting a region of text, the user
may request that a particular function be compiled, that a set of
functions be compiled, or that the whole buffer be compiled. In any
case, localized changes to the source program require only localized
recompilation of functions.

As a consequence of its ability to support incremental compilation,
the Id compiler also supports {\em separate compilation}.  As
mentioned previously, separate compilation allows groups of functions
that refer to each other to be placed into separate files at compile
time. This allows for a more modular programming style and provides
the ability to build useful libraries of functions. References from
functions in one file to functions in another file are resolved when
the object code for the functions is loaded into the machine.

\subsection{Librarian}
The previous sections discussed the ability of the Id compiler to
support separate compilation and mentioned that references to
functions and other top-level identifiers must be resolved at load
time. The compiler generates information about these symbols in {\tt
.etb}\footnote{The suffix {\tt .etb} stands for Exsym Table (Binary)
format.} files. The purpose of the librarian is to manage the exsym
table information stored in {\tt .etb} files. As Id files as compiled,
the librarian keeps a cache of the exsym information produced by
previous compilations so that subsequent invocations of the compiler
can use this information.

\section{Summary}
This chapter has attempted to present a high level overview of the Id
compiler by introducing a broad spectrum of topics and by keeping the
discussions of each of these topics short and concise.  These quick
glimpses into the structure of the compiler should provide the reader
with some intuition behind its underlying ideas.  Later chapters will
develop the topics touched in this chapter and will provide more
precise detail.
