  % -*- Mode:TeX -*-

\chapter{Introduction}
\label{IntroductionChapter}

\begin{center}
\bf WARNING:  This document is subject to change.
\end{center}

This document describes the data structures and abstractions that underlie
the ID Compiler, Version 2 \cite{Traub86}, a compiler from the programming
language ID to machine code for the MIT Tagged-Token Dataflow Architecture.
The most important attribute of Version 2 is flexibility, as it must be
adaptable to changes in the language, changes in compilation strategies,
and changes in the target machine architecture.  Furthermore, it must be
capable of being used in a tinker-toy fashion: the parser output may feed a
back end for a non-dataflow implementation, the intermediate graphs may be
processed by a user application and then fed back into the compiler for
machine code generation, and so forth.

This need for flexibility has led to a design that is as independent from the
language and the dataflow machine as possible, so that the substrate will be
immune to all but the most radical changes to these.  Beyond this adaptability
to the changing needs of the TTDA project, this independence results in the
additional benefit that the compiler substrate can be used not only for an ID
to TTDA compiler, but also for a VIMVAL to static dataflow architecture
compiler, a SISAL to Manchester architecture compiler, \etc.  It is even
conceivable that given an ID to TTDA compiler and a VIMVAL to static dataflow
architecture compiler, both built upon the abstractions described herein, it
would be possible to construct ID to static and VIMVAL to TTDA compilers with a
relatively small amount of additional code.

\section{Overview}

\begin{fig}{BlockDiagramFigure}{Block diagram of a Dataflow Compiler}
\illustration{csg261-1}
\end{fig}

The substrate described here is designed for compilers whose overall structure
is as shown in Figure \ref{BlockDiagramFigure}.  The compiler is a collection of
modules, each of which operates on an intermediate representation of the
program being compiled.  The intermediate representations, which are fully
described here, serve as the only channel of communication between the modules.
A simple top-level procedure supervises the passing of control from module to
module.

\begin{aside}
{\bf Design Note:}  At this point, it is not clear whether the entire source code
will move from one module to the next or whether smaller units, such as
procedure definitions, will successively move through the compiler.  While no
stand is being taken at present, certain conventions may be introduced in the
future.
\end{aside}

Referring to the figure, in the first phase of compilation the source code is
parsed, resulting in a parse tree.\index{parse tree} Initially, the parse tree
is just a hierarchical representation of the source code, with no other
information or annotations beyond some indications of where in the input file
(line number, character position, {\it etc}.) each construct appeared.  The parse
tree then undergoes a series of transformations, each of which may alter the
original parse tree in several ways.  A module may add, delete, or replace
nodes of the tree, the effect being equivalent to a source-to-source
transformation.  A prime example of this kind of parse tree modification is
``desugaring'', in which a program construct is replaced by a semantically
equivalent construct.  A module may also {\it annotate\/} the parse tree by adding
information to nodes of the tree.\index{annotation} These annotations do not
affect the structure of the program, but may affect how later phases interpret
constructs found in the tree.  An annotation might be employed by a type
checking module, for example, to indicate that a construct results in a
particular type of data.  Finally, a module may introduce new nodes into the
parse tree which could not have been produced by the parser.  This might be
done, for example, to replace an overloaded construct by one of two
non-overloaded constructs which later phases can deal with separately.

While any kind of parser may be used to produce the parse tree, it is
expected that the parser used for Id will be a Deterministic Finite
Automaton (DFA) lexical analyzer\index{lexical analyzer} followed by a Look
Ahead Left-to-Right (LALR) parser\index{LALR parser}, with a stream of
lexical tokens\index{lexical token} connecting the two.  As this model is
applicable to a wide variety of languages, an abstraction for lexical
tokens is described here.  If some other type of parser is used, the
lexical token stream may be absent entirely.

