% -*- Mode: LaTeX -*-

\section{Current Status and Future Optimizations}
\label{optimize}

The compilation scheme outlined in Section~\ref{compile} and the
reconstruction algorithm of Section~\ref{reconstruct} have been
implemented in the Id programming environment for Monsoon
\cite{Monsoon}. It might seem that our compilation scheme incurs a lot
of run-time overhead but our experience has been that realistic
programs contain very few (if any) non-type-conserving functions, so
the overhead of generating and propagating their type-hints is
reasonably small. Besides, this scheme permits the Id
debugger to reconstruct the types of all identifiers in
any Id program successfully which is an extremely desirable feature.

Although our current performance is adequate, we hope to be able to
improve our scheme through several compiler optimizations that are
discussed below.

\subsection{Rearranging the Hint Parameters}

Currently, all hint parameters that need to be added to a function
definition are placed in front of its regular parameters as shown in
Section~\ref{hint-gen}. This is not strictly necessary. We can place a
hint parameter anywhere before (or just after) the regular parameter
whose type contains the non-conserved type-variable that is encoded by
the hint parameter. This observation follows from
definition~\ref{conserve} by viewing every curried application closure
of a multiple-arity function as attempting to conserve the overall
type information contained in it either in the form of explicit type-hints
in its dynamic environment or in its remaining type signature. It
follows that only those hint parameters need to be placed up front
that correspond to the non-conserved type-variables in the types of
the free variables of a function.

The benefit of such rearrangement is that it may reduce 
the propagation overhead of type-hints by removing some extra
parameters altogether using $\eta$-reduction. For example, the following
alternate translation for Example~\ref{ex6} is also valid (compare
with Example~\ref{ex8}):

\begin{myexample}{ex9}
def f3 x = 
  \{ def h3 h3\_hint\_1 z = if length x == 1
                        then z:nil
                        else z:z:nil;
   in h3 \};
g3 = if ... 
     then f3 (1:nil) (tc "int" nil)
     else f3 (true:nil) (tc "bool" nil);
\end{myexample}

Here, the  parameter {\tt f3\_hint\_1} of {\tt f3} was pushed after its
parameter {\tt x} which made this $\eta$-reduction possible.

\subsection{Arity Analysis}
\label{arity}
Definition~\ref{conserve} conservatively prescribes that the only
type-variables that are conserved in a multiple-arity function are
those present in its final application type because the
function could be curried over its initial arguments. This definition
can be generalized to include the types of all the arguments present
at a call site, if that call site is guaranteed to be accessible
through the dynamic activation tree. This is true for
all first-order (or full-arity) applications of a function where all
its arguments are supplied at once. In such cases, all the
type-variables in the function's signature can be instantiated from
its call site, though it may still require type-hints to reconstruct
the types of its free variables.

In our current scheme, it is not possible to optimize away the
type-hints at a first-order application site of a function because it
may still need additional hint parameters in its definition due to
higher-order application sites present elsewhere. This is just a
consequence of our choice to provide type-hints by adding extra
parameters to a function's definition. Alternatively, we can either
generate a special first-order version of the function that does
not carry any type-hints and use it wherever possible, or choose another
mechanism for hint propagation that is transparent to the
usual parameter passing conventions. Then we would be able to tailor
the type-hints according to the information available at a particular
call site without affecting the function's definition. We are currently
investigating such schemes.

\subsection{Escape Analysis}

Along with first-order call site information, if the types of the free
variables of a function are also known to be reconstructible \via the
currently visible activation tree, then no extra types-hints may be
necessary in its definition even if it was determined to be
non-type-conserving by definition~\ref{conserve}. Escape analysis of
function closures offers this information.  Specifically, if analysis
shows that a function closure does not escape from the lexical scope
where it was defined, then the correct instantiations of its free
variables would still be available from the activation of this
ancestor in the activation tree. In that case, we do not need to set
up extra type-hints to reconstruct these instantiations within the
function's activation.

\subsection{Tail Calls}

Our current scheme does not deal with tail calls where the usual
caller--callee relationship is violated. A tail call removes the
caller's activation frame from the activation tree and connects the
callee to the parent of the caller directly. In such a situation, the
call site information for the callee is lost. Consider the following
example:

\begin{myexample}{ex10}
def f10 x = 1 + length x;
def g10 n = if n == 1
            then f10 (1:2:nil)
            else f10 (true:nil);
\vsp
ex9 = g10 ...;
\end{myexample}

Without tail calls, the type of {\tt x} in an activation of {\tt f10}
can be determined by locating its call site within the {\tt then} or
the {\tt else} branch of the conditional inside {\tt
g10}. But, if these applications were compiled as tail calls, then the
{\tt f10}'s activation will get directly connected to the top-level and
the call site information will be lost. 

It is easy to extend our scheme to deal with this situation. We simply
modify definition~\ref{conserve} to reflect the fact that no call site
information is available for {\tt f10} and therefore explicit
type-hints may be needed for all of its free type-variables. This
leads to the following translation:

\begin{myexample}{ex11}
def f10 f10\_hint\_1 x = 1 + length x;
def g10 n = 
  if n == 1
  then f10 (tc "int" nil) (1:2:nil)
  else f10 (tc "bool" nil) (true:nil);
\vsp
ex9 = g10 ...;
\end{myexample}

Now, all the type information is available from within the activation
of {\tt f10}. Of course, this scheme is not optimal because it ignores
the call site information even when it is available using regular
calling conventions. In order to incorporate that flexibility, we need
to generate site specific type-hints as described in Section~\ref{arity}.

\subsection{Compiled \vs Interpreted Schemes}

Goldberg showed in \cite{Goldberg91} how to {\em compile} function-specific
and site-specific garbage collection routines that understand the
structure and the liveness properties of the local variables of a
function. Our scheme, on the other hand, generates and {\em
interprets} encoded type information in order to reconstruct the types
of all local and free variables of a function. We do not take any
position on what to do with these types.  This strategy is adequate
and desirable for a source debugger because it may wish to manipulate
an object in many different ways. But, for a specific application like
garbage collection, a compiled scheme may be more efficient.

It is possible to apply the principle of type conservation
(definition~\ref{conserve}) and the information propagation strategy
(Section~\ref{hint-prop}) in any specific context to allow complete
analysis of run-time objects in that context. Specifically for garbage
collection, we can generate specialized GC-routine(s) for a function
instead of its type-map, parameterized by GC-routine parameters that
correspond to the free type-variables in its type-map. Then, we can
generate and propagate closures of GC-routines in the same way as
type-hints which will be picked up automatically by the GC-routine(s)
of a function from its activation frame. We will investigate such
garbage collection schemes for Id in the future.
