From 528a37d55e475944ecbe497c3ea16f8b569abbbb Mon Sep 17 00:00:00 2001 From: Christophe Rhodes Date: Thu, 6 Feb 2014 08:07:40 +0000 Subject: [PATCH] draft as sent to Jan and David --- els-specializers.org | 268 ++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 264 insertions(+), 4 deletions(-) diff --git a/els-specializers.org b/els-specializers.org index 1cecedf..6af1392 100644 --- a/els-specializers.org +++ b/els-specializers.org @@ -1,7 +1,267 @@ #+TITLE: Generalizers: New Metaobjects for Generalized Dispatch -#+AUTHOR: Christophe Rhodes +#+AUTHOR: Christophe Rhodes, Jan Moringen, David Lichteblau +#+OPTIONS: toc:nil +#+LaTeX_HEADER: \usepackage[margin=1in]{geometry} -#+BEGIN_ABSTRACT -Foo -#+END_ABSTRACT +#+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{CLtL1} + 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 parts, the first two of which covered XXX [what?] + and were incorporated into the final standard, and the third, + 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 -- 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 + 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 + persistence; maybe ref. Kizcales "MOPs: why we want them and what + else they can do"? (Fig. 2 in that is good) ORMs; sparse slots. + + 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 (ref. closer, also check how ContextL and filtered dispatch + are implemented). + + 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 [Newton/Rhodes] 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 arbitrary subclasses of =specializer=. In particular, + it introduces the =generalizer= protocol class, which generalizes + (ahem) the return value of =class-of=, and allows the metaprogrammer + to hook into cacheing schemes to avoid needless recomputation of + effective methods for sufficiently similar generic function + arguments. + + The remaining sections in this paper can be read in any order. We + give some motivating examples in section XX, 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 YY, 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 ZZ, 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 WW; reading that section before the others indicates + substantial trust in the authors' work. +* Examples + - [ ] =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. +#+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)))) + +#| less interesting methods elided |# + +#| XXX insert motivating example from Newton/Rhodes here |# +#+end_src +** signum + NB this example can definitely be done using filtered dispatch. + + Point out obvious similarity between this and car-of-cons. Note + the subtlety, though, in generalizer-of-using-class / signum wrt + rational vs floating point arguments +#+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)) ; this will create multiple entries for the same emf, but that's OK +(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-p ((s signum-specializer) o) + (and (realp o) (= (%signum s) (signum o)))) + +#| again elide more boring methods |# + +(defgeneric fact (n) + (:generic-function-class signum-generic-function)) +(defmethod fact ((n (signum 1))) (* n (fact (1- n)))) +(defmethod fact ((n (signum 0))) 1) +(defmethod fact ((n (signum -1))) + (error "factorial of negative number: ~D" n)) +#+end_src +** HTTP Accept header + implement RFC2616 content negotiation + + 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 ...)) +#+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. +#+begin_src lisp +(defclass accept-specializer (extended-specializer) + ((media-type :initarg :media-type :reader media-type))) +(defclass accept-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 acc +ept-specializer) (generalizer accept-generalizer)) + (values (q (media-type s) (tree generalizer)) t)) +(defmethod specializer-accepts-generalizer-p ((gf accept-generic-function) (s sb- +mop: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) + (cond + ((string= (media-type s1) (media-type s2)) '=) + (t (let ((q1 (q (media-type s1) (tree generalizer))) + (q2 (q (media-type s2) (tree generalizer)))) + (cond + ((= q1 q2) '=) + ((< q1 q2) '>) + (t '<)))))) + +;; here are the only methods that actually know about TBNL +(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:requ +est)) + (q (media-type specializer) (parse-accept-string (tbnl:header-in :accept obj))) +) + +;; 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 + :header s + :next (class-of s))) +(defmethod specializer-accepts-p ((s accept-specializer) (string string)) + (q (media-type s) (parse-accept-string string))) +#+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? It would be really nice to put a + marker in the sand. +* Protocol +** Generalizer + - [ ] =generalizer-of-using-class= (NB class of gf not class of object) + - [ ] =compute-applicable-methods-using-generalizers= + - [ ] =generalizer-equal-hash-key= + - [ ] =specializer-accepts-generalizer-p= + - [ ] =specializer-accepts-p= + - [ ] =specializer<= +** 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= + - [ ] =make-method-lambda= revision (use environment arg?) +* Related Work + - [ ] Newton/Rhodes + - [ ] filtered dispatch + - [ ] ContextL / context-oriented programming + - [ ] 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 + - [ ] Sheeple +* Conclusions -- 2.39.5