1 #+TITLE: Generalizers: New Metaobjects for Generalized Dispatch
2 #+AUTHOR: Christophe Rhodes, Jan Moringen, David Lichteblau
5 #+LaTeX_HEADER: \usepackage[margin=1in]{geometry}
8 1. This paper introduces a new metaobject, the generalizer, which
9 complements the existing specializer metaobject.
10 2. With the help of examples, we show that this metaobject allows for
11 the efficient implementation of complex non-class-based dispatch
12 within the framework of existing metaobject protocols
13 3. We present the generalizer protocol, implemented within the SBCL
14 implementation of Common Lisp
15 4. In combination with previous work, this produces a fully-functional
16 extension of the existing mechanism for method selection and
17 effective method computation, including support for standard and
18 user-defined method combination independent from method selection.
22 The revisions to the original Common Lisp language \cite{CLtL1}
23 included the detailed specification of an object system, known as
24 the Common Lisp Object System (CLOS), which was eventually
25 standardized as part of the ANSI Common Lisp standard \cite{CLtS}.
26 The object system as presented to the standardization committee was
27 formed of three parts, the first two of which covered XXX [what?]
28 and were incorporated into the final standard, and the third,
29 covering a Metaobject Protocol (MOP) for CLOS, was not.
31 Nevertheless, the CLOS MOP has proven to be a robust design, and
32 while many implementations have derived their implementations of
33 CLOS from either the Closette illustrative implementation in
34 \cite{AMOP}, or the Portable Common Loops implementation of CLOS
35 from Xerox Parc, there have been from-scratch reimplementations of
36 CLOS (in at least CLISP; check for others -- ABCL? Lisp500?!)
37 incorporating the majority of the Metaobject Protocol as described.
39 Although it has stood the test of time, the MOP is neither without issues
40 (e.g. M-M-L considered harmful; slot-definition initargs issue) nor
41 a complete framework for the metaprogrammer to implement all
42 conceivable variations of object-oriented behaviour; indeed, while
43 metaprogramming offers some possibilities for customization of the
44 object system behaviour, those possibilities cannot extend
45 arbitrarily in all directions. There is still an expectation that
46 functionality is implemented with methods on generic functions,
47 acting on objects with slots. [XXX find Paepke picture here? Not
48 Paepke; AMOP?]. XXX include typical examples of MOP: object
49 persistence; maybe ref. Kizcales "MOPs: why we want them and what
50 else they can do"? (Fig. 2 in that is good) ORMs; sparse slots.
52 + introspection, e.g. documentation generation
53 + programmatic construction of classes and generic functions
54 e.g. for IDL compilers, model transformations
56 One area of functionality where there is scope for customization by
57 the metaprogrammer is in the mechanics and semantics of method
58 applicability and dispatch. While in principle AMOP allows
59 customization of dispatch in various different ways (the
60 metaprogrammer can define methods on protocol functions such as
61 =compute-applicable-methods=,
62 =compute-applicable-methods-using-classes=), for example, in
63 practice implementation support for this was weak until relatively
64 recently (ref. closer, also check how ContextL and filtered dispatch
66 jmoringe: filtered dispatch uses a custom method combination, i
69 Another potential mechanism for customizing dispatch is implicit in
70 the class structure defined by AMOP: standard specializer objects
71 (instances of =class= and =eql-specializer=) are generalized
72 instances of the =specializer= protocol class, and in principle
73 there are no restrictions on the metaprogrammer constructing
74 additional subclasses. Previous work [Newton/Rhodes] has explored
75 the potential for customizing generic function dispatch using
76 extended specializers, but as of that work the metaprogrammer must
77 override the entirety of the generic function invocation protocol
78 (from =compute-discriminating-function= on down), leading to toy
79 implementations and duplicated effort.
81 This paper introduces a protocol for efficient and controlled
82 handling of arbitrary subclasses of =specializer=. In particular,
83 it introduces the =generalizer= protocol class, which generalizes
84 (ahem) the return value of =class-of=, and allows the metaprogrammer
85 to hook into cacheing schemes to avoid needless recomputation of
86 effective methods for sufficiently similar generic function
87 arguments (See Figure\nbsp\ref{fig:dispatch}).
89 #+CAPTION: Dispatch Comparison
91 #+ATTR_LATEX: width=0.9\linewidth float
92 [[file:figures/dispatch-comparison.pdf]]
94 The remaining sections in this paper can be read in any order. We
95 give some motivating examples in section XX, including
96 reimplementations of examples from previous work, as well as
97 examples which are poorly supported by previous protocols. We
98 describe the protocol itself in section YY, describing each protocol
99 function in detail and, where applicable, relating it to existing
100 protocol functions within the CLOS MOP. We survey related work in
101 more detail in section ZZ, touching on work on customized dispatch
102 schemes in other environments. Finally, we draw our conclusions
103 from this work, and indicate directions for further development, in
104 section WW; reading that section before the others indicates
105 substantial trust in the authors' work.
107 - [ ] =cons-specializer= (can be done using filtered dispatch)
108 - [ ] factorial (like filtered dispatch)
109 - [ ] HTTP Accept header
111 - [ ] prototype/multimethod
113 NB this example can be done using filtered dispatch, with a filter
114 calling =car= on cons arguments.
116 Note also that there's no real need for =cons-specializer= and
117 =cons-generalizer= to be distinct classes (as with =class= and
118 =class=). Also true for =signum=, below; but more interesting
119 dispatch reveals the need to split.
121 (defclass cons-specializer (specializer)
122 ((%car :reader %car :initarg :car)))
123 (defclass cons-generalizer (generalizer)
124 ((%car :reader %car :initarg :car)))
125 (defmethod generalizer-of-using-class ((gf cons-generic-function) arg)
127 ((cons symbol) (make-instance 'cons-generalizer :car (car arg)))
128 (t (call-next-method))))
129 (defmethod generalizer-equal-hash-key ((gf cons-generic-function)
130 (g cons-generalizer))
132 (defmethod specializer-accepts-generalizer-p ((gf cons-generic-function)
134 (g cons-generalizer))
135 (if (eql (%car s) (%car g))
138 (defmethod specializer-accepts-p ((s cons-specializer) o)
139 (and (consp o) (eql (car o) (%car s))))
141 #| less interesting methods elided: jmoringe: (un)parsing, specializer<?, more? |#
143 #| XXX insert motivating example from Newton/Rhodes here |#
146 Our second example of the implementation and use of generalized
147 specializers is a reimplementation of one of the examples in
148 \cite{Costanza.etal:2008}: specifically, the factorial function.
149 Here, we will perform dispatch based on the =signum= of the
150 argument, and again, at most one method with a =signum= specializer
151 will be appliable to any given argument, which makes the structure
152 of the specializer implementation very similar to the =cons=
153 specializers in the previous section.
155 We have chosen to compare signum values using \texttt{=}, which
156 means that a method with specializer =(signum 1)= will be
157 applicable to positive floating-point arguments (see the first
158 method on =specializer-accepts-generalizer-p= and the method on
159 =specializer=accepts-p= below). This leads to one subtle
160 difference in behaviour compared to that of the =cons=
161 specializers: in the case of =signum= specializers, the /next/
162 method after any =signum= specializer can be different, depending
163 on the class of the argument. This aspect of the dispatch is
164 handled by the second method on =specializer-accepts-generalizer-p=
167 (defclass signum-specializer (specializer)
168 ((%signum :reader %signum :initarg :signum)))
169 (defclass signum-generalizer (generalizer)
170 ((%signum :reader %signum :initarg :signum)))
171 (defmethod generalizer-of-using-class ((gf signum-generic-function) arg)
173 (real (make-instance 'signum-generalizer :signum (signum arg)))
174 (t (call-next-method))))
175 (defmethod generalizer-equal-hash-key ((gf signum-generic-function)
176 (g signum-specializer))
177 (%signum g)) ; this will create multiple entries for the same emf, but that's OK
178 (defmethod specializer-accepts-generalizer-p ((gf signum-generic-function)
179 (s signum-specializer)
180 (g signum-generalizer))
181 (if (= (%signum s) (%signum g)) ; or EQL?
185 ;; this method is perhaps interesting enough to talk about?
186 (defmethod specializer-accepts-generalizer-p ((gf signum-generic-function) (specializer sb-mop:specializer) (thing signum-specializer))
187 (specializer-accepts-generalizer-p gf specializer (class-of (%signum thing))))
190 (defmethod specializer-accepts-p ((s signum-specializer) o)
191 (and (realp o) (= (%signum s) (signum o))))
193 #| again elide more boring methods |#
196 Given these definitions, and some more straightforward ones elided for
197 reasons of space, we can implement the factorial function as follows:
201 (:generic-function-class signum-generic-function))
202 (defmethod fact ((n (signum 0))) 1)
203 (defmethod fact ((n (signum 1))) (* n (fact (1- n))))
206 We do not need to include a method on (signum -1), as the standard
207 =no-applicable-method= protocol will automatically apply to negative
208 real or non-real arguments.
210 Benchmarketing: we chose to benchmark 20! because that is the largest
211 factorial whose answer fits in SBCL's 63-bit fixnums, so as to attempt
212 to measure the maximum effect of dispatch (unobscured by allocation /
215 | fact (signum-gf) | %fact (fun) | %%fact (gf / 1meth) | fact (signum-gf / 1arg hash-special-case) |
216 |------------------+-------------+---------------------+-------------------------------------------|
217 | 0.284 | 0.004 | 0.016 | 0.032 |
218 | 0.076 | 0.008 | 0.012 | 0.024 |
219 | 0.072 | 0.004 | 0.012 | 0.116 |
220 | 0.264 | 0.004 | 0.008 | 0.120 |
221 | 0.292 | 0.008 | 0.012 | 0.120 |
222 | 0.264 | 0.004 | 0.016 | 0.084 |
223 | 0.276 | 0.008 | 0.012 | 0.092 |
224 | 0.264 | 0.008 | 0.012 | 0.036 |
225 | 0.276 | 0.008 | 0.004 | 0.104 |
226 | 0.272 | 0.004 | 0.012 | 0.020 |
229 (progn (gc :full t) (time (dotimes (i 10000) (%fact 20))))
231 ** HTTP Accept header
232 implement RFC2616 content negotiation
234 NB this definitely can't be done with filtered dispatch, except by
235 generating anonymous classes with all the right mime-types as
236 direct superclasses in dispatch order,so the filter does
238 (ensure-class nil :direct-superclasses '(text/html image/webp ...))
240 and dispatch is defined by using those classes. And that's even
241 more awkward than it sounds, because that means that in principle
242 all the mime types in the universe need an existence as classes, to
243 cater for arbitrary mime types in accept headers. And handling
244 wildcards is pretty much impossible, too. See that in
245 =specializer<= which involves a nontrivial ordering of methods
246 (whereas in two above previous cases only a single extended
247 specializer could be applicable to any given argument)
249 Also of interest: note that we can have these
250 specializer/generalizers handle arbitrary objects: the =string= and
251 =tbnl:request= methods are independent of each other; this
252 generalizes to dealing with multiple web server libraries.
254 jmoringe: the name =accept-specializer=, while sensible, may
255 confusing in this context because "accept" occurs as part of the
256 protocol with a different semantic.
259 (defclass accept-specializer (extended-specializer)
260 ((media-type :initarg :media-type :reader media-type)))
261 (defclass accept-generalizer ()
262 ((header :initarg :header :reader header)
264 (next :initarg :next :reader next)))
265 (defmethod generalizer-equal-hash-key
266 ((gf accept-generic-function) (g accept-generalizer))
267 `(accept-generalizer ,(header g)))
268 (defmethod specializer-accepts-generalizer-p ((gf accept-generic-function) (s acc
269 ept-specializer) (generalizer accept-generalizer))
270 (values (q (media-type s) (tree generalizer)) t))
271 (defmethod specializer-accepts-generalizer-p ((gf accept-generic-function) (s sb-
272 mop:specializer) (generalizer accept-generalizer))
273 (specializer-accepts-generalizer-p gf s (next generalizer)))
275 (defmethod specializer< ((gf accept-generic-function) (s1 accept-specializer) (s2
276 accept-specializer) generalizer)
278 ((string= (media-type s1) (media-type s2)) '=)
279 (t (let ((q1 (q (media-type s1) (tree generalizer)))
280 (q2 (q (media-type s2) (tree generalizer))))
286 ;; here are the only methods that actually know about TBNL
287 (defmethod generalizer-of-using-class ((gf accept-generic-function) (arg tbnl:request))
288 (make-instance 'accept-generalizer
289 :header (tbnl:header-in :accept arg)
290 :next (class-of arg)))
291 (defmethod specializer-accepts-p ((specializer accept-specializer) (obj tbnl:requ
293 (q (media-type specializer) (parse-accept-string (tbnl:header-in :accept obj)))
296 ;; we can define methods on STRING too, for debugging/simulation purposes
297 (defmethod generalizer-of-using-class ((gf accept-generic-function) (s string))
298 (make-instance 'accept-generalizer
301 (defmethod specializer-accepts-p ((s accept-specializer) (string string))
302 (q (media-type s) (parse-accept-string string)))
305 jmoringe: The role of =accept-generalizer.tree= and the =q=
306 function are hard to understand and may require some
307 explanation. However, the example with its distinct, asymmetric
308 specializers/generalizers, =accept-generalizer.next= and
309 =specializer<= is likely worth it.
311 ** Pattern / xpattern / regex / optima
312 Here's the /really/ interesting bit, but on the other hand we're
313 probably going to run out of space, and the full description of
314 these is going to take us into =make-method-lambda= territory.
315 A second paper? Future work?
318 - [ ] =generalizer-of-using-class= (NB class of gf not class of object)
319 - [ ] =compute-applicable-methods-using-generalizers=
320 - [ ] =generalizer-equal-hash-key=
321 - [ ] =specializer-accepts-generalizer-p=
322 - [ ] =specializer-accepts-p=
324 jmoringe: If I remember correctly, closette has
325 =method-more-specific-p= should we aim for parity with that and
326 use =specializer-more-specific-p=? The downside would be that
327 =-p= indicates a Boolean return value which is not the case here.
329 Description and specification left for reasons of space (we'll see?)
330 - [ ] =same-specializer-p=
331 - [ ] =parse/unparse-specializer-using-class=
332 - [ ] =make-method-specializers-form=
333 - [ ] jmoringe: In an email, I suggested
334 =make-specializer-form-using-class=:
337 Could we change =make-method-specializers-form='s default
338 behaviour to call a new generic function
340 make-specializer-form-using-class gf method name env
342 with builtin methods on =sb-mop:specializer=, =symbol=, =cons= (for
343 eql-specializers)? This would make it unnecessary to repeat
344 boilerplate along the lines of
346 (flet ((make-parse-form (name)
347 (if <name-is-interesting>
348 <handle-interesting-specializer>
349 <repeat-handling-of-standard-specializers>)))
350 `(list ,@(mapcar #'make-parse-form specializer-names)))
352 for each generic function class.
354 - [ ] =make-method-lambda= revision (use environment arg?)
356 jmoringe: would only be relevant for pattern dispatch, right? I
357 think, we didn't finish the discussion regarding special
358 variables vs. environment vs. new protocol function
361 - [ ] filtered dispatch -- the point is that our work continues to
362 be useful in cases where there are unbounded numbers of
363 equivalence classes but each given invokation involves a small
365 - [ ] ContextL / context-oriented programming -- dispatch occurs on
366 hidden layer argument being an instance of an anonymous class with
367 suitably arranged superclasses -- OK because set of layers is
368 bounded and under programmer control
369 - [ ] http://soft.vub.ac.be/Publications/2010/vub-tr-soft-10-04.pdf
370 - [ ] http://soft.vub.ac.be/lambic/files/lambic-ilc09.pdf
371 - [ ] http://soft.vub.ac.be/Publications/2011/vub-soft-phd-11-03.pdf
372 - [ ] Prototypes with Multiple Dispatch
373 http://sauerbraten.org/lee/ecoop.pdf -- extension of Self-style
374 object system to handle multiple equally-privileged "receivers".
375 A good test case for our protocol; handled adequately with
376 generalizer being the tuple of (roles,delegations), with some
377 thought needed for method redefinitions but otherwise working
382 We thank Lee Salzman, Pascal Costanza, Mikel Evins for their