When all transformations to the parse tree have been completed, the program is
converted into a dataflow graph.\index{dataflow graph} The initial form that
this dataflow graph takes is called the {\it program graph}\index{program graph},
because the level of detail present in this graph is roughly the same as that
found in the source program.  For example, a procedure application might appear
as a single {\sc apply} instruction in the program graph, even though this may
later be expanded into a whole collection of dataflow instructions depending on
the implementation of procedure linkage.\footnote{In the past, the program graph
has also been referred to as the ``abstract graph''.}  Following the initial
transformation to program graph there may be several modules which transform
the program graph, such as optimizers, {\it etc}.  At some point, the a
transformation takes place which replaces large, machine-independent
instructions such as {\sc apply} and {\sc loop} with the machine instructions
actually necessary to implement these schemata.  The resulting graph, called the
{\it machine graph}\index{machine graph}, contains only instructions executable
by the dataflow machine.  Additional optimization phases may follow machine
graph generation, and the result is finally fed to an assembly\index{assembler}
phase, which assigns addresses to the machine graph and produces output in a
form understandable by the various dataflow implementations.

As described above, there are really two kinds of dataflow graphs used in the
compiler: the program graph and the machine graph.  The advantage of using
these two forms is that many if not all of the optimizations performed at the
graph level can be performed upon the program graph, which is fairly
independent of the details of the target dataflow machine.  As a result,
changing the dataflow machine (altering the instruction set, changing
restrictions on the number of destinations, redefining the procedure linkage
mechanism, {\it etc}.)  will require few if any modifications to the bulk of the
graph manipulation phases.  The program graph is also likely to have fewer
instructions in it than the corresponding machine graph, and so optimizations
may be faster.  It is important to realize, however, that program graphs are
not entirely independent of implementation details; for example, data-driven
and demand-driven (a la Pingali) program graphs for the same program will be
quite different.

Although there are conceptually two kinds of graphs, both program graphs and
machine graphs are built on the same abstractions.  Hence, this document only
describes one kind of graph data structure, called a dataflow graph.  The
distinction between program graph and machine graph, then, is not one built
into the compiler substrate, but is enforced as a convention by the compiler
modules that manipulate graphs.

Again, it is emphasized that this document only describes the substrate of the
Id Compiler, Version 2, and that this substrate is applicable to a wide variety
of compilers and compiler related programs.  Details of the programming
language Id, what constitute legal parse trees and legal program graphs for Id,
what constitutes legal machine graphs for the Tagged-Token Dataflow
Architecture, and how Tagged-Token machine code is represented are described in
another document.

\section{Common Lisp}

The compiler substrate and all compilers built on top of it are written in
Common Lisp.  Every attempt has been made to make the compiler conform to
the specifications and conventions defined in Steele's {\it Common LISP:
The Language} \cite{Steele84a}\footnote{The latest version is
\cite{Steele90}.}, hereafter referred to as ``The Common Lisp Manual''.
The compiler substrate and any compilers built on top of it are to depend
only on language features found in this manual, as far as possible.
Furthermore, programs should conform as much as possible to coding
conventions and practices described in the manual.  These include, but are
not limited to, conventions for naming symbols (pages 24-25), for
indicating comments (page 348), for naming predicates (page 71), and for
indicating {\tt nil} (page 4).  The compiler writer should strive for
consistency with Common Lisp and with the compiler substrate in naming and
choosing arguments for functions.

It is assumed that the reader of this document is intimately familiar with all
the material in the Common Lisp Manual.

\section{Packages}

The code that makes up the compiler substrate is found in the
{\tt dfcs} package, and the symbols described in this document are all
in that package (descriptions in this document do not include the
{\tt dfcs} package qualifier as it is understood that all symbols
described here that are not a part of the Common Lisp system are in the
{\tt dfcs} package).  
%This package has nicknames {\tt id}, {\tt id-compiler}, and {\tt idv2}.

In addition, the symbols described in this document are exactly the external
symbols of the {\tt dfcs} package.  It is intended that compiler modules will
exist in other packages which use the {\tt dfcs} package\footnote{The word
``use'' in this context is defined in Chapter 11 of the Common Lisp Manual.},
allowing modules to refer to compiler substrate functions without package
qualifiers, yet preventing modules from conflicting with each other and with
internal functions of the substrate.  For the benefit of users developing code,
an {\tt dfcs-user} package is provided which is just a package that uses the
{\tt dfcs} and the {\tt lisp} package, with nothing in it initially.

