els2014 talk

diff --git a/talk/outline.org b/talk/outline.org
new file mode 100644 (file)
index 0000000..9289360
--- /dev/null
+++ b/talk/outline.org
@@ -0,0 +1,34 @@
+* Introductory material
+** CLOS, generally
+   - generic functions as the base unit
+   - classes group state and assist in method selection
+   - Best. Object System. Ever.
+** How method selection/combination works
+   (basic version)
+** MOP + cacheing implementation of same
+   - C-A-M-U-C, COMPUTE-EFFECTIVE-METHOD
+** MOP, generally
+   - Mention CLASS-EQ here?
+* Example
+  - dispatch based on signum
+* Previous work
+** Predicate Dispatch
+   problem: order basically undecideable.  EVENP / PRIMEP
+** Filtered functions
+   problems: hijacks method combination for its implementation; EQL
+   specializers makes it basically uncacheable
+** Generalized specialisers
+   problem: too complicated/general to implement C-A-M, no specified
+   cacheing, interop between extensions unclear
+* Generalizers
+** double-duty of CLASS
+** cheap cacheability
+** examples
+   - signum
+   - http accept
+   - optima?  Would be good to demo something that's not in the paper,
+     and would tie up loose end from ELS 1 / ECOOP
+* Conclusions
+** Hey, neat!
+** Could be better but is usable now
+** Compiler writers speed things up by a factor of 2 every 18 years...

diff --git a/talk/slides.tex b/talk/slides.tex
new file mode 100644 (file)
index 0000000..3d3caf9
--- /dev/null
+++ b/talk/slides.tex
@@ -0,0 +1,343 @@
+\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}