#+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
projects / paper-els-specializers.git / commitdiff