1 \documentclass[toc]{beamer}
3 \usepackage[british]{babel}
6 \setsansfont[Mapping=tex-text]{Linux Biolinum O}
8 \author{Christophe Rhodes, Jan Moringen, David Lichteblau}
10 \subtitle{New Metaobjects for Generalized Dispatch}
13 \pgfdeclareimage[height=0.4cm]{Goldsmiths}{Goldsmiths}
14 \logo{\pgfuseimage{Goldsmiths}}
26 \section{Introduction}
28 \subsection{Method Dispatch}
31 \frametitle{Method dispatch}
32 \framesubtitle{CL algorithm}
34 \begin{enumerate}[widest=10]
35 \item[7.6.6.1] \href{http://l1sp.org/cl/7.6.6.1}{Determining the
38 \item[1] \href{http://l1sp.org/cl/7.6.6.1.1}{Selecting the
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}
49 \frametitle{Method dispatch}
50 \framesubtitle{MOP for standard-generic-function}
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
62 \frametitle{Method dispatch}
63 \framesubtitle{compute-applicable-methods-using-classes}
65 \href{http://l1sp.org/mop/compute-applicable-methods-using-classes}{\texttt{compute-applicable-methods-using-classes}}
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
74 Computes sorted list of applicable methods of the generic function
76 \item ... or defers to \texttt{compute-applicable-methods}
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.
83 \item effective method can be cached and reused!
89 \frametitle{Method dispatch}
90 \framesubtitle{MOP class hierarchy}
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};
98 \draw (specializer) -- (class);
99 \draw (specializer) -- (eql-specializer);
102 \node (xxx) at (4.5,0) {?};
103 \draw (specializer) -- (xxx);
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
114 \subsection{Simple Example}
116 \begin{frame}[fragile]
117 \frametitle{Custom specializers}
118 \framesubtitle{Example: dispatch on signum}
122 (:generic-function-class signum-generic-function))
124 (defmethod fact ((n (signum 1)))
126 (defmethod fact ((n (signum 0)))
130 (fact 10) ; => 3628800
131 (fact -1) ; error "no applicable method"
135 \section{Generalizers}
138 \frametitle{Generalizers}
140 How to replace \texttt{compute-applicable-methods-using-classes}
141 for custom specializers?
145 1st try: \texttt{compute-applicable-methods-using-specializers}
148 \item (does not even make sense)
154 2nd try: distinguish between class as specializer (restrictive) and
155 class as equivalence class (expansive)
158 \item motivates the \texttt{generalizer} metaobject
163 \subsection{Protocol}
166 \frametitle{Generalizers}
167 \framesubtitle{The Generalizer protocol}
170 \item \texttt{generalizer} [class]
171 \item \texttt{generalizer-of-using-class (gf ob)} [gf]
173 \item<2-> \texttt{specializer-accepts-generalizer-p (gf sp ge)} [gf]
174 \item<2-> \texttt{specializer-accepts-p (sp ob)} [gf]
176 \item<3-> \texttt{specializer< (gf sp1 sp2 ge)} [gf]
178 \item<4-> \texttt{generalizer-equal-hash-key (gf ge)} [gf]
182 \subsection{Examples}
184 \begin{frame}[fragile]
185 \frametitle{Generalizer protocol}
186 \framesubtitle{Example: dispatch on signum revisited}
190 (defclass signum-generalizer (generalizer)
191 ((%signum :reader %signum :initarg :signum)))
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))
200 (defmethod specializer-accepts-generalizer-p
201 ((gf signum-generic-function)
202 (s signum-specializer) (g signum-generalizer))
203 (if (= (%signum s) (%signum g))
206 (defmethod specializer-accepts-p ((s signum-specializer) o)
207 (and (realp o) (= (%signum s) (signum o))))
212 \begin{frame}[fragile]
213 \frametitle{Generalizer protocol}
214 \framesubtitle{Example: HTTP content negotiation}
218 (defgeneric foo (request)
219 (:generic-function-class accept-generic-function))
220 (defmethod foo ((request t)) (http:406 request))
222 (defmethod foo ((request (accept "text/html")))
224 <html><head><title>Foo</title></head>
225 <body><p>Foo</p></body></html>")
227 (defmethod foo ((request (accept "text/turtle")))
228 "@prefix foo: <http://example.org/ns#> .
229 @prefix : <http://other.example.org/ns#> .
232 (foo "text/html,application/xml;q=0.9,*/*;q=0.8")
233 ; => text/html version
234 (foo "text/turtle") ; => text/turtle version
241 \frametitle{Generalizer protocol}
242 \framesubtitle{Example: HTTP content negotiation}
245 \item non-trivial non-standard dispatch
246 \item distinct specializer and generalizer objects
247 \item dispatch decoupled from web server implementation:
249 \item one new method on \texttt{specializer-accepts-p}
250 \item one new method on \texttt{generalizer-of-using-class}
255 \subsection{Efficiency}
258 \frametitle{Generalizer protocol}
259 \framesubtitle{Efficiency}
266 implementation & time (µs/call) & overhead\\
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\%\\
277 \section{Conclusions}
280 \frametitle{Related Work}
283 \item \alert<+>{predicate dispatch}
284 \item \alert<+>{filtered functions}
285 \item \alert<+>{layered functions}
286 \item \alert<+>{prototype dispatch}
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.
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.
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
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
320 \frametitle{Conclusions}
322 Customizing specializers is now:
324 \item \alert{easier} (thanks to a simple protocol with local
326 \item \alert{better-performing} (10-30 times faster than naïve
327 implementation, though still 2--6 times slower than standard
329 \item \alert{straightforwardly available} (simply load into a
334 Currently working on:
336 \item pattern specializers (optima) with automatic variable
338 \item more flexibility on cacheing / dispatch computation.