%\documentstyle[times,10pt,twocolumn]{article}
\documentclass[twocolumn]{article}
\usepackage{times}
\usepackage{calc}

\makeatletter
% Some macros cpied from latex8.sty [an IEEE Proceedings style]
% by Paolo.Ienne@di.epfl.ch 

% ten point helvetica bold required for captions
% in some sites the name of the helvetica bold font may differ, 
% change the name here:
\font\tenhv  = phvb at 10pt
%\font\tenhv  = phvb7t at 10pt

% eleven point times bold required for second-order headings 
% \font\elvbf  = cmbx10 scaled 1100
\font\elvbf  = ptmb scaled 1100

\setlength{\parindent}{1pc}

\def\@maketitle
   {
   \newpage
   \null
   \vskip .375in 
   \begin{center}
      {\Large \bf \@title \par} 
      % additional two empty lines at the end of the title 
      \vspace*{24pt} 
      {
      \large 
      \lineskip .5em
      \begin{tabular}[t]{c}
         \@author 
      \end{tabular}
      \par
      } 
      % additional small space at the end of the author name 
      \vskip .5em 
      {
       \large 
      \begin{tabular}[t]{c}
         \@affiliation 
      \end{tabular}
      }
      % additional empty line at the end of the title block 
      \vspace*{12pt} 
   \end{center}
   } 

\def\abstract
   {%
   \centerline{\large\bf Abstract}%
   \vspace*{12pt}%
   \it%
   }

\def\endabstract
   {
   % additional empty line at the end of the abstract 
   \vspace*{12pt} 
   }

\def\affiliation#1{\gdef\@affiliation{{\it #1}}} \gdef\@affiliation{}

\setlength{\textheight}{9in}
\setlength{\textwidth}{6.5in}
\setlength{\columnsep}{0.4in}
\setlength{\topsep}{6pt plus 2pt minus 3pt}
\setlength{\itemsep}{2pt plus 2pt minus 1pt}

