\documentclass{beamer}

\mode<presentation>
{
  \usetheme{Hannover}
  \usecolortheme{crane}
  % or ...

  \setbeamercovered{transparent}
  % or whatever (possibly just delete it)
}


\usepackage[british,english]{babel}
%\usepackage[utf-8]{inputenc}
%\usepackage{times}
%\usepackage[T1]{fontenc}
\usepackage{url}
\usepackage{pstricks,pst-node}
\usepackage{verbatim}

\newcommand{\cl}[1]{\texttt{#1}}
\newcommand{\pcl}[1]{\texttt{cl:#1}}

\title{Extensible specializers and the CLOS Metaobject Protocol}

\subtitle{Implementation and Use} % (optional)

\author{Christophe Rhodes}

\institute{\color[RGB]{252,187,6}Goldsmiths, University of London}

\date{Monday 30th July}

\subject{Extensible Specializers}

% If you wish to uncover everything in a step-wise fashion, uncomment
% the following command: 

%\beamerdefaultoverlayspecification{<+->}

% basic structure:
%

\begin{document}

\begin{frame}
  \titlepage
\end{frame}

\begin{frame}
  \frametitle{Outline}
  \tableofcontents
  % You might wish to add the option [pausesections]
\end{frame}

\section{Introduction}

\subsection{Motivation}

\begin{frame}[fragile]
  \frametitle<presentation>{Motivation}

  {\footnotesize
\begin{verbatim}
<[1]solvent> hello. is it possible to make a single method 
             that accepts two different classes of argument
      <H4ns> [1]solvent: no
         ...
       <Xof> I think it is possible to write methods with OR 
             specializers
       <Xof> With a certain amount of wizardry
       <Xof> What I'm working out is how much wizardry
\end{verbatim}
  }
  \pause

  \begin{itemize}

  \item What's so special about classes?

  \item Can we allow expression of algorithms naturally and
    maintainability?

  \item Does the CLOS Metaobject Protocol actually allow this kind of
    expressiveness in a controlled and composable way?

    \pause
    
  \item If not, why not?

  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle<presentation>{Metamotivation}

  Experiment:
  \begin{itemize}
  \item can we get Common Lispers to agree on anything?
  \end{itemize}
  
  \pause

  Theme: generate and implement language extensions, with a minimum of
  backwards incompatibility, and see if and how they are used.
  \begin{itemize}
  \item see also: generic sequences
  \end{itemize}

  \pause

  ``any useful lisp program is doomed to be made portable.''
\end{frame}

\subsection{Generic Functions}

\begin{frame}
  \frametitle<presentation>{CLOS}

  Common Lisp Object System: Standardized by ANSI.
  
  {\footnotesize
    (Historical footnote: Common Lisp was the first ANSI-standardized
    language with Object Oriented features.)
  }

  \pause

  {\footnotesize
    \begin{itemize}
    \item Objects are instances of Classes
    \item Objects may have Slots
    \item Inheritance is mediated through Classes
    \item Generic Functions take Object arguments
    \item Methods implementing behaviour belong to Generic Functions
    \item Methods are applicable to Arguments
    \item Methods are combined to form the Effective Method
    \item ...
      \pause
      
    \item Generic Functions, Classes and Methods are Objects (and so is
      everything else)
    \end{itemize}
  }
\end{frame}

\begin{frame}
  \frametitle<presentation>{CLOS: Metaobject Protocol}

  CLOS:
  \begin{itemize}
  \item implemented with metacircles;
  \item base CLOS standardized by ANSI / X3J13; Metaobject Protocol
    (MOP) not recommended for standardization.
  \item we have a book instead:  \textit{The Art of the Metaobject
      Protocol} (AMOP).
  \end{itemize}

  \pause

  MOP:
  \begin{itemize}
  \item introspection: \texttt{generic-function-methods},
    \texttt{method-qualifiers}
  \item intercession: specifying
    \begin{itemize}
    \item which functions are extensible or overrideable
    \item when functions are called at particular stages in class
      realization, generic function call, etc.
    \end{itemize}
  \end{itemize}

\end{frame}

\begin{frame}[fragile]
  \frametitle<presentation>{CLOS: Methods}

\begin{verbatim}
(defmethod foo :after ((x integer) (y (eql 'foo)))
  (format *trace-output* "~&~S: ~X~%" x y))  
\end{verbatim}

  \pause
  {\footnotesize
\begin{verbatim}
#<STANDARD-METHOD
   :GENERIC-FUNCTION #<STANDARD-GENERIC-FUNCTION FOO>
   :QUALIFIERS (:AFTER)
   :SPECIALIZERS (#<STANDARD-CLASS INTEGER> 
                  #<EQL-SPECIALIZER-OBJECT FOO>)
   :FUNCTION #<FUNCTION (LAMBDA (ARGS NEXT-METHODS))>
   ...>
\end{verbatim}
}
\end{frame}

\begin{frame}
  \frametitle<presentation>{CLOS: Generic Functions}

  Generic functions have a set of methods and a method combination.

  When a generic function is called:
  \begin{enumerate}
  \item All applicable methods are selected;
  \item Applicable methods are sorted by precedence;
  \item Method combination is applied to the sorted applicable methods.
  \end{enumerate}

  \begin{flushright}
    CLHS 7.6.6.1
  \end{flushright}

\end{frame}

\section{Design}

\begin{frame}
  \frametitle{Outline}
  \tableofcontents[currentsection]
  % You might wish to add the option [pausesections]
\end{frame}

\begin{frame}
  \frametitle<presentation>{Desiderata}

  User-generalizeable specializers

  \begin{itemize}
  \item Usefulness
  \item Convenience
  \item Minimize incompatibility with existing standards
  \item Implementability
  \end{itemize}
\end{frame}

\subsection{Utility}

\begin{frame}[fragile]
  \frametitle<presentation>{Example}

\begin{verbatim}
(defgeneric simplify (x)
  (:method (x) x))
(defmethod simplify ((x (+ _ 0)))
  (simplify (second x)))
\end{verbatim}

\begin{verbatim}
(simplify '(+ (+ 1 0) 0)) ; => 1
\end{verbatim} 

  \pause

{\footnotesize
\begin{verbatim}
(defmethod simplify ((x (* _x 0)))
  _x)
\end{verbatim}
}
\end{frame}

\begin{frame}
  \frametitle<presentation>{MOP features}

  {\footnotesize
    \begin{enumerate}
    \item All applicable methods are selected;
    \item Applicable methods are sorted by precedence;
    \item Method combination is applied to the sorted applicable methods.
    \end{enumerate}
  }

  \begin{enumerate}
  \item Discriminating function (returned by
    \texttt{compute-discriminating-function});
  \item \texttt{compute-applicable-methods} (and
    {\footnotesize \texttt{compute-applicable-methods-using-classes}});
  \item \texttt{compute-effective-method}.
  \end{enumerate}

  Additionally MOP defines a \texttt{specializer} class.
  
\end{frame}

\begin{frame}[fragile]
  \frametitle<presentation>{Example: Class definition}
  
  Subclass \texttt{specializer} class:
  {\footnotesize
\begin{verbatim}
(defclass pattern-specializer (mop:specializer)
  ((pattern :initarg pattern :reader pattern)
   (%dms :initform nil 
         :reader mop:specializer-direct-methods)))
\end{verbatim}
  }

  \pause

  Now what?  Make a method!

\begin{verbatim}
(let ((s (make-instance 'pattern-specializer
                        :pattern '(+ _ 0))))
  (eval `(defmethod simplify ((x ,s)) 
           (simplify (second x)))))
\end{verbatim}
  
\end{frame}

\begin{frame}[fragile]
  \frametitle<presentation>{Example: Method definition}

  {\footnotesize
\begin{verbatim}
(let ((s (make-instance 'pattern-specializer
                        :pattern '(+ _ 0))))
  (eval `(defmethod simplify ((x ,s)) 
           (simplify (second x)))))
\end{verbatim}
  }

  Ugly \texttt{eval}.  What's the alternative?

  \pause

\begin{verbatim}
(let* ((s (make-instance 'pattern-specializer
                         :pattern '(+ _ 0)))
       (f (lambda (a nm) (simplify (cadar a))))
       (m (make-instance 'standard-method
                         :qualifiers nil
                         :specializers (list s)
                         :function f)))
  (add-method #'simplify m))
\end{verbatim}

\end{frame}

\begin{frame}[fragile]
  \frametitle<presentation>{Example: Generic function}

\begin{verbatim}
(simplify '(+ 3 0)) ; => ERROR
\end{verbatim}

  Applicability?  Ordering?  Method combination?

\begin{verbatim}
(defclass pattern-gf (standard-generic-function)
  ())
(defmethod compute-discriminating-function
    ((gf pattern-gf))
  (let ((ms (generic-function-methods gf)))
    (interpret-methods ms)))
\end{verbatim}
  
\end{frame}

\begin{frame}[fragile]
  \frametitle<presentation>{Example: Generic function}
  {\footnotesize
\begin{verbatim}
(defmethod compute-discriminating-function
    ((gf pattern-gf))
  (let ((ms (generic-function-methods gf)))
    (interpret-methods ms)))
\end{verbatim}
  }

\begin{verbatim}
(defun interpret-methods (methods)
  (lambda (&rest args)
    (dolist (m methods)
      (when (matches m args)
        (funcall (method-function m) 
                 args nil)))))
\end{verbatim}

\end{frame}

\begin{frame}[fragile]
  \frametitle<presentation>{Usefulness and Convenience}

  Possible to make and call generic functions with non-standard
  specializers.  What about easy?

  New operators:
  \begin{itemize}
  \item \texttt{make-method-specializers-form}
  \item \texttt{parse-specializer-using-class}
  \item \texttt{unparse-specializer-using-class}
  \end{itemize}

  Methods on these operators permit the system to behave as one might
  desire.

  {\footnotesize
\begin{verbatim}
(defgeneric simplify (x)
  (:generic-function-class pattern-gf/1))
(defmethod simplify ((y _)) y)
(defmethod simplify ((x (* _ 0))) 0)
\end{verbatim}
  }
\end{frame}

\begin{frame}
  \frametitle<presentation>{Example: Issues}

  Skated over many complicated issues in generic function protocol:
  \begin{itemize}
  \item multiple arguments;
  \item precedence ordering;
  \item method combination.
  \end{itemize}

  Also not discussed issues for the specializer implementor:
  \begin{itemize}
  \item Implementation of one specializer for general use must
    define interaction with standard specializers
  \item (Implementation of multiple specializer classes intended to be
    composed with arbitrary others must define a protocol for
    ordering.)
  \end{itemize}

\end{frame}

\subsection{Incompatibility}

\begin{frame}[fragile]
  \frametitle<presentation>{Incompatibility}

  No known incompatibility in this with ANSI CL or the Metaobject
  Protocol described in AMOP.\\ [2ex]
  
  \pause
  
  Compatibility with Lisp programmers remains to be seen.
\end{frame}

\subsection{Implementability}

\begin{frame}
  \frametitle<presentation>{Implementability}

  This is all implementable!  \textit{Proof}: SBCL 1.0.7 (June 2007).

  Other Common Lisp implementations:
  \pause
  \begin{itemize}
  \item CMUCL, GCL: straightforward port (similar codebase).
  \item CLISP: no way of getting a non-standard specializer into a method.
  \item Allegro: can trick it, but basically unsupported.
  \item Lispworks: \texttt{mop:specializer} not present.
  \item OpenMCL: different generic function calling protocol
  \item ECL, Corman: do not (claim to) support MOP
  \end{itemize}
  
\end{frame}

\section{Conclusions}

\begin{frame}
  \frametitle{Outline}
  \tableofcontents[currentsection]
  % You might wish to add the option [pausesections]
\end{frame}

\begin{frame}
  \frametitle<presentation>{Conclusions}

  Classes are a bit special: 
  \begin{itemize}
  \item given an instance, natural ordering for classes.
  \item (slightly different from issue of CPL ordering in the first place)
  \end{itemize}

  Specializers can usefully be subclassed:
  \begin{itemize}
  \item express some algorithms more straightforwardly
  \item potentially more efficient than simple, static implementations.
  \end{itemize}
  
  No-one is developing with extended specializers (yet)
  \begin{itemize}
  \item You can be the first!
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle<presentation>{Future Work}

  \begin{itemize}
  \item Get specializers used (and implemented for other CL
    implementations)
  \item Feedback from use might suggest suitable protocols for
    interoperable specializers
  \end{itemize}
\end{frame}

\section*{Summary}

\begin{frame}
  \frametitle<presentation>{Summary}

  Resources:
  \begin{itemize}
  \item SBCL home page: \url{http://www.sbcl.org/}
  \item Manual: \url{http://www.sbcl.org/manual/}
  \item MOP: \url{http://www.lisp.org/mop/}
  \end{itemize}

  Aiming higher than a late-1980s programming language.
\end{frame}

\end{document}