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