% This file is part of Oaklisp.
%
% This program is free software; you can redistribute it and/or modify
% it under the terms of the GNU General Public License as published by
% the Free Software Foundation; either version 2 of the License, or
% (at your option) any later version.
%
% This program is distributed in the hope that it will be useful,
% but WITHOUT ANY WARRANTY; without even the implied warranty of
% MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
% GNU General Public License for more details.
%
% The GNU GPL is available at http://www.gnu.org/licenses/gpl.html
% or from the Free Software Foundation, 59 Temple Place - Suite 330,
% Boston, MA 02111-1307, USA


\chapter{Methods}

In this chapter we describe how methods are created, represented, and
looked up.  This is intimately related to instance variable reference,
so we describe how that works here as well.

\subsection{Invoking Methods}

Methods are looked up by by doing a depth first search of the
inheritance tree.  Some Oaklisp code to find a method would look like
this,
\begin{verbatim}
(define (%find-method op typ)
  (let ((here (assq op (type-operation-method-alist typ))))
    (if (null? here)
        (any? (lambda (typ) (%find-method op typ))
              (type-supertype-list typ))
        (list typ (cdr here)))))
\end{verbatim}
Once this information is found, we need to find the offset of the
appropriate block of instance variables, put a pointer to the instance
variable frame in the \df{bp} register, set the other registers
correctly, and branch.
\begin{verbatim}
(define (%send-operation op obj)
  (let ((typ (get-type obj)))
    (destructure (found-typ method) (%find-method op typ)
      (set! ((%register 'current-method)) method)
      (set! ((%register 'bp))
            (increment-locative
               (%crunch (%data obj) %loc-tag)
               (cdr (assq found-typ (type-bp-offset-alist typ)))))
      (set! ((%register 'env)) (method-env method))
      (set! ((%register 'pc))
            (code-body-instr (method-code (%method))))))
\end{verbatim}

Of course, the actual code to find a method is written in C and has a
number of tricks to improve efficiency.

\begin{itemize}

\item
Simple lambdas (operations which have only one method defined at the
type \df{object}) are ubiquitous, so the overhead of method lookup is
avoided for them by having a \df{lambda?} slot in each operation.
This slot holds a zero if no methods are defined for the given
operation.  If the only method defined for the operation is for the
type \df{object} then the \df{lambda?} slot holds that method, and the
method is not incorporated in the \df{operation-method-alist} of type
\df{object}.  If neither of these conditions holds, the
\df{lambda?} slot holds \df{\#f}.

\item
To reduce the frequency of full blown method lookup, each operation
has three slots devoted to a method cache.  When \emph{op} is sent to
\emph{obj}, we check if the \df{cache-type} slot of \emph{op} is equal
to the type of \emph{obj}.  If so, instead of doing a method search and
finding the instance variable frame offset, we can use the cached
values from \df{cache-method} and \df{cache-offset}.  In addition,
after each full blown method search, the results of the search are
inserted into the cache.

Giving the \dfsw{-M} switch to a version of the emulator compiled with
\df{FAST} not defined will print an \texttt{H} when there is a
method cache hit and an \texttt{M} when there is a miss.  The method
cache can be completely disabled by defining
\df{NO\protect\_METH\protect\_CACHE} when compiling the emulator.  We
note in passing that we have one method cache for each operation.  In
contrast, the Smalltalk-80 \index{Smalltalk-80} system has an
analogous cache at each call point.  We know of no head to head
comparison of the two techniques, but suspect that if we were to
switch to the Smalltalk-80 technique we would achieve a higher average
hit rate at considerable cost in storage.

\item
In order to speed up full blown method searches, a move to front
heuristic reorders the association lists inside the types.  In
addition, the C code for method lookup was tuned for speed, is coded
inline, and uses an internal stack to avoid recursion.
\end{itemize}

For most of this tuning we used the time required to compile
\df{compile-bench.oak} as our primary benchmark for determining the
speed of generic operations, since the compiler is written in a highly
object-oriented style and makes extensive use of inheritance.



\subsection{Adding Methods}

A serious complication results from the fact that the type field in an
\df{add-method} form is not evaluated until the method is installed at
run time.  Since the target type for the method is unknown at compile
time the appropriate instance variable map is also unknown, and hence
the correct instance variable offsets cannot be determined.  Our
solution is to have the compiler guess the order\footnote{The compiler
guesses by attempting to evaluate the type expression at compile
time.} or simply invent one, compile the offsets accordingly, and
incorporate this map in the header of the emitted code block.  When
the \df{add-method} form is actually executed at run time, the assumed
instance variable map is compared to the actual map for the type that
is the recipient of the method, and the code is copied and patched if
necessary.  The code only needs to be copied in the rare case when a
single \df{add-method} is performed on multiple types that require
different offsets.

After instance variable references in the code block have been
resolved, which usually involves no work at all since the compiler
almost always guesses correctly, the method can actually be created
and installed.  Creating the method involves pairing the code block
with an appropriate environment vector containing references to
variables that have been closed over.  Because this environment vector
is frequently empty, a special empty environment vector is kept in the
global variable \df{\%empty-environment} so a new one doesn't have to
be created on such occations.  All other environment vectors are
created by pushing the elements of the environment onto the stack and
executing the \df{make-closed-environment} opcode.  Environment
vectors are never shared in our current implementation, with the
exception of the empty environment.

After the method is created it must be installed.  The method cache
for the involved operation is invalidated, and the method is either
put in the \df{lambda?} slot of the operation or the
\df{operation-method-alist} of the type it is being installed in.  If
there is already a value in the \df{lambda?} slot and the new method
is not being installed for type \df{object}, the \df{lambda?} slot is
cleared and the method that used to reside there is added to
\df{operation-method-alist} of type \df{object}.

\op{\%install-method-with-env}{type operation code-body environment}
\doc{This flushes the method cache of \emph{operation}, ensures that
the instance variable maps of \emph{code-body} and \emph{type} agree
(possibly by copying \emph{code-body} and remapping the instance
variable references), creates a method out of \emph{code-body} and
\emph{environment}, and adds this method to the \df{operation-method-alist}
of \emph{type}, modulo the simple lambda optimization if \emph{type} is
\df{object}.}

\op{\%install-method}{type operation code-body}
\doc{\macdef{}{(\%install-method-with-env \emph{type operation
code-body} \%empty-environment)}}

\op{\%install-lambda-with-env}{code-body environment}
\doc{\macdef{}{(\%install-method-with-env object (make operation)
\emph{code-body environment})} but more efficient.}

\op{\%install-lambda}{code-body}
\doc{\macdef{}{(\%install-method-with-env object (make operation)
\emph{code-body} \%empty-environment)} but more efficient.}