\documentclass[toc]{beamer}

\usepackage[british]{babel}
\usepackage{tikz}
\usepackage{fontspec}
\setsansfont[Mapping=tex-text]{Linux Biolinum O}

\author{Christophe Rhodes, Jan Moringen, David Lichteblau}
\title{Generalizers}
\subtitle{New Metaobjects for Generalized Dispatch}
\date{5th May 2014}

\pgfdeclareimage[height=0.4cm]{Goldsmiths}{Goldsmiths}
\logo{\pgfuseimage{Goldsmiths}}

\begin{document}

\begin{frame}
  \maketitle
\end{frame}

\begin{frame}
  \tableofcontents
\end{frame}

\section{Introduction}

\subsection{Method Dispatch}

\begin{frame}
  \frametitle{Method dispatch}
  \framesubtitle{CL algorithm}

  \begin{enumerate}[widest=10]
  \item[7.6.6.1] \href{http://l1sp.org/cl/7.6.6.1}{Determining the
      Effective Method}
    \begin{enumerate}
    \item[1] \href{http://l1sp.org/cl/7.6.6.1.1}{Selecting the
        Applicable Methods}
    \item[2] \href{http://l1sp.org/cl/7.6.6.1.2}{Sorting the
        Applicable Methods by Precedence Order}
    \item[3] \href{http://l1sp.org/cl/7.6.6.1.3}{Applying method
        combination to the sorted list of applicable methods}
    \end{enumerate}
  \end{enumerate}
\end{frame}

