\documentstyle[slide]{article} % -*- Dictionary: pap:papers -*- 

%\nologo	% Remove the '%' at the beginning to eliminate the logo

\begin{document}
\pagestyle{headings}

\begin{titlepage}
\begin{center}
\vspace*{2.5 cm}
{\bf Compiler Technology in Gwydion}\\
\vspace{2 em}
{\bf Robert A. MacLachlan}\\
\vspace{2 em}
\today
\end{center}
\end{titlepage}


\slidehead{Overview}

The purpose of a compiler is to provide an {\it efficient} implementation of
language {\it semantics.}  Gwydion differs from other programming environments
because:
\begin{itemize}
\item Dylan semantics are different from conventional implementation and
prototyping languages.

\item The Gwydion compiler will apply different techniques to efficiently
implement these semantics.

\item Efficient implementation of high-level operations allows programs to be
written differently.

\item Instead of being text or syntax oriented, Gwydion is {\it semantics}
oriented.

\item Incremental semantic analysis is stored in a shared OODB, allowing
consistent concurrent browsing of multiple semantically-based views.
\end{itemize}


\slidehead{Efficiency}

Delivered speed:
\begin{itemize}
\item State-of-the-art back-end technology (register allocation, etc.)

\item High-level optimization of high-level programs.

\item Special techniques developed for efficient compilation of dynamic
languages.

\item Whole-program compilation.
\end{itemize}

Delivered space:
\begin{itemize}
\item Shared libraries.

\item Library-oriented system architecture with non-resident development
tools (as opposed to monolithic development/runtime environment.)

\item Static demand linking of referenced library components.

\item Byte compilation for rarely used code.
\end{itemize}


\slidehead{Semantics and Optimization}

Dylan differs from conventional implementation languages such as C++:
\begin{itemize}
\item Dynamic typing provides the lowest barrier to evolution and reuse.

\item Function closures greatly increase the power of functional abstraction.

\item The Dylan object model is significantly more powerful and pervasive.

\item Augmenting the compiler with arbitrary transformations provides a unique
degree of language extensibility.
\end{itemize}

Dylan differs from prototyping languages in that:
\begin{itemize}
\item It is designed with efficiency in mind, and

\item Rather than being specialized, it is specializable.
\end{itemize}


\slidehead{High Level Programming}

High-level programming via extension is the hidden secret of high-productivity
general-purpose languages such as Smalltalk and Lisp:
\begin{itemize}
\item Extensible systems provide a sound base on which special-purpose
high-level operations can be built.

\item Designing new high-level operations is inevitably hard, but profitable (a
form of reuse.)

\item Efficient extension is easier than writing a whole new compiler.
\end{itemize}

Programming at a high level:
\begin{itemize}
\item Improves expressiveness and programmer productivity,
\item Hides irrelevant implementation details, and
\item Has a reputation for poor implementation efficiency.
\end{itemize}


\slidehead{Extensibility and Metaprogramming}

High-level programming via extensions of a simple language can be efficient
because:
\begin{itemize}
\item Missing high level operations can easily be added; programmers are not
forced to use high-level operations inappropriately (and inefficiently.)

\item When necessary, speed-critical portions of programs can recoded using
lower-level operations without requiring an abrupt transition to a different
low-level language.

\item High level operations can be optimized automatically based on their
underlying implementation (partial evaluation.)

\item Meta-programming of the compiler allows extensions to optimize
themselves according to their own semantics.
\end{itemize}


\slidehead{Optimization and Tuning}

The strength of high-level programming (hiding the implementation) is also a
weakness:
\begin{itemize}
\item Efficient coding requires knowledge of the costs of operations; in
low-level languages, these costs are fairly constant and context-independent.

\item High-level operations require high levels of optimization for acceptable
efficiency, and

\item High-level optimization relies on exploiting obscure context
dependencies.

\item The tools for efficiency may exist, but it isn't clear when and how to
use them.
\end{itemize}


\slidehead{Accountable Optimization}

Accountable optimization eliminates the need for a mental efficiency model by
telling the programmer:
\begin{itemize}
\item when an inefficient implementation is chosen for non-obvious reasons,

\item how serious the situation is,

\item precisely what part of the program is being referred to, and

\item why the inefficient choice was made (and how to enable efficient
compilation.)
\end{itemize}

