\documentclass{article}

\usepackage{hyperref}
\usepackage{alltt}
\usepackage{geometry}

\usepackage{natbib}

\def\name#1{\texttt{\hyphenchar\font=`-#1}}
\newcommand{\cl}[1]{\href{http://www.xach.com/clhs?q=#1}{\name{#1}}}
\newcommand{\mop}[1]{\name{mop:#1}}
\newcommand{\pcl}[1]{\name{pcl:#1}}

\newcommand{\gf}[2]{%
  \begin{flushleft}%
    \textit{Generic Function}~\name{#1}\\
    ~~~~Syntax:\\
    ~~~~\name{#1} #2%
  \end{flushleft}%
}%

\newcommand{\meth}[2]{%
  \begin{flushleft}%
    \textit{Primary Method}~\name{#1}~#2%
  \end{flushleft}%
}%

\title{CLOS discriminating functions and user-defined specializers}
\author{Christophe Rhodes\footnote{\texttt{c.rhodes@gold.ac.uk}}\\Goldsmiths, University of London\\New Cross, London SE14 6NW}

\begin{document}

\maketitle

\begin{abstract}
  We discuss the possibility for users of CLOS to extend the
  \mop{specializer} metaobject class in the \textit{de facto} standard
  Metaobject Protocol for Common Lisp, and how this possibility
  interacts with ANSI-standardized functionality.  To motivate the
  discussion, we provide two simple examples: a specializer on a
  disjunction of classes and a simple pattern-matching specializer; we
  note the extent to which they can be accomodated with the standard
  mechanisms, and detail the work done to support that in a
  contemporary implementation of the CLOS MOP in Steel Bank Common
  Lisp, and discuss the remaining open problems and scope for
  resolving them.
\end{abstract}

\section{Introduction}

Lisp has a venerable history of object-oriented programming; at one
point in time, early in the history of object-orientation, Flavors
\citep{flavors1986} and New Flavors, Common Objects, Object Lisp and
Common Loops \citep{commonloops1986} all coexisted.  The Common Lisp
Object System (CLOS) was incorporated into the language in June 1988
\citep[][Chapter 26]{CLtL2}, and when the ANSI Common Lisp standard
\citep{CLtS} was formalized in 1995, Common Lisp became the first
ANSI-standardized programming language with support for
object-oriented programming.

In addition, CLOS was developed in conjunction with the design of a
Metaobject Protocol (MOP), as exemplified in \citet{AMOP}.  Common
Lisp as standardized only includes a very small portion of this
metaobject protocol (for instance, a recommendation to use
\mop{slot-value-using-class} in \cl{slot-value}; some introspective
functionality such as \cl{find-method}; and arguably a little ability
for intercession in \cl{compute-applicable-methods}, though in fact
the standard does not require that \cl{compute-applicable-methods} be
called as part of generic function dispatch), and so to customize the
behaviour of the object system in Common Lisp, it is necessary to go
beyond the standard language.

Many Common Lisp implementations support some of the MOP, to varying
extents; a survey from a few years ago \citep{bradshaw2000} revealed
many aspects of MOP support as being incomplete, even at the coarse
level of specified classes and generic functions being unimplemented.
More recently, the
Closer\footnote{\url{http://common-lisp.net/project/closer/}} project
has provided both a set of test cases for implementations of the
Metaobject Protocol -- which has encouraged some implementations to
enhance their support for it\footnote{At the time of writing, the MOP
  implementation of Steel Bank Common Lisp \citep{sbcl} fails none of
  the Closer MOP test suite.} -- and a compatibility layer to provide
an environment as close as possible to that described in AMOP in major
implementations of Common Lisp.

This paper addresses primarily the issues found and resolved in
supporting simple uses of non-standard specializers.  Specifically, we
examine those uses for which certain simplifying assumptions can be
made, for example assumptions about ordering the specializers: either
that there is a unique order of specificity in all possible
specializers that are applicable to any given object, or else that any
ambiguities in ordering do not affect the result of calling the
generic function.  Even with these simplifying assumptions, it is
necessary to go beyond the standard portions of the Metaobject
Protocol to achieve integration of non-standard specializers with the
rest of the system.

The rest of this paper is organized as follows: after introducing some
details about the historical treatment of specializers in the CLOS
MOP, and other related work, this paper in section \ref{s:examples}
attempts to motivate the use of non-standard specializers by
presenting two simple examples.  We discuss the problems that were
overcome in providing the support for even simple examples of
non-standard subclasses of \mop{specializer} and enumerate other, open
problems in section \ref{s:future}, and finish by detailing one
particular avenue for possible further experimentation along with our
conclusions.

\subsection{Specializers in the CLOS MOP}

Closer is an evolving project, and does not at present test all
aspects of the Metaobject Protocol -- concentrating on the portions
which are most clearly described.  One aspect which has received
relatively little attention at the time of writing is the extensible
nature of the \mop{specializer} metaobject class, whose instances
represent a description of the set of objects in one argument position
to which a method with that specializer is applicable.

For \cl{defmethod}, there is only a surface syntax defined by the
Common Lisp standard, with \textit{parameter specializer names} being
class names for matching a class, and \texttt{(eql \textit{form})} for
specializers to match the value of \textit{form} in the lexical
environment.  However, for \cl{find-method}, the ANSI standard defines
a \textit{parameter specializer} as either a class or a list
\texttt{(eql \textit{value})}.

The Art of the Metaobject Protocol defines the objects backing the
surface syntax as being \cl{class}es themselves and objects of class
\mop{eql-specializer-object} obtained by calling
\mop{intern-eql-specializer}; both \cl{class} and
\mop{eql-specializer-object} are subclasses of \mop{specializer}.
There are discussions on the CLOS MOP mailing list between Gregor
Kiczales and David Moon about whether the nature of the
\mop{eql-specializer-object} is strictly incompatible with the
language which was eventually standardized by ANSI\footnote{Thanks to
  Pascal Costanza for bringing this exchange to the author's
  attention.}: Moon specifically points out the need for a
compatibility translation for elements of the the
\textit{specializers} argument to \cl{find-method}.

AMOP leaves open (does not disallow explicitly) user-defined
subclasses of \mop{specializer} (but standard methods on
\textit{e.g.}\ \cl{compute-applicable-methods} signal error on
non-standard specializer classes; we shall return to this point
later).  We can examine the historical record of the development of
CLOS by inspecting the source code of Portable Common Loops (PCL),
modified versions of which are used in a number of Common Lisp
implementations: PCL internally defines and uses a \pcl{class-eq}
specializer, which is applicable only to objects whose class is
\cl{eq} to the specializer's class object (as opposed to a normal
\cl{class} specializer, which is also applicable to objects whose
class is a subclass of the specializer).

Additionally, there is evidence that PCL developers were interested in
developing more esoteric specializers, as there are remnants of what
appears to be an experiment in implementing prototype-based dispatch:
in the source code supporting
\mop{compute-applicable-methods-using-classes}, there is incomplete
support for of \pcl{prototype} specializers, such as
\begin{alltt}
  (defun saut-prototype\footnotemark (specl type)
    (declare (ignore specl type))
    (values nil nil)) ; fix this someday
\end{alltt}
\footnotetext{\texttt{saut} here stands for \name{specializer-applicable-using-type}, a function internal to PCL for which this is one among several helper routines.}
\subsection{Related Work}

Predicate dispatching -- a dispatching system in which a method's
applicability is determined by calling an arbitrary predicate -- has
been discussed in \citet{ucko-predicate}, where the solution discussed
was to extend method qualifiers (arbitrary predicates not being
associated with any particular argument, and methods being
distinguished from each other only on the basis of qualifiers and
specializers).  The author notes portability difficulties with this
approach, which would likely still be present today: for example, some
implementations will only accept non-standard qualifiers if the
generic function has a non-standard method combination, while a strict
implementation of \cl{define-method-combination} will lead to errors
if methods are placed in the same method group with the same
specializers (irrespective of how their qualifiers later affect
dispatch).

\section{Worked Examples}
\label{s:examples}

\subsection{Disjunction specializer}

\begin{figure}
\begin{alltt}
  (defclass class1 () ())
  (defclass class2 () ())
  (defclass class3 () ())
  (defclass class4 (class1) ())

  (defgeneric foo (x)
    (:generic-function-class gf-with-or))

  (let ((specializer (ensure-or-specializer 'class1 'class2)))
    (eval `(defmethod foo ((x ,specializer)) t)))

  (assert (foo (make-instance 'class1)))
  (assert (foo (make-instance 'class2)))
  (assert (raises-error? (foo (make-instance 'class3))))
  (assert (foo (make-instance 'class4)))
\end{alltt}
\caption{Example code illustrating the semantics of a specializer on
  the disjunction of multiple classes.}
\label{f:orspec}
\end{figure}

The disjunction specializer we present here is applicable to arguments
that are subclasses of any of the classes of the specializer.  While a
disjunction specializer is not well-motivated from the point of view
of object-orientation -- classes whose instances share behaviour
should probably have that shared behaviour modelled by a common
superclass -- the implementation details of such a specializer are
illustrative of some points.

Firstly, such a disjunction specializer has a natural place within the
standard ordering of specializers: such a specializer is as specific
as a specializer representing a common direct superclass of the
classes in question.  If such a class in fact exists, then the tie can
be broken in an arbitrary (but consistent) way by choice of a suitable
convention.

The major point to note is that, despite this natural and unambiguous
ordering of the specializers, the entirety of
\cl{compute-applicable-methods} and
\mop{compute-applicable-methods-using-classes} need to be overridden
as the standard methods on those functions are specified to signal an
error if they encounter a specializer which is neither a \cl{class}
nor an \mop{eql-specializer}.  Because the standard methods are
otherwise opaque, there is no way of informing the system about a
`natural' ordering for the non-standard specializers, and so a large
amount of complex code needs to be written by the user of non-standard
specializers.

Additionally, some notion of specializer equality needs to be present,
so that method redefinitions behave as expected (removing an existing
method with the semantically same specializer).  In implementing the
disjunction specializer, we act conservatively by canonising unions to
the same, \cl{eql}, specializer object: this is again a non-trivial
operation, but it is necessary not only for \cl{find-method} to work
as expected but also for relatively simple implementations of
\mop{specializer-direct-methods} and
\mop{specializer-direct-generic-functions}.

\subsection{Pattern specializer}

A pattern specializer is perhaps more applicable in a well-founded way
to programming, though its connection to object-orientation is
tenuous.  However, the protocols exposed in the CLOS MOP provide a
convenient way to express functions using pattern-matching for
dispatch (as in ML or Haskell), without sacrificing the ability to
program in a dynamic fashion typically afforded by CLOS.\footnote{We
  could of course implement pattern functions simply using the same
  funcallable instances on which CLOS is typically implemented.  The
  benefits of using the existing CLOS MOP protocols are simplicity and
  parsimony; however, it is possible that an implementation of
  pattern-matching functions might wish not to document that it is
  implemented in this manner.}

\begin{figure}
\begin{alltt}
  (defgeneric simplify (x)
    (:generic-function-class pattern-gf/1))
  (defmethod simplify ((y _)) y)

  ;;; near the implementation of the * operator
  (defmethod simplify ((x (* _ 0))) 0)
  (defmethod simplify ((x (* 0 _))) 0)
  (defmethod simplify ((x (* _ 1))) (simplify (second x)))
  (defmethod simplify ((x (* 1 _))) (simplify (third x)))

  ;;; near the implementation of the + operator
  (defmethod simplify ((x (+ _ 0))) (simplify (second x)))
  (defmethod simplify ((x (+ 0 _))) (simplify (third x)))
\end{alltt}
\caption{An example for how a pattern-matching specializer might
  improve code locality, by encouraging the implementation of
  relevant portions of overarching functionality to be located near
  related definitions.  We have intentionally kept the
  pattern-matching language simple for presentational purposes.}
\label{f:simplify}
\end{figure}

An example of how we might wish to use a pattern-matching specializer
is shown in figure \ref{f:simplify}.  The application example is the
simplification module of a hypothetical computer algebra system, and
we suggest that it is reasonable to place methods for simplifying
expressions with given operators near the definition of other methods
relating to those operators, such as their semantics or possibly their
graphical representation, so that the addition of a new operator need
not involve editing of existing functions.

In this example, there is no strongly-defined unambiguous ordering for
the specializers: of the patterns \texttt{(\_~.~x)} and
\texttt{(y~.~\_)}, it is not clear which should follow the other.  Note
that in our example application for simplification, the same results
are obtained whichever of the specializers is treated as most specific
(\textit{e.g.} for an argument of \texttt{(*~1~1)} the return value
will be \texttt{1}, whichever of the applicable \texttt{*} patterns is
judged most specific.

The metaobject classes and support functions allowing the code in
figure \ref{f:simplify} to run are shown in figure \ref{f:classes}.
These, along with the overriding of
\mop{compute-discriminating-function} in figure \ref{f:discrim},
provide enough support for SBCL's CLOS implementation to function as
expected.  Note in particular that we again canonicalise specializers
so that specializers with the same semantics are \cl{eql}, and also
note the use of \pcl{make-method-specializers-form} to generate code
that creates the right specializer when evaluated.

Although we have assumed in figure \ref{f:simplify} that
the pattern matching specializers match list structure, it would be
straightforward to adapt the code in figure \ref{f:discrim} to match
instead patterns in a richer domain-specific data structure, while
keeping the lists as surface specializer syntax.

\begin{figure}
{\small%
\begin{alltt}
  (defclass pattern-specializer (specializer)
    ((pattern :initarg pattern :reader pattern)
     (direct-methods :initform nil :reader specializer-direct-methods)))
  (defvar *pattern-specializer-table* (make-hash-table :test 'equal))
  (defun ensure-pattern-specializer (pattern)
    (or (gethash pattern *pattern-specializer-table*)
        (setf (gethash pattern *pattern-specializer-table*)
              (make-instance 'pattern-specializer 'pattern pattern))))
  (defclass pattern-gf/1 (standard-generic-function) ()
    (:metaclass funcallable-standard-class)
    (:default-initargs :method-class (find-class 'pattern-method)))
  (defclass pattern-method (standard-method)
    ((lambda-expr :initarg :lambda-expr :reader pattern-method-lambda-expr)))
  (defmethod sb-pcl:make-method-specializers-form 
      ((gf pattern-gf/1) method snames env)
    `(list ,@(mapcar (lambda (s) `(ensure-pattern-specializer ',s)) snames)))
\end{alltt}
}
\caption{Implementation classes and methods for one-argument generic
  functions with methods specialized on patterns.}
\label{f:classes}
\end{figure}
\begin{figure}
{\small
\begin{alltt}
  (defun matchesp (arg pattern)
    (cond
      ((or (null pattern) (eq pattern '_)) t)
      ((atom pattern) (eql arg pattern))
      (t (and (matchesp (car arg) (car pattern)) (matchesp (cdr arg) (cdr pattern))))))
  (defun method-interpreting-function (methods gf)
    (lambda (arg)
      (dolist (method methods (no-applicable-method gf (list arg)))
        (when (matchesp arg (pattern (car (method-specializers method))))
          (return (funcall (method-function method) (list arg) nil))))))
  (defmethod compute-discriminating-function ((gf pattern-gf/1))
    (method-interpreting-function (generic-function-methods gf) gf))
\end{alltt}
}
\caption{Implementation of a discriminating function for one-argument
  pattern-matching method dispatch.  Note that the result is dependent
  on the order of method definition, but also that we are able to
  cache the generic function methods (as the discriminating function
  is recomputed if methods are added or removed).}
\label{f:discrim}
\end{figure}

\begin{figure}
\begin{alltt}
  (defun compile-matcher (arg pattern success fail)
    (cond
      ((or (null pattern) (eq pattern '_)) success)
      ((atom pattern) `(if (eql ,arg ',pattern) ,success ,fail))
      (t (let ((car-name (gensym "CAR")) (cdr-name (gensym "CDR")))
           `(if (consp ,arg)
                (let ((,car-name (car ,arg)) (,cdr-name (cdr ,arg)))
                  (declare (ignorable ,car-name ,cdr-name))
                  ,(compile-matcher car-name (car pattern)
                                    (compile-matcher cdr-name (cdr pattern) 
                                                     success fail)
                                    fail))
                ,fail)))))
\end{alltt}
\caption{A simple compiler for the pattern language of figure
  \ref{f:discrim}, taking an argument name, pattern, and success and
  failure forms, and returning code to perform the discrimination.}
\label{f:compiler}
\end{figure}

The code in figure \ref{f:discrim} is an interpreter for our pattern
language; we can of course implement a compiler for that language and
use that compiler to generate more efficient discriminating functions.
A simple compiler (without any optimizations based on static analysis
of the set of patterns) is shown in figure \ref{f:compiler}; more
complex compilation strategies (see \textit{e.g.} \citet{patterns} and
references therein) would improve performance here.

We note that the method dispatch protocol means that we cannot
straightforwardly get full micro-efficiency with these pattern
methods: we must destructure the argument to check whether a given
method is applicable, but we must invoke the method with a list of the
(undestructured) arguments.  It is possible that a suitable override
of \mop{make-method-lambda} might enable us to recover this loss of
efficiency, and also possibly to refer to pattern variables in method
bodies.

\section{Future Work}
\label{s:future}

For some of the problems noted in this paper, we can propose solutions
that we believe are compatible in spirit with the \textit{de facto}
standard Metaobject Protocol, though there may be difficulties in
incorporating those solutions into existing implementations of Common
Lisp; we have validated those solutions to the point of testing them
with SBCL's implementation of the Metaobject Protocol.  There are
additionally some issues to note that we have not attempted to address
in our implementation.

\subsection{Solved problems}

To support use of \cl{find-method} with non-standard specializers, we
suggest that there should be a generic function equivalent to
\pcl{parse-specializer-using-class}, dispatching on the generic
function's class and returning a specializer object -- and that for
introspective purposes, it is also reasonable to provide
\pcl{unparse-specializer-using-class}.

However, \pcl{parse-specializer-using-class} is insufficient to
support the implementation of specializer names in \cl{defmethod}, as
the issue of running in the correct lexical environment is important.
In
\begin{alltt}
  (defmethod foo ((x integer) (y (eql bar))) ...)
\end{alltt}
the specializers are treated in a similar fashion to the method body,
in that some of the portions are evaluated in the lexical environment:
specifically, while \cl{integer} and \cl{eql} are syntactic markers,
it is the value of \name{bar} when the \cl{defmethod} form is executed
that is the object being specialized on, rather than the symbol
\name{bar}.  To support this (and arbitrary other ways of handling
specializers in \cl{defmethod} forms) we suggest a new operator
\pcl{make-method-specializers-form}, analogous to
\mop{make-method-lambda}, which should return a form which (when
evaluated in the right lexical environment) evaluates to a list of
specializers\footnote{Although Common Lisp and the CLOS MOP do not
  define any qualifiers as having portions evaluated in the lexical
  environment of the \cl{defmethod} form, if a user were to need this,
  then a similar operator \pcl{make-method-qualifiers-form} could be
  implemented.}.  Note that this function suffers from one of the same
design quirks as \mop{make-method-lambda}, in that specializing it
requires the generic function to be extant and as an instance of its
final class at the point when the \cl{defmethod} form is
macroexpanded.

Individual implementations will need to take care over various
codepaths; certainly PCL as used in SBCL implements certain
optimizations which can be invalidated by user-defined specializers,
but because of the lack of attempts at using this facility, the
optimizations were written insufficiently defensively.  For example,
in \mop{make-method-lambda}, the system method attempted to insert
type declarations into the lambda corresponding to system class
specializers, which allows for efficient method functions with no
extra user-provided declarations.  Another case is that if the second
return value from \mop{compute-applicable-method-using-classes} is
null while the first is not, the system treats the first value as a
list of possibly-applicable methods which it should build a
discrimination net to distinguish between.  Both of these cases caused
problems to the initial implementation of user-defined specializers.

\subsubsection{Dictionary}

{\small
  \gf{parse-specializer-using-class}{\textit{generic-function} \textit{specializer-name}}
  This generic function returns an instance of \mop{specializer},
  representing the specializer named by \textit{specializer-name}
  in the context of \textit{generic-function}.
  
  \meth{parse-specializer-using-class}{(\textit{gf} \texttt{standard-generic-function}) (\textit{name} \texttt{t})}
  This method applies the standard parsing rules for consistency with
  the specified behaviour of \cl{find-method}.
  
  \gf{unparse-specializer-using-class}{\textit{generic-function} \textit{specializer}}
  
  This generic function returns the name of \textit{specializer}
  for generic functions with class the same as 
  \textit{generic-function}
  
  \meth{unparse-specializer-using-class}{\\~~~~~(\textit{gf} \texttt{standard-generic-function}) (\textit{specializer} \texttt{specializer})}
  This method applies the standard unparsing rules for consistency with
  the specified behaviour of \cl{find-method}.

  \gf{make-method-specializers-form}{\textit{generic-function} \textit{method} \textit{specializer-names} \textit{env}}

  This function is called with (maybe uninitialized, as with the
  analogous arguments to \mop{make-method-lambda})
  \textit{generic-function} and \textit{method}, and a list of
  specializer names (being the parameter specializer names from a
  \cl{defmethod} form, or the symbol \cl{t} if unsupplied), and
  returns a form which evaluates to a list of specializer objects in
  the lexical environment of the \cl{defmethod} form.

  \meth{make-method-specializers-form}{\\~~~~~(\textit{gf} \texttt{standard-generic-function}) (\textit{method} \texttt{standard-method}) \textit{names} \textit{env}}

  This method implements the standard behaviour for parameter
  specializer names.
}

\subsection{Open problems}

The greatest problem in opening specializers to user definition lies
in method ordering and method combination.  In the general case, there
is no single unambiguous ordering of a set of applicable methods, even
given particular arguments.  This is largely a problem for the
implementor of a specializer, as \cl{compute-applicable-methods} and
\mop{compute-applicable-methods-using-classes} must be overriden in
any case, and it is the return value of those functions that
determines the order of specificity.

However, this does imply that the entirety of
\cl{compute-applicable-methods} and
\mop{compute-applicable-methods-using-classes} must be reimplemented
for every new generic function class accepting extended specializers
-- a non-trivial amount of work, as implementing those functions (even
with just the standard behaviour) comes to hundreds of lines of code.
This is probably not optimal, and suggests that there is scope for
experimentation with a protocol to replace the applicable method
computation performed by \cl{compute-applicable-methods}.

A sketch of such a protocol might include calling a function
\pcl{specializer-of} (taking two arguments: an object and the generic
function being called, and returning the most specific specializer
applicable to the object for which cacheing of applicable methods is
suitable) instead of \pcl{class-of}, so that methods on
\pcl{specializer-of} specialized on a generic function class could be
written to return an application-specific specializer for a given
argument object; then a function
\pcl{compute-applicable-methods-using-specializers} could replace the
computation and cacheing functionality of
\mop{compute-applicable-methods-using-classes}.

Another ingredient of such a protocol might be a predicate for
determining whether a specializer is more or less specific than
another (say \pcl{specializer-lessp}, along with \cl{eql} to test for
equal specificity), and defining how this is called from within the
method ordering protocol functions.  We suggest that experimentation
along the lines of this sketch, using a defined generic function
class, is a way to begin exploring the issues involved in the
interoperability of user-defined specializers with the standard
specializers and with each other.

In practice, the major impediment to the use of \mop{specializer}
subclasses is that support for them is patchy to nonexistent.  Aside
from recent work in SBCL, which could be straightforwardly ported to
PCL-based CLOS implementations such as CMUCL and GCL, there are
architectural hurdles to clear: Allegro Common Lisp and GNU CLISP do
not implement \mop{make-method-lambda}, and do not allow subclasses of
\mop{specializer} to be used (even as literals) as arguments to
\cl{defmethod}.  Thus, there is no way to create a method with
non-standard specializers in those implementations.  Lispworks Common
Lisp does not include the \mop{specializer} metaobject class at all,
representing \cl{eql} specializers as conses -- which makes it rather
difficult to subclass \mop{specializer} in the first place.
MCL-derived Lisps have an entirely different generic function calling
protocol, so much of the discussion above does not apply to them, while 
most of the newer Common Lisp implementations do not purport to support the
Metaobject Protocol.

\section{Conclusions}

We have presented our work allowing the MOP programmer to define
subclasses of \mop{specializer} which integrate cleanly with the rest
of CLOS, including the need for a protocol operator to act at
macroexpansion time in a similar fashion to \mop{make-method-lambda}.
We have additionally enumerated some open problems with
user-extensible specializers, and suggested a path for experimenting
with possible protocol resolutions to these open problems.

\section*{Acknowledgments}

The author thanks Paul
Khuong\footnote{\texttt{khuongpv@iro.umontreal.ca}} and the workshop
reviewers for valuable discussions and helpful feedback.

\bibliographystyle{apalike}
\bibliography{ilc,standard,objects}

\end{document}