\begin{frame}
  \frametitle{Method dispatch}
  \framesubtitle{MOP for standard-generic-function}

  \begin{itemize}
  \item \href{http://l1sp.org/mop/compute-discriminating-function}{\tt compute-discriminating-function}
  \item<3-> \href{http://l1sp.org/mop/compute-applicable-methods-using-classes}{\tt compute-applicable-methods-using-classes}
  \item \href{http://l1sp.org/cl/compute-applicable-methods}{\tt compute-applicable-methods}
  \item \href{http://l1sp.org/mop/compute-effective-method}{\tt compute-effective-method}
  \item<2-> invoke the effective method somehow
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Method dispatch}
  \framesubtitle{compute-applicable-methods-using-classes}

  \href{http://l1sp.org/mop/compute-applicable-methods-using-classes}{\texttt{compute-applicable-methods-using-classes}}
  (gf list)
  \begin{itemize}
  \item \textit{gf} argument is the generic function being called
  \item \textit{list} argument is a list of the \alert{classes} of the
    objects in the required-argument position
  \end{itemize}

  \uncover<2->{
    Computes sorted list of applicable methods of the generic function
    \begin{itemize}
    \item ... or defers to \texttt{compute-applicable-methods}
    \end{itemize}
  }
  \uncover<3->{
    If \texttt{c-a-m-u-c} succeeds, its return value is usable for all
    actual arguments to the generic function of the same classes.
    \begin{itemize}
    \item effective method can be cached and reused!
    \end{itemize}
}
\end{frame}

\begin{frame}
  \frametitle{Method dispatch}
  \framesubtitle{MOP class hierarchy}

  \begin{tikzpicture}
    \draw[white] (-1,-1) rectangle (10,3);
    \node (specializer) at (4,2) {specializer};
    \node (class) at (3,1) {class};
    \node (eql-specializer) at (6,1) {eql-specializer};

    \draw (specializer) -- (class);
    \draw (specializer) -- (eql-specializer);

    \only<2>{
      \node (xxx) at (4.5,0) {?};
      \draw (specializer) -- (xxx);
    }
  \end{tikzpicture}

  \begin{flushright}
    \scriptsize Jim Newton and Christophe Rhodes,
    \href{http://dx/doi.org/10.3217/jucs-014-20-3370}{\textit{Custom
        Specializers in Object-Oriented Lisp}}, 2008
  \end{flushright}
\end{frame}

\subsection{Simple Example}

\begin{frame}[fragile]
  \frametitle{Custom specializers}
  \framesubtitle{Example: dispatch on signum}

\begin{verbatim}
(defgeneric fact (n)
  (:generic-function-class signum-generic-function))

(defmethod fact ((n (signum 1)))
  (* n (fact (1- n))))
(defmethod fact ((n (signum 0)))
  1)

(fact 0) ; => 1
(fact 10) ; => 3628800
(fact -1) ; error "no applicable method"
\end{verbatim}
\end{frame}

\section{Generalizers}

\begin{frame}
  \frametitle{Generalizers}

  How to replace \texttt{compute-applicable-methods-using-classes}
  for custom specializers?

  \vspace{1ex}

  1st try: \texttt{compute-applicable-methods-using-specializers}
  \begin{itemize}
  \item does not work!
  \item (does not even make sense)
  \end{itemize}

  \vspace{1ex}

  \uncover<2->{
    2nd try: distinguish between class as specializer (restrictive) and
    class as equivalence class (expansive)
    \begin{itemize}
    \item works!
    \item motivates the \texttt{generalizer} metaobject
    \end{itemize}
  }
\end{frame}

\subsection{Protocol}

\begin{frame}
  \frametitle{Generalizers}
  \framesubtitle{The Generalizer protocol}

  \begin{itemize}
  \item \texttt{generalizer} [class]
  \item \texttt{generalizer-of-using-class (gf ob)} [gf]

  \item<2-> \texttt{specializer-accepts-generalizer-p (gf sp ge)} [gf]
  \item<2-> \texttt{specializer-accepts-p (sp ob)} [gf]

  \item<3-> \texttt{specializer< (gf sp1 sp2 ge)} [gf]

  \item<4-> \texttt{generalizer-equal-hash-key (gf ge)} [gf]
  \end{itemize}
\end{frame}

\subsection{Examples}

\begin{frame}[fragile]
  \frametitle{Generalizer protocol}
  \framesubtitle{Example: dispatch on signum revisited}

{\footnotesize
\begin{verbatim}
(defclass signum-generalizer (generalizer)
  ((%signum :reader %signum :initarg :signum)))

(defmethod generalizer-of-using-class
    ((gf signum-generic-function) (arg real))
  (make-instance 'signum-generalizer :signum (signum arg)))
(defmethod generalizer-equal-hash-key 
    ((gf signum-generic-function) (g signum-generalizer))
  (%signum g))

(defmethod specializer-accepts-generalizer-p
    ((gf signum-generic-function)
     (s signum-specializer) (g signum-generalizer))
  (if (= (%signum s) (%signum g))
      (values t t)
      (values nil t)))
(defmethod specializer-accepts-p ((s signum-specializer) o)
  (and (realp o) (= (%signum s) (signum o))))
\end{verbatim}
}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Generalizer protocol}
  \framesubtitle{Example: HTTP content negotiation}

{\footnotesize
\begin{verbatim}
(defgeneric foo (request)
  (:generic-function-class accept-generic-function))
(defmethod foo ((request t)) (http:406 request))

(defmethod foo ((request (accept "text/html")))
  "<!DOCTYPE html>
<html><head><title>Foo</title></head>
<body><p>Foo</p></body></html>")

(defmethod foo ((request (accept "text/turtle")))
  "@prefix foo: <http://example.org/ns#> .
@prefix : <http://other.example.org/ns#> .
foo:bar foo: : .")

(foo "text/html,application/xml;q=0.9,*/*;q=0.8")
  ; => text/html version
(foo "text/turtle") ; => text/turtle version

\end{verbatim}
}
\end{frame}

\begin{frame}
  \frametitle{Generalizer protocol}
  \framesubtitle{Example: HTTP content negotiation}

\begin{itemize}
\item non-trivial non-standard dispatch
\item distinct specializer and generalizer objects
\item dispatch decoupled from web server implementation:
  \begin{itemize}
  \item one new method on \texttt{specializer-accepts-p}
  \item one new method on \texttt{generalizer-of-using-class}
  \end{itemize}
\end{itemize}
\end{frame}

\subsection{Efficiency}

\begin{frame}
  \frametitle{Generalizer protocol}
  \framesubtitle{Efficiency}

  \only<1>{
    Signum Specializers:
    
    \begin{center}
      \begin{tabular}{lrl}
        implementation & time (µs/call) & overhead\\
        \hline
        function & 0.6 & \\
        standard-gf/fixnum & 1.2 & +100\%\\
        signum-gf/one-arg-cache & 7.5 & +1100\%\\
        signum-gf & 23 & +3800\%\\
        signum-gf/no-cache & 240 & +41000\%\\
      \end{tabular}
    \end{center}
  }
\end{frame}
\section{Conclusions}

\begin{frame}
  \frametitle{Related Work}

  \begin{itemize}
  \item \alert<+>{predicate dispatch}
  \item \alert<+>{filtered functions}
  \item \alert<+>{layered functions}
  \item \alert<+>{prototype dispatch}
  \end{itemize}

  \only<1>{
    \begin{flushright}
      \scriptsize Michael Ernst, Craig Kaplan, and Craig Chambers.
      \href{http://dx.doi.org/10.1007/BFb0054092}{\textit{Predicate
          dispatching: A unified theory of dispatch}}, 1998.
    \end{flushright}
  }
  \only<2>{
    \begin{flushright}
      \scriptsize Pascal Costanza, Charlotte Herzeel, Jorge Vallejos,
      and Theo D'Hondt. \href{http://dx.doi.org/10.1145/1408681.1408685}{\textit{Filtered Dispatch}}, 2008.
    \end{flushright}
  }
  \only<3>{
    \begin{flushright}
      \scriptsize Robert Hirschfeld, Pascal Costanza, and Oscar
      Nierstrasz. \href{http://dx.doi.org/10.5381/jot.2008.7.3.a4}{\textit{Context-oriented
          programming}}, 2008

    \end{flushright}
  } \only<4>{
    \begin{flushright}
      \scriptsize Lee Salzman and Jonathan
      Aldrich. \href{http://dx.doi.org/10.1007/11531142_14}{\textit{Prototypes
          with Multiple Dispatch: An Expressive and Dynamic Object
          Model}}, 2005.
    \end{flushright}
  }
\end{frame}
  
\begin{frame}
  \frametitle{Conclusions}

  Customizing specializers is now:
  \begin{itemize}
  \item \alert{easier} (thanks to a simple protocol with local
    computations);
  \item \alert{better-performing} (10-30 times faster than naïve
    implementation, though still 2--6 times slower than standard
    dispatch);
  \item \alert{straightforwardly available} (simply load into a
    running SBCL).
  \end{itemize}

  \uncover<2->{
    Currently working on:
    \begin{itemize}
    \item pattern specializers (optima) with automatic variable
      bindings;
    \item more flexibility on cacheing / dispatch computation.
    \end{itemize}
  }
\end{frame}

\end{document}