\renewcommand{\@seccntformat}[1]{\csname the#1\endcsname.\quad}
\def\section{\@startsection {section}{1}{\z@}
   {14pt plus 2pt minus 2pt}{12pt plus 2pt minus 2pt} {\large\bf}} 
\def\subsection{\@startsection {subsection}{2}{\z@}
   {13pt plus 2pt minus 2pt}{11pt plus 2pt minus 2pt} {\elvbf}}

\newcommand{\LBr}{\char"7B}
\newcommand{\RBr}{\char"7D}
\newcommand{\Tab}{\>}
\newcommand{\UnTab}{\<}

% take the % away on next line to produce the final camera-ready version 
\pagestyle{empty}

\begin{document}
\title{Kawa:  Compiling Scheme to Java}
\author{Per Bothner}
\affiliation{Cygnus Solutions}
\maketitle

\thispagestyle{empty}
\begin{abstract}
Kawa is an implementation of the Scheme programming language
written entirely in Java.  It compiles Scheme procedures
into Java bytecode classes, either on-the-fly, or in
batch mode for later use.  Kawa also includes a full Scheme run-time
environment written in an object-oriented style, with class
hierarchies for collections, procedures, and the full numeric ``tower.''

This paper gives an overview of the features of Kawa.
It concentrates on the compiler, and how Scheme values are
represented by Java objects.  The paper is structured
as a ``tour'' of the Java classes used in the implementation.

\end{abstract}


\newcommand{\CHead}[2]%
  {{\parbox{\linewidth-\dimen\@curtab}
    {{\strut}#1\penalty-500{}#2{\strut}\rightskip=0pt plus3em\hangindent=3ex\hangafter=1}}}
\newcommand{\MHead}[3]{\CHead{#1 #2}{#3}}
\makeatother

\newcommand{\Comment}[1]{{\tt //} {\it #1}}

\newcommand{\TabSkip}{\kern2ex}
\newenvironment{Code}%
  {\begingroup\tt\frenchspacing\begin{tabbing}\TabSkip\=\TabSkip\=\TabSkip\=\TabSkip\=\TabSkip\=\kill}
  {\end{tabbing}\endgroup}

\newenvironment{ClassNoDots}[3]%
  {\begin{Code}#1 {\bf #2}#3 \LBr\+\\}
  {\UnTab\RBr\end{Code}}
\newenvironment{Class}[2]%
  {\begin{ClassNoDots}{class}{#1}{#2}}
  {...\\\end{ClassNoDots}}

\newcommand{\class}[1]{class {\bf #1}}

\section{Introduction}

While Java is a decent programming language, its success
is largely due to using portable bytecodes, and its
integration into secure web browsers.  Many prefer other
programming languages.  If they are implemented on top of
Java, programmers can gain many of the extra-linguistic
benefits of Java, including libraries, portable bytecodes,
web applets, and the existing efforts to improve Java
implementations and tools.

Scheme is a simple yet powerful language.  It is a
non-pure functional language ({\it i.e.} it has first-class
functions, lexical scoping, non-lazy evaluation, and side
effects).  It has dynamic typing, and usually has an
interactive read-evaluate-print interface.  The dynamic
nature of Scheme (run-time typing, immediate expression
evaluation) may be a better match for the dynamic Java
environment (interpreted bytecodes, dynamic loading) than
Java is!

{\bf Note:}  Kawa is also the trademarked name of a commercial Java
development environment.  To avoid confusion, we may soon change
the name of the system described here, but in any case, information
and source code will be available
from {\tt http:\discretionary{}{}{}//www.cygnus.com/\discretionary{}{}{}\verb|~bothner|/\discretionary{}{}{}kawa.html}.

%\Slide{Scheme vs Java}
%Scheme and Java are very different kinds of languages:
%\Item Scheme is dynamically typed, while Java is statically typed.
%\Item Java is an object-oriented language.
%Standard Scheme has neither objects, inheritance, or methods.
%\Item Scheme is a (non-pure) functional language:
%Procedures are first-class objects;  lexical scoping
%requires closures.
%\Item Scheme defines arithmetic on a tree of number types.
%Java normally uses raw machine-level numbers.
%
%How should we map Scheme constructs into Java constructs?

\section{Background}

Starting in 1995 Cygnus (on behalf of the Free Software Foundation)
developed Guile, an implementation of Scheme suitable as a general
embedding and extension language.  Guile was based on
Aubrey Jaffar's SCM interpreter;  the various Guile enhancements
were initially done by Tom Lord.  In 1995 we got a major contract
to enhance Guile, and with our client we added
more features, including threads (primarily done by Anthony Green),
and internationalization.

The contract called for a byte-code
compiler for Guile, and it looked like doing a good job
on this would be a major project.  One option we considered was compiling
Scheme into Java bytecodes and executing them by a Java engine.
The disadvantage would be that such a Scheme system would not
co-exist with Guile (on the other hand, we had run into various
technical and  non-technical problems with Guile that led us to
conclude that Guile would after all not be strategic to Cygnus).
The advantage of a Java solution was leveraging off the
tools and development being done in the Java ``space'', plus that Java
was more likely to be strategic long-term.

The customer agreed to using Java, and I started active development June 1996.
Kawa 1.0 was released to our customer and ``the Net'' September 1996.
Development has continued since then, at a less intense pace!
The long-term goal is an object-oriented environment
that harmoniously integrates Scheme, Java, and other languages.

As a base, I used the Kawa Scheme interpreter written
by R.~Alexander Milowski.  He needed an object-oriented
Scheme interpreter to implement DSSSL \cite{DSSSL},
a Scheme-like environment for expressing style, formatting,
and other processing of SGML \cite{SGML} documents.
DSSSL is an subset of ``pure'' Scheme with some extensions.
%  [See http://www.edu.uni-klu.ac.at/~nmikula]
Kawa 0.2 was a simple interpreter which was far from
complete.  It provided a useful starting point, but almost all
of the original code has by now been re-written.

There are three basic ways of implementing Scheme in Java.
\begin{enumerate}
\item One could write an interpreter in Java, but this has
poor performance.
\item One could translate into Java source code.  However,
invoking an external Java source-to-bytecode compiler is
too slow except for batch compilation.  Also, some features
of Java bytecodes (such as goto) are not available in the
Java language.
\item One could translate into Java bytecodes, either ahead
of time (a batch compiler), or for immediate execution.
\end{enumerate}

We have implemented the last option for Kawa,
partly because that was what our contract called for, but also because
it is the best solution.  To generate
bytecodes, we use a new ``{\tt codegen}'' package, which is an
intermediate-level toolkit to generate Java bytecodes and
"{\tt .class}" files.

We will discuss the compiler later, but first we will give an
overview of the run-time environment of Kawa, and the
classes used to implement Scheme values.

\section{Objects and Values}

Java \cite{JavaSpec} has primitive types (such as 32-bit {\tt int}) as well
reference types.  If a variable has a reference type, it means that it can
contains references (essentially pointers) to objects of a class,
or it can contain references to objects of classes that ``extend''
(inherit from) the named class.  
The inheritance graph is ``rooted'' (like Smalltalk and unlike C++);
this means that all classes inherit from a distinguished class
{\tt java.lang.Object} (or just {\tt Object} for short).

Standard Scheme \cite{R4RS} has a fixed set of types, with no way of creating
new types.  It has run-time typing, which means that types are not declared,
and a variable can contain values of different types at different times.
The most natural type of a Java variable that can contain any
Scheme value is therefore {\tt Object}, and all
Scheme values must be implemented using some class that
inherits from {\tt Object}.

%There are alternatives:  We could declare a new {\tt SchemeObject}
%class ... Also compiler analysis (type inference) ...

The task then is to map each Scheme type into a Java class.
Whether to use a standard Java class, or to write our own
is a tradeoff.  Using standard Java classes simplifies
the passing of values between Scheme functions and existing Java methods.
On the other hand, even when Java has suitable built-in classes,
they usually lack functionality needed for Scheme, or are not organized
in any kind of class hierarchy as in Smalltalk or Dylan.
% E.g. number classes
Since Java lacks standard classes corresponding to pairs,
symbols, or procedures, we \emph{have} to write some new
classes, so we might as well write new classes whenever the
existing classes lack functionality.  One extreme would
be to define a new {\tt SchemeObject} class, and derive from
it classes for all Scheme values.  While this might make
implementing Scheme easier, Kawa does not go that far,
partly because we want to allow Scheme variables to contain
arbitrary Java objects.

The Scheme boolean type is one where we use a standard Java type,
in this case {\tt Boolean} (strictly speaking {\tt java.lang.Boolean}).
The Scheme constants \verb'#f' and \verb'#t' are mapped into
static fields (i.e. constants) {\tt Scheme.falseObject} and
{\tt Scheme.trueObject}.  These are initialized to {\tt new Boolean(false)}
and {\tt new Boolean(true)}, respectively, when Kawa starts up.

On the other hand, numbers and collections are reasonably organized
into class hierarchies, which Java does not do well.
So Kawa has its own classes for those, discussed in the following sections.

\section{Symbols}
Symbols represent names, and do not need much functionality.
Scheme needs to be able to convert them to and from strings,
and they need to be ``interned'' (which means that there is a global
table to ensure that there is a unique symbol for a given string).
Symbols are immutable and have no accessible internal structure.
Currently, Scheme symbols are implemented using a Kawa-specific
{\tt Symbol} class.

I am planning to re-implement symbols to use the the
standard Java {\tt String} class, which supports an {\tt intern}
operator.  Note that the Java {\tt String} class implements
immutable strings, and is therefore cannot be used to implement
Scheme strings.  However, it makes sense to use it to implement symbols,
since the way Scheme symbols are used is very similar to how
Java {\tt String}s are used.  While Kawa currently assumes a Java
implementation corresponding to version 1.0 of JDK (Sun's Java Development
Kit), a future version will
depend on JDK 1.1 features.  One such new 1.1 feature is that
literal Java {\tt String}s will be required to be automatically
interned.  This will make it even more appealing to use {\tt String}
to implement Scheme symbols.

\section{Numbers}

Scheme defines a ``numerical tower'' of numerical types:
number, complex, real, rational, and integer.
Kawa implements the full ``tower'' of Scheme number types,
which are all sub-classes of the abstract
class {\tt Quantity} discussed in section~\ref{QuantitySection}.

\begin{Class}{Complex}{ extends Quantity}
\MHead{public abstract RealNum}{re}{();}\\
\MHead{public abstract RealNum}{im}{();}\\
\end{Class}

{\tt Complex} is the class of abstract complex numbers.
It has three subclasses:  the abstract class {\tt RealNum}
of real numbers;  the general class {\tt CComplex} where the
components are arbitrary {\tt RealNum} fields; and the
optimized {\tt DComplex} where the components
are represented by {\tt double} fields.

\begin{Class}{RealNum}{ extends Complex}
\MHead{public final RealNum}{re}{()}\\
{\LBr} return this; {\RBr}\\
\MHead{public final RealNum}{im}{()}\\
{\LBr} return IntNum.zero(); {\RBr}\\
\MHead{public abstract boolean}{isNegative}{();}\\
\end{Class}

\begin{Class}{DFloNum}{ extends RealNum}
double value;\\
\end{Class}
Concrete class for double-precision (64-bit) floating-point real numbers.

\begin{Class}{RatNum}{ extends RealNum}
public abstract IntNum numerator();\\
public abstract IntNum denominator();\\
\end{Class}

{\tt RatNum}, the abstract class for exact rational numbers,
has two sub-classes:  {\tt IntFraction} and {\tt IntNum}.

\begin{Class}{IntFraction}{ extends RatNum}
IntNum num;\\
IntNum den;\\
\end{Class}

The {\tt IntFraction} class implements fractions in the obvious way.
Exact real infinities are identified with the
fractions {\tt 1/0} and {\tt -1/0}.

\begin{Class}{IntNum}{ extends RatNum}
int ival;\\
int[] words;\\
\end{Class}

The {\tt IntNum} concrete class implements infinite-precision integers.
The value is stored in the first {\tt ival} elements of {\tt words},
in 2's complement form (with the low-order bits in \verb|word[0]|).

There are already many bignum packages, including a couple written
in Java.  What are the advantages of this one?
\begin{itemize}
\item A complete set of operations, including gcd and lcm;  logical, bit,
and shift operations; power by repeated squaring; all of the
division modes from Common Lisp (floor, ceiling, truncate, and round);
and exact conversion to {\tt double}.
\item Consistency and integration with a complete ``numerical tower.''
Specifically, consistency and integration with ``fixnum'' (see below).
\item Most bignum packages use a signed-magnitude representation,
while Kawa uses 2's complement.  This makes for easier integration
with fixnums, and also makes it cheap to implement
logical and bit-fiddling operations.
\item Use of all 32 bits of each ``big-digit'' word, which
is the ``expected'' space-efficient representation.
More importantly, it is compatible with the {\tt mpn} routines
from the Gnu Multi-Precision library ({\tt gmp}) \cite{gmp}.
The {\tt mpn} routines are low-level algorithms that work
on unsigned pre-allocated bignums;  they have been transcribed
into Java in the {\tt MPN} class.  If better efficiency is
desired, it is straight-forward to replace the {\tt MPN}
methods with native ones that call the highly-optimized {\tt mpn} functions.
\end{itemize}

If the integer value fits within a signed 32-bit {\tt int},
then it is stored in {\tt ival} and {\tt words} is null.
This avoids the need for extra memory allocation for the {\tt words}
array, and also allows us to special-case the common case.

As a further optimization, the integers in the range $- 100$ to $1024$
are pre-allocated.

\section{Mixed-type arithmetic}

Many operations are overloaded to have different
definitions depending on the argument types.
The classic examples are the functions of arithmetic
such as ``\verb|+|'', which needs to use different
algorithms depending on the argument types.
If there is a fixed and reasonably small set of number types
(as is the case with standard Scheme), then we can just
enumerate each possibility.  However, the Kawa system is
meant to be more extensible and support adding new
number types.

The solution is straight-forward in the case of a one-operand
function such as ``negate'', since we can use method
overriding and virtual method calls to dynamically
select the correct method.  However, it is more difficult
in the case of a binary method like ``\verb|+|,'' since
classic object-oriented languages (including Java) only
support dynamic method selection using the type of the
first argument (``{\tt this}'').  
Common Lisp and some Scheme dialects support dynamic method
selection using all the arguments, and in fact the
problem of binary arithmetic operations is probably the
most obvious example where ``multi-dispatch'' is useful.

Since Java does not have multi-dispatch, we have to solve
the problem in other ways.  Smalltalk has the same problems,
and solved it using ``coercive generality'':  Each number class
has a generality number, and operands of lower generality are
converted to the class with the higher generality.
This is inefficient because of all the conversions and
temporary objects (see \cite{Budd91Arith}), and it is limited
to what extent you can add new kinds of number types.

In ``double dispatch'' \cite{Ingalls86} the expression {\tt x-y}
is implemented as {\tt x.sub(y)}.  Assuming the (run-time)
class of {\tt x} is {\tt Tx} and that of {\tt y} is {\tt Ty},
this causes the {\tt sub} method defined in {\tt Tx} to be
invoked, which just does {\tt y.subTx(x)}.  That invokes
the {\tt subTx} method defined in {\tt Ty} which can without
further testing do the subtraction for types {\tt Tx} and {\tt Ty}.

The problem with this approach is that it is difficult to add
a new {\tt Tz} class, since you have to also add {\tt subTz}
methods in all the existing number classes, not to mention
{\tt addTz} and all the other operations.

In Kawa, {\tt x-y} is also implemented by {\tt x.sub(y)}.
The {\tt sub} method of {\tt Tx} checks if {\tt Ty} is one
of the types it knows how to handle.  If so, it does the
subtraction and returns the result itself.
Otherwise, {\tt Tx.sub} does \verb|y.sub_reversed(x)|.  This invokes
\verb|Ty.sub_reversed| (or \verb|sub_reversed| as defined in
a super-class of {\tt Ty}).  Now {\tt Ty} (or one of its
super-classes) gets a chance to see if it knows how to
subtract itself from a {\tt Tx} object.

The advantage of this scheme is flexibility.  The knowledge of
how to handle a binary operation for types {\tt Tx} and {\tt Ty}
can be in either of {\tt Tx} or {\tt Ty} or either of their
super-classes.  This makes is easier to add new classes without
having to modify existing ones.

\section{Quantities}
\label{QuantitySection}

The DSSSL language \cite{DSSSL} is a dialect of Scheme used
to process SGML documents.  DSSSL has ``quantities'' in addition
to real and integer numbers.  Since DSSSL is used to format documents,
it provides length values that are a multiple of a meter
({\it e.g.} {\tt 0.2m}), as well as derived units like {\tt cm} and
{\tt pt} (point).
A DSSSL quantity is a product of a dimension-less number with an integral
power of a length unit (the meter).  A (pure) number is a quantity where
the length power is zero.

For Kawa, I wanted to merge the Scheme number types with the DSSSL
number types, and also generalize the DSSSL quantities to support
other dimensions (such as mass and time) and units (such as {\tt kg}
and seconds).  Quantities are implemented by the abstract class {\tt Quantity}.
A {\it quantity} is a product of a {\tt Unit} and a pure
number.  The number can be an arbitrary complex number.

\begin{Class}{Quantity}{ extends Number}
\MHead{public Unit}{unit}{()}\\
{\LBr} return Unit.Empty; \RBr\\
\MHead{public abstract Complex}{number}{();}\\
\end{Class}

\begin{Class}{CQuantity}{ extends Quantity}
Complex num;\\
Unit unt;\\
\MHead{public Complex}{number}{()}\\
{\LBr} return num; {\RBr}\\
\MHead{public Unit}{unit}{()}\\
{\LBr} return unt; {\RBr}\\
\end{Class}

A {\tt CQuantity} is a concrete class that implements general
{\tt Quantities}.  But usually we don't need that much generality,
and instead use {\tt DQuanity}.

\begin{Class}{DQuantity}{ extends Quantity}
double factor;\\
Unit unt;\\
\MHead{public final Unit}{unit}{()}\\
{\LBr} return unt; {\RBr}\\
\MHead{public final Complex}{number}{()}\\
{\LBr} return new DFloNum(factor); {\RBr}\\
\end{Class}

\begin{Class}{Unit}{ extends Quantity}
String name; \Comment{Optional.}\\
Dimensions dims;\\
double factor;\\
\end{Class}

A {\tt Unit} is a product of a floating-point {\tt factor}
and one or more primitive units, combined into a {\tt Dimensions} object.
The {\tt Unit} name have a name (such as ``{\tt kg}''), which is
used for printing, and when parsing literals.

\begin{Class}{BaseUnit}{ extends Unit}
int index;\\
\end{Class}

A {\tt BaseUnit} is a primitive unit that is not
defined in terms of any other {\tt Unit}, for example the meter.
Each {\tt BaseUnit} has a different {\tt index}, which is used
for identification and comparison purposes.  Two {\tt BaseUnit}s
have the same {\tt index} if and only if they are the same {\tt BaseUnit}.

\begin{Class}{Dimensions}{}
BaseUnit[] bases;\\
short[] powers;\\
\end{Class}

A {\tt Dimensions} object is a product and/or ratio of {\tt BaseUnit}s.
You can think of it as a data structure that maps every {\tt BaseUnit}
to an integer power.  The {\tt bases} array is a list of the {\tt BaseUnit}s
that have a non-zero power, in order of the {\tt index} of the {\tt BaseUnit}.
The {\tt powers} array gives the power (exponent) of the {\tt BaseUnit}
that has the same index in the {\tt bases} array.

Two {\tt Dimensions} objects are equal if they have the same list of
{\tt bases} and {\tt powers}.  {\tt Dimensions} objects are ``interned''
(using a global hash table) so that they are equal only if they are
the same object.  This makes it easy to implement addition and
subtraction:

\begin{Code}
\MHead{public static DQuantity}{add}{(DQuantity~x, DQuantity~y)}\\
\LBr\+\\
  if (x.unit().dims != y.unit().dims)\\
  \Tab throw new ArithmeticException\\
  \Tab\Tab ("units mis-match");\\
  double r = y.unit().factor\\
  \Tab / x.unit().factor;\\
  double s = x.factor + r * y.factor;\\
  return new DQuantity (s, x.unit());\-\\
\RBr\\
\end{Code}

The {\tt Unit} of the result of an addition or subtraction
is the {\tt Unit} of the first operand.  This makes it easy to convert units:
\begin{verbatim}
kawa> (+ 0cm 2.5m)
250cm
\end{verbatim}

Because Kawa represents quantities relative to user-specified units,
instead of representing them relative to primitive base units,
it can automatically print quantities using the user's preferred units.
However, this does make multiplication and division more difficult.
The actual calculation (finding the right {\tt Dimensions} and
multiplying the constant factors) is straight-forward.
The problem is generating the new compound unit, and
later printing out the result in a human-friendly format.
There is no obvious right way to do this.  Kawa creates
a {\tt MulUnit} to represent a compound unit, but it is not
obvious which simplifications should be done when.
Kawa uses a few heuristics to simplify compound
units, but this is an area that could be improved.

\section{Collections}

Kawa has a rudimentary hierarchy of collection classes.

\begin{Class}{Sequence}{}
abstract public int length();\\
\MHead{abstract public Object}{elementAt}{(int~index);}\\
\end{Class}

A {\tt Sequence} is the abstract class that includes
lists, vectors, and strings.

\begin{Class}{FString}{ extends Sequence}
char[] value;\\
\end{Class}

Used to implement fixed-length mutable strings (array of Unicode character).
This is used to represent Scheme strings.

\begin{Class}{FVector}{ extends Sequence}
Object[] value;\\
\end{Class}
Used to implement fixed-length mutable general one-dimensional array
of {\tt Object}.
This is used to represent Scheme vectors.

\begin{Class}{List}{ extends Sequence}
protected List () {\LBr} \RBr\\
static public List Empty\\
\Tab = new List ();\\
\end{Class}

Used to represent Scheme (linked) lists.
The empty list \verb|'()| is the static (global)
value {\tt List.Empty}.  Non-empty-lists are implemented using {\tt Pair}
objects.

\begin{Class}{Pair}{ extends Sequence}
public Object car;\\
public Object cdr;\\
\end{Class}

Used for Scheme pairs.

\begin{Class}{PairWithPosition}{ extends Pair}
\end{Class}

Like {\tt Pair}, but includes the filename and linenumber in the
file from which the pair was read.

Future plans include more interesting collection classes,
such a sequences implemented as a seekable disk file;
lazily evaluated sequences; hash tables;  APL-style
multi-dimensional arrays; stretchy buffers.\footnote{Many of
	these ideas were implemented in my earlier experimental
	language {\tt Q} -- see \cite{PBthesis} and
	{\tt ftp:\discretionary{}{}{}//ftp.cygnus.com/pub/bothner/Q/}.}

\section{Procedures}

Scheme has procedures as first-class values.
Java does not.  However, we can simulate procedure values,
by overriding of virtual methods.

\begin{Class}{Procedure}{}
\MHead{public abstract Object}{applyN}{(Object[]~args);}\\
public abstract Object apply0 ();\\
\MHead{public abstract Object}{apply1}{(Object~arg1);}\\
...;\\
\MHead{public abstract Object}{apply4}{(Object~arg1, ..., Object~arg4);}\\
\end{Class}

We represent Scheme procedures using sub-classes of
the abstract class {\tt Procedure}.
To call (apply) a procedure with no arguments,
you invoke its {\tt apply0} method;  to invoke a
procedure, passing it a single argument, you use its
{\tt apply1} method; and so on using {\tt apply4} if
you have 4 arguments.  Alternatively, you can bundle
up all the arguments into an array, and use the {\tt applyN}
method.  If you have more than 4 arguments, you
have to use {\tt applyN}.

Notice that all {\tt Procedure} sub-classes have to
implement all 6 methods, at least to the extent of
throwing an exception if it is passed the wrong number of
arguments.  However, there are utility classes
{\tt Procedure0} to {\tt Procedure4} and {\tt ProcedureN}.

\begin{Class}{Procedure1}{ extends Procedure}
\MHead{public abstract Object}{applyN}{(Object[]~args)}\\
{\LBr\+}\\
  if (args.length != 1)\\
  \Tab  throw new WrongArguments();\\
   return apply1(args[0]);\-\\
{\RBr}\\
\MHead{public Object}{apply0}{()}\\
\Tab {\LBr} throw new WrongArguments();{\RBr}\\
\MHead{public abstract Object}{apply1}{(Object~arg1);}\\
\MHead{public Object}{apply2}{(Object~arg1, Object~arg2)}\\
{\LBr} throw new WrongArguments();{\RBr}\\
\end{Class}

Primitive procedures are generally written in Java as
sub-classes of these helper classes. For example:

\begin{ClassNoDots}{class}{cdr}{ extends Procedure1}
\MHead{public Object}{apply1}{(Object~arg1)}\\
\Tab {\LBr} return ((Pair) arg1).cdr; {\RBr}\\
\end{ClassNoDots}

A user-defined Scheme procedure is compiled to a
class that is descended from {\tt Procedure}.
For example, a variable-argument procedure is implemented as a
sub-class of {\tt ProcedureN}, with an {\tt applyN}
method comprising the bytecode compiled from the Scheme procedure
body.  Thus primitive and user-defined procedure have the
same calling convention.

If a nested procedure references a lexical variable in an
outer procedure, the inner procedure is implemented
by a ``closure''.  Kawa implements a closure 
as a {\tt Procedure} object with a ``static link''
field that points to the inherited
environment.  In that case the lexical variable must be
heap allocated, but otherwise lexical variables use local Java
variable slots.  (This is conceptually similar
to the ``Inner classes'' proposed for JDK 1.1.)

\label{ModuleBody}
\begin{Class}{ModuleBody}{ extends Procedure0}
\MHead{public Object}{apply0}{()}\\
{\LBr}return run(\\
\Tab\Tab\Tab Environment.current());{\RBr}\\
\MHead{public abstract Object}{run}{(Environment~env);}\\
\end{Class}

Top-level forms (including top-level definitions) are
treated as if they were nested inside a dummy procedure.
A {\tt ModuleBody} is such a dummy procedure.
When a file is {\tt load}ed, the result is a {\tt ModuleBody};
invoking {\tt run} causes the top-level actions to be executed.

\section{Overview of compilation}

These are the stages of compilation:
\begin{description}
\item[Reading]  The first compilation stage reads the input
from a file, from a string,
or from the interactive command interpreter.
The result is one or more Scheme forms (S-expressions), usually lists.
If reading commands interactively, only a single form is read;
if reading from a file or string, all the forms are read until
end-of-file or end-of-string;  in either case, the result is treated
as the body of a dummy function ({\it i.e.} a {\tt ModuleBody}).
\item[Translation] The source form body is rewritten into an
{\tt Expression} object, specifically a {\tt ModuleExp}.
This stage handles macro expansion and lexical name binding.
Many (future) optimizations can be done in this phase by annotating
and re-arranging {\tt Expression} trees.
\item[Code generation]  The resulting {\tt ModuleExp} is compiled into
one or more byte-coded classes.
This is done by invoking the virtual {\tt compile}
method recursively on the {\tt Expression}s, which generates
instructions (using the {\tt codegen} package) to evaluate the
expression and leave the result on the Java operand stack.
At the end we ask the {\tt codegen} package to write out the resulting
classes and methods.  They can be written to a file (for
future use), or into byte arrays in memory.
\item[Loading]  The compiled bytecodes are loaded into the Kawa
interpreter.  In the case of code that is compiled and then
immediately executed, the compiled code can be immediately
turned into Java classes using the Java {\tt ClassLoader} feature.
(That is how the read-eval-print loop works.)
An instance of the compiled sub-class of {\tt ModuleBody}
is created and {\tt run}, which normally produces various side-effects.
\end{description}

\section{Top-level environments}

\begin{Class}{Environment}{}
\end{Class}

An {\tt Environment} is a mapping from symbols to bindings.
It contains the bindings of the user top-level.
There can be multiple top-level {\tt Environments}, and
an {\tt Environment} can be defined as an extension 
of an existing {\tt Environment}.
The latter feature is used to implement the various standard
environment arguments that can be passed to {\tt eval},
as adopted for the next Scheme standard revision (``R5RS'').
Nested environments were also implemented to support threads,
and fluid bindings (even in the presence of threads).

\section{Expressions}

\begin{Class}{Expression}{}
\MHead{public abstract Object}{eval}{(Environment~env);}\\
\MHead{public abstract void}{compile}{(Compilation~comp, int~flags);}\\
\end{Class}

The abstract {\tt Expression} class represents partially processed expressions.
These are in principle independent of the source language,
but in practice there are some Scheme assumptions.

The {\tt eval} method evaluates the {\tt Expression} in the
given {\tt Environment}.  The interactive command interface uses
{\tt eval} to evaluate expressions typed by the user.  However,
{\tt eval} only support ``simple'' expressions, such as literals,
identifiers, and applications.  Expressions that define new
local bindings (such lambda expressions and {\tt let} forms)
do not implement {\tt eval}.  If the user types in such an
expression, it is wrapped inside a dummy function,
compiled, and immediately executed.  This is to avoid dealing
with lexical binding in the evaluator.  (We could compile
\emph{all} user expressions, but that entails a certain amount of
overhead.  Code generation creates new classes, and JDK 1.0 does
not garbage-collect unused classes.)

The {\tt compile} method is called when we are compiling
the body of a procedure.  It is responsible for generating bytecodes
that evaluate the expression, and leave the result on the Java
evaluation stack.

\begin{Class}{QuoteExp}{ extends Expression}
Object value;\\
\MHead{public}{QuoteExp}{(Object~val)}\\
{\LBr} value = val; {\RBr}\\
\MHead{public Object}{eval}{(Environment~env)}\\
{\LBr} return value; {\RBr}\\
\MHead{public void}{compile}{(Compilation~comp, int~flags)}\\
{\LBr} comp.compileConstant (value); {\RBr}\\
\end{Class}

A {\tt QuoteExp} represents a literal (self-evaluating form),
or a quoted form.

\begin{Class}{ReferenceExp}{ extends Expression}
Symbol symbol;\\
Declaration binding;\\
\end{Class}

A {\tt ReferenceExp} is a reference to a named variable.
The {\tt symbol} is the source form identifier.
If {\tt binding} is non-null, it is the lexical
binding of the identifier.

\begin{Class}{ApplyExp}{ extends Expression}
Expression func;\\
Expression[] args;\\
\end{Class}

An {\tt ApplyExp} is an application of a procedure {\tt func}
to an argument list {\tt args}.

\begin{Class}{ScopeExp}{ extends Expression}
ScopeExp outer; \Comment{Surrounding scope.}\\
\MHead{public Declaration}{add\_decl}{(Symbol~name)}\\
{\LBr} {\it Create new local variable.} {\RBr}\\
\end{Class}

A {\tt ScopeExp} is a abstract class that represents a lexical
scoping construct.  Concrete sub-classes are {\tt LetExp}
(used for a {\tt let} binding form) and {\tt LambdaExp}.

\begin{Class}{LambdaExp}{ extends ScopeExp}
Symbol name; \Comment{Optional.}\\
Expression body;\\
int min\_args;\\
int max\_args;\\
\end{Class}

The Scheme primitive syntax {\tt lambda} is translated
into a {\tt LambdaExp}, which represents anonymous procedures.
Each {\tt LambdaExp} is compiled into a different bytecoded class.
Invoking {\tt eval} causes the {\tt LambdaExp} to be compiled
into a class, the class to be loaded, and instance of the
class to be created, and the result coerced to a {\tt Procedure}.

Other sub-classes of {\tt Expression} are
{\tt IfExp} (used for conditional expressions);
{\tt BeginExp} (used for compound expressions);
{\tt SetExp} (used for assignments);  and
{\tt ErrorExp} (used to mark code that has a syntax error);

\section{Translation}

The translation phase takes a top-level form (or body),
and generates a {\tt ModuleExp}, which is a top-level expression.
This is done using a {\tt Translator}, which keeps track of
lexical bindings and other translation state.

\begin{Class}{Translator}{}
\MHead{public Expression}{rewrite}{(Object~exp)}\\
{\LBr} ... {\RBr}\\
\MHead{public Expression}{syntaxError}{(String~message)}\\
{\LBr} ... {\RBr}\\
\end{Class}

The {\tt rewrite} method converts a Scheme source form to
an {\tt Expression}.  The {\tt syntaxError} method is called when
a syntax error is seen.  It prints out the current
source filename and line number with the given {\tt message}.

A {\tt ModuleExp} represents a top-level form.

\begin{Class}{ModuleExp}{ extends LambdaExp}
\MHead{public Object}{eval\_module}{(Environment~env)}\\
\LBr\+\\
  if (body\_is\_simple) \Comment{Optimization}\\
  \Tab return body.eval (env);\\
  Object v = eval (env);\\
  return ((ModuleBody) v).run (env);\-\\
\RBr\\
\end{Class}

{\tt ModuleExp} is a sub-class of {\tt LambdaExp},
since it is actually a dummy function created by
wrapping the top-level forms in an implicit {\tt lambda}.
The {\tt eval\_module} method evaluates the top-level forms.
It invokes the {\tt eval} in {\tt LambdaExp} (which invokes the compiler).
The result of {\tt eval} is a {\tt ModuleBody} (see section \ref{ModuleBody}),
which we can {\tt run}.  If the {\tt body} is ``simple''
we don't bother actually evaluating the {\tt ModuleExp},
since that entails compiling it to a bytecoded class;
we just {\tt eval} the {\tt body} instead.

\section{Syntax and Macros}

\begin{Class}{Syntax}{}
\MHead{public abstract Expression}{rewrite}{(Object~obj, Translator~tr);}\\
\end{Class}

The {\tt rewrite} method in {\tt Translator} checks for
syntactic keywords and macros.  If the {\tt car} of
a ``call'' is a {\tt Syntax} or if it is a {\tt Symbol}
that is bound to a {\tt Syntax}, then its {\tt rewrite}
method is called.

As an example, this trivial class implements {\tt quote}.

\begin{Class}{quote}{ extends Syntax}
\MHead{public Expression}{rewrite}{(Object~obj, Translator~tr)}\\
\LBr\+\\
    \Comment{Error-checking is left out.}\\
    Object value = ((Pair)obj).car;\\
    return new QuoteExp(value);\-\\
\RBr
\end{Class}

Much more complicated is the {\tt Syntax} that implements
{\tt define-syntax}.

\begin{Class}{define\_syntax}{ extends Syntax}
\MHead{public Expression}{rewrite}{(Object~obj, Translator~tr)}\\
{\LBr}\+\\
  enter (new SyntaxRules (...));\-\\
{\RBr}\\
\end{Class}

The result is a {\tt SyntaxRules} object, which contains an encoded
representation of the patterns and templates in the {\tt syntax-rules}.
This is in its own right a {\tt Syntax} object.

\begin{Class}{SyntaxRules}{ extends Syntax}
SyntaxRule[] rules;\\
\MHead{public Expression}{rewrite}{(Object~obj, Translator~tr)}\\
\LBr\+\\
    Object[] v = new Object[maxVars];\\
    for (int i = 0;  i < rules.length;)\\
      \LBr\+\\
        SyntaxRule r = rules[i++];\\
        if (r.match (obj, v))\\
        \Tab return r.execute\_template(v, tr);\-\\
      \RBr\\
    return tr.syntaxError\\
    \Tab ("no matching syntax-rule");\-\\
\RBr\\
\end{Class}

Contrast evaluating a procedure definition ({\tt lambda}), which
causes a new \emph{sub-class} of {\tt Procedure} to be created and compiled,
while evaluating a {\tt define-syntax} only causes a new \emph{instance}
of {\tt SyntaxRules} to be created.  This is because the {\tt syntax-rules}
can be represented using relatively simple and compact data structures.
A traditional low-level macro facility specifies the transformations using
executable code, and that probably would need a new
{\tt Procedure} sub-class.

\section{Code generation}

A {\tt Compilation} object keeps track of the classes, methods, and
temporary state generated as a result of compiling a
single top-level {\tt ModuleExp}.

\begin{Class}{Compilation}{}
ClassType[] classes;\\
boolean immediate;\\
\MHead{public ClassType}{addClass}{(LambdaExp~lexp, String name)}\\
{\LBr} ... {\RBr}\\
\MHead{public}{ClassType}{(ModuleExp~exp, ...)}\\
{\LBr} ...; addClass (exp, ...); {\RBr}\\
\end{Class}

Each {\tt Compilation} may create one or more {\tt ClassType}
objects, each of which generates
the bytecodes for one class.  Each {\tt ClassType} is generated
from a {\tt LambdaExp}, including the top {\tt ModuleExp}.
The boolean {\tt immediate} is true if we are compiling for immediate loading,
and is false if the target is one or more {\tt .class} files.

The {\tt addClass} method does all the work to
compile a given {\tt LambdaExp}.  It creates a {\tt ClassType},
adds it to {\tt Compilation}'s {\tt classes} array,
and generates {\tt Method} objects for the constructor and the main
{\tt apply{\it X}} method.  Once the {\tt apply{\it X}} {\tt Method}
has been created, {\tt addClass} emits some bytecodes to set up the
incoming parameters, and then invokes the virtual {\tt compile}
method on the body of the {\tt LambdaExp}, which generates
the code that does the actual work of the procedure.

The {\tt Compilation} constructor gets a {\tt ModuleExp},
which it passes to {\tt addClass}.  The {\tt compile}
method of {\tt LambdaExp} (which gets called for all {\tt lambda}s
except the dummy top-level) also calls {\tt addClass} to generate
the class corresponding to the {\tt lambda}, and then it emits
instructions to create a new instance of the generated {\tt Procedure} class,
and pushes it on the Java stack.

\section{The {\tt codegen} package}

The {\tt ClassType} and {\tt Method} classes are in a separate
{\tt codegen} package, which is an intermediate-level
interface to code generation and Java {\tt .class} files.
It is essentially independent of Scheme or the rest of Kawa,
and could be used for generating code for other languages.

\begin{Class}{ClassType}{ extends Type}
CpoolEntry[] constant\_pool;\\
Method methods; \Comment{List of methods.}\\
Field fields; \Comment{List of fields.}\\
\MHead{public Field}{new\_field}{(String~name, Type~type, int~flags)}\\
{\LBr} {\it Create new field.} {\RBr}\\
\MHead{public method}{new\_method}{(String~name, ...)}\\
{\LBr} {\it Create new method.} {\RBr}\\
\MHead{public void}{emit\_to\_stream}{(OutputStream~stream)}\\
{\LBr} ... {\RBr}\\
\MHead{public void}{emit\_to\_file}{(String~filename)}\\
{\LBr} ... {\RBr}\\
\MHead{public byte[]}{emit\_to\_array}{()}\\
{\LBr} ... {\RBr}\\
\end{Class}

The {\tt ClassType} class is the main class of the {\tt codegen} package.
It  manages a list {\tt Field}s , a list of {\tt Method}s,
and the constant pool.
There are utility methods for adding new fields, methods, and constant
pool entries.

When the {\tt ClassType} has been fully built, the \verb|emit_to_file| method
can be used to write out the contents into a file.
The result has the format of a {\tt .class} file \cite{JavaVmSpec}.
Alternatively, the class can be written
to an internal byte array (that has the same layout as a {\tt .class}
file) using the \verb|emit_to_array| method.
The resulting byte array may be used by a {\tt ClassLoader}
to define a new class for immediate execution.
Both of the these methods are implemented on top of the more
general \verb|emit_to_stream|.

The largest class in the {\tt codegen} package is {\tt Method}.

\begin{Class}{Method}{}
\MHead{Variable}{new\_local}{(Type~type, String~name)}\\
{\LBr} ... {\RBr}\\
\MHead{public void}{compile\_push\_value}{(Variable~var)}\\
{\LBr} ... {\RBr}\\
\MHead{public void}{compile\_push\_int}{(int~i)}\\
{\LBr} ... {\RBr}\\
\MHead{public void}{compile\_linenumber}{(int~linenumber)}\\
{\LBr} ... {\RBr}\\
\end{Class}

As an example of the level of functionality,
\verb|compile_push_int| compiles code to push an integer {\it i} on stack.
It selects the right instruction, and if {\it i} is too
big for one of the instructions that take an inline value,
it will create a constant pool entry for {\tt i},
and push that.

The method {\tt new\_local} creates a new local variable
(and makes sure debugging information is emitted for it),
while {\tt compile\_push\_value} pushes the value of
the variable on the stack.

Kawa calls {\tt compile\_linenumber} to indicate that the current location
corresponds to a given line number.  These are emitted in the
{\tt .class file}, and most Java interpreters will use them
when printing a stack trace.

\section{Literals}

A Scheme quoted form or self-evaluating form expands to a {\tt QuoteExp}.
Compiling a {\tt QuoteExp} would seem a trivial exercise, but it is not.
There is no way to embed (say) a list literal in Java code.
Instead we create a static field in the top-level class
for a each (different) {\tt QuoteExp} in the body we are compiling.
The code compiled for a {\tt QuoteExp} then just needs
to load the value from the corresponding static field.
The tricky part is making sure that the static field gets
initialized (when the top-level class is loaded) to the
value of the quoted form.

The basic idea is that for:

\begin{verbatim}
(define (foo) '(3 . 4))
\end{verbatim}

we compile:

\begin{ClassNoDots}{class}{foo}{ extends Procedure0}
Object static lit1;\\
\MHead{public}{foo}{()}\\
\LBr \Comment{Initializer}\\
\Tab lit1 = new Pair(\pushtabs\=IntNum.make(3),\\
\Tab\Tab\poptabs IntNum.make(4));\\
\RBr\\
\MHead{public Object}{apply0}{()}\\
{\LBr} return lit1; {\RBr}\\
\end{ClassNoDots}

When the compiled class {\tt foo} is loaded, we do:

\begin{Code}
Class fooCl = Class.forName("foo");\\
Procedure fooPr = (Procedure)\\
\Tab fooCl.newInstance ();\\
\hbox{ }\\
\Comment{Using foo:}\\
Object result = fooPr.apply0 ();\\
\end{Code}

How does the Kawa compiler generate the appropriate {\tt new Pair}
expression as shown above?  A class whose instances may appear
in a quoted form implements the {\tt Compilable} interface:

\begin{ClassNoDots}{interface}{Compilable}{}
\MHead{Literal}{makeLiteral}{(Compilation~comp);}\\
\MHead{void}{emit}{(Literal~literal, Compilation~comp);}\\
\end{ClassNoDots}

The {\tt makeLiteral} creates a {\tt Literal} object
that represents the value of {\tt this} object.
That {\tt Literal} is later passed to {\tt emit}, which emits
bytecode instructions that (when evaluated) cause a value
equal to {\tt this} to be pushed on the Java evaluation stack.

This two-part protocol may be overkill, but it makes it
possible to combine duplicate constants and it also
supports circularly defined constants.  (Standard Scheme does not
support self-referential constants, but Common Lisp does.
See section 25.1.4 {\it Similarity of Constants} in
\cite{Steele:common-lisp-2}.)

It is likely that the {\tt Compilable} interface will
be replaced in the future with the serialization features
of JDK~1.1.

If we are compiling for immediate execution, we do not need
to generate code to regenerate the literal.  In fact, we want to
re-use the literal from the original source form.
The problem is passing the source literal to the
byte-compiled class.  To do that, we use the {\tt CompiledProc}
interface.

\begin{ClassNoDots}{interface}{CompiledProc}{}
\MHead{public abstract void}{setLiterals}{(Object[]~values);}\\
\end{ClassNoDots}

An immediate class compiled from a top-level form implements
the {\tt CompiledProc} form.  After an instance of the {\tt ModuleBody}
has been created, it is coerced to a {\tt CompiledProc}, and
{\tt setLiterals} is called.  The argument to {\tt setLiterals}
is an array of the necessary literal values, and the method
that implements it in the compiled code causes the array of literal
values to be saved in the {\tt ModuleBody} instance, so it can
be accessed by the compiled code.

\section{Low-level procedures}

Using a named global {\tt Procedure} object has a bit of overhead.
We refer to it by name, and finding the right {\tt Procedure} is
done by a run time name lookup.  Once we have the procedure,
we do a virtual method call to apply the procedure, which is
relatively fast, but we would like to be able to inline
known functions.  Also, in the future, we want to support type
declarations and the use of machine types such as {\tt int}.
Having to convert an {\tt int} to an {\tt IntNum} just because
that is what the apply interface requires is expensive.

\label{LowProc}
Another problem is that being able to call a Java method
from Scheme requires writing by hand a new {\tt Procedure} subclass.
This is not a friendly interface.

The plan is to provide new syntax for defining Scheme procedures in terms
of Java methods.  The syntax will look something like:

\begin{Code}
(define-virtual exec-process\\
\Tab\Tab "java.lang.RunTime" "exec"\\
\Tab\Tab "java.lang.Process"\\
\Tab\Tab ("java.lang.String"))\\
(set! ls (exec-process "ls -l"))\\
\end{Code}

The primitive syntax {\tt define-syntax} defines a {\tt PrimitiveProcedure}
object (which inherits from {\tt PrcedureN}), which refers to
a named virtual method in a named class with specified
parameter and return types.
The primitives {\tt define-static} and {\tt define-interface}
are similar, but for static and interface methods.

When the {\tt compile} method of {\tt ApplyExp} sees that the function
is a {\tt PrimitiveProcedure}, it will emit code to call the method.
It will also emit code to coerce the arguments to the required types.
It will not do any checking that the method actually exists and
has declared type, since the method may not be available yet
(and it is also a pain to do, though the JDK~1.1 reflection
facility will make it easier).

The name declared by {\tt define-virtual} has the same scope
as that of a macro.  It must be seen at compile-time.
A {\tt PrimitiveProcedure} cannot be applied or called at top-level
interactively.

We can lift these restrictions when Kawa switches
to JDK 1.1 and its reflective features.  In that case, using
a {\tt PrimitiveProcedure} may be the preferred way to define
many builtin functions.  The advantage is simpler declarations,
fewer standard classes, much faster invocation when the compiler
knows which method is being called, but at the cost of somewhat
slower calls when we have to use the general {\tt applyN} interface,
which would use the probably slower reflection facilities.

\section{Continuations}

Scheme continuations ``capture'' the current execution
state.  They can be implemented by copying the stack, but
this requires non-portable native code.  Kawa continuations
are implemented using Java exceptions, and can be used to
prematurely exit (throw), but not to implement co-routines
(which should use threads anyway).

\begin{Class}{callcc}{ extends Procedure1}
\MHead{public Object}{apply1}{(Object~arg1)}\\
\LBr\+\\
    Procedure proc = (Procedure) arg1;\\
    Continuation cont\\
    \Tab = new Continuation ();\\
    try {\LBr} return proc.apply1(cont); \RBr\\
    catch (CalledContinuation ex)\\
      \LBr\+\\
        if (ex.continuation != cont)\\
          \Tab throw ex;  \Comment{Re-throw.}\\
        return ex.value;\-\\
      \RBr\-\\
\RBr\\
\end{Class}

This is the {\tt Procedure} that implements
{\tt call-with-\discretionary{}{}{}current-\discretionary{}{}{}continuation}.
It creates {\tt cont}, which is the ``current continuation'',
and passes it to the incoming {\tt proc}.
If {\tt callcc} catches a {\tt CalledContinuation} exception it means
that {\tt proc} invoked some {\tt Continuation}.  If it is ``our''
continuation, return the value passed to the continuation;  otherwise
re-throw it up the stack until we get a matching handler.
(I have left out code to detect unsupported invocation of {\tt cont}
after {\tt callcc} returns.)

\begin{Class}{Continuation}{ extends Procedure1}
\MHead{public Object}{apply1}{(Object~arg1)}\\
\LBr\+\\
    throw new CalledContinuation\\
	\Tab\Tab (arg1, this);\-\\
\RBr\\
\end{Class}

A {\tt Continuation} is the actual continuation object
that is passed to {\tt callcc}'s argument;
when it is invoked, it throws a {\tt CalledContinuation}
that contains the continuation and the value returned.

\begin{Class}{CalledContinuation}{\\\Tab\Tab extends RuntimeException}
Object value;\\
Continuation continuation;\\
\CHead{CalledContinuation}{(Object~value, Continuation~continuation)}\\
\LBr\+\\
    super ("call/cc called");\\
    this.value = value;\\
    this.continuation = continuation;\-\\
\RBr\\
\end{Class}

{\tt CalledContinuation} is the exception that is thrown
when the continuation is invoked.

\section{Tail-calls}

Scheme requires that tail-calls be implemented without
causing stack growth.  This is difficult to do
portably in Java (or for that matter in C), since implementing
it efficiently requires low-level access to the hardware stack.
There are tricks one can use (a function returns a pointer to the
next function to be called, rather than calling it directly), but
these are rather expensive, especially in Java (which does not
have function pointers).

Compiler optimizations can re-write many tail-calls into
{\tt goto}s.  The most important case is self-tail-calls
or tail recursion.  Kawa rewrites these
when it can prove that is safe.  It is rather
conservative:  it must be able to prove that the procedure
binding cannot be re-assigned to some other value.  Thus
only {\tt letrec} tail-recursion is supported, not
tail-recursion of global procedures.  This restriction may
be excessively paranoid, but it is required by the language,
and it is sufficient to optimize the standard {\tt do}
and named-{\tt let} forms.  A future version will provide a way
to specify that Kawa can be less conservative (using either a
module system or compiler switches).

While full tail-call elimination will probably never be supported
by Kawa (except perhaps on modified Java interpreters),
some forms of mutual tail-recursion can be eliminated with
more sophisticated compiler analysis, though there are no concrete
plans for that yet.

\section{Class, types, and declarations}
\label{Types}
An extensive type system that supports user-defined classes is
important for extensibility and for integration with other Java packages.
This section describes current ideas for future extensions.

The record extension proposed (and rejected) for R5RS will
probably be added.  It has been partially written; however
a new implementation based on the JDK 1.1 reflective features
seems preferable, since that means the record accessor
features can be used on arbitrary Java objects.
%This feature will then integrate with the first-class types feature.
After than, the next step is to add methods, and we have a way to define
and access Java classes from Scheme.

Type declarations and some form of first-class
types are also planned.  This will improve documentation,
error-checking, and code efficiency.  Among the types to be
supported are ``unboxed'' number types, so the compiler
could use raw {\tt double} instead of having to allocate
a {\tt DFloNum} object.  In addition to allowing better code,
this feature will also make it it easier to integrate with
primitive Java types.  (The {\tt define-virtual} syntax in
section~\ref{LowProc} will be extended to support type values.)

Some kind of module system is desirable.  One reason is to
control names and names clashes;  another reason is so that
the compiler can map global variables references to their
definitions. This makes it easier to do better optimizations.
It is tempting to define a module as a kind of class:
A simple module is a packaging of data and function definitions,
and it is easy to map these into static fields and methods of a class.
Controlling which components are exported is similar to
specifying visibility ({\tt public} or {\tt private}).
What is more challenging is how to model import lists,
or module signature/interfaces.  Perhaps we can use Java interface types.

Given all this new infrastructure (types and modules),
then the compiler will need some re-writing.  At the very least it
needs to know that expressions may have other types than just
plain {\tt Object}.


\section{Current and Future Work}

There is very  preliminary threads support in Kawa.
It provides an interface to Java threads that looks
somewhat like {\tt delay}, except that the delayed expression
is evaluated in a new thread.  (The model is similar to
to the ``futures'' concept of MultiScheme \cite{Miller:phd:1987},
but there is no implicit force, at least yet.)  Recent re-implementation
of core classes (such {\tt Environment} and {\tt Translator})
has been done to support threads with optionally separate
top-level environments.

An interface to graphics primitives is needed, but no work has been
done.  Unfortunately, Java's Abstract Windowing Toolkit is commonly
considered among the weaker parts of Java, and lacks important
features, such as a decent multi-line text editor.

More sophisticated Scheme code rewriting, optimizations,
and inlining should also be investigated after Kawa has been
taught to know about types as discussed in section~\ref{Types}.

One important goal of Kawa is that it should support
multiple languages.  This includes an interface to plug in
new parsers, pre-defined functions, data types, and output
formatting.
Of special interest is re-implementing some of the ideas and syntax
from my earlier Q language  \cite{PBthesis}. These include a
line-oriented syntax with fewer parentheses, and high-level
sequence and array operations (as in APL).

Also of interest is support for Emacs Lisp.
This would require an extensive library to implement the Emacs
data types (such as buffers and windows), in addition to the
challenges of the Emacs Lisp language itself (it has different
data types and name binding rules than Scheme), but may be
a good way to build a next-generation Emacs.

\section{Conclusion}

Kawa is a solid implementation of Scheme with many features.
It is portable to any environment that can run Java applications.
It has active use and development.
I have not bothered running benchmarks, because the state
of the art in Java implementation is in such flux, because
many optimizations are planned but have not been implemented,
and because the different feature sets of the various Scheme implementations
makes them difficult to compare fairly.
But Kawa has the potential of being
a reasonably fast Scheme implementation (though probably never
among the very fastest), and will reap benefits from current
efforts in Java compilation \cite{GccJava}.

\bibliographystyle{latex8}
\bibliography{mine}

\section*{Biographical Information}
{\bf Per} Magnus Alfred {\bf Bothner} studied at
the University of Oslo, Norway,
and received his {Ph.D.} in Computer Science from Stanford University in 1989.
He then worked for Digital Equipment; University of
Wisconsin; and has worked for Cygnus since 1991.
He can be reached at {\tt <bothner@cygnus.com>}
or {\tt <bothner@gnu.ai.mit.edu>}.

His highly unimpressive home page is
{\tt http:\discretionary{}{}{}//www.cygnus.com/\verb|~bothner|},
but at least it tells you where to get Kawa.

\end{document}