X-Git-Url: http://christophe.rhodes.io/gitweb/?p=paper-els-specializers.git;a=blobdiff_plain;f=els-specializers.org;h=5b5731c4fda94d428d46019fc4c0de539a229f80;hp=1cecedf587a816f5607e87213ae30a8cbbc09269;hb=d42453fadbac3bab620fa079b894b143a8c24946;hpb=a1e049025441509a712fccc1135212b54e66ad44 diff --git a/els-specializers.org b/els-specializers.org index 1cecedf..5b5731c 100644 --- a/els-specializers.org +++ b/els-specializers.org @@ -1,7 +1,827 @@ #+TITLE: Generalizers: New Metaobjects for Generalized Dispatch -#+AUTHOR: Christophe Rhodes +#+AUTHOR: Christophe Rhodes, Jan Moringen, David Lichteblau +#+OPTIONS: toc:nil +#+LaTeX_CLASS: acm_proc_article-sp +#+LaTeX_HEADER: \DeclareTextFontCommand{\texttt}{\ttfamily\hyphenchar\font=45\relax} -#+BEGIN_ABSTRACT -Foo -#+END_ABSTRACT +#+begin_src elisp :exports none +(add-to-list 'org-latex-classes + '("acm_proc_article-sp" "\\documentclass{acm_proc_article-sp}" + ("\\section{%s}" . "\\section*{%s}") + ("\\subsection{%s}" . "\\subsection*{%s}") + ("\\subsubsection{%s}" . "\\subsubsection*{%s}") + ("\\paragraph{%s}" . "\\paragraph*{%s}") + ("\\subparagraph{%s}" . "\\subparagraph*{%s}"))) +#+end_src + +#+begin_abstract +1. This paper introduces a new metaobject, the generalizer, which + complements the existing specializer metaobject. +2. With the help of examples, we show that this metaobject allows for + the efficient implementation of complex non-class-based dispatch + within the framework of existing metaobject protocols +3. We present the generalizer protocol, implemented within the SBCL + implementation of Common Lisp +4. In combination with previous work, this produces a fully-functional + extension of the existing mechanism for method selection and + effective method computation, including support for standard and + user-defined method combination independent from method selection. +#+end_abstract + +* Introduction + The revisions to the original Common Lisp language \cite{CLtL} + included the detailed specification of an object system, known as + the Common Lisp Object System (CLOS), which was eventually + standardized as part of the ANSI Common Lisp standard \cite{CLtS}. + The object system as presented to the standardization committee was + formed of three chapters. The first two chapters covered programmer + interface concepts and the functions in the programmer interface + \cite[Chapter 28]{CLtL2} and were largely incorporated into the + final standard; the third chapter, covering a Metaobject Protocol + (MOP) for CLOS, was not. + + Nevertheless, the CLOS MOP has proven to be a robust design, and + while many implementations have derived their implementations of + CLOS from either the Closette illustrative implementation in + \cite{AMOP}, or the Portable Common Loops implementation of CLOS + from Xerox Parc, there have been from-scratch reimplementations of + CLOS (in at least CLISP; check for others -- Lisp500? CCL?) + incorporating substantial fractions of the Metaobject Protocol as + described. + + Although it has stood the test of time, the CLOS MOP is neither + without issues (e.g. semantic problems with =make-method-lambda= + \cite{Costanza.Herzeel:2008}; useful functions such as + =compute-effective-slot-definition-initargs= being missing from the + standard) nor is it a complete framework for the metaprogrammer to + implement all conceivable variations of object-oriented behaviour. + While metaprogramming offers some possibilities for customization of + the object system behaviour, those possibilities cannot extend + arbitrarily in all directions. There is still an expectation that + functionality is implemented with methods on generic functions, + acting on objects with slots. Nevertheless, the MOP is flexible, + and is used for a number of things, including: documentation + generation (where introspective functionality in the MOP is used to + extract information from a running system); object-relational + mapping and other approaches to object persistence; alternative + backing stores for slots (hash-tables or symbols); and programmatic + construction of metaobjects, for example for IDL compilers and model + transformations. + + [ A picture on MOP flexibility here would be good; I have in my mind + one where an object system is a point and the MOP opens up a blob + around that point, and I'm sure I've seen it somewhere but I can't + remember where. Alternatively, there's Kiczales et al "MOPs: why we + want them and what else they can do", fig. 2 ] + + One area of functionality where there is scope for customization by + the metaprogrammer is in the mechanics and semantics of method + applicability and dispatch. While in principle AMOP allows + customization of dispatch in various different ways (the + metaprogrammer can define methods on protocol functions such as + =compute-applicable-methods=, + =compute-applicable-methods-using-classes=), for example, in + practice implementation support for this was weak until relatively + recently[fn:1]. + + Another potential mechanism for customizing dispatch is implicit in + the class structure defined by AMOP: standard specializer objects + (instances of =class= and =eql-specializer=) are generalized + instances of the =specializer= protocol class, and in principle + there are no restrictions on the metaprogrammer constructing + additional subclasses. Previous work \cite{Newton.Rhodes:2008} has + explored the potential for customizing generic function dispatch + using extended specializers, but as of that work the metaprogrammer + must override the entirety of the generic function invocation + protocol (from =compute-discriminating-function= on down), leading + to toy implementations and duplicated effort. + + This paper introduces a protocol for efficient and controlled + handling of new subclasses of =specializer=. In particular, it + introduces the =generalizer= protocol class, which generalizes the + return value of =class-of= in method applicability computation, and + allows the metaprogrammer to hook into cacheing schemes to avoid + needless recomputation of effective methods for sufficiently similar + generic function arguments (See Figure\nbsp\ref{fig:dispatch}). + + #+CAPTION: Dispatch Comparison + #+LABEL: fig:dispatch + #+ATTR_LATEX: width=0.9\linewidth float + [[file:figures/dispatch-comparison.pdf]] + + The remaining sections in this paper can be read in any order. We + give some motivating examples in section [[#Examples]], including + reimplementations of examples from previous work, as well as + examples which are poorly supported by previous protocols. We + describe the protocol itself in section [[#Protocol]], describing each + protocol function in detail and, where applicable, relating it to + existing protocol functions within the CLOS MOP. We survey related + work in more detail in section [[#Related Work]], touching on work on + customized dispatch schemes in other environments. Finally, we draw + our conclusions from this work, and indicate directions for further + development, in section [[#Conclusions]]; reading that section before the + others indicates substantial trust in the authors' work. +* Examples + :PROPERTIES: + :CUSTOM_ID: Examples + :END: + In this section, we present a number of examples of dispatch + implemented using our protocol, which we describe in section + [[#Protocol]]. For reasons of space, the metaprogram code examples in + this section do not include some of the necessary support code to + run; complete implementations of each of these cases are included in + an appendix / in the accompanying repository snapshot / at this + location. + + A note on terminology: we will attempt to distinguish between the + user of an individual case of generalized dispatch (the + “programmer”), the implementor of a particular case of generalized + dispatch (the “metaprogrammer”), and the authors as the designers + and implementors of our generalized dispatch protocol (the + “metametaprogammer”, or more likely “we”). +** CONS specializers + :PROPERTIES: + :CUSTOM_ID: Cons + :END: + We start by presenting our original use case, performing + dispatching on the first element of lists. Semantically, we allow + the programmer to specialize any argument of methods with a new + kind of specializer, =cons-specializer=, which is applicable if and + only if the corresponding object is a =cons= whose =car= is =eql= + to the symbol associated with the =cons-specializer=; these + specializers are more specific than the =cons= class, but less + specific than an =eql-specializer= on any given =cons=. + + One motivation for the use of this specializer is in an extensible + code walker: a new special form can be handled simply by writing an + additional method on the walking generic function, seamlessly + interoperating with all existing methods. + + The programmer code using these specializers is unchanged from + \cite{Newton.Rhodes:2008}; the benefits of the protocol described + here are centered on performance and generality: in an application + such as walking source code, we would expect to encounter special + forms (distinguished by particular atoms in the =car= position) + multiple times, and hence to dispatch to the same effective method + repeatedly. We discuss this in more detail in section [[#Memoization]]; + we present the metaprogrammer code below. + +#+begin_src lisp +(defclass cons-specializer (specializer) + ((%car :reader %car :initarg :car))) +(defclass cons-generalizer (generalizer) + ((%car :reader %car :initarg :car))) +(defmethod generalizer-of-using-class + ((gf cons-generic-function) arg) + (typecase arg + ((cons symbol) + (make-instance 'cons-generalizer + :car (car arg))) + (t (call-next-method)))) +(defmethod generalizer-equal-hash-key + ((gf cons-generic-function) + (g cons-generalizer)) + (%car g)) +(defmethod specializer-accepts-generalizer-p + ((gf cons-generic-function) + (s cons-specializer) + (g cons-generalizer)) + (if (eql (%car s) (%car g)) + (values t t) + (values nil t))) +(defmethod specializer-accepts-p + ((s cons-specializer) o) + (and (consp o) (eql (car o) (%car s)))) +#+end_src + +The code above shows the core of the use of our protocol. We have +elided some support code for parsing and unparsing specializers, and +for handling introspective functions such as finding generic functions +for a given specializer. We have also elided methods on the protocol +function =specializer<=; for =cons-specializers= here, specializer +ordering is trivial, as only one =cons-specializer= can ever be +applicable to any given argument. See section [[#Accept]] for a case +where specializer ordering is substantially different. + +As in \cite{Newton.Rhodes:2008}, we can use these specializers to +implement a modular code walker, where we define one method per +special operator. We show two of those methods below, in the context +of a walker which checks for unused bindings and uses of unbound +variables. + +#+begin_src +(defgeneric walk (form env stack) + (:generic-function-class cons-generic-function)) +(defmethod walk ((expr (cons lambda)) env call-stack) + (let ((lambda-list (cadr expr)) + (body (cddr expr))) + (with-checked-bindings + ((bindings-from-ll lambda-list) env call-stack) + (dolist (form body) + (walk form env (cons form call-stack)))))) +(defmethod walk ((expr (cons let)) env call-stack) + (flet ((let-binding (x) + (walk (cadr x) env (cons (cadr x) call-stack)) + (cons (car x) (make-instance 'binding)))) + (with-checked-bindings + ((mapcar #'let-binding (cadr expr)) env call-stack) + (dolist (form (cddr expr)) + (walk form env (cons form call-stack)))))) +#+end_src + + Note that in this example there is no strict need for + =cons-specializer= and =cons-generalizer= to be distinct classes – + just as in the normal protocol involving + =compute-applicable-methods= and + =compute-applicable-methods-using-classes=, the specializer object + for mediating dispatch contains the same information as the object + representing the equivalence class of objects to which that + specializer is applicable: here it is the =car= of the =cons= + (which we wrap in a distinct object); in the standard dispatch it + is the =class= of the object. This feature also characterizes + those use cases where the metaprogrammer could straightforwardly + use filtered dispatch \cite{Costanza.etal:2008} to implement their + dispatch semantics. We will see in section [[#Accept]] an example + of a case where filtered dispatch is incapable of straightforwardly + expressing the dispatch, but first we present our implementation of + the motivating case from \cite{Costanza.etal:2008}. +** SIGNUM specializers + :PROPERTIES: + :CUSTOM_ID: Signum + :END: + Our second example of the implementation and use of generalized + specializers is a reimplementation of one of the examples in + \cite{Costanza.etal:2008}: specifically, the factorial function. + Here, we will perform dispatch based on the =signum= of the + argument, and again, at most one method with a =signum= specializer + will be appliable to any given argument, which makes the structure + of the specializer implementation very similar to the =cons= + specializers in the previous section. + + We have chosen to compare signum values using \texttt{=}, which + means that a method with specializer =(signum 1)= will be + applicable to positive floating-point arguments (see the first + method on =specializer-accepts-generalizer-p= and the method on + =specializer=accepts-p= below). This leads to one subtle + difference in behaviour compared to that of the =cons= + specializers: in the case of =signum= specializers, the /next/ + method after any =signum= specializer can be different, depending + on the class of the argument. This aspect of the dispatch is + handled by the second method on =specializer-accepts-generalizer-p= + below. +#+begin_src lisp +(defclass signum-specializer (specializer) + ((%signum :reader %signum :initarg :signum))) +(defclass signum-generalizer (generalizer) + ((%signum :reader %signum :initarg :signum))) +(defmethod generalizer-of-using-class + ((gf signum-generic-function) arg) + (typecase arg + (real (make-instance 'signum-generalizer + :signum (signum arg))) + (t (call-next-method)))) +(defmethod generalizer-equal-hash-key + ((gf signum-generic-function) + (g signum-specializer)) + (%signum g)) +(defmethod specializer-accepts-generalizer-p + ((gf signum-generic-function) + (s signum-specializer) + (g signum-generalizer)) + (if (= (%signum s) (%signum g)) ; or EQL? + (values t t) + (values nil t))) + +(defmethod specializer-accepts-generalizer-p + ((gf signum-generic-function) + (specializer sb-mop:specializer) + (thing signum-specializer)) + (specializer-accepts-generalizer-p + gf specializer (class-of (%signum thing)))) + +(defmethod specializer-accepts-p + ((s signum-specializer) o) + (and (realp o) (= (%signum s) (signum o)))) +#+end_src + + Given these definitions, and once again some more straightforward + ones elided for reasons of space, we can implement the factorial + function as follows: + +#+begin_src lisp +(defgeneric fact (n) + (:generic-function-class signum-generic-function)) +(defmethod fact ((n (signum 0))) 1) +(defmethod fact ((n (signum 1))) (* n (fact (1- n)))) +#+end_src + + We do not need to include a method on =(signum -1)=, as the + standard =no-applicable-method= protocol will automatically apply to + negative real or non-real arguments. +** Accept HTTP header specializers + :PROPERTIES: + :CUSTOM_ID: Accept + :END: + In this section, we implement a non-trivial form of dispatch. The + application in question is a web server, and specifically to allow + the programmer to support RFC 2616 \cite{rfc2616} content + negotiation, of particular interest to publishers and consumers of + REST-style Web APIs. + + The basic mechanism in content negotiation is as follows: the web + client sends an HTTP request with an =Accept= header, which is a + string describing the media types it is willing to receive as a + response to the request, along with numerical preferences. The web + server compares these stated client preferences with the resources + it has available to satisfy this request, and sends the best + matching resource in its response. + + For example, a graphical web browser might by default send an + =Accept= header such as + =text/html,application/xml;q=0.9,*/*;q=0.8=. This should be + interpreted by a web server as meaning that if for a given resource + the server can provide content of type =text/html= (i.e. HTML), + then it should do so. Otherwise, if it can provide + =application/xml= content (i.e. XML of any schema), then that + should be provided; failing that, any other content type is + acceptable. + + In the case where there are static files on the filesystem, and the + web server must merely select between them, there is not much more + to say. However, it is not unusual for a web service to be backed + by some other form of data, and responses computed and sent on the + fly, and in these circumstances the web server must compute which + of its known output formats it can use to satisfy the request + before actually generating the best matching response. This can be + modelled as one generic function responsible for generating the + response, with methods corresponding to content-types -- and the + generic function must then perform method selection against the + request's =Accept= header to compute the appropriate response. + + The =accept-specializer= below implements the dispatch. It depends + on a lazily-computed =tree= slot to represent the information in + the accept header (generated by =parse-accept-string=), and a + function =q= to compute the (defaulted) preference level for a + given content-type and =tree=; then, method selection and ordering + involves finding the =q= for each =accept-specializer='s content + type given the =tree=, and sorting them according to the preference + level. + +#+begin_src lisp +(defclass accept-specializer (specializer) + ((media-type :initarg :media-type :reader media-type))) +(defclass accept-generalizer (generalizer) + ((header :initarg :header :reader header) + (tree) + (next :initarg :next :reader next))) +(defmethod generalizer-equal-hash-key + ((gf accept-generic-function) + (g accept-generalizer)) + `(accept-generalizer ,(header g))) +(defmethod specializer-accepts-generalizer-p + ((gf accept-generic-function) + (s accept-specializer) + (generalizer accept-generalizer)) + (values (q (media-type s) (tree generalizer)) t)) +(defmethod specializer-accepts-generalizer-p + ((gf accept-generic-function) + (s specializer) + (generalizer accept-generalizer)) + (specializer-accepts-generalizer-p + gf s (next generalizer))) + +(defmethod specializer< + ((gf accept-generic-function) + (s1 accept-specializer) + (s2 accept-specializer) + (generalizer accept-generalizer)) + (let ((m1 (media-type s1)) + (m2 (media-type s2)) + (tree (tree generalizer))) + (cond + ((string= m1 m2) '=) + (t (let ((q1 (q m1 tree))) + (q2 (q m2 tree)))) + (cond + ((= q1 q2) '=) + ((< q1 q2) '>) + (t '<)))))) +#+end_src + + The metaprogrammer can then support dispatching in this way for + suitable objects, such as the =request= object representing a + client request in the Hunchentoot web server. The code below + implements this, by defining the computation of a suitable + =generalizer= object for a given request, and specifying how to + compute whether the specializer accepts the given request object + (=q= returns a number between 0 and 1 if any pattern in the =tree= + matches the media type, and =nil= if the media type cannot be + matched at all). + +#+begin_src +(defmethod generalizer-of-using-class + ((gf accept-generic-function) + (arg tbnl:request)) + (make-instance 'accept-generalizer + :header (tbnl:header-in :accept arg) + :next (class-of arg))) +(defmethod specializer-accepts-p + ((specializer accept-specializer) + (obj tbnl:request)) + (let* ((accept (tbnl:header-in :accept obj)) + (tree (parse-accept-string accept)) + (q (q (media-type specializer) tree))) + (and q (> q 0)))) +#+end_src + + This dispatch cannot be implemented using filtered dispatch, except + by generating anonymous classes with all the right mime-types as + direct superclasses in dispatch order; the filter would generate +#+begin_src lisp +(ensure-class nil :direct-superclasses + '(text/html image/webp ...)) +#+end_src + and dispatch the operates using those anonymous classes. While + this is possible to do, it is awkward to express content-type + negotiation in this way, as it means that the dispatcher must know + about the universe of mime-types that clients might declare that + they accept, rather than merely the set of mime-types that a + particular generic function is capable of serving; handling + wildcards in accept strings is particularly awkward in the + filtering paradigm. + + Note that in this example, the method on =specializer<= involves a + nontrivial ordering of methods based on the =q= values specified in + the accept header (whereas in sections [[#Cons]] and [[#Signum]] only a + single extended specializer could be applicable to any given + argument). + + Also note that the accept specializer protocol is straightforwardly + extensible to other suitable objects; for example, one simple + debugging aid is to define that an =accept-specializer= should be + applicable to =string= objects. This can be done in a modular + fashion (see the code below, which can be completely disconnected + from the code for Hunchentoot request objects), and generalizes to + dealing with multiple web server libraries, so that + content-negotiation methods are applicable to each web server's + request objects. + +#+begin_src lisp +(defmethod generalizer-of-using-class + ((gf accept-generic-function) + (s string)) + (make-instance 'accept-generalizer + :header s + :next (class-of s))) +(defmethod specializer-accepts-p + ((s accept-specializer) (string string)) + (let* ((tree (parse-accept-string string)) + (q (q (media-type s) tree))) + (and q (> q 0)))) +#+end_src +** Pattern / xpattern / regex / optima + Here's the /really/ interesting bit, but on the other hand we're + probably going to run out of space, and the full description of + these is going to take us into =make-method-lambda= territory. + A second paper? Future work? +* Protocol + :PROPERTIES: + :CUSTOM_ID: Protocol + :END: + + In section [[#Examples]], we have seen a number of code fragments as + partial implementations of particular non-standard method dispatch, + using =generalizer= metaobjects to mediate between the methods of + the generic function and the actual arguments passed to it. In + section [[#Generalizer metaobjects]], we go into more detail regarding + these =generalizer= metaobjects, describing the generic function + invocation protocol in full, and showing how this protocol allows a + similar form of effective method cacheing as the standard one does. + In section [[#Generalizer performance]], we show the results of some + simple performance measurements to highlight the improvement that + this protocol can bring over a naïve implementation of generalized + dispatch, as well as highlighting the potential for further + improvement. + +** Generalizer metaobjects + :PROPERTIES: + :CUSTOM_ID: Generalizer metaobjects + :END: + +*** Generic function invocation + As in the standard generic function invocation protocol, the + generic function's actual functionality is provided by a + discriminating function. The functionality described in this + protocol is implemented by having a distinct subclass of + =standard-generic-function=, and a method on + =compute-discriminating-function= which produces a custom + discriminating function. The basic outline of the discriminating + function is the same as the standard one: it must first compute the + set of applicable methods given particular arguments; from that, it + must compute the effective method by combining the methods + appropriately according to the generic function's method + combination; finally, it must call the effective method with the + arguments. + + Computing the set of applicable methods is done using a pair of + functions: =compute-applicable-methods=, the standard metaobject + function, and a new function + =compute-applicable-methods-using-generalizers=. We define a + custom method on =compute-applicable-methods= which tests the + applicability of a particular specializer against a given argument + using =specializer-accepts-p=, a new protocol function with + default implementations on =class= and =eql-specializer= to + implement the expected behaviour. In order to order the methods, + as required by the protocol, we define a pairwise comparison + operator =specializer<= which defines an ordering between + specializers for a given generalizer argument (remembering that + even in standard CLOS the ordering between =class= specializers + can change depending on the actual class of the argument). + + The new =compute-applicable-methods-using-generalizers= is the + analogue of the MOP's =compute-applicable-methods-using-classes=. + Instead of calling it with the =class-of= each argument, we compute + the generalizers of each argument using the new function + =generalizer-of-using-class= (where the =-using-class= refers to + the class of the generic function rather than the class of the + object), and call it with the list of generalizers. As with the + standard function, a secondary return value indicates whether the + result of the function is definitive for that list of generalizers. + + Thus, in generic function invocation, we first compute the + generalizers of the arguments; we compute the ordered set of + applicable methods, either from the generalizers or (if that is + not definitive) from the arguments themselves; then the normal + effective method computation and call can occur. Unfortunately, + the nature of an effective method object is not specified, so we + have to reach into implementation internals a little in order to + call it, but otherwise the remainder of the generic function + invocation protocol is unchanged from the standard one. In + particular, method combination is completely unchanged; + programmers can choose arbitrary method combinations, including + user-defined long form combinations, for their generic functions + involving generalized dispatch. + +*** Effective method memoization + :PROPERTIES: + :CUSTOM_ID: Memoization + :END: + The potential efficiency benefit to having =generalizer= + metaobjects lies in the use of + =compute-applicable-methods-using-generalizers=. If a particular + generalized specializer accepts a variety of objects (such as the + =signum= specializer accepting all reals with a given sign, or the + =accept= specializer accepting all HTTP requests with a particular + =Accept= header), then there is the possibility of cacheing and + reusing the results of the applicable and effective method + computation. If the computation of the applicable method from + =compute-applicable-methods-using-generalizers= is definitive, + then the ordered set of applicable methods and the effective + method can be cached. + + One issue is what to use as the key for that cache. We cannot use + the generalizers themselves, as two generalizers that should be + considered equal for cache lookup will not compare as =equal= – + and indeed even the standard generalizer, the =class=, cannot be + used as we must be able to invalidate cache entries upon class + redefinition. The issue of =class= generalizers we can solve as + in \cite{Kiczales.Rodriguez:1990} by using the =wrapper= of a + class, which is distinct for each distinct (re)definition of a + class; for arbitrary generalizers, however, there is /a priori/ no + good way of computing a suitable hash key automatically, so we + allow the metaprogrammer to specify one by defining a method on + =generalizer-equal-hash-key=, and combining the hash keys for all + required arguments in a list to use as a key in an =equal= + hash-table. + + [XXX could we actually compute a suitable hash key using the + generalizer's class name and initargs?] + + - [X] =generalizer-of-using-class= (NB class of gf not class of object) + - [X] =compute-applicable-methods-using-generalizers= + - [X] =generalizer-equal-hash-key= + - [X] =specializer-accepts-generalizer-p= + - [X] =specializer-accepts-p= + - [X] =specializer<= +** Performance + :PROPERTIES: + :CUSTOM_ID: Generalizer performance + :END: + We have argued that the protocol presented here allows for + expressive control of method dispatch while preserving the + possibility of efficiency. In this section, we quantify the + efficiency that the memoization protocol described in section + [[#Memoization]] achieves, by comparing it both to the same protocol + with no memoization, as well as with equivalent dispatch + implementations in the context of methods with regular + specializers, and with implementation in straightforward functions. + + In the case of the =cons-specializer=, we benchmark the walker + acting on a small but non-trivial form. The implementation + strategies in the table below refer to: an implementation in a + single function with a large =typecase= to dispatch between all the + cases; the natural implementation in terms of a standard generic + function with multiple methods (the method on =cons= having a + slightly reduced =typecase= to dispatch on the first element, and + other methods handling =symbol= and other atoms); and three + separate cases using =cons-specializer= objects. As well as + measuring the effect of memoization against the full invocation + protocol, we can also introduce a special case: when only one + argument participates in method selection (all the other required + arguments only being specialized on =t=), we can avoid the + construction of a list of hash keys and simply use the key + from the single active generalizer directly. + + Refer to \cite{Kiczales.Rodriguez:1990} + + | implementation | time (µs/call) | overhead | + |-----------------------+----------------+----------| + | function | 3.17 | | + | standard-gf/methods | 3.6 | +14% | + | cons-gf/one-arg-cache | 7.4 | +130% | + | cons-gf | 15 | +370% | + | cons-gf/no-cache | 90 | +2700% | + + The benchmarking results from this exercise are promising: in + particular, the introduction of the effective method cache speeds + up the use of generic specializers in this case by a factor of 6, + and the one-argument special case by another factor of 2. For this + workload, even the one-argument special case only gets to within a + factor of 2-3 of the function and standard generic function + implementations, but the overall picture is that the memoizability + in the protocol does indeed drastically reduce the overhead + compared with the full invocation. + + For the =signum-specializer= case, we choose to benchmark the + computation of 20!, because that is the largest factorial whose + answer fits in SBCL's 63-bit fixnums – in an attempt to measure the + worst case for generic dispatch, where the work done within the + methods is as small as possible without being meaningless, and in + particular does not cause allocation or garbage collection to + obscure the picture. + +#+begin_src lisp :exports none +(progn (gc :full t) (time (dotimes (i 10000) (%fact 20)))) +#+end_src + + | implementation | time (µs/call) | overhead | + |-------------------------+----------------+----------| + | function | 0.6 | | + | standard-gf/fixnum | 1.2 | +100% | + | signum-gf/one-arg-cache | 7.5 | +1100% | + | signum-gf | 23 | +3800% | + | signum-gf/no-cache | 240 | +41000% | + + The relative picture is similar to the =cons-specializer= case; + including a cache saves a factor of 10 in this case, and another + factor of 3 for the one-argument cache special case. The cost of + the genericity of the protocol here is starker; even the + one-argument cache is a factor of 6 slower than the standard + generic-function implementation, and a further factor of 2 away + from the implementation of factorial as a function. We discuss + ways in which we expect to be able to improve performance in + section [[#Future Work]]. + + We could allow the metaprogrammer to improve on the one-argument + performance by constructing a specialized cache: for =signum= + arguments of =rational= arguments, the logical cache structure is + to index a three-element vector with =(1+ signum)=. The current + protocol does not provide a way of eliding the two generic function + calls for the generic cache; we discuss possible approaches in + section [[#Conclusions]]. +** Full protocol + Description and specification left for reasons of space (we'll see?) + - [ ] =same-specializer-p= + - [ ] =parse/unparse-specializer-using-class= + - [ ] =make-method-specializers-form= + - [ ] jmoringe: In an email, I suggested + =make-specializer-form-using-class=: + + #+begin_quote + Could we change =make-method-specializers-form='s default + behaviour to call a new generic function + #+begin_src + make-specializer-form-using-class gf method name env + #+end_src + with builtin methods on =sb-mop:specializer=, =symbol=, =cons= (for + eql-specializers)? This would make it unnecessary to repeat + boilerplate along the lines of + #+begin_src lisp + (flet ((make-parse-form (name) + (if + + ))) + `(list ,@(mapcar #'make-parse-form specializer-names))) + #+end_src + for each generic function class. + #+end_quote + - [ ] =make-method-lambda= revision (use environment arg?) + + jmoringe: would only be relevant for pattern dispatch, right? I + think, we didn't finish the discussion regarding special + variables vs. environment vs. new protocol function + +* Related Work + :PROPERTIES: + :CUSTOM_ID: Related Work + :END: + - [ ] Newton/Rhodes, \cite{Newton.Rhodes:2008} + - [ ] filtered dispatch -- the point is that our work continues to + be useful in cases where there are unbounded numbers of + equivalence classes but each given invokation involves a small + number of methods. Filtered dispatch works by having a custom + discriminating function which wraps the usual one, and augments + the set of applicable methods computed with applicable methods + from other (hidden) generic functions (one per filter group). It + then also has a custom method combination to handle combining + these applicable methods. \cite{Costanza.etal:2008} + - [ ] ContextL / context-oriented programming -- dispatch occurs on + hidden layer argument being an instance of an anonymous class with + suitably arranged superclasses -- OK because set of layers is + bounded and under programmer control. \cite{Hirschfeld.etal:2008,Vallejos.etal:2010} + - [ ] http://soft.vub.ac.be/Publications/2010/vub-tr-soft-10-04.pdf + - [ ] http://soft.vub.ac.be/lambic/files/lambic-ilc09.pdf + - [ ] http://soft.vub.ac.be/Publications/2011/vub-soft-phd-11-03.pdf + - [ ] Prototypes with Multiple Dispatch + http://sauerbraten.org/lee/ecoop.pdf -- extension of Self-style + object system to handle multiple equally-privileged "receivers". + A good test case for our protocol; handled adequately with + generalizer being the tuple of (roles,delegations), with some + thought needed for method redefinitions but otherwise working + fine. \cite{Salzman.Aldrich:2005} + - [ ] Sheeple + - [ ] Multiple dispatch in Clojure + http://clojure.org/multimethods -- seems to allow hierarchy-based, + eql and the equivalent of filtered dispatch +* Conclusions + :PROPERTIES: + :CUSTOM_ID: Conclusions + :END: + - protocol for straightforward definition of custom dispatch + + interoperates seamlessly with rest of CLOS: method combination, + etc. + + tolerably efficient: two extra standard gf invokations and one + hash table lookup per call on the fast path (but more to be + done) + + expressive: handles forms of dispatch not handled elsewhere; all + the usual niceties of redefinition, modularity, introspection +** Future Work + :PROPERTIES: + :CUSTOM_ID: Future Work + :END: + Although the protocol described in this paper allows for a more + efficient implementation, as described in section [[#Memoization]], + than computing the applicable and effective methods at each generic + function call, the efficiency is still some way away from a + baseline of the standard generic-function, let alone a standard + function. Most of the invocation protocol is memoized, but there + are still two full standard generic-function calls – + =generalizer-of-using-class= and =generalizer-equal-hash-key= – per + argument per call to a generic function with extended specializers, + not to mention a hash table lookup. + + For many applications, the additional flexibility afforded by + generalized specializers might be worth the cost in efficiency, but + it would still be worth investigating how much the overhead from + generalized specializers can be reduced; one possible avenue for + investigation is giving greater control over the cacheing strategy + to the metaprogrammer. + + As an example, consider the =signum-specializer=. The natural + cache structure for a single argument generic function specializing + on =signum= is probably a four-element vector, where the first + three elements hold the effective methods for =signum= values of + -1, 0, and 1, and the fourth holds the cached effective methods for + everything else. This would make the invocation of such functions + very fast for the (presumed) common case where the argument is in + fact a real number. We hope to develop and show the effectiveness + of an appropriate protocol to allow the metaprogrammer to construct + and exploit such cacheing strategies, and (more speculatively) to + implement the lookup of an effective method function in other ways. + + We also aim to demonstrate support within this protocol for some + particular cases of generalized specializers which seem to have + widespread demand (in as much as any language extension can be said + to be in “demand”). In particular, we have preliminary work + towards supporting efficient dispatch over pattern specializers + such as implemented in the \textsf{Optima} library[fn:2], and over + a prototype object system similar to that in Slate + \cite{Salzman.Aldrich:2005}. Our current source code for the work + described in this paper can be seen in the git source code + repository at [[http://christophe.rhodes.io/git/specializable.git]], + which will be updated with future developments. +** Acknowledgments + We thank Lee Salzman, Pascal Costanza and Mikel Evins for helpful + and informative discussions, and all the respondents to one + author's call for imaginative uses for generalized specializers. + +\bibliographystyle{plain} +\bibliography{crhodes,specializers} + +* Footnotes + +[fn:1] the \textsf{Closer to MOP} project attempts to harmonize the + different implementations of the metaobject protocol in Common Lisp. + +[fn:2] https://github.com/m2ym/optima