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}")))
17 (set (make-local-variable 'org-latex-title-command)
20 \\alignauthor Christophe Rhodes\\\\
21 \\affaddr{Department of Computing}\\\\
22 \\affaddr{Goldsmiths, University of London}\\\\
23 \\affaddr{London SE14 6NW}\\\\
24 \\email{c.rhodes@gold.ac.uk}
25 \\alignauthor Jan Moringen\\\\
26 \\affaddr{Universität Bielefeld}\\\\
27 \\affaddr{Technische Fakultät}\\\\
28 \\affaddr{33594 Bielefeld}\\\\
29 \\email{jmoringe@techfak.uni-bielefeld.de}
30 \\alignauthor David Lichteblau\\\\
31 \\affaddr{ZenRobotics Ltd}\\\\
32 \\affaddr{Vilhonkatu 5 A}\\\\
33 \\affaddr{FI-00100 Helsinki}\\\\
34 \\email{david@lichteblau.com}
40 This paper introduces a new metaobject, the generalizer, which
41 complements the existing specializer metaobject. With the help of
42 examples, we show that this metaobject allows for the efficient
43 implementation of complex non-class-based dispatch within the
44 framework of existing metaobject protocols. We present our
45 modifications to the generic function invocation protocol from the
46 /Art of the Metaobject Protocol/; in combination with previous work,
47 this produces a fully-functional extension of the existing mechanism
48 for method selection and combination, including support for method
49 combination completely independent from method selection. We discuss
50 our implementation, within the SBCL implementation of Common Lisp, and
51 in that context compare the performance of the new protocol with the
52 standard one, demonstrating that the new protocol can be tolerably
57 \category{D.1}{Software}{Programming Techniques}[Object-oriented Programming]
58 \category{D.3.3}{Programming Languages}{Language Constructs and Features}
59 \terms{Languages, Design}
60 \keywords{generic functions, specialization-oriented programming, method selection, method combination}
64 The revisions to the original Common Lisp language \cite{CLtL}
65 included the detailed specification of an object system, known as
66 the Common Lisp Object System (CLOS), which was eventually
67 standardized as part of the ANSI Common Lisp standard \cite{CLtS}.
68 The object system as presented to the standardization committee was
69 formed of three chapters. The first two chapters covered programmer
70 interface concepts and the functions in the programmer interface
71 \cite[Chapter 28]{CLtL2} and were largely incorporated into the
72 final standard; the third chapter, covering a Metaobject Protocol
73 (MOP) for CLOS, was not.
75 Nevertheless, the CLOS MOP has proven to be a robust design, and
76 while many implementations have derived their implementations of
77 CLOS from either the Closette illustrative implementation in
78 \cite{AMOP}, or the Portable Common Loops implementation of CLOS
79 from Xerox Parc, there have been largely from-scratch
80 reimplementations of CLOS (in CLISP[fn:1] and CCL[fn:2], at least)
81 incorporating substantial fractions of the Metaobject Protocol as
84 Although it has stood the test of time, the CLOS MOP is neither
85 without issues (e.g. semantic problems with =make-method-lambda=
86 \cite{Costanza.Herzeel:2008}; useful functions such as
87 =compute-effective-slot-definition-initargs= being missing from the
88 standard) nor is it a complete framework for the metaprogrammer to
89 implement all conceivable variations of object-oriented behaviour.
90 While metaprogramming offers some possibilities for customization of
91 the object system behaviour, those possibilities cannot extend
92 arbitrarily in all directions. There is still an expectation that
93 functionality is implemented with methods on generic functions,
94 acting on objects with slots; it is not possible, for example, to
95 transparently implement support for “message not understood” as in
96 the message-passing paradigm, because the analogue of messages
97 (generic functions) need to be defined before they are used.
99 Nevertheless, the MOP is flexible, and is used for a number of
100 things, including: documentation generation (where introspection in
101 the MOP is used to extract information from a running system);
102 object-relational mapping and other approaches to object
103 persistence; alternative backing stores for slots (hash-tables or
104 symbols); and programmatic construction of metaobjects, for example
105 for IDL compilers and model transformations.
107 [ XXX: A picture on MOP flexibility here would be good; I have in my mind
108 one where an object system is a point and the MOP opens up a blob
109 around that point, and I'm sure I've seen it somewhere but I can't
110 remember where. Alternatively, there's Kiczales et al "MOPs: why we
111 want them and what else they can do", fig. 2 ]
112 [AMOP, page 5] paints that picture, but again, only using words :)
114 One area of functionality where there is scope for customization by
115 the metaprogrammer is in the mechanics and semantics of method
116 applicability and dispatch. While in principle AMOP allows
117 customization of dispatch in various different ways (the
118 metaprogrammer can define methods on protocol functions such as
119 =compute-applicable-methods=,
120 =compute-applicable-methods-using-classes=), for example, in
121 practice implementation support for this was weak until relatively
124 Another potential mechanism for customizing dispatch is implicit in
125 the class structure defined by AMOP: standard specializer objects
126 (instances of =class= and =eql-specializer=) are generalized
127 instances of the =specializer= protocol class, and in principle
128 there are no restrictions on the metaprogrammer constructing
129 additional subclasses. Previous work \cite{Newton.Rhodes:2008} has
130 explored the potential for customizing generic function dispatch
131 using extended specializers, but there the metaprogrammer must
132 override the entirety of the generic function invocation protocol
133 (from =compute-discriminating-function= on down), leading to toy
134 implementations and duplicated effort.
136 This paper introduces a protocol for efficient and controlled
137 handling of new subclasses of =specializer=. In particular, it
138 introduces the =generalizer= protocol class, which generalizes the
139 return value of =class-of= in method applicability computation, and
140 allows the metaprogrammer to hook into cacheing schemes to avoid
141 needless recomputation of effective methods for sufficiently similar
142 generic function arguments (See Figure\nbsp\ref{fig:dispatch}).
144 #+CAPTION: Dispatch Comparison
145 #+LABEL: fig:dispatch
146 #+ATTR_LATEX: width=0.9\linewidth float
147 [[file:figures/dispatch-comparison.pdf]]
149 The remaining sections in this paper can be read in any order. We
150 give some motivating examples in section [[#Examples]], including
151 reimplementations of examples from previous work, as well as
152 examples which are poorly supported by previous protocols. We
153 describe the protocol itself in section [[#Protocol]], describing each
154 protocol function in detail and, where applicable, relating it to
155 existing protocol functions within the CLOS MOP. We survey related
156 work in more detail in section [[#Related Work]], touching on work on
157 customized dispatch schemes in other environments. Finally, we draw
158 our conclusions from this work, and indicate directions for further
159 development, in section [[#Conclusions]]; reading that section before the
160 others indicates substantial trust in the authors' work.
165 In this section, we present a number of examples of dispatch
166 implemented using our protocol, which we describe in section
167 [[#Protocol]]. For reasons of space, the metaprogram code examples in
168 this section do not include some of the necessary support code to
169 run; complete implementations of each of these cases, along with the
170 integration of this protocol into the SBCL implementation
171 \cite{Rhodes:2008} of Common Lisp, are included in an appendix / in
172 the accompanying repository snapshot / at this location.
174 A note on terminology: we will attempt to distinguish between the
175 user of an individual case of generalized dispatch (the
176 “programmer”), the implementor of a particular case of generalized
177 dispatch (the “metaprogrammer”), and the authors as the designers
178 and implementors of our generalized dispatch protocol (the
179 “metametaprogammer”, or more likely “we”).
184 One motivation for the use of generalized dispatch is in an
185 extensible code walker: a new special form can be handled simply by
186 writing an additional method on the walking generic function,
187 seamlessly interoperating with all existing methods. In this
188 use-case, dispatch is performed on the first element of lists.
189 Semantically, we allow the programmer to specialize any argument of
190 methods with a new kind of specializer, =cons-specializer=, which
191 is applicable if and only if the corresponding object is a =cons=
192 whose =car= is =eql= to the symbol associated with the
193 =cons-specializer=; these specializers are more specific than the
194 =cons= class, but less specific than an =eql-specializer= on any
197 The programmer code using these specializers is unchanged from
198 \cite{Newton.Rhodes:2008}; the benefits of the protocol described
199 here are: that the separation of concerns is complete – method
200 selection is independent of method combination – and that the
201 protocol allows for efficient implementation where possible, even
202 when method selection is customized. In an application such as
203 walking source code, we would expect to encounter special forms
204 (distinguished by particular atoms in the =car= position) multiple
205 times, and hence to dispatch to the same effective method
206 repeatedly. We discuss the efficiency aspects of the protocol in
207 more detail in section [[#Memoization]]; we present the metaprogrammer
208 code to implement the =cons-specializer= below.
211 (defclass cons-specializer (specializer)
212 ((%car :reader %car :initarg :car)))
213 (defclass cons-generalizer (generalizer)
214 ((%car :reader %car :initarg :car)))
215 (defmethod generalizer-of-using-class
216 ((gf cons-generic-function) arg)
219 (make-instance 'cons-generalizer
221 (t (call-next-method))))
222 (defmethod generalizer-equal-hash-key
223 ((gf cons-generic-function)
224 (g cons-generalizer))
226 (defmethod specializer-accepts-generalizer-p
227 ((gf cons-generic-function)
229 (g cons-generalizer))
230 (if (eql (%car s) (%car g))
233 (defmethod specializer-accepts-p
234 ((s cons-specializer) o)
235 (and (consp o) (eql (car o) (%car s))))
238 The code above shows a minimal use of our protocol. We have elided
239 some support code for parsing and unparsing specializers, and for
240 handling introspective functions such as finding generic functions for
241 a given specializer. We have also elided methods on the protocol
242 functions =specializer<= and =same-specializer-p=; for
243 =cons-specializer= objects, specializer ordering is trivial, as only
244 one =cons-specializer= (up to equality) can ever be applicable to any
245 given argument. See section [[#Accept]] for a case where specializer
246 ordering is non-trivial.
248 As in \cite{Newton.Rhodes:2008}, the programmer can use these
249 specializers to implement a modular code walker, where they define one
250 method per special operator. We show two of those methods below, in
251 the context of a walker which checks for unused bindings and uses of
255 (defgeneric walk (form env stack)
256 (:generic-function-class cons-generic-function))
258 ((expr (cons lambda)) env call-stack)
259 (let ((lambda-list (cadr expr))
261 (with-checked-bindings
262 ((bindings-from-ll lambda-list)
265 (walk form env (cons form call-stack))))))
267 ((expr (cons let)) env call-stack)
268 (flet ((let-binding (x)
270 (cons (cadr x) call-stack))
272 (make-instance 'binding))))
273 (with-checked-bindings
274 ((mapcar #'let-binding (cadr expr))
276 (dolist (form (cddr expr))
277 (walk form env (cons form call-stack))))))
280 Note that in this example there is no strict need for
281 =cons-specializer= and =cons-generalizer= to be distinct classes.
282 In standard generic function dispatch, the =class= functions both
283 as the specializer for methods and as the generalizer for generic
284 function arguments; we can think of the dispatch implemented by
285 =cons-specializer= objects as providing for subclasses of the
286 =cons= class distinguished by the =car= of the =cons=. This
287 analogy also characterizes those use cases where the metaprogrammer
288 could straightforwardly use filtered dispatch
289 \cite{Costanza.etal:2008} to implement their dispatch semantics.
290 We will see in section [[#Accept]] an example of a case where filtered
291 dispatch is incapable of straightforwardly expressing the dispatch,
292 but first we present our implementation of the motivating case from
293 \cite{Costanza.etal:2008}.
294 ** SIGNUM specializers
298 Our second example of the implementation and use of generalized
299 specializers is a reimplementation of one of the examples in
300 \cite{Costanza.etal:2008}: specifically, the factorial function.
301 Here, dispatch will be performed based on the =signum= of the
302 argument, and again, at most one method with a =signum= specializer
303 will be applicable to any given argument, which makes the structure
304 of the specializer implementation very similar to the =cons=
305 specializers in the previous section.
307 The metaprogrammer has chosen in the example below to compare
308 signum values using \texttt{=}, which means that a method with
309 specializer =(signum 1)= will be applicable to positive
310 floating-point arguments (see the first method on
311 =specializer-accepts-generalizer-p= and the method on
312 =specializer-accepts-p= below). This leads to one subtle
313 difference in behaviour compared to that of the =cons=
314 specializers: in the case of =signum= specializers, the /next/
315 method after any =signum= specializer can be different, depending
316 on the class of the argument. This aspect of the dispatch is
317 handled by the second method on =specializer-accepts-generalizer-p=
321 (defclass signum-specializer (specializer)
322 ((%signum :reader %signum :initarg :signum)))
323 (defclass signum-generalizer (generalizer)
324 ((%signum :reader %signum :initarg :signum)))
325 (defmethod generalizer-of-using-class
326 ((gf signum-generic-function) (arg real))
327 (make-instance 'signum-generalizer
328 :signum (signum arg)))
329 (defmethod generalizer-equal-hash-key
330 ((gf signum-generic-function)
331 (g signum-generalizer))
333 (defmethod specializer-accepts-generalizer-p
334 ((gf signum-generic-function)
335 (s signum-specializer)
336 (g signum-generalizer))
337 (if (= (%signum s) (%signum g))
341 (defmethod specializer-accepts-generalizer-p
342 ((gf signum-generic-function)
344 (g signum-generalizer))
345 (specializer-accepts-generalizer-p
346 gf s (class-of (%signum g))))
348 (defmethod specializer-accepts-p
349 ((s signum-specializer) o)
350 (and (realp o) (= (%signum s) (signum o))))
353 Given these definitions, and once again some more straightforward
354 ones elided for reasons of space, the programmer can implement the
355 factorial function as follows:
359 (:generic-function-class signum-generic-function))
360 (defmethod fact ((n (signum 0))) 1)
361 (defmethod fact ((n (signum 1))) (* n (fact (1- n))))
364 The programmer does not need to include a method on =(signum -1)=,
365 as the standard =no-applicable-method= protocol will automatically
366 apply to negative real or non-real arguments.
367 ** Accept HTTP header specializers
371 In this section, we implement a non-trivial form of dispatch. The
372 application in question is a web server, and specifically to allow
373 the programmer to support RFC 2616 \cite{rfc2616} content
374 negotiation, of particular interest to publishers and consumers of
377 The basic mechanism in content negotiation is as follows: the web
378 client sends an HTTP request with an =Accept= header, which is a
379 string describing the media types it is willing to receive as a
380 response to the request, along with numerical preferences. The web
381 server compares these stated client preferences with the resources
382 it has available to satisfy this request, and sends the best
383 matching resource in its response.
385 For example, a graphical web browser might send an =Accept= header
386 of =text/html,application/xml;q=0.9,*/*;q=0.8= for a request of a
387 resource typed in to the URL bar. This should be interpreted as
388 meaning that: if the server can provide content of type =text/html=
389 (i.e. HTML) for that resource, then it should do so. Otherwise, if
390 it can provide =application/xml= content (i.e. XML of any schema),
391 then that should be provided; failing that, any other content type
394 In the case where there are static files on the filesystem, and the
395 web server must merely select between them, there is not much more
396 to say. However, it is not unusual for a web service to be backed
397 by some other form of data, and responses computed and sent on the
398 fly, and in these circumstances the web server must compute which
399 of its known output formats it can use to satisfy the request
400 before actually generating the best matching response. This can be
401 modelled as one generic function responsible for generating the
402 response, with methods corresponding to content-types -- and the
403 generic function must then perform method selection against the
404 request's =Accept= header to compute the appropriate response.
406 The =accept-specializer= below implements this dispatch. It depends
407 on a lazily-computed =tree= slot to represent the information in
408 the accept header (generated by =parse-accept-string=), and a
409 function =q= to compute the (defaulted) preference level for a
410 given content-type and =tree=; then, method selection and ordering
411 involves finding the =q= for each =accept-specializer='s content
412 type given the =tree=, and sorting them according to the preference
416 (defclass accept-specializer (specializer)
417 ((media-type :initarg :media-type :reader media-type)))
418 (defclass accept-generalizer (generalizer)
419 ((header :initarg :header :reader header)
421 (next :initarg :next :reader next)))
422 (defmethod generalizer-equal-hash-key
423 ((gf accept-generic-function)
424 (g accept-generalizer))
425 `(accept-generalizer ,(header g)))
426 (defmethod specializer-accepts-generalizer-p
427 ((gf accept-generic-function)
428 (s accept-specializer)
429 (g accept-generalizer))
430 (values (q (media-type s) (tree g)) t))
431 (defmethod specializer-accepts-generalizer-p
432 ((gf accept-generic-function)
434 (g accept-generalizer))
435 (specializer-accepts-generalizer-p
438 (defmethod specializer<
439 ((gf accept-generic-function)
440 (s1 accept-specializer)
441 (s2 accept-specializer)
442 (g accept-generalizer))
443 (let ((m1 (media-type s1))
448 (t (let ((q1 (q m1 tree)))
456 The metaprogrammer can then add support for objects representing
457 client requests, such as instances of the =request= class in the
458 Hunchentoot web server, by translating these into
459 =accept-generalizer= instances. The code below implements this, by
460 defining the computation of a =generalizer= object for a given
461 request, and specifying how to compute whether the specializer
462 accepts the given request object (=q= returns a number between 0
463 and 1 if any pattern in the =tree= matches the media type, and
464 =nil= if the media type cannot be matched at all).
467 (defmethod generalizer-of-using-class
468 ((gf accept-generic-function)
470 (make-instance 'accept-generalizer
471 :header (tbnl:header-in :accept arg)
472 :next (call-next-method)))
473 (defmethod specializer-accepts-p
474 ((s accept-specializer)
476 (let* ((accept (tbnl:header-in :accept o))
477 (tree (parse-accept-string accept))
478 (q (q (media-type s) tree)))
482 This dispatch cannot be implemented using filtered dispatch, except
483 by generating anonymous classes with all the right mime-types as
484 direct superclasses in dispatch order; the filter would generate
486 (ensure-class nil :direct-superclasses
487 '(text/html image/webp ...))
489 and dispatch would operate using those anonymous classes. While
490 this is possible to do, it is awkward to express content-type
491 negotiation in this way, as it means that the dispatcher must know
492 about the universe of mime-types that clients might declare that
493 they accept, rather than merely the set of mime-types that a
494 particular generic function is capable of serving; handling
495 wildcards in accept strings is particularly awkward in the
498 Note that in this example, the method on =specializer<= involves a
499 non-trivial ordering of methods based on the =q= values specified
500 in the accept header (whereas in sections [[#Cons]] and [[#Signum]] only a
501 single extended specializer could be applicable to any given
504 Also note that the accept specializer protocol is straightforwardly
505 extensible to other suitable objects; for example, one simple
506 debugging aid is to define that an =accept-specializer= should be
507 applicable to =string= objects. This can be done in a modular
508 fashion (see the code below, which can be completely disconnected
509 from the code for Hunchentoot request objects), and generalizes to
510 dealing with multiple web server libraries, so that
511 content-negotiation methods are applicable to each web server's
515 (defmethod generalizer-of-using-class
516 ((gf accept-generic-function)
518 (make-instance 'accept-generalizer
520 :next (call-next-method)))
521 (defmethod specializer-accepts-p
522 ((s accept-specializer) (o string))
523 (let* ((tree (parse-accept-string o))
524 (q (q (media-type s) tree)))
528 The =next= slot in the =accept-generalizer= is used to deal with
529 the case of methods specialized on the classes of objects as well
530 as on the acceptable media types; there is a method on
531 =specializer-accepts-generalizer-p= for specializers that are not
532 of type =accept-specializer= which calls the generic function again
533 with the next generalizer, so that methods specialized on the
534 classes =tbnl:request= and =string= are treated as applicable to
535 corresponding objects, though less specific than methods with
536 =accept-specializer= specializations.
538 ** COMMENT Pattern / xpattern / regex / optima
539 Here's the /really/ interesting bit, but on the other hand we're
540 probably going to run out of space, and the full description of
541 these is going to take us into =make-method-lambda= territory.
542 A second paper? Future work?
548 In section [[#Examples]], we have seen a number of code fragments as
549 partial implementations of particular non-standard method dispatch
550 strategies, using =generalizer= metaobjects to mediate between the
551 methods of the generic function and the actual arguments passed to
552 it. In section [[#Generalizer metaobjects]], we go into more detail
553 regarding these =generalizer= metaobjects, describing the generic
554 function invocation protocol in full, and showing how this protocol
555 allows a similar form of effective method cacheing as the standard
556 one does. In section [[#Generalizer performance]], we show the results
557 of some simple performance measurements on our implementation of
558 this protocol in the SBCL implementation \cite{Rhodes:2008} of
559 Common Lisp to highlight the improvement that this protocol can
560 bring over a naïve implementation of generalized dispatch, as well
561 as to make the potential for further improvement clear.
563 ** Generalizer metaobjects
565 :CUSTOM_ID: Generalizer metaobjects
568 *** Generic function invocation
569 As in the standard generic function invocation protocol, the
570 generic function's actual functionality is provided by a
571 discriminating function. The functionality described in this
572 protocol is implemented by having a distinct subclass of
573 =standard-generic-function=, and a method on
574 =compute-discriminating-function= which produces a custom
575 discriminating function. The basic outline of the discriminating
576 function is the same as the standard one: it must first compute the
577 set of applicable methods given particular arguments; from that, it
578 must compute the effective method by combining the methods
579 appropriately according to the generic function's method
580 combination; finally, it must call the effective method with the
583 Computing the set of applicable methods is done using a pair of
584 functions: =compute-applicable-methods=, the standard metaobject
585 function, and a new function
586 =compute-applicable-methods-using-generalizers=. We define a
587 custom method on =compute-applicable-methods= which tests the
588 applicability of a particular specializer against a given argument
589 using =specializer-accepts-p=, a new protocol function with
590 default implementations on =class= and =eql-specializer= to
591 implement the expected behaviour. To order the methods, as
592 required by the protocol, we define a pairwise comparison operator
593 =specializer<= which defines an ordering between specializers for
594 a given generalizer argument (remembering that even in standard
595 CLOS the ordering between =class= specializers can change
596 depending on the actual class of the argument).
598 The new =compute-applicable-methods-using-generalizers= is the
599 analogue of the MOP's =compute-applicable-methods-using-classes=.
600 Instead of calling it with the =class-of= each argument, we compute
601 the generalizers of each argument using the new function
602 =generalizer-of-using-class= (where the =-using-class= refers to
603 the class of the generic function rather than the class of the
604 object), and call it with the list of generalizers. As with the
605 standard function, a secondary return value indicates whether the
606 result of the function is definitive for that list of generalizers.
608 Thus, in generic function invocation, we first compute the
609 generalizers of the arguments; we compute the ordered set of
610 applicable methods, either from the generalizers or (if that is
611 not definitive) from the arguments themselves; then the normal
612 effective method computation and call can occur. Unfortunately,
613 the nature of an effective method object is not specified, so we
614 have to reach into implementation internals a little in order to
615 call it, but otherwise the remainder of the generic function
616 invocation protocol is unchanged from the standard one. In
617 particular, method combination is completely unchanged;
618 programmers can choose arbitrary method combinations, including
619 user-defined long form combinations, for their generic functions
620 involving generalized dispatch.
622 *** Effective method memoization
624 :CUSTOM_ID: Memoization
626 The potential efficiency benefit to having =generalizer=
627 metaobjects lies in the use of
628 =compute-applicable-methods-using-generalizers=. If a particular
629 generalized specializer accepts a variety of objects (such as the
630 =signum= specializer accepting all reals with a given sign, or the
631 =accept= specializer accepting all HTTP requests with a particular
632 =Accept= header), then there is the possibility of cacheing and
633 reusing the results of the applicable and effective method
634 computation. If the computation of the applicable method from
635 =compute-applicable-methods-using-generalizers= is definitive,
636 then the ordered set of applicable methods and the effective
637 method can be cached.
639 One issue is what to use as the key for that cache. We cannot use
640 the generalizers themselves, as two generalizers that should be
641 considered equal for cache lookup will not compare as =equal= –
642 and indeed even the standard generalizer, the =class=, cannot be
643 used as we must be able to invalidate cache entries upon class
644 redefinition. The issue of =class= generalizers we can solve as
645 in \cite{Kiczales.Rodriguez:1990} by using the =wrapper= of a
646 class, which is distinct for each distinct (re)definition of a
647 class; for arbitrary generalizers, however, there is /a priori/ no
648 good way of computing a suitable hash key automatically, so we
649 allow the metaprogrammer to specify one by defining a method on
650 =generalizer-equal-hash-key=, and combining the hash keys for all
651 required arguments in a list to use as a key in an =equal=
654 [XXX could we actually compute a suitable hash key using the
655 generalizer's class name and initargs?]
658 - [X] =generalizer-of-using-class= (NB class of gf not class of object)
659 - [X] =compute-applicable-methods-using-generalizers=
660 - [X] =generalizer-equal-hash-key=
661 - [X] =specializer-accepts-generalizer-p=
662 - [X] =specializer-accepts-p=
666 :CUSTOM_ID: Generalizer performance
668 We have argued that the protocol presented here allows for
669 expressive control of method dispatch while preserving the
670 possibility of efficiency. In this section, we quantify the
671 efficiency that the memoization protocol described in section
672 [[#Memoization]] achieves, by comparing it both to the same protocol
673 with no memoization, as well as with equivalent dispatch
674 implementations in the context of methods with regular specializers
675 (in an implementation similar to that in
676 \cite{Kiczales.Rodriguez:1990}), and with implementation in
677 straightforward functions.
679 In the case of the =cons-specializer=, we benchmark the walker
680 acting on a small but non-trivial form. The implementation
681 strategies in the table below refer to: an implementation in a
682 single function with a large =typecase= to dispatch between all the
683 cases; the natural implementation in terms of a standard generic
684 function with multiple methods (the method on =cons= having a
685 slightly reduced =typecase= to dispatch on the first element, and
686 other methods handling =symbol= and other atoms); and three
687 separate cases using =cons-specializer= objects. As well as
688 measuring the effect of memoization against the full invocation
689 protocol, we can also introduce a special case: when only one
690 argument participates in method selection (all the other required
691 arguments only being specialized on =t=), we can avoid the
692 construction of a list of hash keys and simply use the key
693 from the single active generalizer directly.
695 | implementation | time (µs/call) | overhead |
696 |-----------------------+----------------+----------|
697 | function | 3.17 | |
698 | standard-gf/methods | 3.6 | +14% |
699 | cons-gf/one-arg-cache | 7.4 | +130% |
700 | cons-gf | 15 | +370% |
701 | cons-gf/no-cache | 90 | +2700% |
703 The benchmarking results from this exercise are promising: in
704 particular, the introduction of the effective method cache speeds
705 up the use of generic specializers in this case by a factor of 6,
706 and the one-argument special case by another factor of 2. For this
707 workload, even the one-argument special case only gets to within a
708 factor of 2-3 of the function and standard generic function
709 implementations, but the overall picture is that the memoizability
710 in the protocol does indeed drastically reduce the overhead
711 compared with the full invocation.
713 For the =signum-specializer= case, we choose to benchmark the
714 computation of 20!, because that is the largest factorial whose
715 answer fits in SBCL's 63-bit fixnums – in an attempt to measure the
716 worst case for generic dispatch, where the work done within the
717 methods is as small as possible without being meaningless, and in
718 particular does not cause heap allocation or garbage collection to
721 #+begin_src lisp :exports none
722 (progn (gc :full t) (time (dotimes (i 10000) (%fact 20))))
725 | implementation | time (µs/call) | overhead |
726 |-------------------------+----------------+----------|
728 | standard-gf/fixnum | 1.2 | +100% |
729 | signum-gf/one-arg-cache | 7.5 | +1100% |
730 | signum-gf | 23 | +3800% |
731 | signum-gf/no-cache | 240 | +41000% |
733 The relative picture is similar to the =cons-specializer= case;
734 including a cache saves a factor of 10 in this case, and another
735 factor of 3 for the one-argument cache special case. The cost of
736 the genericity of the protocol here is starker; even the
737 one-argument cache is a factor of 6 slower than the standard
738 generic-function implementation, and a further factor of 2 away
739 from the implementation of factorial as a function. We discuss
740 ways in which we expect to be able to improve performance in
741 section [[#Future Work]].
743 We could allow the metaprogrammer to improve on the one-argument
744 performance by constructing a specialized cache: for =signum=
745 arguments of =rational= arguments, the logical cache structure is
746 to index a three-element vector with =(1+ signum)=. The current
747 protocol does not provide a way of eliding the two generic function
748 calls for the generic cache; we discuss possible approaches in
749 section [[#Conclusions]].
751 The protocol described in this paper is only part of a complete
752 protocol for =specializer= and =generalizer= metaobjects. Our
753 development of this protocol is as yet incomplete; the work
754 described here augments that in \cite{Newton.Rhodes:2008}, but is
755 yet relatively untested – and additionally our recent experience of
756 working with that earlier protocol suggests that there might be
757 useful additions to the handling of =specializer= metaobjects,
758 independent of the =generalizer= idea presented here.
761 Description and specification left for reasons of space (we'll see?)
762 - [ ] =same-specializer-p=
763 - [ ] =parse/unparse-specializer-using-class=
764 - [ ] =make-method-specializers-form=
765 - [ ] jmoringe: In an email, I suggested
766 =make-specializer-form-using-class=:
769 Could we change =make-method-specializers-form='s default
770 behaviour to call a new generic function
772 make-specializer-form-using-class gf method name env
774 with builtin methods on =sb-mop:specializer=, =symbol=, =cons= (for
775 eql-specializers)? This would make it unnecessary to repeat
776 boilerplate along the lines of
778 (flet ((make-parse-form (name)
779 (if <name-is-interesting>
780 <handle-interesting-specializer>
781 <repeat-handling-of-standard-specializers>)))
782 `(list ,@(mapcar #'make-parse-form specializer-names)))
784 for each generic function class.
786 - [ ] =make-method-lambda= revision (use environment arg?)
788 jmoringe: would only be relevant for pattern dispatch, right? I
789 think, we didn't finish the discussion regarding special
790 variables vs. environment vs. new protocol function
794 :CUSTOM_ID: Related Work
797 The work presented here builds on specializer-oriented programming
798 described in \cite{Newton.Rhodes:2008}. Approximately
799 contemporaneously, filtered dispatch \cite{Costanza.etal:2008} was
800 introduced to address some of the same use cases: filtered dispatch
801 works by having a custom discriminating function which wraps the
802 usual one, where the wrapping function augments the set of
803 applicable methods with applicable methods from other (hidden)
804 generic functions, one per filter group; this step is not memoized,
805 and using =eql= methods to capture behaviours of equivalence classes
806 means that it is hard to see how it could be. The methods are then
807 combined using a custom method combination to mimic the standard
808 one; in principle implementors of other method combinations could
809 cater for filtered dispatch, but they would have to explicitly
810 modify their method combinations. The Clojure programming language
811 supports multimethods[fn:5] with a variant of filtered dispatch as
812 well as hierarchical and identity-based method selectors.
814 In context-oriented programming
815 \cite{Hirschfeld.etal:2008,Vallejos.etal:2010}, context dispatch
816 occurs by maintaining the context state as an anonymous class with
817 the superclasses representing all the currently active layers; this
818 is then passed as a hidden argument to context-aware functions. The
819 set of layers is known and under programmer control, as layers must
820 be defined beforehand.
822 In some sense, all dispatch schemes are specializations of predicate
823 dispatch \cite{Ernst.etal:1998}. The main problem with predicate
824 dispatch is its expressiveness: with arbitrary predicates able to
825 control dispatch, it is essentially impossible to perform any
826 substantial precomputation, or even to automatically determine an
827 ordering of methods given a set of arguments. Even Clojure's
828 restricted dispatch scheme provides an explicit operator for stating
829 a preference order among methods, where here we provide an operator
830 to order specializers; in filtered dispatch the programmer
831 implicitly gives the system an order of precedence, through the
832 lexical ordering of filter specification in a filtered function
835 The Slate programming environment combines prototype-oriented
836 programming with multiple dispatch \cite{Salzman.Aldrich:2005}; in
837 that context, the analogue of an argument's class (in Common Lisp)
838 as a representation of the equivalence class of objects with the
839 same behaviour is the tuple of roles and delegations: objects with
840 the same roles and delegations tuple behave the same, much as
841 objects with the same generalizer have the same behaviour in the
842 protocol described in this paper.
844 The idea of generalization is of course not new, and arises in other
845 contexts. Perhaps of particular interest is generalization in the
846 context of partial evaluation; for example, \cite{Ruf:1993}
847 considers generalization in online partial evaluation, where sets of
848 possible values are represented by a type system construct
849 representing an upper bound. Exploring the relationship between
850 generalizer metaobjects and approximation in type systems might
851 yield strategies for automatically computing suitable generalizers
852 and cache functions for a variety of forms of generalized dispatch.
855 :CUSTOM_ID: Conclusions
857 In this paper, we have presented a new generalizer metaobject
858 protocol allowing the metaprogrammer to implement in a
859 straightforward manner metaobjects to implement custom method
860 selection, rather than the standard method selection as standardized
861 in Common Lisp. This protocol seamlessly interoperates with the
862 rest of CLOS and Common Lisp in general; the programmer (the user of
863 the custom specializer metaobjects) may without constraints use
864 arbitrary method combination, intercede in effective method
865 combination, or write custom method function implementations. The
866 protocol is expressive, in that it handles forms of dispatch not
867 possible in more restricted dispatch systems, while not suffering
868 from the indeterminism present in predicate dispatch through the use
869 of explicit ordering predicates.
871 The protocol is also reasonably efficient; the metaprogrammer can
872 indicate that a particular effective method computation can be
873 memoized, and under those circumstances much of the overhead is
874 amortized (though there remains a substantial overhead compared with
875 standard generic-function or regular function calls). We discuss
876 how the efficiency could be improved below.
879 :CUSTOM_ID: Future Work
881 Although the protocol described in this paper allows for a more
882 efficient implementation, as described in section [[#Memoization]],
883 than computing the applicable and effective methods at each generic
884 function call, the efficiency is still some way away from a
885 baseline of the standard generic-function, let alone a standard
886 function. Most of the invocation protocol is memoized, but there
887 are still two full standard generic-function calls –
888 =generalizer-of-using-class= and =generalizer-equal-hash-key= – per
889 argument per call to a generic function with extended specializers,
890 not to mention a hash table lookup.
892 For many applications, the additional flexibility afforded by
893 generalized specializers might be worth the cost in efficiency, but
894 it would still be worth investigating how much the overhead from
895 generalized specializers can be reduced; one possible avenue for
896 investigation is giving greater control over the cacheing strategy
897 to the metaprogrammer.
899 As an example, consider the =signum-specializer=. The natural
900 cache structure for a single argument generic function specializing
901 on =signum= is probably a four-element vector, where the first
902 three elements hold the effective methods for =signum= values of
903 -1, 0, and 1, and the fourth holds the cached effective methods for
904 everything else. This would make the invocation of such functions
905 very fast for the (presumed) common case where the argument is in
906 fact a real number. We hope to develop and show the effectiveness
907 of an appropriate protocol to allow the metaprogrammer to construct
908 and exploit such cacheing strategies, and (more speculatively) to
909 implement the lookup of an effective method function in other ways.
911 We also aim to demonstrate support within this protocol for some
912 particular cases of generalized specializers which seem to have
913 widespread demand (in as much as any language extension can be said
914 to be in “demand”). In particular, we have preliminary work
915 towards supporting efficient dispatch over pattern specializers
916 such as implemented in the \textsf{Optima} library[fn:4], and over
917 a prototype object system similar to that in Slate
918 \cite{Salzman.Aldrich:2005}. Our current source code for the work
919 described in this paper can be seen in the git source code
920 repository at [[http://christophe.rhodes.io/git/specializable.git]],
921 which will be updated with future developments.
923 Finally, after further experimentation (and, ideally, non-trivial
924 use in production) if this protocol stands up to use as we hope, we
925 aim to produce a standards-quality document so that other
926 implementors of Common Lisp can, if they choose, independently
927 reimplement the protocol, and so that users can use the protocol
928 with confidence that the semantics will not change in a
929 backwards-incompatible fashion.
931 We thank Lee Salzman, Pascal Costanza and Mikel Evins for helpful
932 and informative discussions, and all the respondents to one
933 author's request for imaginative uses for generalized specializers.
935 \bibliographystyle{plain}
936 \bibliography{crhodes,specializers}
940 [fn:1] GNU CLISP, at http://www.clisp.org/
942 [fn:2] Clozure Common Lisp, at http://ccl.clozure.com/
944 [fn:3] the \textsf{Closer to MOP} project, at
945 http://common-lisp.net/project/closer/, attempts to harmonize the
946 different implementations of the metaobject protocol in Common
949 [fn:4] https://github.com/m2ym/optima
951 [fn:5] http://clojure.org/multimethods