# Alternative to compute-discriminating-function protocol

• To: MOP.pa@Xerox.COM
• Subject: Alternative to compute-discriminating-function protocol
• From: Danny Bobrow <bobrow@parc.xerox.com>
• Date: Wed, 13 Jun 90 21:04:10 -0700 (PDT)
• References: <9006121818.AA22774@roo.parc.xerox.com>, <QaRJOlQB0KGg086RsC@nero.parc.xerox.com>

This message suggests an slight alternative to the current set of
generic functions that make up the protocol for computing the
discriminating function and effective method of a generic function.  It
takes as a premise that systems will often do class-based caching of
effective methods, and provides a direct interface for that
functionality.  I first describe the basic idea (worked out by Jim
desRivieres and myself), and then provide an alternative set of proposed
function pages.

--
When a generic function is invoked, the discriminating function must
determine an effective method created from the methods applicable to the
arguments. Depending on the generic function and the arguments, this is
done in one
of three ways: using a cached value;
calling {\bf compute-cacheable-method-using-classes};
or calling {\bf compute-effective-method} on the result of {\bf
compute-applicable-methods}.

The generic function {\bf compute-cacheable-method-using-classes}
computes such an effective method using only the classes of the required
arguments to the function.  If it returns an effective method, this can
be used and cached (see details below).

If it returns nil, then the "classical" mechanism for computing the
effective method for the specific arguments is used.

The generic function {\bf compute-applicable-methods-using-classes} can
be used by  {\bf compute-cacheable-method-using-classes} in constructing
the cacheble effective method.  The former returns two values, an
ordered list of methods with only class specializers, and a second list
of other methods that might be applicable given only the classes of the
required arguments.  For standard-generic-functions, these would be all
methods with EQL specializers of the given classes.  More details below.

-----
\begingfcom{compute-applicable-methods}

\label Syntax:

\Defgen {compute-applicable-methods} {generic-function arguments}

\label Arguments:

The {\it generic-function} argument is a generic function metaobject.

The {\it arguments} argument is a list of objects.

\label Values:

This generic function returns a possibly empty list of method
metaobjects.

\label Purpose:

The generic function {\bf compute-applicable-methods} determines the
method applicability of a generic function given a list of required
arguments for the generic function.  The returned list of method
metaobjects is sorted by precedence order with the most specific method
is first.  If no methods are applicable to the supplied arguments the
empty list is returned.

When a generic function is invoked, the discriminating function must
determine an effective method to be applied to the arguments.
Depending on the generic function and the arguments, this is done in one
of three ways: using a cached value; calling {\bf
compute-cacheable-method-using-classes}; or calling {\bf
compute-effective-method} on the result of {\bf
compute-applicable-methods}.  Refer to the description of {\bf
compute-discriminating-function} for the details of this process.

For any given generic function and set of arguments, if {\bf
compute-cacheable-method-using-classes} returns a non-nil value, this
must be an effective method; the values returned
and side-effects from calling this method must be identical to using
those values and side effects
from a corresponding call to {\bf
compute-effective-method} on the result of a call to {\bf
compute-applicable-methods}.  The results are undefined if this is not
the case.

The {\it arguments} argument must have at least as many elements as the
generic function accepts required arguments.  If fewer arguments are
supplied, an error is signalled.

\label Methods:

\Defmeth {compute-applicable-methods}
{\vtop{\hbox{({\it generic-function}
standard-generic-function)}
\hbox{{\it arguments\/}}}}

This method signals an error if any method of the generic function has a
specializer which is not either a class metaobject or a list of the form
{\bf(eql {\it object})}.

Otherwise, this method computes the sorted list of applicable methods
according to the rules described in the section of Chapter 1 called
Method Selection and Combination''.

This method can be overridden.  Because of the consistency requirements
between this generic function and {\bf
compute-cacheable-method-using-classes}, doing so may require also
overidding
\method{compute-cacheable-method-using-classes}{standard-generic-function
t}.

Method Lookup Protocol''

{\bf compute-cacheable-method-using-classes}

{\bf compute-discriminating-function}

\endcom

\begingfcom{compute-applicable-methods-using-classes}

\label Syntax:

\Defgen {compute-applicable-methods-using-classes} {generic-function
classes}

\label Arguments:

The {\it generic-function} argument is a generic function metaobject.

The {\it classes} argument is a list of class metaobjects.

\label Values:

This generic function returns two values.  Both are possibly empty
lists of method metaobjects.  The first is an ordered list of methods
whose specializers are all classes.  The second is a list of other methods
that might be applicable knowing only the classes of the arguments (e.g.
all the methods with EQL specializers in the same class).

\label Purpose:

