From cdaf5a1dd66c66b3d5cbb663ae1af485ce8ff37c Mon Sep 17 00:00:00 2001 From: Christophe Rhodes Date: Wed, 12 Feb 2014 22:04:33 +0000 Subject: [PATCH] a pass through the text on an extended train journey. Thanks, #UKstorm. Thorm. --- els-specializers.org | 217 +++++++++++++++++++++++++++++-------------- 1 file changed, 149 insertions(+), 68 deletions(-) diff --git a/els-specializers.org b/els-specializers.org index d7e129d..59b1bd1 100644 --- a/els-specializers.org +++ b/els-specializers.org @@ -36,13 +36,13 @@ CLOS (in at least CLISP; check for others -- ABCL? Lisp500?!) incorporating the majority of the Metaobject Protocol as described. - Although it has stood the test of time, the MOP is neither without issues - (e.g. M-M-L considered harmful; slot-definition initargs issue) nor - a complete framework for the metaprogrammer to implement all - conceivable variations of object-oriented behaviour; indeed, 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 + Although it has stood the test of time, the MOP is neither without + issues (e.g. M-M-L considered harmful; slot-definition initargs + issue) nor a complete framework for the metaprogrammer to implement + all conceivable variations of object-oriented behaviour; indeed, + 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. [XXX find Paepke picture here? Not Paepke; AMOP?]. XXX include typical examples of MOP: object @@ -104,19 +104,47 @@ section WW; reading that section before the others indicates substantial trust in the authors' work. * Examples + In this section, we present a number of examples of dispatch + implemented using our protocol, which we describe in section YY. + 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-specializer= (can be done using filtered dispatch) - [ ] factorial (like filtered dispatch) - [ ] HTTP Accept header - [ ] xpattern - [ ] prototype/multimethod ** car-of-cons - NB this example can be done using filtered dispatch, with a filter - calling =car= on cons arguments. - - Note also that there's no real need for =cons-specializer= and - =cons-generalizer= to be distinct classes (as with =class= and - =class=). Also true for =signum=, below; but more interesting - dispatch reveals the need to split. + 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: 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. #+begin_src lisp (defclass cons-specializer (specializer) ((%car :reader %car :initarg :car))) @@ -142,6 +170,26 @@ #| XXX insert motivating example from Newton/Rhodes here |# #+end_src + + TODO Timings: generalizer-enabled vs not vs case (car x) for CL special + operators. Tweak so that the overhead of =case= is actually important. + + 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= + 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 XX.x an example of a case where filtered + dispatch is incapable of efficiently implementing the dispatch, but + first we present our implementation of the motivating case from + \cite{Costanza.etal:2008}. ** signum Our second example of the implementation and use of generalized specializers is a reimplementation of one of the examples in @@ -193,8 +241,9 @@ #| again elide more boring methods |# #+end_src -Given these definitions, and some more straightforward ones elided for -reasons of space, we can implement the factorial function as follows: + Given these definitions, and some more straightforward ones elided + for reasons of space, we can implement the factorial function as + follows: #+begin_src lisp (defgeneric fact (n) @@ -203,57 +252,69 @@ reasons of space, we can implement the factorial function as follows: (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. - -Benchmarketing: we chose to benchmark 20! because that is the largest -factorial whose answer fits in SBCL's 63-bit fixnums, so as to attempt -to measure the maximum effect of dispatch (unobscured by allocation / -gc issues) - -| fact (signum-gf) | %fact (fun) | %%fact (gf / 1meth) | fact (signum-gf / 1arg hash-special-case) | -|------------------+-------------+---------------------+-------------------------------------------| -| 0.284 | 0.004 | 0.016 | 0.032 | -| 0.076 | 0.008 | 0.012 | 0.024 | -| 0.072 | 0.004 | 0.012 | 0.116 | -| 0.264 | 0.004 | 0.008 | 0.120 | -| 0.292 | 0.008 | 0.012 | 0.120 | -| 0.264 | 0.004 | 0.016 | 0.084 | -| 0.276 | 0.008 | 0.012 | 0.092 | -| 0.264 | 0.008 | 0.012 | 0.036 | -| 0.276 | 0.008 | 0.004 | 0.104 | -| 0.272 | 0.004 | 0.012 | 0.020 | + 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. -#+begin_src lisp -(progn (gc :full t) (time (dotimes (i 10000) (%fact 20)))) -#+end_src -** HTTP Accept header - implement RFC2616 content negotiation + Benchmarketing: we chose to benchmark 20! because that is the + largest factorial whose answer fits in SBCL's 63-bit fixnums, so as + to attempt to measure the maximum effect of dispatch (unobscured by + allocation / gc issues) - NB this definitely can't be done with filtered dispatch, except by - generating anonymous classes with all the right mime-types as - direct superclasses in dispatch order,so the filter does #+begin_src lisp -(ensure-class nil :direct-superclasses '(text/html image/webp ...)) +(progn (gc :full t) (time (dotimes (i 10000) (%fact 20)))) #+end_src - and dispatch is defined by using those classes. And that's even - more awkward than it sounds, because that means that in principle - all the mime types in the universe need an existence as classes, to - cater for arbitrary mime types in accept headers. And handling - wildcards is pretty much impossible, too. See that in - =specializer<= which involves a nontrivial ordering of methods - (whereas in two above previous cases only a single extended - specializer could be applicable to any given argument) - Also of interest: note that we can have these - specializer/generalizers handle arbitrary objects: the =string= and - =tbnl:request= methods are independent of each other; this - generalizes to dealing with multiple web server libraries. - - jmoringe: the name =accept-specializer=, while sensible, may - confusing in this context because "accept" occurs as part of the - protocol with a different semantic. + | fact (signum-gf) | %fact (fun) | %%fact (gf / 1meth) | fact (signum-gf / 1arg hash-special-case) | + |------------------+-------------+---------------------+-------------------------------------------| + | 0.284 | 0.004 | 0.016 | 0.032 | + | 0.076 | 0.008 | 0.012 | 0.024 | + | 0.072 | 0.004 | 0.012 | 0.116 | + | 0.264 | 0.004 | 0.008 | 0.120 | + | 0.292 | 0.008 | 0.012 | 0.120 | + | 0.264 | 0.004 | 0.016 | 0.084 | + | 0.276 | 0.008 | 0.012 | 0.092 | + | 0.264 | 0.008 | 0.012 | 0.036 | + | 0.276 | 0.008 | 0.004 | 0.104 | + | 0.272 | 0.004 | 0.012 | 0.020 | + + 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 WW. +** HTTP Accept header + 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. + + 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. + + The =accept-specializer= below implements the dispatch. It depends + on a lazily-computed =tree= to represent the information in the + accept header, 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 (extended-specializer) @@ -292,7 +353,30 @@ mop:specializer) (generalizer accept-generalizer)) est)) (q (media-type specializer) (parse-accept-string (tbnl:header-in :accept obj))) ) +#+end_src + This dispatch can't be done with filtered dispatch, except by + generating anonymous classes with all the right mime-types as + direct superclasses in dispatch order,so the filter does +#+begin_src lisp +(ensure-class nil :direct-superclasses '(text/html image/webp ...)) +#+end_src + and dispatch is defined by using those classes. And that's even + more awkward than it sounds, because that means that in principle + all the mime types in the universe need an existence as classes, to + cater for arbitrary mime types in accept headers. And handling + wildcards is pretty much impossible, too. See that in + =specializer<= which involves a nontrivial ordering of methods + (whereas in two above previous cases only a single extended + specializer could be applicable to any given argument) + + Also of interest: note that we can have these + specializer/generalizers handle arbitrary objects: we can define + methods on =string=, completely independently from the methods on + =tbnl:request= methods are independent of each other; this + generalizes to dealing with multiple web server libraries. + +#+begin_src lisp ;; we can define methods on STRING too, for debugging/simulation purposes (defmethod generalizer-of-using-class ((gf accept-generic-function) (s string)) (make-instance 'accept-generalizer @@ -302,12 +386,9 @@ est)) (q (media-type s) (parse-accept-string string))) #+end_src - jmoringe: The role of =accept-generalizer.tree= and the =q= - function are hard to understand and may require some - explanation. However, the example with its distinct, asymmetric - specializers/generalizers, =accept-generalizer.next= and - =specializer<= is likely worth it. - + jmoringe: the name =accept-specializer=, while sensible, may + confusing in this context because "accept" occurs as part of the + protocol with a different semantic. ** 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 -- 2.39.5