From 3c7654e54e2e3bcceef0ba7251a30a97654d489f Mon Sep 17 00:00:00 2001 From: Christophe Rhodes Date: Mon, 5 May 2014 13:37:55 +0100 Subject: [PATCH] els2014 talk --- talk/outline.org | 34 +++++ talk/slides.tex | 343 +++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 377 insertions(+) create mode 100644 talk/outline.org create mode 100644 talk/slides.tex diff --git a/talk/outline.org b/talk/outline.org new file mode 100644 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 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"))) + " +Foo +

Foo

") + +(defmethod foo ((request (accept "text/turtle"))) + "@prefix foo: . +@prefix : . +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} -- 2.30.2