The generic function {\bf compute-applicable-methods-using-classes} is
called to attempt to determine the method applicability given only the
classes of the required arguments to the generic function.

If it is possible to completely determine the ordered list of applicable
methods based only on the supplied classes, this generic function
returns that list as its first value and nil as its second value.  The
returned list of method metaobjects is sorted by precedence order, the
most specific method is first.  If no methods are applicable to the
specified arguments the empty list is returned.

If it is not possible to completely determine the ordered list of
applicable methods based only on the supplied classes, this generic
function returns the rest of the methods in the second value,
potentially unordered.  This generic function is designed to be used
with
{\bf compute-cacheable-method-using-classes} which would use these
two lists to compute code that would produce code to do run time
discrimination to determine the applicability of methods on the second list.

For any given generic function and set of arguments, if {\bf
compute-applicable-methods-using-classes} returns a second value of
nil, the first value must be equal to the value returned by {\bf
compute-applicable-methods}.  The results are undefined if this is not
the case.

\newpage

\label Methods:

\Defmeth {compute-applicable-methods-using-classes}
{\vtop{\hbox{({\it generic-function}
standard-generic-function)}
\hbox{({\it classes\/} t)}}}

In cases where the generic function has no methods with {\bf eql}
specializers, or has no methods with {\bf eql} specializers which could
be applicable to arguments of the supplied classes, this method returns
the ordered list of applicable methods as its first value and nil as
its second value.

This method can be overridden. Because of the consistency requirements
between this generic function and {\bf compute-applicable-methods},
doing so may require also overidding
\method{compute-applicable-methods}{standard-generic-function t}.

\endcom

\begingfcom{compute-cacheable-method-using-classes}

\label Syntax:

\Defgen {compute-cacheable-method-using-classes} {generic-function
classes}

\label Arguments:

The {\it generic-function} argument is a generic function metaobject.

The {\it classes} argument is a list of class metaobjects.

\label Values:

This generic function returns an effective method, or nil.  The
effective method is any Common Lisp form, allowing the addition of the
locally defined special forms {\bf method-arg} plus those described with
respect to method-combination. {\bf method-arg}  provides a mechanism
for the effective method code to refer to arguments of the method.  It takes
a single argument, n,  a non-negative integer which must less than the
number of
required arguments to the generic function.

\label Purpose:

The generic function {\bf compute-cacheable-method-using-classes} is
called to attempt to determine an effective method given only the
classes of the required arguments to the generic function.  How it does
this is not specified, though it may call {\bf compute-effective-method}
and {\bf compute-applicable-methods-using-classes}.

When a generic function is invoked, the discriminating function must
determine the ordered list of methods applicable to the arguments.
Depending on the generic function and the arguments, this is done in
one of three ways: using a cached value; calling {\bf
compute-cacheable-method-using-classes}; or calling {\bf
compute-effective-method} on the result of calling {\bf
compute-applicable-methods}.  Refer to the description of {\bf
compute-discriminating-function} for the details of this process.
The value returned by {\bf compute-cacheable-method-using-classes} is
known to depend only on the definitions of the classes of the required
arguments, and the contents of the generic function, and the system
will be responsible for ensuring the consistency of any cache if these
change in any way.  If there are other dependencies, then the user is
responsible for calling {\bf forget-cacheable-methods}
on the generic function to ensure that
any cache is cleared.

\newpage

\label Methods:

\Defmeth {compute-cacheable-method-using-classes}
{\vtop{\hbox{({\it generic-function}
standard-generic-function)}
\hbox{({\it classes\/} t)}}}

If any method of the generic function has a specializer which is neither
a class metaobject nor a list of the form {\bf(eql {\it object})}, this
method returns nil.

Otherwise this method returns an effective method.

This method can be overridden. Because of the consistency requirements
between this generic function and {\bf compute-applicable-methods},
doing so may require also overidding
\method{compute-applicable-methods}{standard-generic-function t}.

\label Remarks:

This generic function exists to support extensions which modify the
rules of method applicability but which base the new, modified rules
only on the classes of the arguments to the generic function.  .

An extension which bases method applicability on properties of the
arguments to the generic function other than their class, as is the
case with {\bf eql} specializers, can be implemented in one of two ways.

The first involves a method on this generic function which returns an
appropriate value.  For example, it create a piece of code that
discriminates on the values of the given arguments at run time (either
using case for example, or a hash-table).

The second involves definining a method on {\bf
compute-discriminating-function}.  The discriminating function returned
by this method implements the desired method applicability rules
directly without making any calls to {\bf compute-applicable-methods} or
{\bf compute-cacheable-method-using-classes}.

Method Lookup Protocol''

{\bf compute-applicable-methods}

\{bf compute-applicable-methods-using-classes}

{\bf compute-discriminating-function}

