1 #+TITLE: Generalizers: New Metaobjects for Generalized Dispatch
2 #+AUTHOR: Christophe Rhodes, Jan Moringen, David Lichteblau
5 #+LaTeX_CLASS: acm_proc_article-sp
6 #+LaTeX_HEADER: \DeclareTextFontCommand{\texttt}{\ttfamily\hyphenchar\font=45\relax}
8 #+begin_src elisp :exports none
9 ;;; use C-x C-e on this if org refuses to export
10 (add-to-list 'org-latex-classes
11 '("acm_proc_article-sp" "\\documentclass{acm_proc_article-sp}"
12 ("\\section{%s}" . "\\section*{%s}")
13 ("\\subsection{%s}" . "\\subsection*{%s}")
14 ("\\subsubsection{%s}" . "\\subsubsection*{%s}")
15 ("\\paragraph{%s}" . "\\paragraph*{%s}")
16 ("\\subparagraph{%s}" . "\\subparagraph*{%s}")))
20 This paper introduces a new metaobject, the generalizer, which
21 complements the existing specializer metaobject. With the help of
22 examples, we show that this metaobject allows for the efficient
23 implementation of complex non-class-based dispatch within the
24 framework of existing metaobject protocols. We present our
25 modifications to the generic function invocation protocol from the
26 /Art of the Metaobject Protocol/; in combination with previous work,
27 this produces a fully-functional extension of the existing mechanism
28 for method selection and combination, including support for method
29 combination completely independent from method selection. We discuss
30 our implementation, within the SBCL implementation of Common Lisp, and
31 in that context compare the performance of the new protocol with the
32 standard one, demonstrating that the new protocol can be tolerably
37 The revisions to the original Common Lisp language \cite{CLtL}
38 included the detailed specification of an object system, known as
39 the Common Lisp Object System (CLOS), which was eventually
40 standardized as part of the ANSI Common Lisp standard \cite{CLtS}.
41 The object system as presented to the standardization committee was
42 formed of three chapters. The first two chapters covered programmer
43 interface concepts and the functions in the programmer interface
44 \cite[Chapter 28]{CLtL2} and were largely incorporated into the
45 final standard; the third chapter, covering a Metaobject Protocol
46 (MOP) for CLOS, was not.
48 Nevertheless, the CLOS MOP has proven to be a robust design, and
49 while many implementations have derived their implementations of
50 CLOS from either the Closette illustrative implementation in
51 \cite{AMOP}, or the Portable Common Loops implementation of CLOS
52 from Xerox Parc, there have been largely from-scratch
53 reimplementations of CLOS (in CLISP[fn:1] and CCL[fn:2], at least)
54 incorporating substantial fractions of the Metaobject Protocol as
57 Although it has stood the test of time, the CLOS MOP is neither
58 without issues (e.g. semantic problems with =make-method-lambda=
59 \cite{Costanza.Herzeel:2008}; useful functions such as
60 =compute-effective-slot-definition-initargs= being missing from the
61 standard) nor is it a complete framework for the metaprogrammer to
62 implement all conceivable variations of object-oriented behaviour.
63 While metaprogramming offers some possibilities for customization of
64 the object system behaviour, those possibilities cannot extend
65 arbitrarily in all directions. There is still an expectation that
66 functionality is implemented with methods on generic functions,
67 acting on objects with slots. Nevertheless, the MOP is flexible,
68 and is used for a number of things, including: documentation
69 generation (where introspective functionality in the MOP is used to
70 extract information from a running system); object-relational
71 mapping and other approaches to object persistence; alternative
72 backing stores for slots (hash-tables or symbols); and programmatic
73 construction of metaobjects, for example for IDL compilers and model
76 [ A picture on MOP flexibility here would be good; I have in my mind
77 one where an object system is a point and the MOP opens up a blob
78 around that point, and I'm sure I've seen it somewhere but I can't
79 remember where. Alternatively, there's Kiczales et al "MOPs: why we
80 want them and what else they can do", fig. 2 ]
82 One area of functionality where there is scope for customization by
83 the metaprogrammer is in the mechanics and semantics of method
84 applicability and dispatch. While in principle AMOP allows
85 customization of dispatch in various different ways (the
86 metaprogrammer can define methods on protocol functions such as
87 =compute-applicable-methods=,
88 =compute-applicable-methods-using-classes=), for example, in
89 practice implementation support for this was weak until relatively
92 Another potential mechanism for customizing dispatch is implicit in
93 the class structure defined by AMOP: standard specializer objects
94 (instances of =class= and =eql-specializer=) are generalized
95 instances of the =specializer= protocol class, and in principle
96 there are no restrictions on the metaprogrammer constructing
97 additional subclasses. Previous work \cite{Newton.Rhodes:2008} has
98 explored the potential for customizing generic function dispatch
99 using extended specializers, but as of that work the metaprogrammer
100 must override the entirety of the generic function invocation
101 protocol (from =compute-discriminating-function= on down), leading
102 to toy implementations and duplicated effort.
104 This paper introduces a protocol for efficient and controlled
105 handling of new subclasses of =specializer=. In particular, it
106 introduces the =generalizer= protocol class, which generalizes the
107 return value of =class-of= in method applicability computation, and
108 allows the metaprogrammer to hook into cacheing schemes to avoid
109 needless recomputation of effective methods for sufficiently similar
110 generic function arguments (See Figure\nbsp\ref{fig:dispatch}).
112 #+CAPTION: Dispatch Comparison
113 #+LABEL: fig:dispatch
114 #+ATTR_LATEX: width=0.9\linewidth float
115 [[file:figures/dispatch-comparison.pdf]]
117 The remaining sections in this paper can be read in any order. We
118 give some motivating examples in section [[#Examples]], including
119 reimplementations of examples from previous work, as well as
120 examples which are poorly supported by previous protocols. We
121 describe the protocol itself in section [[#Protocol]], describing each
122 protocol function in detail and, where applicable, relating it to
123 existing protocol functions within the CLOS MOP. We survey related
124 work in more detail in section [[#Related Work]], touching on work on
125 customized dispatch schemes in other environments. Finally, we draw
126 our conclusions from this work, and indicate directions for further
127 development, in section [[#Conclusions]]; reading that section before the
128 others indicates substantial trust in the authors' work.
133 In this section, we present a number of examples of dispatch
134 implemented using our protocol, which we describe in section
135 [[#Protocol]]. For reasons of space, the metaprogram code examples in
136 this section do not include some of the necessary support code to
137 run; complete implementations of each of these cases are included in
138 an appendix / in the accompanying repository snapshot / at this
141 A note on terminology: we will attempt to distinguish between the
142 user of an individual case of generalized dispatch (the
143 “programmer”), the implementor of a particular case of generalized
144 dispatch (the “metaprogrammer”), and the authors as the designers
145 and implementors of our generalized dispatch protocol (the
146 “metametaprogammer”, or more likely “we”).
151 We start by presenting our original use case, performing
152 dispatching on the first element of lists. Semantically, we allow
153 the programmer to specialize any argument of methods with a new
154 kind of specializer, =cons-specializer=, which is applicable if and
155 only if the corresponding object is a =cons= whose =car= is =eql=
156 to the symbol associated with the =cons-specializer=; these
157 specializers are more specific than the =cons= class, but less
158 specific than an =eql-specializer= on any given =cons=.
160 One motivation for the use of this specializer is in an extensible
161 code walker: a new special form can be handled simply by writing an
162 additional method on the walking generic function, seamlessly
163 interoperating with all existing methods.
165 The programmer code using these specializers is unchanged from
166 \cite{Newton.Rhodes:2008}; the benefits of the protocol described
167 here are centered on performance and generality: in an application
168 such as walking source code, we would expect to encounter special
169 forms (distinguished by particular atoms in the =car= position)
170 multiple times, and hence to dispatch to the same effective method
171 repeatedly. We discuss this in more detail in section [[#Memoization]];
172 we present the metaprogrammer code below.
175 (defclass cons-specializer (specializer)
176 ((%car :reader %car :initarg :car)))
177 (defclass cons-generalizer (generalizer)
178 ((%car :reader %car :initarg :car)))
179 (defmethod generalizer-of-using-class
180 ((gf cons-generic-function) arg)
183 (make-instance 'cons-generalizer
185 (t (call-next-method))))
186 (defmethod generalizer-equal-hash-key
187 ((gf cons-generic-function)
188 (g cons-generalizer))
190 (defmethod specializer-accepts-generalizer-p
191 ((gf cons-generic-function)
193 (g cons-generalizer))
194 (if (eql (%car s) (%car g))
197 (defmethod specializer-accepts-p
198 ((s cons-specializer) o)
199 (and (consp o) (eql (car o) (%car s))))
202 The code above shows the core of the use of our protocol. We have
203 elided some support code for parsing and unparsing specializers, and
204 for handling introspective functions such as finding generic functions
205 for a given specializer. We have also elided methods on the protocol
206 function =specializer<=; for =cons-specializers= here, specializer
207 ordering is trivial, as only one =cons-specializer= can ever be
208 applicable to any given argument. See section [[#Accept]] for a case
209 where specializer ordering is substantially different.
211 As in \cite{Newton.Rhodes:2008}, we can use these specializers to
212 implement a modular code walker, where we define one method per
213 special operator. We show two of those methods below, in the context
214 of a walker which checks for unused bindings and uses of unbound
218 (defgeneric walk (form env stack)
219 (:generic-function-class cons-generic-function))
220 (defmethod walk ((expr (cons lambda)) env call-stack)
221 (let ((lambda-list (cadr expr))
223 (with-checked-bindings
224 ((bindings-from-ll lambda-list) env call-stack)
226 (walk form env (cons form call-stack))))))
227 (defmethod walk ((expr (cons let)) env call-stack)
228 (flet ((let-binding (x)
229 (walk (cadr x) env (cons (cadr x) call-stack))
230 (cons (car x) (make-instance 'binding))))
231 (with-checked-bindings
232 ((mapcar #'let-binding (cadr expr)) env call-stack)
233 (dolist (form (cddr expr))
234 (walk form env (cons form call-stack))))))
237 Note that in this example there is no strict need for
238 =cons-specializer= and =cons-generalizer= to be distinct classes –
239 just as in the normal protocol involving
240 =compute-applicable-methods= and
241 =compute-applicable-methods-using-classes=, the specializer object
242 for mediating dispatch contains the same information as the object
243 representing the equivalence class of objects to which that
244 specializer is applicable: here it is the =car= of the =cons=
245 (which we wrap in a distinct object); in the standard dispatch it
246 is the =class= of the object. This feature also characterizes
247 those use cases where the metaprogrammer could straightforwardly
248 use filtered dispatch \cite{Costanza.etal:2008} to implement their
249 dispatch semantics. We will see in section [[#Accept]] an example
250 of a case where filtered dispatch is incapable of straightforwardly
251 expressing the dispatch, but first we present our implementation of
252 the motivating case from \cite{Costanza.etal:2008}.
253 ** SIGNUM specializers
257 Our second example of the implementation and use of generalized
258 specializers is a reimplementation of one of the examples in
259 \cite{Costanza.etal:2008}: specifically, the factorial function.
260 Here, we will perform dispatch based on the =signum= of the
261 argument, and again, at most one method with a =signum= specializer
262 will be appliable to any given argument, which makes the structure
263 of the specializer implementation very similar to the =cons=
264 specializers in the previous section.
266 We have chosen to compare signum values using \texttt{=}, which
267 means that a method with specializer =(signum 1)= will be
268 applicable to positive floating-point arguments (see the first
269 method on =specializer-accepts-generalizer-p= and the method on
270 =specializer=accepts-p= below). This leads to one subtle
271 difference in behaviour compared to that of the =cons=
272 specializers: in the case of =signum= specializers, the /next/
273 method after any =signum= specializer can be different, depending
274 on the class of the argument. This aspect of the dispatch is
275 handled by the second method on =specializer-accepts-generalizer-p=
278 (defclass signum-specializer (specializer)
279 ((%signum :reader %signum :initarg :signum)))
280 (defclass signum-generalizer (generalizer)
281 ((%signum :reader %signum :initarg :signum)))
282 (defmethod generalizer-of-using-class
283 ((gf signum-generic-function) arg)
285 (real (make-instance 'signum-generalizer
286 :signum (signum arg)))
287 (t (call-next-method))))
288 (defmethod generalizer-equal-hash-key
289 ((gf signum-generic-function)
290 (g signum-specializer))
292 (defmethod specializer-accepts-generalizer-p
293 ((gf signum-generic-function)
294 (s signum-specializer)
295 (g signum-generalizer))
296 (if (= (%signum s) (%signum g)) ; or EQL?
300 (defmethod specializer-accepts-generalizer-p
301 ((gf signum-generic-function)
302 (specializer sb-mop:specializer)
303 (thing signum-specializer))
304 (specializer-accepts-generalizer-p
305 gf specializer (class-of (%signum thing))))
307 (defmethod specializer-accepts-p
308 ((s signum-specializer) o)
309 (and (realp o) (= (%signum s) (signum o))))
312 Given these definitions, and once again some more straightforward
313 ones elided for reasons of space, we can implement the factorial
318 (:generic-function-class signum-generic-function))
319 (defmethod fact ((n (signum 0))) 1)
320 (defmethod fact ((n (signum 1))) (* n (fact (1- n))))
323 We do not need to include a method on =(signum -1)=, as the
324 standard =no-applicable-method= protocol will automatically apply to
325 negative real or non-real arguments.
326 ** Accept HTTP header specializers
330 In this section, we implement a non-trivial form of dispatch. The
331 application in question is a web server, and specifically to allow
332 the programmer to support RFC 2616 \cite{rfc2616} content
333 negotiation, of particular interest to publishers and consumers of
336 The basic mechanism in content negotiation is as follows: the web
337 client sends an HTTP request with an =Accept= header, which is a
338 string describing the media types it is willing to receive as a
339 response to the request, along with numerical preferences. The web
340 server compares these stated client preferences with the resources
341 it has available to satisfy this request, and sends the best
342 matching resource in its response.
344 For example, a graphical web browser might by default send an
345 =Accept= header such as
346 =text/html,application/xml;q=0.9,*/*;q=0.8=. This should be
347 interpreted by a web server as meaning that if for a given resource
348 the server can provide content of type =text/html= (i.e. HTML),
349 then it should do so. Otherwise, if it can provide
350 =application/xml= content (i.e. XML of any schema), then that
351 should be provided; failing that, any other content type is
354 In the case where there are static files on the filesystem, and the
355 web server must merely select between them, there is not much more
356 to say. However, it is not unusual for a web service to be backed
357 by some other form of data, and responses computed and sent on the
358 fly, and in these circumstances the web server must compute which
359 of its known output formats it can use to satisfy the request
360 before actually generating the best matching response. This can be
361 modelled as one generic function responsible for generating the
362 response, with methods corresponding to content-types -- and the
363 generic function must then perform method selection against the
364 request's =Accept= header to compute the appropriate response.
366 The =accept-specializer= below implements the dispatch. It depends
367 on a lazily-computed =tree= slot to represent the information in
368 the accept header (generated by =parse-accept-string=), and a
369 function =q= to compute the (defaulted) preference level for a
370 given content-type and =tree=; then, method selection and ordering
371 involves finding the =q= for each =accept-specializer='s content
372 type given the =tree=, and sorting them according to the preference
376 (defclass accept-specializer (specializer)
377 ((media-type :initarg :media-type :reader media-type)))
378 (defclass accept-generalizer (generalizer)
379 ((header :initarg :header :reader header)
381 (next :initarg :next :reader next)))
382 (defmethod generalizer-equal-hash-key
383 ((gf accept-generic-function)
384 (g accept-generalizer))
385 `(accept-generalizer ,(header g)))
386 (defmethod specializer-accepts-generalizer-p
387 ((gf accept-generic-function)
388 (s accept-specializer)
389 (generalizer accept-generalizer))
390 (values (q (media-type s) (tree generalizer)) t))
391 (defmethod specializer-accepts-generalizer-p
392 ((gf accept-generic-function)
394 (generalizer accept-generalizer))
395 (specializer-accepts-generalizer-p
396 gf s (next generalizer)))
398 (defmethod specializer<
399 ((gf accept-generic-function)
400 (s1 accept-specializer)
401 (s2 accept-specializer)
402 (generalizer accept-generalizer))
403 (let ((m1 (media-type s1))
405 (tree (tree generalizer)))
408 (t (let ((q1 (q m1 tree)))
416 The metaprogrammer can then support dispatching in this way for
417 suitable objects, such as the =request= object representing a
418 client request in the Hunchentoot web server. The code below
419 implements this, by defining the computation of a suitable
420 =generalizer= object for a given request, and specifying how to
421 compute whether the specializer accepts the given request object
422 (=q= returns a number between 0 and 1 if any pattern in the =tree=
423 matches the media type, and =nil= if the media type cannot be
427 (defmethod generalizer-of-using-class
428 ((gf accept-generic-function)
430 (make-instance 'accept-generalizer
431 :header (tbnl:header-in :accept arg)
432 :next (class-of arg)))
433 (defmethod specializer-accepts-p
434 ((specializer accept-specializer)
436 (let* ((accept (tbnl:header-in :accept obj))
437 (tree (parse-accept-string accept))
438 (q (q (media-type specializer) tree)))
442 This dispatch cannot be implemented using filtered dispatch, except
443 by generating anonymous classes with all the right mime-types as
444 direct superclasses in dispatch order; the filter would generate
446 (ensure-class nil :direct-superclasses
447 '(text/html image/webp ...))
449 and dispatch the operates using those anonymous classes. While
450 this is possible to do, it is awkward to express content-type
451 negotiation in this way, as it means that the dispatcher must know
452 about the universe of mime-types that clients might declare that
453 they accept, rather than merely the set of mime-types that a
454 particular generic function is capable of serving; handling
455 wildcards in accept strings is particularly awkward in the
458 Note that in this example, the method on =specializer<= involves a
459 nontrivial ordering of methods based on the =q= values specified in
460 the accept header (whereas in sections [[#Cons]] and [[#Signum]] only a
461 single extended specializer could be applicable to any given
464 Also note that the accept specializer protocol is straightforwardly
465 extensible to other suitable objects; for example, one simple
466 debugging aid is to define that an =accept-specializer= should be
467 applicable to =string= objects. This can be done in a modular
468 fashion (see the code below, which can be completely disconnected
469 from the code for Hunchentoot request objects), and generalizes to
470 dealing with multiple web server libraries, so that
471 content-negotiation methods are applicable to each web server's
475 (defmethod generalizer-of-using-class
476 ((gf accept-generic-function)
478 (make-instance 'accept-generalizer
481 (defmethod specializer-accepts-p
482 ((s accept-specializer) (string string))
483 (let* ((tree (parse-accept-string string))
484 (q (q (media-type s) tree)))
487 ** COMMENT Pattern / xpattern / regex / optima
488 Here's the /really/ interesting bit, but on the other hand we're
489 probably going to run out of space, and the full description of
490 these is going to take us into =make-method-lambda= territory.
491 A second paper? Future work?
497 In section [[#Examples]], we have seen a number of code fragments as
498 partial implementations of particular non-standard method dispatch,
499 using =generalizer= metaobjects to mediate between the methods of
500 the generic function and the actual arguments passed to it. In
501 section [[#Generalizer metaobjects]], we go into more detail regarding
502 these =generalizer= metaobjects, describing the generic function
503 invocation protocol in full, and showing how this protocol allows a
504 similar form of effective method cacheing as the standard one does.
505 In section [[#Generalizer performance]], we show the results of some
506 simple performance measurements on our implementation of this
507 protocol in the SBCL implementation \cite{Rhodes:2008} of Common
508 Lisp to highlight the improvement that this protocol can bring over
509 a naïve implementation of generalized dispatch, as well as
510 to make the potential for further improvement clear.
512 ** Generalizer metaobjects
514 :CUSTOM_ID: Generalizer metaobjects
517 *** Generic function invocation
518 As in the standard generic function invocation protocol, the
519 generic function's actual functionality is provided by a
520 discriminating function. The functionality described in this
521 protocol is implemented by having a distinct subclass of
522 =standard-generic-function=, and a method on
523 =compute-discriminating-function= which produces a custom
524 discriminating function. The basic outline of the discriminating
525 function is the same as the standard one: it must first compute the
526 set of applicable methods given particular arguments; from that, it
527 must compute the effective method by combining the methods
528 appropriately according to the generic function's method
529 combination; finally, it must call the effective method with the
532 Computing the set of applicable methods is done using a pair of
533 functions: =compute-applicable-methods=, the standard metaobject
534 function, and a new function
535 =compute-applicable-methods-using-generalizers=. We define a
536 custom method on =compute-applicable-methods= which tests the
537 applicability of a particular specializer against a given argument
538 using =specializer-accepts-p=, a new protocol function with
539 default implementations on =class= and =eql-specializer= to
540 implement the expected behaviour. In order to order the methods,
541 as required by the protocol, we define a pairwise comparison
542 operator =specializer<= which defines an ordering between
543 specializers for a given generalizer argument (remembering that
544 even in standard CLOS the ordering between =class= specializers
545 can change depending on the actual class of the argument).
547 The new =compute-applicable-methods-using-generalizers= is the
548 analogue of the MOP's =compute-applicable-methods-using-classes=.
549 Instead of calling it with the =class-of= each argument, we compute
550 the generalizers of each argument using the new function
551 =generalizer-of-using-class= (where the =-using-class= refers to
552 the class of the generic function rather than the class of the
553 object), and call it with the list of generalizers. As with the
554 standard function, a secondary return value indicates whether the
555 result of the function is definitive for that list of generalizers.
557 Thus, in generic function invocation, we first compute the
558 generalizers of the arguments; we compute the ordered set of
559 applicable methods, either from the generalizers or (if that is
560 not definitive) from the arguments themselves; then the normal
561 effective method computation and call can occur. Unfortunately,
562 the nature of an effective method object is not specified, so we
563 have to reach into implementation internals a little in order to
564 call it, but otherwise the remainder of the generic function
565 invocation protocol is unchanged from the standard one. In
566 particular, method combination is completely unchanged;
567 programmers can choose arbitrary method combinations, including
568 user-defined long form combinations, for their generic functions
569 involving generalized dispatch.
571 *** Effective method memoization
573 :CUSTOM_ID: Memoization
575 The potential efficiency benefit to having =generalizer=
576 metaobjects lies in the use of
577 =compute-applicable-methods-using-generalizers=. If a particular
578 generalized specializer accepts a variety of objects (such as the
579 =signum= specializer accepting all reals with a given sign, or the
580 =accept= specializer accepting all HTTP requests with a particular
581 =Accept= header), then there is the possibility of cacheing and
582 reusing the results of the applicable and effective method
583 computation. If the computation of the applicable method from
584 =compute-applicable-methods-using-generalizers= is definitive,
585 then the ordered set of applicable methods and the effective
586 method can be cached.
588 One issue is what to use as the key for that cache. We cannot use
589 the generalizers themselves, as two generalizers that should be
590 considered equal for cache lookup will not compare as =equal= –
591 and indeed even the standard generalizer, the =class=, cannot be
592 used as we must be able to invalidate cache entries upon class
593 redefinition. The issue of =class= generalizers we can solve as
594 in \cite{Kiczales.Rodriguez:1990} by using the =wrapper= of a
595 class, which is distinct for each distinct (re)definition of a
596 class; for arbitrary generalizers, however, there is /a priori/ no
597 good way of computing a suitable hash key automatically, so we
598 allow the metaprogrammer to specify one by defining a method on
599 =generalizer-equal-hash-key=, and combining the hash keys for all
600 required arguments in a list to use as a key in an =equal=
603 [XXX could we actually compute a suitable hash key using the
604 generalizer's class name and initargs?]
607 - [X] =generalizer-of-using-class= (NB class of gf not class of object)
608 - [X] =compute-applicable-methods-using-generalizers=
609 - [X] =generalizer-equal-hash-key=
610 - [X] =specializer-accepts-generalizer-p=
611 - [X] =specializer-accepts-p=
615 :CUSTOM_ID: Generalizer performance
617 We have argued that the protocol presented here allows for
618 expressive control of method dispatch while preserving the
619 possibility of efficiency. In this section, we quantify the
620 efficiency that the memoization protocol described in section
621 [[#Memoization]] achieves, by comparing it both to the same protocol
622 with no memoization, as well as with equivalent dispatch
623 implementations in the context of methods with regular specializers
624 (in an implementation similar to that in
625 \cite{Kiczales.Rodriguez:1990}), and with implementation in
626 straightforward functions.
628 In the case of the =cons-specializer=, we benchmark the walker
629 acting on a small but non-trivial form. The implementation
630 strategies in the table below refer to: an implementation in a
631 single function with a large =typecase= to dispatch between all the
632 cases; the natural implementation in terms of a standard generic
633 function with multiple methods (the method on =cons= having a
634 slightly reduced =typecase= to dispatch on the first element, and
635 other methods handling =symbol= and other atoms); and three
636 separate cases using =cons-specializer= objects. As well as
637 measuring the effect of memoization against the full invocation
638 protocol, we can also introduce a special case: when only one
639 argument participates in method selection (all the other required
640 arguments only being specialized on =t=), we can avoid the
641 construction of a list of hash keys and simply use the key
642 from the single active generalizer directly.
644 | implementation | time (µs/call) | overhead |
645 |-----------------------+----------------+----------|
646 | function | 3.17 | |
647 | standard-gf/methods | 3.6 | +14% |
648 | cons-gf/one-arg-cache | 7.4 | +130% |
649 | cons-gf | 15 | +370% |
650 | cons-gf/no-cache | 90 | +2700% |
652 The benchmarking results from this exercise are promising: in
653 particular, the introduction of the effective method cache speeds
654 up the use of generic specializers in this case by a factor of 6,
655 and the one-argument special case by another factor of 2. For this
656 workload, even the one-argument special case only gets to within a
657 factor of 2-3 of the function and standard generic function
658 implementations, but the overall picture is that the memoizability
659 in the protocol does indeed drastically reduce the overhead
660 compared with the full invocation.
662 For the =signum-specializer= case, we choose to benchmark the
663 computation of 20!, because that is the largest factorial whose
664 answer fits in SBCL's 63-bit fixnums – in an attempt to measure the
665 worst case for generic dispatch, where the work done within the
666 methods is as small as possible without being meaningless, and in
667 particular does not cause allocation or garbage collection to
670 #+begin_src lisp :exports none
671 (progn (gc :full t) (time (dotimes (i 10000) (%fact 20))))
674 | implementation | time (µs/call) | overhead |
675 |-------------------------+----------------+----------|
677 | standard-gf/fixnum | 1.2 | +100% |
678 | signum-gf/one-arg-cache | 7.5 | +1100% |
679 | signum-gf | 23 | +3800% |
680 | signum-gf/no-cache | 240 | +41000% |
682 The relative picture is similar to the =cons-specializer= case;
683 including a cache saves a factor of 10 in this case, and another
684 factor of 3 for the one-argument cache special case. The cost of
685 the genericity of the protocol here is starker; even the
686 one-argument cache is a factor of 6 slower than the standard
687 generic-function implementation, and a further factor of 2 away
688 from the implementation of factorial as a function. We discuss
689 ways in which we expect to be able to improve performance in
690 section [[#Future Work]].
692 We could allow the metaprogrammer to improve on the one-argument
693 performance by constructing a specialized cache: for =signum=
694 arguments of =rational= arguments, the logical cache structure is
695 to index a three-element vector with =(1+ signum)=. The current
696 protocol does not provide a way of eliding the two generic function
697 calls for the generic cache; we discuss possible approaches in
698 section [[#Conclusions]].
700 The protocol described in this paper is only part of a complete
701 protocol for =specializer= and =generalizer= metaobjects. Our
702 development of this protocol is as yet incomplete; the work
703 described here augments that in \cite{Newton.Rhodes:2008}, but is
704 yet relatively untested – and additionally our recent experience of
705 working with that earlier protocol suggests that there might be
706 useful additions to the handling of =specializer= metaobjects,
707 independent of the =generalizer= idea presented here.
710 Description and specification left for reasons of space (we'll see?)
711 - [ ] =same-specializer-p=
712 - [ ] =parse/unparse-specializer-using-class=
713 - [ ] =make-method-specializers-form=
714 - [ ] jmoringe: In an email, I suggested
715 =make-specializer-form-using-class=:
718 Could we change =make-method-specializers-form='s default
719 behaviour to call a new generic function
721 make-specializer-form-using-class gf method name env
723 with builtin methods on =sb-mop:specializer=, =symbol=, =cons= (for
724 eql-specializers)? This would make it unnecessary to repeat
725 boilerplate along the lines of
727 (flet ((make-parse-form (name)
728 (if <name-is-interesting>
729 <handle-interesting-specializer>
730 <repeat-handling-of-standard-specializers>)))
731 `(list ,@(mapcar #'make-parse-form specializer-names)))
733 for each generic function class.
735 - [ ] =make-method-lambda= revision (use environment arg?)
737 jmoringe: would only be relevant for pattern dispatch, right? I
738 think, we didn't finish the discussion regarding special
739 variables vs. environment vs. new protocol function
743 :CUSTOM_ID: Related Work
746 The work presented here builds on specializer-oriented programming
747 described in \cite{Newton.Rhodes:2008}. Approximately
748 contemporaneously, filtered dispatch \cite{Costanza.etal:2008} was
749 introduced to address some of the same use cases: filtered dispatch
750 works by having a custom discriminating function which wraps the
751 usual one, where the wrapping function augments the set of
752 applicable methods with applicable methods from other (hidden)
753 generic functions, one per filter group; this step is not memoized,
754 and using =eql= methods to capture behaviours of equivalence classes
755 means that it is hard to see how it could be. The methods are then
756 combined using a custom method combination to mimic the standard
757 one; in principle implementors of other method combinations could
758 cater for filtered dispatch, but they would have to explicitly
759 modify their method combinations. The Clojure programming language
760 supports multimethods[fn:5] with a variant of filtered dispatch as
761 well as hierachical and identity-based method selectors.
763 In context-oriented programming
764 \cite{Hirschfeld.etal:2008,Vallejos.etal:2010}, context dispatch
765 occurs by maintaining the context state as an anonymous class with
766 the superclasses representing all the currently active layers; this
767 is then passed as a hidden argument to context-aware functions. The
768 set of layers is known and under programmer control, as layers must
769 be defined beforehand.
771 In some sense, all dispatch schemes are specializations of predicate
772 dispatch \cite{Ernst.etal:1998}. The main problem with predicate
773 dispatch is its expressiveness: with arbitrary predicates able to
774 control dispatch, it is essentially impossible to perform any
775 substantial precomputation, or even to automatically determine an
776 ordering of methods given a set of arguments. Even Clojure's
777 restricted dispatch scheme provides an explicit operator for stating
778 a preference order among methods, where here we provide an operator
779 to order specializers; in filtered dispatch the programmer
780 implicitly gives the system an order of precedence, through the
781 lexical ordering of filter specification in a filtered function
784 The Slate programming environment combines prototype-oriented
785 programming with multiple dispatch \cite{Salzman.Aldrich:2005}; in
786 that context, the analogue of an argument's class (in Common Lisp)
787 as a representation of the equivalence class of objects with the
788 same behaviour is the tuple of roles and delegations: objects with
789 the same roles and delegations tuple behave the same, much as
790 objects with the same generalizer have the same behaviour in the
791 protocol described in this paper.
793 The idea of generalization is of course not new, and arises in other
794 contexts. Perhaps of particular interest is generalization in the
795 context of partial evaluation; for example, \cite{Ruf:1993}
796 considers generalization in online partial evaluation, where sets of
797 possible values are represented by a type system construct
798 representing an upper bound. The relationship between generalizer
799 metaobjects and approximation in type systems could be further
803 :CUSTOM_ID: Conclusions
805 In this paper, we have presented a new generalizer metaobject
806 protocol allowing the metaprogrammer to implement in a
807 straightforward manner metaobjects to implement custom method
808 selection, rather than the standard method selection as standardized
809 in Common Lisp. This protocol seamlessly interoperates with the
810 rest of CLOS and Common Lisp in general; the programmer (the user of
811 the custom specializer metaobjects) may without constraints use
812 arbitrary method combination, intercede in effective method
813 combination, or write custom method function implementations. The
814 protocol is expressive, in that it handles forms of dispatch not
815 possible in more restricted dispatch systems, while not suffering
816 from the indeterminism present in predicate dispatch through the use
817 of explicit ordering predicates.
819 The protocol is also reasonably efficient; the metaprogrammer can
820 indicate that a particular effective method computation can be
821 memoized, and under those circumstances much of the overhead is
822 amortized (though there remains a substantial overhead compared with
823 standard generic-function or regular function calls). We discuss
824 how the efficiency could be improved below.
827 :CUSTOM_ID: Future Work
829 Although the protocol described in this paper allows for a more
830 efficient implementation, as described in section [[#Memoization]],
831 than computing the applicable and effective methods at each generic
832 function call, the efficiency is still some way away from a
833 baseline of the standard generic-function, let alone a standard
834 function. Most of the invocation protocol is memoized, but there
835 are still two full standard generic-function calls –
836 =generalizer-of-using-class= and =generalizer-equal-hash-key= – per
837 argument per call to a generic function with extended specializers,
838 not to mention a hash table lookup.
840 For many applications, the additional flexibility afforded by
841 generalized specializers might be worth the cost in efficiency, but
842 it would still be worth investigating how much the overhead from
843 generalized specializers can be reduced; one possible avenue for
844 investigation is giving greater control over the cacheing strategy
845 to the metaprogrammer.
847 As an example, consider the =signum-specializer=. The natural
848 cache structure for a single argument generic function specializing
849 on =signum= is probably a four-element vector, where the first
850 three elements hold the effective methods for =signum= values of
851 -1, 0, and 1, and the fourth holds the cached effective methods for
852 everything else. This would make the invocation of such functions
853 very fast for the (presumed) common case where the argument is in
854 fact a real number. We hope to develop and show the effectiveness
855 of an appropriate protocol to allow the metaprogrammer to construct
856 and exploit such cacheing strategies, and (more speculatively) to
857 implement the lookup of an effective method function in other ways.
859 We also aim to demonstrate support within this protocol for some
860 particular cases of generalized specializers which seem to have
861 widespread demand (in as much as any language extension can be said
862 to be in “demand”). In particular, we have preliminary work
863 towards supporting efficient dispatch over pattern specializers
864 such as implemented in the \textsf{Optima} library[fn:4], and over
865 a prototype object system similar to that in Slate
866 \cite{Salzman.Aldrich:2005}. Our current source code for the work
867 described in this paper can be seen in the git source code
868 repository at [[http://christophe.rhodes.io/git/specializable.git]],
869 which will be updated with future developments.
871 Finally, after further experimentation (and, ideally, non-trivial
872 use in production) if this protocol stands up to use as we hope, we
873 aim to produce a standards-quality document so that other
874 implementors of Common Lisp can, if they choose, independently
875 reimplement the protocol, and so that users can use the protocol
876 with confidence that the semantics will not change in a
877 backwards-incompatible fashion.
879 We thank Lee Salzman, Pascal Costanza and Mikel Evins for helpful
880 and informative discussions, and all the respondents to one
881 author's request for imaginative uses for generalized specializers.
883 \bibliographystyle{plain}
884 \bibliography{crhodes,specializers}
888 [fn:1] GNU CLISP, at http://www.clisp.org/
890 [fn:2] Clozure Common Lisp, at http://ccl.clozure.com/
892 [fn:3] the \textsf{Closer to MOP} project, at
893 http://common-lisp.net/project/closer/, attempts to harmonize the
894 different implementations of the metaobject protocol in Common
897 [fn:4] https://github.com/m2ym/optima
899 [fn:5] http://clojure.org/multimethods