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
58 Report-No.:~\url{http://eprints.gold.ac.uk/id/eprint/9924}
60 \category{D.1}{Software}{Programming Techniques}[Object-oriented Programming]
61 \category{D.3.3}{Programming Languages}{Language Constructs and Features}
62 \terms{Languages, Design}
63 \keywords{generic functions, specialization-oriented programming, method selection, method combination}
67 The revisions to the original Common Lisp language \cite{CLtL}
68 included the detailed specification of an object system, known as
69 the Common Lisp Object System (CLOS), which was eventually
70 standardized as part of the ANSI Common Lisp standard \cite{CLtS}.
71 The object system as presented to the standardization committee was
72 formed of three chapters. The first two chapters covered programmer
73 interface concepts and the functions in the programmer interface
74 \cite[Chapter 28]{CLtL2} and were largely incorporated into the
75 final standard; the third chapter, covering a Metaobject Protocol
76 (MOP) for CLOS, was not.
78 Nevertheless, the CLOS MOP continued to be developed, and the
79 version documented in \cite{AMOP} has proven to be a reasonably
80 robust design. While many implementations have derived their
81 implementations of CLOS from either the Closette illustrative
82 implementation in \cite{AMOP}, or the Portable Common Loops
83 implementation of CLOS from Xerox Parc, there have been largely
84 from-scratch reimplementations of CLOS (in CLISP[fn:1] and
85 CCL[fn:2], at least) incorporating substantial fractions of the
86 Metaobject Protocol as described.
88 #+CAPTION: MOP Design Space
89 #+LABEL: fig:mopdesign
90 #+ATTR_LATEX: width=\linewidth float
91 [[file:figures/mop-design-space.pdf]]
93 Although it has stood the test of time, the CLOS MOP is neither
94 without issues (e.g. semantic problems with =make-method-lambda=
95 \cite{Costanza.Herzeel:2008}; useful functions such as
96 =compute-effective-slot-definition-initargs= being missing from the
97 standard) nor is it a complete framework for the metaprogrammer to
98 implement all conceivable variations of object-oriented behaviour.
99 While metaprogramming offers some possibilities for customization of
100 the object system behaviour, those possibilities cannot extend
101 arbitrarily in all directions (conceptually, if a given object
102 system is a point in design space, then a MOP for that object system
103 allows exploration of a region of design space around that point;
104 see figure \ref{fig:mopdesign}). In the case of the CLOS MOP, there is
105 still an expectation that functionality is implemented with methods
106 on generic functions, acting on objects with slots; it is not
107 possible, for example, to transparently implement support for
108 “message not understood” as in the message-passing paradigm, because
109 the analogue of messages (generic functions) need to be defined
110 before they are used.
112 Nevertheless, the MOP is flexible, and is used for a number of
113 things, including: documentation generation (where introspection in
114 the MOP is used to extract information from a running system[fn:3]);
115 object-relational mapping[fn:4] and other approaches to object
116 persistence \cite{Paepke:1988}; alternative backing stores for slots
117 (hash-tables \cite{Kiczales.etal:1993} or symbols
118 \cite{Costanza.Hirschfeld:2005}); and programmatic construction of
119 metaobjects, for example for interoperability with other language
120 runtimes' object systems.
122 One area of functionality where there is scope for customization by
123 the metaprogrammer is in the mechanics and semantics of method
124 applicability and dispatch. While in principle AMOP allows
125 customization of dispatch in various different ways (the
126 metaprogrammer can define methods on protocol functions such as
127 =compute-applicable-methods=,
128 =compute-applicable-methods-using-classes=), for example, in
129 practice implementation support for this was weak until relatively
132 Another potential mechanism for customizing dispatch is implicit in
133 the class structure defined by AMOP: standard specializer objects
134 (instances of =class= and =eql-specializer=) are generalized
135 instances of the =specializer= protocol class, and in principle
136 there are no restrictions on the metaprogrammer constructing
137 additional subclasses. Previous work \cite{Newton.Rhodes:2008} has
138 explored the potential for customizing generic function dispatch
139 using extended specializers, but there the metaprogrammer must
140 override the entirety of the generic function invocation protocol
141 (from =compute-discriminating-function= on down), leading to toy
142 implementations and duplicated effort.
144 This paper introduces a protocol for efficient and controlled
145 handling of new subclasses of =specializer=. In particular, it
146 introduces the =generalizer= protocol class, which generalizes the
147 return value of =class-of= in method applicability computation, and
148 allows the metaprogrammer to hook into cacheing schemes to avoid
149 needless recomputation of effective methods for sufficiently similar
150 generic function arguments (See Figure\nbsp\ref{fig:dispatch}).
152 #+CAPTION: Dispatch Comparison
153 #+LABEL: fig:dispatch
154 #+ATTR_LATEX: width=\linewidth float
155 [[file:figures/dispatch-relationships.pdf]]
157 The remaining sections in this paper can be read in any order. We
158 give some motivating examples in section [[#Examples]], including
159 reimplementations of examples from previous work, as well as
160 examples which are poorly supported by previous protocols. We
161 describe the protocol itself in section [[#Protocol]], describing each
162 protocol function in detail and, where applicable, relating it to
163 existing protocol functions within the CLOS MOP. We survey related
164 work in more detail in section [[#Related Work]], touching on work on
165 customized dispatch schemes in other environments. Finally, we draw
166 our conclusions from this work, and indicate directions for further
167 development, in section [[#Conclusions]]; reading that section before the
168 others indicates substantial trust in the authors' work.
173 In this section, we present a number of examples of dispatch
174 implemented using our protocol, which we describe in section
175 [[#Protocol]]. For reasons of space, the metaprogram code examples in
176 this section do not include some of the necessary support code to
177 run; complete implementations of each of these cases, along with the
178 integration of this protocol into the SBCL implementation
179 \cite{Rhodes:2008} of Common Lisp, are included in the authors'
182 A note on terminology: we will attempt to distinguish between the
183 user of an individual case of generalized dispatch (the
184 “programmer”), the implementor of a particular case of generalized
185 dispatch (the “metaprogrammer”), and the authors as the designers
186 and implementors of our generalized dispatch protocol (the
187 “metametaprogrammer”, or more likely “we”).
192 One motivation for the use of generalized dispatch is in an
193 extensible code walker: a new special form can be handled simply by
194 writing an additional method on the walking generic function,
195 seamlessly interoperating with all existing methods. In this
196 use-case, dispatch is performed on the first element of lists.
197 Semantically, we allow the programmer to specialize any argument of
198 methods with a new kind of specializer, =cons-specializer=, which
199 is applicable if and only if the corresponding object is a =cons=
200 whose =car= is =eql= to the symbol associated with the
201 =cons-specializer=; these specializers are more specific than the
202 =cons= class, but less specific than an =eql-specializer= on any
205 The programmer code using these specializers is unchanged from
206 \cite{Newton.Rhodes:2008}; the benefits of the protocol described
207 here are: that the separation of concerns is complete – method
208 selection is independent of method combination – and that the
209 protocol allows for efficient implementation where possible, even
210 when method selection is customized. In an application such as
211 walking source code, we would expect to encounter special forms
212 (distinguished by particular atoms in the =car= position) multiple
213 times, and hence to dispatch to the same effective method
214 repeatedly. We discuss the efficiency aspects of the protocol in
215 more detail in section [[#Memoization]]; we present the metaprogrammer
216 code to implement the =cons-specializer= below.
219 (defclass cons-specializer (specializer)
220 ((%car :reader %car :initarg :car)))
221 (defclass cons-generalizer (generalizer)
222 ((%car :reader %car :initarg :car)))
223 (defmethod generalizer-of-using-class
224 ((gf cons-generic-function) arg)
227 (make-instance 'cons-generalizer
229 (t (call-next-method))))
230 (defmethod generalizer-equal-hash-key
231 ((gf cons-generic-function)
232 (g cons-generalizer))
234 (defmethod specializer-accepts-generalizer-p
235 ((gf cons-generic-function)
237 (g cons-generalizer))
238 (if (eql (%car s) (%car g))
241 (defmethod specializer-accepts-p
242 ((s cons-specializer) o)
243 (and (consp o) (eql (car o) (%car s))))
246 The code above shows a minimal use of our protocol. We have elided
247 some support code for parsing and unparsing specializers, and for
248 handling introspective functions such as finding generic functions for
249 a given specializer. We have also elided methods on the protocol
250 functions =specializer<= and =same-specializer-p=; for
251 =cons-specializer= objects, specializer ordering is trivial, as only
252 one =cons-specializer= (up to equality) can ever be applicable to any
253 given argument. See section [[#Accept]] for a case where specializer
254 ordering is non-trivial.
256 As in \cite{Newton.Rhodes:2008}, the programmer can use these
257 specializers to implement a modular code walker, where they define one
258 method per special operator. We show two of those methods below, in
259 the context of a walker which checks for unused bindings and uses of
263 (defgeneric walk (form env stack)
264 (:generic-function-class cons-generic-function))
266 ((expr (cons lambda)) env call-stack)
267 (let ((lambda-list (cadr expr))
269 (with-checked-bindings
270 ((bindings-from-ll lambda-list)
273 (walk form env (cons form call-stack))))))
275 ((expr (cons let)) env call-stack)
276 (flet ((let-binding (x)
278 (cons (cadr x) call-stack))
280 (make-instance 'binding))))
281 (with-checked-bindings
282 ((mapcar #'let-binding (cadr expr))
284 (dolist (form (cddr expr))
285 (walk form env (cons form call-stack))))))
288 Note that in this example there is no strict need for
289 =cons-specializer= and =cons-generalizer= to be distinct classes.
290 In standard generic function dispatch, the =class= functions both
291 as the specializer for methods and as the generalizer for generic
292 function arguments; we can think of the dispatch implemented by
293 =cons-specializer= objects as providing for subclasses of the
294 =cons= class distinguished by the =car= of the =cons=. This
295 analogy also characterizes those use cases where the metaprogrammer
296 could straightforwardly use filtered dispatch
297 \cite{Costanza.etal:2008} to implement their dispatch semantics.
298 We will see in section [[#Accept]] an example of a case where filtered
299 dispatch is incapable of straightforwardly expressing the dispatch,
300 but first we present our implementation of the motivating case from
301 \cite{Costanza.etal:2008}.
302 ** SIGNUM specializers
306 Our second example of the implementation and use of generalized
307 specializers is a reimplementation of one of the examples in
308 \cite{Costanza.etal:2008}: specifically, the factorial function.
309 Here, dispatch will be performed based on the =signum= of the
310 argument, and again, at most one method with a =signum= specializer
311 will be applicable to any given argument, which makes the structure
312 of the specializer implementation very similar to the =cons=
313 specializers in the previous section.
315 The metaprogrammer has chosen in the example below to compare
316 signum values using \texttt{=}, which means that a method with
317 specializer =(signum 1)= will be applicable to positive
318 floating-point arguments (see the first method on
319 =specializer-accepts-generalizer-p= and the method on
320 =specializer-accepts-p= below). This leads to one subtle
321 difference in behaviour compared to that of the =cons=
322 specializers: in the case of =signum= specializers, the /next/
323 method after any =signum= specializer can be different, depending
324 on the class of the argument. This aspect of the dispatch is
325 handled by the second method on =specializer-accepts-generalizer-p=
329 (defclass signum-specializer (specializer)
330 ((%signum :reader %signum :initarg :signum)))
331 (defclass signum-generalizer (generalizer)
332 ((%signum :reader %signum :initarg :signum)))
333 (defmethod generalizer-of-using-class
334 ((gf signum-generic-function) (arg real))
335 (make-instance 'signum-generalizer
336 :signum (signum arg)))
337 (defmethod generalizer-equal-hash-key
338 ((gf signum-generic-function)
339 (g signum-generalizer))
341 (defmethod specializer-accepts-generalizer-p
342 ((gf signum-generic-function)
343 (s signum-specializer)
344 (g signum-generalizer))
345 (if (= (%signum s) (%signum g))
349 (defmethod specializer-accepts-generalizer-p
350 ((gf signum-generic-function)
352 (g signum-generalizer))
353 (specializer-accepts-generalizer-p
354 gf s (class-of (%signum g))))
356 (defmethod specializer-accepts-p
357 ((s signum-specializer) o)
358 (and (realp o) (= (%signum s) (signum o))))
361 Given these definitions, and once again some more straightforward
362 ones elided for reasons of space, the programmer can implement the
363 factorial function as follows:
367 (:generic-function-class signum-generic-function))
368 (defmethod fact ((n (signum 0))) 1)
369 (defmethod fact ((n (signum 1))) (* n (fact (1- n))))
372 The programmer does not need to include a method on =(signum -1)=,
373 as the standard =no-applicable-method= protocol will automatically
374 apply to negative real or non-real arguments.
375 ** Accept HTTP header specializers
379 In this section, we implement a non-trivial form of dispatch. The
380 application in question is a web server, and specifically to allow
381 the programmer to support RFC 2616 \cite{rfc2616} content
382 negotiation, of particular interest to publishers and consumers of
385 The basic mechanism in content negotiation is as follows: the web
386 client sends an HTTP request with an =Accept= header, which is a
387 string describing the media types it is willing to receive as a
388 response to the request, along with numerical preferences. The web
389 server compares these stated client preferences with the resources
390 it has available to satisfy this request, and sends the best
391 matching resource in its response.
393 For example, a graphical web browser might send an =Accept= header
394 of =text/html,application/xml;q=0.9,*/*;q=0.8= for a request of a
395 resource typed in to the URL bar. This should be interpreted as
396 meaning that: if the server can provide content of type =text/html=
397 (i.e. HTML) for that resource, then it should do so. Otherwise, if
398 it can provide =application/xml= content (i.e. XML of any schema),
399 then that should be provided; failing that, any other content type
402 In the case where there are static files on the filesystem, and the
403 web server must merely select between them, there is not much more
404 to say. However, it is not unusual for a web service to be backed
405 by some other form of data, and responses computed and sent on the
406 fly, and in these circumstances the web server must compute which
407 of its known output formats it can use to satisfy the request
408 before actually generating the best matching response. This can be
409 modelled as one generic function responsible for generating the
410 response, with methods corresponding to content-types -- and the
411 generic function must then perform method selection against the
412 request's =Accept= header to compute the appropriate response.
414 The =accept-specializer= below implements this dispatch. It depends
415 on a lazily-computed =tree= slot to represent the information in
416 the accept header (generated by =parse-accept-string=), and a
417 function =q= to compute the (defaulted) preference level for a
418 given content-type and =tree=; then, method selection and ordering
419 involves finding the =q= for each =accept-specializer='s content
420 type given the =tree=, and sorting them according to the preference
424 (defclass accept-specializer (specializer)
425 ((media-type :initarg :media-type :reader media-type)))
426 (defclass accept-generalizer (generalizer)
427 ((header :initarg :header :reader header)
429 (next :initarg :next :reader next)))
430 (defmethod generalizer-equal-hash-key
431 ((gf accept-generic-function)
432 (g accept-generalizer))
433 `(accept-generalizer ,(header g)))
434 (defmethod specializer-accepts-generalizer-p
435 ((gf accept-generic-function)
436 (s accept-specializer)
437 (g accept-generalizer))
438 (values (q (media-type s) (tree g)) t))
439 (defmethod specializer-accepts-generalizer-p
440 ((gf accept-generic-function)
442 (g accept-generalizer))
443 (specializer-accepts-generalizer-p
446 (defmethod specializer<
447 ((gf accept-generic-function)
448 (s1 accept-specializer)
449 (s2 accept-specializer)
450 (g accept-generalizer))
451 (let ((m1 (media-type s1))
456 (t (let ((q1 (q m1 tree)))
464 The metaprogrammer can then add support for objects representing
465 client requests, such as instances of the =request= class in the
466 Hunchentoot[fn:7] web server, by translating these into
467 =accept-generalizer= instances. The code below implements this, by
468 defining the computation of a =generalizer= object for a given
469 request, and specifying how to compute whether the specializer
470 accepts the given request object (=q= returns a number between 0
471 and 1 if any pattern in the =tree= matches the media type, and
472 =nil= if the media type cannot be matched at all).
475 (defmethod generalizer-of-using-class
476 ((gf accept-generic-function)
478 (make-instance 'accept-generalizer
479 :header (tbnl:header-in :accept arg)
480 :next (call-next-method)))
481 (defmethod specializer-accepts-p
482 ((s accept-specializer)
484 (let* ((accept (tbnl:header-in :accept o))
485 (tree (parse-accept-string accept))
486 (q (q (media-type s) tree)))
490 This dispatch cannot be implemented using filtered dispatch, except
491 by generating anonymous classes with all the right mime-types as
492 direct superclasses in dispatch order; the filter would generate
494 (ensure-class nil :direct-superclasses
495 '(text/html image/webp ...))
497 and dispatch would operate using those anonymous classes. While
498 this is possible to do, it is awkward to express content-type
499 negotiation in this way, as it means that the dispatcher must know
500 about the universe of mime-types that clients might declare that
501 they accept, rather than merely the set of mime-types that a
502 particular generic function is capable of serving; handling
503 wildcards in accept strings is particularly awkward in the
506 Note that in this example, the method on =specializer<= involves a
507 non-trivial ordering of methods based on the =q= values specified
508 in the accept header (whereas in sections [[#Cons]] and [[#Signum]] only a
509 single extended specializer could be applicable to any given
512 Also note that the accept specializer protocol is straightforwardly
513 extensible to other suitable objects; for example, one simple
514 debugging aid is to define that an =accept-specializer= should be
515 applicable to =string= objects. This can be done in a modular
516 fashion (see the code below, which can be completely disconnected
517 from the code for Hunchentoot request objects), and generalizes to
518 dealing with multiple web server libraries, so that
519 content-negotiation methods are applicable to each web server's
523 (defmethod generalizer-of-using-class
524 ((gf accept-generic-function)
526 (make-instance 'accept-generalizer
528 :next (call-next-method)))
529 (defmethod specializer-accepts-p
530 ((s accept-specializer) (o string))
531 (let* ((tree (parse-accept-string o))
532 (q (q (media-type s) tree)))
536 The =next= slot in the =accept-generalizer= is used to deal with
537 the case of methods specialized on the classes of objects as well
538 as on the acceptable media types; there is a method on
539 =specializer-accepts-generalizer-p= for specializers that are not
540 of type =accept-specializer= which calls the generic function again
541 with the next generalizer, so that methods specialized on the
542 classes =tbnl:request= and =string= are treated as applicable to
543 corresponding objects, though less specific than methods with
544 =accept-specializer= specializations.
546 ** COMMENT Pattern / xpattern / regex / optima
547 Here's the /really/ interesting bit, but on the other hand we're
548 probably going to run out of space, and the full description of
549 these is going to take us into =make-method-lambda= territory.
550 A second paper? Future work?
556 In section [[#Examples]], we have seen a number of code fragments as
557 partial implementations of particular non-standard method dispatch
558 strategies, using =generalizer= metaobjects to mediate between the
559 methods of the generic function and the actual arguments passed to
560 it. In section [[#Generalizer metaobjects]], we go into more detail
561 regarding these =generalizer= metaobjects, describing the generic
562 function invocation protocol in full, and showing how this protocol
563 allows a similar form of effective method cacheing as the standard
564 one does. In section [[#Generalizer performance]], we show the results
565 of some simple performance measurements on our implementation of
566 this protocol in the SBCL implementation \cite{Rhodes:2008} of
567 Common Lisp to highlight the improvement that this protocol can
568 bring over a naïve implementation of generalized dispatch, as well
569 as to make the potential for further improvement clear.
571 ** Generalizer metaobjects
573 :CUSTOM_ID: Generalizer metaobjects
576 *** Generic function invocation
577 As in the standard generic function invocation protocol, the
578 generic function's actual functionality is provided by a
579 discriminating function. The functionality described in this
580 protocol is implemented by having a distinct subclass of
581 =standard-generic-function=, and a method on
582 =compute-discriminating-function= which produces a custom
583 discriminating function. The basic outline of the discriminating
584 function is the same as the standard one: it must first compute the
585 set of applicable methods given particular arguments; from that, it
586 must compute the effective method by combining the methods
587 appropriately according to the generic function's method
588 combination; finally, it must call the effective method with the
591 Computing the set of applicable methods is done using a pair of
592 functions: =compute-applicable-methods=, the standard metaobject
593 function, and a new function
594 =compute-applicable-methods-using-generalizers=. We define a
595 custom method on =compute-applicable-methods= which tests the
596 applicability of a particular specializer against a given argument
597 using =specializer-accepts-p=, a new protocol function with
598 default implementations on =class= and =eql-specializer= to
599 implement the expected behaviour. To order the methods, as
600 required by the protocol, we define a pairwise comparison operator
601 =specializer<= which defines an ordering between specializers for
602 a given generalizer argument (remembering that even in standard
603 CLOS the ordering between =class= specializers can change
604 depending on the actual class of the argument).
606 The new =compute-applicable-methods-using-generalizers= is the
607 analogue of the MOP's =compute-applicable-methods-using-classes=.
608 Instead of calling it with the =class-of= each argument, we
609 compute the generalizers of each argument using the new function
610 =generalizer-of-using-class= (where the =-using-class= refers to
611 the class of the generic function rather than the class of the
612 object), and call =compute-applicable-methods-using-generalizers=
613 with the generic function and list of generalizers. As with
614 =compute-applicable-methods-using-classes=, a secondary return
615 value indicates whether the result of the function is definitive
616 for that list of generalizers.
618 Thus, in generic function invocation, we first compute the
619 generalizers of the arguments; we compute the ordered set of
620 applicable methods, either from the generalizers or (if that is
621 not definitive) from the arguments themselves; then the normal
622 effective method computation and call can occur. Unfortunately,
623 the nature of an effective method function is not specified, so we
624 have to reach into implementation internals a little in order to
625 call it, but otherwise the remainder of the generic function
626 invocation protocol is unchanged from the standard one. In
627 particular, method combination is completely unchanged;
628 programmers can choose arbitrary method combinations, including
629 user-defined long form combinations, for their generic functions
630 involving generalized dispatch.
632 *** Effective method memoization
634 :CUSTOM_ID: Memoization
636 The potential efficiency benefit to having =generalizer=
637 metaobjects lies in the use of
638 =compute-applicable-methods-using-generalizers=. If a particular
639 generalized specializer accepts a variety of objects (such as the
640 =signum= specializer accepting all reals with a given sign, or the
641 =accept= specializer accepting all HTTP requests with a particular
642 =Accept= header), then there is the possibility of cacheing and
643 reusing the results of the applicable and effective method
644 computation. If the computation of the applicable method from
645 =compute-applicable-methods-using-generalizers= is definitive,
646 then the ordered set of applicable methods and the effective
647 method can be cached.
649 One issue is what to use as the key for that cache. We cannot use
650 the generalizers themselves, as two generalizers that should be
651 considered equal for cache lookup will not compare as =equal= –
652 and indeed even the standard generalizer, the =class=, cannot
653 easily be used as we must be able to invalidate cache entries upon
654 class redefinition. The issue of =class= generalizers we can
655 solve as in \cite{Kiczales.Rodriguez:1990} by using the =wrapper=
656 of a class, which is distinct for each distinct (re)definition of
657 a class; for arbitrary generalizers, however, there is /a priori/
658 no good way of computing a suitable hash key automatically, so we
659 allow the metaprogrammer to specify one by defining a method on
660 =generalizer-equal-hash-key=, and combining the hash keys for all
661 required arguments in a list to use as a key in an =equal=
665 [could we actually compute a suitable hash key using the
666 generalizer's class name and initargs?]
670 - [X] =generalizer-of-using-class= (NB class of gf not class of object)
671 - [X] =compute-applicable-methods-using-generalizers=
672 - [X] =generalizer-equal-hash-key=
673 - [X] =specializer-accepts-generalizer-p=
674 - [X] =specializer-accepts-p=
678 :CUSTOM_ID: Generalizer performance
680 We have argued that the protocol presented here allows for
681 expressive control of method dispatch while preserving the
682 possibility of efficiency. In this section, we quantify the
683 efficiency that the memoization protocol described in section
684 [[#Memoization]] achieves, by comparing it both to the same protocol
685 with no memoization, as well as with equivalent dispatch
686 implementations in the context of methods with regular specializers
687 (in an implementation similar to that in
688 \cite{Kiczales.Rodriguez:1990}), and with implementation in
689 straightforward functions. We performed our benchmarks on a
690 quad-core X-series ThinkPad with 8GB of RAM running Debian
691 GNU/Linux, and took the mean of the 10 central samples of 20 runs,
692 with the number of iterations per run chosen so as to take
693 substantially over the clock resolution for the fastest case.
694 Despite these precautions, we advise against reading too much into
695 these numbers, which are best used as an order-of-magnitude
698 In the case of the =cons-specializer=, we benchmark the walker
699 acting on a small but non-trivial form. The implementation
700 strategies in the table below refer to: an implementation in a
701 single function with a large =typecase= to dispatch between all the
702 cases; the natural implementation in terms of a standard generic
703 function with multiple methods (the method on =cons= having a
704 slightly reduced =typecase= to dispatch on the first element, and
705 other methods handling =symbol= and other atoms); and three
706 separate cases using =cons-specializer= objects. As well as
707 measuring the effect of memoization against the full invocation
708 protocol, we can also introduce a special case: when only one
709 argument participates in method selection (all the other required
710 arguments only being specialized on =t=), we can avoid the
711 construction of a list of hash keys and simply use the key
712 from the single active generalizer directly.
714 | implementation | time (µs/call) | overhead |
715 |-----------------------+----------------+----------|
716 | function | 3.17 | |
717 | standard-gf/methods | 3.6 | +14% |
718 | cons-gf/one-arg-cache | 7.4 | +130% |
719 | cons-gf | 15 | +370% |
720 | cons-gf/no-cache | 90 | +2700% |
722 The benchmarking results from this exercise are promising: in
723 particular, the introduction of the effective method cache speeds
724 up the use of generic specializers in this case by a factor of 6,
725 and the one-argument special case by another factor of 2. For this
726 workload, even the one-argument special case only gets to within a
727 factor of 2-3 of the function and standard generic function
728 implementations, but the overall picture is that the memoizability
729 in the protocol does indeed drastically reduce the overhead
730 compared with the full invocation.
732 For the =signum-specializer= case, we choose to benchmark the
733 computation of 20!, because that is the largest factorial whose
734 answer fits in SBCL's 63-bit fixnums – in an attempt to measure the
735 worst case for generic dispatch, where the work done within the
736 methods is as small as possible without being meaningless, and in
737 particular does not cause heap allocation or garbage collection to
740 #+begin_src lisp :exports none
741 (progn (gc :full t) (time (dotimes (i 10000) (%fact 20))))
744 | implementation | time (µs/call) | overhead |
745 |-------------------------+----------------+----------|
747 | standard-gf/fixnum | 1.2 | +100% |
748 | signum-gf/one-arg-cache | 7.5 | +1100% |
749 | signum-gf | 23 | +3800% |
750 | signum-gf/no-cache | 240 | +41000% |
752 The relative picture is similar to the =cons-specializer= case;
753 including a cache saves a factor of 10 in this case, and another
754 factor of 3 for the one-argument cache special case. The cost of
755 the genericity of the protocol here is starker; even the
756 one-argument cache is a factor of 6 slower than the standard
757 generic-function implementation, and a further factor of 2 away
758 from the implementation of factorial as a function. We discuss
759 ways in which we expect to be able to improve performance in
760 section [[#Future Work]].
762 We could allow the metaprogrammer to improve on the one-argument
763 performance by constructing a specialized cache: for =signum=
764 arguments of =rational= arguments, the logical cache structure is
765 to index a three-element vector with =(1+ signum)=. The current
766 protocol does not provide a way of eliding the two generic function
767 calls for the generic cache; we discuss possible approaches in
768 section [[#Conclusions]].
770 The protocol described in this paper is only part of a complete
771 protocol for =specializer= and =generalizer= metaobjects. Our
772 development of this protocol is as yet incomplete; the work
773 described here augments that in \cite{Newton.Rhodes:2008}, but is
774 yet relatively untested – and additionally our recent experience of
775 working with that earlier protocol suggests that there might be
776 useful additions to the handling of =specializer= metaobjects,
777 independent of the =generalizer= idea presented here.
780 Description and specification left for reasons of space (we'll see?)
781 - [ ] =same-specializer-p=
782 - [ ] =parse/unparse-specializer-using-class=
783 - [ ] =make-method-specializers-form=
784 - [ ] jmoringe: In an email, I suggested
785 =make-specializer-form-using-class=:
788 Could we change =make-method-specializers-form='s default
789 behaviour to call a new generic function
791 make-specializer-form-using-class gf method name env
793 with builtin methods on =sb-mop:specializer=, =symbol=, =cons= (for
794 eql-specializers)? This would make it unnecessary to repeat
795 boilerplate along the lines of
797 (flet ((make-parse-form (name)
798 (if <name-is-interesting>
799 <handle-interesting-specializer>
800 <repeat-handling-of-standard-specializers>)))
801 `(list ,@(mapcar #'make-parse-form specializer-names)))
803 for each generic function class.
805 - [ ] =make-method-lambda= revision (use environment arg?)
807 jmoringe: would only be relevant for pattern dispatch, right? I
808 think, we didn't finish the discussion regarding special
809 variables vs. environment vs. new protocol function
813 :CUSTOM_ID: Related Work
816 The work presented here builds on specializer-oriented programming
817 described in \cite{Newton.Rhodes:2008}. Approximately
818 contemporaneously, filtered dispatch \cite{Costanza.etal:2008} was
819 introduced to address some of the same use cases: filtered dispatch
820 works by having a custom discriminating function which wraps the
821 usual one, where the wrapping function augments the set of
822 applicable methods with applicable methods from other (hidden)
823 generic functions, one per filter group; this step is not memoized,
824 and using =eql= methods to capture behaviours of equivalence classes
825 means that it is hard to see how it could be. The methods are then
826 combined using a custom method combination to mimic the standard
827 one; in principle implementors of other method combinations could
828 cater for filtered dispatch, but they would have to explicitly
829 modify their method combinations. The Clojure programming language
830 supports multimethods[fn:8] with a variant of filtered dispatch as
831 well as hierarchical and identity-based method selectors.
833 In context-oriented programming
834 \cite{Hirschfeld.etal:2008,Vallejos.etal:2010}, context dispatch
835 occurs by maintaining the context state as an anonymous class with
836 the superclasses representing all the currently active layers; this
837 is then passed as a hidden argument to context-aware functions. The
838 set of layers is known and under programmer control, as layers must
839 be defined beforehand.
841 In some sense, all dispatch schemes are specializations of predicate
842 dispatch \cite{Ernst.etal:1998}. The main problem with predicate
843 dispatch is its expressiveness: with arbitrary predicates able to
844 control dispatch, it is essentially impossible to perform any
845 substantial precomputation, or even to automatically determine an
846 ordering of methods given a set of arguments. Even Clojure's
847 restricted dispatch scheme provides an explicit operator for stating
848 a preference order among methods, where here we provide an operator
849 to order specializers; in filtered dispatch the programmer
850 implicitly gives the system an order of precedence, through the
851 lexical ordering of filter specification in a filtered function
854 The Slate programming environment combines prototype-oriented
855 programming with multiple dispatch \cite{Salzman.Aldrich:2005}; in
856 that context, the analogue of an argument's class (in Common Lisp)
857 as a representation of the equivalence class of objects with the
858 same behaviour is the tuple of roles and delegations: objects with
859 the same roles and delegations tuple behave the same, much as
860 objects with the same generalizer have the same behaviour in the
861 protocol described in this paper.
863 The idea of generalization is of course not new, and arises in other
864 contexts. Perhaps of particular interest is generalization in the
865 context of partial evaluation; for example, \cite{Ruf:1993}
866 considers generalization in online partial evaluation, where sets of
867 possible values are represented by a type system construct
868 representing an upper bound. Exploring the relationship between
869 generalizer metaobjects and approximation in type systems might
870 yield strategies for automatically computing suitable generalizers
871 and cache functions for a variety of forms of generalized dispatch.
874 :CUSTOM_ID: Conclusions
876 In this paper, we have presented a new generalizer metaobject
877 protocol allowing the metaprogrammer to implement in a
878 straightforward manner metaobjects to implement custom method
879 selection, rather than the standard method selection as standardized
880 in Common Lisp. This protocol seamlessly interoperates with the
881 rest of CLOS and Common Lisp in general; the programmer (the user of
882 the custom specializer metaobjects) may without constraints use
883 arbitrary method combination, intercede in effective method
884 combination, or write custom method function implementations. The
885 protocol is expressive, in that it handles forms of dispatch not
886 possible in more restricted dispatch systems, while not suffering
887 from the indeterminism present in predicate dispatch through the use
888 of explicit ordering predicates.
890 The protocol is also reasonably efficient; the metaprogrammer can
891 indicate that a particular effective method computation can be
892 memoized, and under those circumstances much of the overhead is
893 amortized (though there remains a substantial overhead compared with
894 standard generic-function or regular function calls). We discuss
895 how the efficiency could be improved below.
898 :CUSTOM_ID: Future Work
900 Although the protocol described in this paper allows for a more
901 efficient implementation, as described in section [[#Memoization]],
902 than computing the applicable and effective methods at each generic
903 function call, the efficiency is still some way away from a
904 baseline of the standard generic-function, let alone a standard
905 function. Most of the invocation protocol is memoized, but there
906 are still two full standard generic-function calls –
907 =generalizer-of-using-class= and =generalizer-equal-hash-key= – per
908 argument per call to a generic function with extended specializers,
909 not to mention a hash table lookup.
911 For many applications, the additional flexibility afforded by
912 generalized specializers might be worth the cost in efficiency, but
913 it would still be worth investigating how much the overhead from
914 generalized specializers can be reduced; one possible avenue for
915 investigation is giving greater control over the cacheing strategy
916 to the metaprogrammer.
918 As an example, consider the =signum-specializer=. The natural
919 cache structure for a single argument generic function specializing
920 on =signum= is probably a four-element vector, where the first
921 three elements hold the effective methods for =signum= values of
922 -1, 0, and 1, and the fourth holds the cached effective methods for
923 everything else. This would make the invocation of such functions
924 very fast for the (presumed) common case where the argument is in
925 fact a real number. We hope to develop and show the effectiveness
926 of an appropriate protocol to allow the metaprogrammer to construct
927 and exploit such cacheing strategies, and (more speculatively) to
928 implement the lookup of an effective method function in other ways.
930 We also aim to demonstrate support within this protocol for some
931 particular cases of generalized specializers which seem to have
932 widespread demand (in as much as any language extension can be said
933 to be in “demand”). In particular, we have preliminary work
934 towards supporting efficient dispatch over pattern specializers
935 such as implemented in the \textsf{Optima} library[fn:9], and over
936 a prototype object system similar to that in Slate
937 \cite{Salzman.Aldrich:2005}. Our current source code for the work
938 described in this paper can be seen in the git source code
939 repository at [[http://christophe.rhodes.io/git/specializable.git]],
940 which will be updated with future developments.
942 Finally, after further experimentation (and, ideally, non-trivial
943 use in production) if this protocol stands up to use as we hope, we
944 aim to produce a standards-quality document so that other
945 implementors of Common Lisp can, if they choose, independently
946 reimplement the protocol, and so that users can use the protocol
947 with confidence that the semantics will not change in a
948 backwards-incompatible fashion.
950 We thank the anonymous reviewers for their helpful suggestions and
951 comments on the submitted version of this paper. We also thank Lee
952 Salzman, Pascal Costanza and Mikel Evins for helpful and
953 informative discussions, and all the respondents to the first
954 author's request for imaginative uses for generalized specializers.
956 \bibliographystyle{plain}
957 \bibliography{crhodes,specializers}
961 [fn:1] GNU CLISP, at http://www.clisp.org/
963 [fn:2] Clozure Common Lisp, at http://ccl.clozure.com/
965 [fn:3] as in many of the systems surveyed at
966 https://sites.google.com/site/sabraonthehill/lisp-document-generation-apps
968 [fn:4] e.g. CLSQL, at http://clsql.b9.com/
970 [fn:5] the \textsf{Closer to MOP} project, at
971 http://common-lisp.net/project/closer/, attempts to harmonize the
972 different implementations of the metaobject protocol in Common
975 [fn:6] the tag =els2014-submission= in
976 http://christophe.rhodes.io/git/specializable.git corresponds to the
977 code repository at the point of submitting this paper.
979 [fn:7] Hunchentoot is a web server written in Common Lisp, allowing
980 the user to write handler functions to compute responses to requests;
981 http://weitz.de/hunchentoot/
983 [fn:8] http://clojure.org/multimethods
985 [fn:9] https://github.com/m2ym/optima