\endcom

\begingfcom{compute-discriminating-function}

\label Syntax:

\Defgen {compute-discriminating-function} {generic-function}

\label Arguments:

The {\it generic-function} argument is a generic function metaobject.

\label Values:

The value returned by this generic function is a function.

\label Purpose:

The generic function {\bf compute-discriminating-function} is called to
determine the discriminating function for a generic function.  When a
generic function is called, the discriminating function is called to
implement the behavior of calling the generic function:  determining the
ordered set of applicable methods, determining the effective method, and
running the effective method.

To determine the effective method, the discriminating
function first calls {\bf compute-cacheable-method-using-classes}.  If
{\bf compute-cacheable-method-using-classes} returns a nil value, the
discriminating function then calls {bf compute-effective-method} on the
result of calling {\bf compute-applicable-methods}.

When {\bf compute-cacheable-method-using-classes} returns a non-nil
value, the discriminating function is permitted to memoize the
value as follows.  If the generic function is called
again with required arguments which are instances of the same classes;
and the generic function has not been reinitialized,
{\bf forget-cacheable-methods} has not been called;
and no method has been added to the generic function;
and no method has been removed from
the generic function; and for all the specializers of all the generic
function's methods which are classes the class precedence list has not
changed; for any such memoized value, no class precedence list of the
required argument classes has changed; then the discriminating function
may reuse the effective method without calling {\bf
compute-cacheable-method-using-classes} again.

When the effective method is run, each method's function is called using
the result of calling {\bf method-function-applier}.

The result of {\bf compute-discriminating-function} is intended to be
used as the discriminating function for {\it generic-function} and is
intended to replace all previous discriminating functions for {\it
generic-function}.  The result of {\bf compute-discriminating-function}
cannot be called directly with {\bf apply} or {\bf funcall}.  Instead,
once it has been installed with {\bf set-funcallable-instance-function},
the generic function itself can be called.  Once {\bf
compute-discriminating-function} is called, the result must be installed
before {\it generic-function} is called again.  Moreover the installed
discriminating function must not subsequently be replaced by a previous
result of {\bf compute-discriminating-function}.

This generic function is called, and the result is installed by {\bf
add-method}, {\bf remove-method}, {\bf initialize-instance} and {\bf
reinitialize-instance}.

\label Methods:

\Defmeth {compute-discriminating-function} {({\it generic-function}
standard-generic-function)}

This method returns a discriminating function as described above.

This method can be shadowed.  The shadowing method is permitted to call
{\bf call-next-method} and return a result which itself calls the result
of this method.

This method can be overridden.

The Method Lookup Protocol''

{\bf compute-applicable-methods}

{\bf compute-cacheable-method-using-classes}

{\bf compute-applicable-methods-using-classes}

{\bf compute-effective-method}

{\bf make-method-lambda}

{\bf method-function-applier}

\endcom

\begingfcom{compute-effective-method}

\label Syntax:

\Defgen {compute-effective-method} {generic-function method-combination
methods}

\label Arguments:

The {\it generic-function} argument is a generic function metaobject.

The {\it method-combination} argument is a method combination
metaobject.

The {\it methods} argument is a list of method metaobjects.

\label Values:

This generic function returns two values.  The first is an effective
method.  The second is a list of effective method options.

\label Purpose:

The generic function {\bf compute-effective-method} is called to
determine the effective method from a sorted list of method metaobjects.

The first value returned by this generic function is the effective
method.  The second is a list of effective method options, these have
the same syntax and interpretation as the options argument to the long
form of define method combination.

This generic function can be called by the user or the implementation.
It is called whenever a sorted list of applicable methods must be
converted to an effective method.  It is called by the result of \method
{compute-discriminating-function} {standard-generic-function}.

Because neither method nor method combination metaobjects can be
reinitialized, the results of this generic function may be memoized.

\label Methods:

\Defmeth {compute-effective-method}
{\vtop{\hbox{({\it generic-function}
standard-generic-function)}
\hbox{({\it method-combination}
standard-method-combination)}
\hbox{{\it methods}}}}

This method computes the effective method according to the rules of the
method combination type implemented by {\it method-combination}.

This method can be overridden.

\vskip 1.6pc

\Defmeth {compute-effective-method}
{\vtop{\hbox{({\it generic-function}
standard-generic-function)}
\hbox{({\it method-combination}
standard-simple-method-combination)}
\hbox{{\it methods}}}}

This method computes the effective method according to the rules of the
method combination type implemented by {\it method-combination}.

This method can be overridden.

Method Lookup Protocol''

Chapter 1 section --- Applying Method Combination to the Sorted List
of Applicable Methods''

{\bf define-method-combination}

{\bf compute-discriminating-function}

\endcom