talk/slides.tex

   1 \documentclass[toc]{beamer}
   2
   3 \usepackage[british]{babel}
   4 \usepackage{tikz}
   5 \usepackage{fontspec}
   6 \setsansfont[Mapping=tex-text]{Linux Biolinum O}
   7
   8 \author{Christophe Rhodes, Jan Moringen, David Lichteblau}
   9 \title{Generalizers}
  10 \subtitle{New Metaobjects for Generalized Dispatch}
  11 \date{5th May 2014}
  12
  13 \pgfdeclareimage[height=0.4cm]{Goldsmiths}{Goldsmiths}
  14 \logo{\pgfuseimage{Goldsmiths}}
  15
  16 \begin{document}
  17
  18 \begin{frame}
  19   \maketitle
  20 \end{frame}
  21
  22 \begin{frame}
  23   \tableofcontents
  24 \end{frame}
  25
  26 \section{Introduction}
  27
  28 \subsection{Method Dispatch}
  29
  30 \begin{frame}
  31   \frametitle{Method dispatch}
  32   \framesubtitle{CL algorithm}
  33
  34   \begin{enumerate}[widest=10]
  35   \item[7.6.6.1] \href{http://l1sp.org/cl/7.6.6.1}{Determining the
  36       Effective Method}
  37     \begin{enumerate}
  38     \item[1] \href{http://l1sp.org/cl/7.6.6.1.1}{Selecting the
  39         Applicable Methods}
  40     \item[2] \href{http://l1sp.org/cl/7.6.6.1.2}{Sorting the
  41         Applicable Methods by Precedence Order}
  42     \item[3] \href{http://l1sp.org/cl/7.6.6.1.3}{Applying method
  43         combination to the sorted list of applicable methods}
  44     \end{enumerate}
  45   \end{enumerate}
  46 \end{frame}
  47
  48 \begin{frame}
  49   \frametitle{Method dispatch}
  50   \framesubtitle{MOP for standard-generic-function}
  51
  52   \begin{itemize}
  53   \item \href{http://l1sp.org/mop/compute-discriminating-function}{\tt compute-discriminating-function}
  54   \item<3-> \href{http://l1sp.org/mop/compute-applicable-methods-using-classes}{\tt compute-applicable-methods-using-classes}
  55   \item \href{http://l1sp.org/cl/compute-applicable-methods}{\tt compute-applicable-methods}
  56   \item \href{http://l1sp.org/mop/compute-effective-method}{\tt compute-effective-method}
  57   \item<2-> invoke the effective method somehow
  58   \end{itemize}
  59 \end{frame}
  60
  61 \begin{frame}
  62   \frametitle{Method dispatch}
  63   \framesubtitle{compute-applicable-methods-using-classes}
  64
  65   \href{http://l1sp.org/mop/compute-applicable-methods-using-classes}{\texttt{compute-applicable-methods-using-classes}}
  66   (gf list)
  67   \begin{itemize}
  68   \item \textit{gf} argument is the generic function being called
  69   \item \textit{list} argument is a list of the \alert{classes} of the
  70     objects in the required-argument position
  71   \end{itemize}
  72
  73   \uncover<2->{
  74     Computes sorted list of applicable methods of the generic function
  75     \begin{itemize}
  76     \item ... or defers to \texttt{compute-applicable-methods}
  77     \end{itemize}
  78   }
  79   \uncover<3->{
  80     If \texttt{c-a-m-u-c} succeeds, its return value is usable for all
  81     actual arguments to the generic function of the same classes.
  82     \begin{itemize}
  83     \item effective method can be cached and reused!
  84     \end{itemize}
  85 }
  86 \end{frame}
  87
  88 \begin{frame}
  89   \frametitle{Method dispatch}
  90   \framesubtitle{MOP class hierarchy}
  91
  92   \begin{tikzpicture}
  93     \draw[white] (-1,-1) rectangle (10,3);
  94     \node (specializer) at (4,2) {specializer};
  95     \node (class) at (3,1) {class};
  96     \node (eql-specializer) at (6,1) {eql-specializer};
  97
  98     \draw (specializer) -- (class);
  99     \draw (specializer) -- (eql-specializer);
 100
 101     \only<2>{
 102       \node (xxx) at (4.5,0) {?};
 103       \draw (specializer) -- (xxx);
 104     }
 105   \end{tikzpicture}
 106
 107   \begin{flushright}
 108     \scriptsize Jim Newton and Christophe Rhodes,
 109     \href{http://dx/doi.org/10.3217/jucs-014-20-3370}{\textit{Custom
 110         Specializers in Object-Oriented Lisp}}, 2008
 111   \end{flushright}
 112 \end{frame}
 113
 114 \subsection{Simple Example}
 115
 116 \begin{frame}[fragile]
 117   \frametitle{Custom specializers}
 118   \framesubtitle{Example: dispatch on signum}
 119
 120 \begin{verbatim}
 121 (defgeneric fact (n)
 122   (:generic-function-class signum-generic-function))
 123
 124 (defmethod fact ((n (signum 1)))
 125   (* n (fact (1- n))))
 126 (defmethod fact ((n (signum 0)))
 127   1)
 128
 129 (fact 0) ; => 1
 130 (fact 10) ; => 3628800
 131 (fact -1) ; error "no applicable method"
 132 \end{verbatim}
 133 \end{frame}
 134
 135 \section{Generalizers}
 136
 137 \begin{frame}
 138   \frametitle{Generalizers}
 139
 140   How to replace \texttt{compute-applicable-methods-using-classes}
 141   for custom specializers?
 142
 143   \vspace{1ex}
 144
 145   1st try: \texttt{compute-applicable-methods-using-specializers}
 146   \begin{itemize}
 147   \item does not work!
 148   \item (does not even make sense)
 149   \end{itemize}
 150
 151   \vspace{1ex}
 152
 153   \uncover<2->{
 154     2nd try: distinguish between class as specializer (restrictive) and
 155     class as equivalence class (expansive)
 156     \begin{itemize}
 157     \item works!
 158     \item motivates the \texttt{generalizer} metaobject
 159     \end{itemize}
 160   }
 161 \end{frame}
 162
 163 \subsection{Protocol}
 164
 165 \begin{frame}
 166   \frametitle{Generalizers}
 167   \framesubtitle{The Generalizer protocol}
 168
 169   \begin{itemize}
 170   \item \texttt{generalizer} [class]
 171   \item \texttt{generalizer-of-using-class (gf ob)} [gf]
 172
 173   \item<2-> \texttt{specializer-accepts-generalizer-p (gf sp ge)} [gf]
 174   \item<2-> \texttt{specializer-accepts-p (sp ob)} [gf]
 175
 176   \item<3-> \texttt{specializer< (gf sp1 sp2 ge)} [gf]
 177
 178   \item<4-> \texttt{generalizer-equal-hash-key (gf ge)} [gf]
 179   \end{itemize}
 180 \end{frame}
 181
 182 \subsection{Examples}
 183
 184 \begin{frame}[fragile]
 185   \frametitle{Generalizer protocol}
 186   \framesubtitle{Example: dispatch on signum revisited}
 187
 188 {\footnotesize
 189 \begin{verbatim}
 190 (defclass signum-generalizer (generalizer)
 191   ((%signum :reader %signum :initarg :signum)))
 192
 193 (defmethod generalizer-of-using-class
 194     ((gf signum-generic-function) (arg real))
 195   (make-instance 'signum-generalizer :signum (signum arg)))
 196 (defmethod generalizer-equal-hash-key
 197     ((gf signum-generic-function) (g signum-generalizer))
 198   (%signum g))
 199
 200 (defmethod specializer-accepts-generalizer-p
 201     ((gf signum-generic-function)
 202      (s signum-specializer) (g signum-generalizer))
 203   (if (= (%signum s) (%signum g))
 204       (values t t)
 205       (values nil t)))
 206 (defmethod specializer-accepts-p ((s signum-specializer) o)
 207   (and (realp o) (= (%signum s) (signum o))))
 208 \end{verbatim}
 209 }
 210 \end{frame}
 211
 212 \begin{frame}[fragile]
 213   \frametitle{Generalizer protocol}
 214   \framesubtitle{Example: HTTP content negotiation}
 215
 216 {\footnotesize
 217 \begin{verbatim}
 218 (defgeneric foo (request)
 219   (:generic-function-class accept-generic-function))
 220 (defmethod foo ((request t)) (http:406 request))
 221
 222 (defmethod foo ((request (accept "text/html")))
 223   "<!DOCTYPE html>
 224 <html><head><title>Foo</title></head>
 225 <body><p>Foo</p></body></html>")
 226
 227 (defmethod foo ((request (accept "text/turtle")))
 228   "@prefix foo: <http://example.org/ns#> .
 229 @prefix : <http://other.example.org/ns#> .
 230 foo:bar foo: : .")
 231
 232 (foo "text/html,application/xml;q=0.9,*/*;q=0.8")
 233   ; => text/html version
 234 (foo "text/turtle") ; => text/turtle version
 235
 236 \end{verbatim}
 237 }
 238 \end{frame}
 239
 240 \begin{frame}
 241   \frametitle{Generalizer protocol}
 242   \framesubtitle{Example: HTTP content negotiation}
 243
 244 \begin{itemize}
 245 \item non-trivial non-standard dispatch
 246 \item distinct specializer and generalizer objects
 247 \item dispatch decoupled from web server implementation:
 248   \begin{itemize}
 249   \item one new method on \texttt{specializer-accepts-p}
 250   \item one new method on \texttt{generalizer-of-using-class}
 251   \end{itemize}
 252 \end{itemize}
 253 \end{frame}
 254
 255 \subsection{Efficiency}
 256
 257 \begin{frame}
 258   \frametitle{Generalizer protocol}
 259   \framesubtitle{Efficiency}
 260
 261   \only<1>{
 262     Signum Specializers:
 263
 264     \begin{center}
 265       \begin{tabular}{lrl}
 266         implementation & time (µs/call) & overhead\\
 267         \hline
 268         function & 0.6 & \\
 269         standard-gf/fixnum & 1.2 & +100\%\\
 270         signum-gf/one-arg-cache & 7.5 & +1100\%\\
 271         signum-gf & 23 & +3800\%\\
 272         signum-gf/no-cache & 240 & +41000\%\\
 273       \end{tabular}
 274     \end{center}
 275   }
 276 \end{frame}
 277 \section{Conclusions}
 278
 279 \begin{frame}
 280   \frametitle{Related Work}
 281
 282   \begin{itemize}
 283   \item \alert<+>{predicate dispatch}
 284   \item \alert<+>{filtered functions}
 285   \item \alert<+>{layered functions}
 286   \item \alert<+>{prototype dispatch}
 287   \end{itemize}
 288
 289   \only<1>{
 290     \begin{flushright}
 291       \scriptsize Michael Ernst, Craig Kaplan, and Craig Chambers.
 292       \href{http://dx.doi.org/10.1007/BFb0054092}{\textit{Predicate
 293           dispatching: A unified theory of dispatch}}, 1998.
 294     \end{flushright}
 295   }
 296   \only<2>{
 297     \begin{flushright}
 298       \scriptsize Pascal Costanza, Charlotte Herzeel, Jorge Vallejos,
 299       and Theo D'Hondt. \href{http://dx.doi.org/10.1145/1408681.1408685}{\textit{Filtered Dispatch}}, 2008.
 300     \end{flushright}
 301   }
 302   \only<3>{
 303     \begin{flushright}
 304       \scriptsize Robert Hirschfeld, Pascal Costanza, and Oscar
 305       Nierstrasz. \href{http://dx.doi.org/10.5381/jot.2008.7.3.a4}{\textit{Context-oriented
 306           programming}}, 2008
 307
 308     \end{flushright}
 309   } \only<4>{
 310     \begin{flushright}
 311       \scriptsize Lee Salzman and Jonathan
 312       Aldrich. \href{http://dx.doi.org/10.1007/11531142_14}{\textit{Prototypes
 313           with Multiple Dispatch: An Expressive and Dynamic Object
 314           Model}}, 2005.
 315     \end{flushright}
 316   }
 317 \end{frame}
 318
 319 \begin{frame}
 320   \frametitle{Conclusions}
 321
 322   Customizing specializers is now:
 323   \begin{itemize}
 324   \item \alert{easier} (thanks to a simple protocol with local
 325     computations);
 326   \item \alert{better-performing} (10-30 times faster than naïve
 327     implementation, though still 2--6 times slower than standard
 328     dispatch);
 329   \item \alert{straightforwardly available} (simply load into a
 330     running SBCL).
 331   \end{itemize}
 332
 333   \uncover<2->{
 334     Currently working on:
 335     \begin{itemize}
 336     \item pattern specializers (optima) with automatic variable
 337       bindings;
 338     \item more flexibility on cacheing / dispatch computation.
 339     \end{itemize}
 340   }
 341 \end{frame}
 342
 343 \end{document}