Unconditional output from a file compiler can easily overload the programmer
with spurious information.  Gwydion's optimization tools will integrate
compiler information with profiling results and complexity-managing browsers.


\slidehead{Partial Evaluation}

Partial evaluation is a generalization of constant folding.  Instead of only
replacing completely constant expressions with the compile-time result of the
expression, partial evaluation transforms arbitrary code using information on
parts of the program that are constant.

Partial evaluation comes into its own when programs are {\it written to be
optimized:}
\begin{itemize}
\item Tuned programs written in low-level languages show little benefit from
partial evaluation because they are already hand-optimized.

\item Partial evaluation helps the efficiency of high-level programming by
specializing high-level operations according to their context.

\item Partial evaluation helps the efficiency of dynamic and polymorphic (or
OO) typing by eliminating unused generality.
\end{itemize}


\slidehead{Partial Evaluation Example}

\begin{tabbing}
(declaim (inline find-in))\\
(d\=\+efun find-in (next \=\+element list \&key (key \#'identity)\\
		     (test \#'eql test-p)\\
			(test-not nil not-p))\-\\
  (w\=\+hen (and test-p not-p)\\
    (error "Both :Test and :Test-Not supplied."))\-\\
  (if \=\+not-p\\
      (d\=\+o \=\+((current list (funcall next current)))\\
	  ((null current) nil)\-\-\\
	(u\=\+nless (funcall \=\+test-not (funcall key current)\\
			     element)\-\\
	  (return current)))\-\\
      (d\=\+o \=\+((current list (funcall next current)))\\
	  ((null current) nil)\-\-\\
	(w\=\+hen (funcall test (funcall key current) element)\\
	  (return current)))))\-\-\-\\
\end{tabbing}


\slidehead{Partial Evaluation Result}

When inline expanded and partially evaluated, this transformation results:
\begin{tabbing}
(find-in \=\+\#'foo-next 3 foo-list\\
	 :key \#'foo-offset :test \#'{\tt\char`\<})\-\\
$\Rightarrow$\\
(d\=\+o \=\+((current foo-list (foo-next current)))\\
    ((null current) nil)\-\\
  (w\=\+hen ({\tt\char`\<} (foo-offset current) 3)\\
    (return current)))\-\-
\end{tabbing}


\slidehead{Whole-Program Compilation}

Whole-program compilation is the opposite of separate compilation:
\begin{itemize}
\item Separate compilation reduces the time and space overhead of compilation
at the cost placing an arbitrary horizon on optimization.

\item High-level dynamic languages need whole-program compilation in order to
optimize across abstraction levels and to remove spurious dynamism.

\item Gwydion is unusually well-positioned to exploit whole-program
compilation, since all code resides in a unified persistent database.

\item Incremental semantic analysis and compilation minimize the need for
whole-program {\it recompilation}.
\end{itemize}


\slidehead{Fast Development Cycle}

\begin{itemize}
\item Studies of the advantages of dynamic prototyping environments often
find the fast design---implement---evaluate cycle to be the primary cause of
improved productivity.

\item Because of its quantifiable and immediate benefits, environments for
C++, etc., are starting to adopt incremental compilation.

\item Although Gwydion emphasizes support for new development paradigms such
as evolution and high-level programming, we still believe responsive
development tools are important.

\item Gwydion advances incremental development into new areas: concurrent
incremental design, coding, testing and documentation.  Quick transition
between all these functions is required to avoid short-term memory loss.
\end{itemize}


\slidehead{Environment Integration}

The Gwydion compiler is highly integrated with the rest of the programming
environment:
\begin{itemize}
\item The compiler implements language semantics; because the compiler is
integrated with the environment, the environment can be {\it semantics
directed}.

\item A semantically aware editor can provide clear, prompt notification of
type errors, dead code, or other semantic problems.

\item Since the database contains semantic information (like
cross-references), it can be searched by semantic criteria, such as ``who
extends this method.''

\item Incremental tools with this level of integration are only possible when
the compiler and environment are co-designed.
\end{itemize}


\slidehead{Summary}

\begin{itemize}
\item Efficiency and semantics are both environment issues; the compiler is the
primary analytic part of the environment.

\item We have experience implementing practical highly optimizing compilers.

\item We know how to efficiently implement evolving high-level programs.

\item We are exploiting new technology (OODBs) to allow both new implementation
techniques (whole-program compilation) and new environment features (multiple
semantic views.)
\end{itemize}

\end{document}
