els-specializers.org

   1 #+TITLE: Generalizers: New Metaobjects for Generalized Dispatch
   2 #+AUTHOR: Christophe Rhodes, Jan Moringen, David Lichteblau
   3 #+OPTIONS: toc:nil
   4
   5 #+LaTeX_HEADER: \usepackage[margin=1in]{geometry}
   6
   7 #+begin_abstract
   8 1. This paper introduces a new metaobject, the generalizer, which
   9    complements the existing specializer metaobject.
  10 2. With the help of examples, we show that this metaobject allows for
  11    the efficient implementation of complex non-class-based dispatch
  12    within the framework of existing metaobject protocols
  13 3. We present the generalizer protocol, implemented within the SBCL
  14    implementation of Common Lisp
  15 4. In combination with previous work, this produces a fully-functional
  16    extension of the existing mechanism for method selection and
  17    effective method computation, including support for standard and
  18    user-defined method combination independent from method selection.
  19 #+end_abstract
  20
  21 * Introduction
  22   The revisions to the original Common Lisp language \cite{CLtL1}
  23   included the detailed specification of an object system, known as
  24   the Common Lisp Object System (CLOS), which was eventually
  25   standardized as part of the ANSI Common Lisp standard \cite{CLtS}.
  26   The object system as presented to the standardization committee was
  27   formed of three parts, the first two of which covered XXX [what?]
  28   and were incorporated into the final standard, and the third,
  29   covering a Metaobject Protocol (MOP) for CLOS, was not.
  30
  31   Nevertheless, the CLOS MOP has proven to be a robust design, and
  32   while many implementations have derived their implementations of
  33   CLOS from either the Closette illustrative implementation in
  34   \cite{AMOP}, or the Portable Common Loops implementation of CLOS
  35   from Xerox Parc, there have been from-scratch reimplementations of
  36   CLOS (in at least CLISP; check for others -- ABCL?  Lisp500?!)
  37   incorporating the majority of the Metaobject Protocol as described.
  38
  39   Although it has stood the test of time, the MOP is neither without issues
  40   (e.g. M-M-L considered harmful; slot-definition initargs issue) nor
  41   a complete framework for the metaprogrammer to implement all
  42   conceivable variations of object-oriented behaviour; indeed, while
  43   metaprogramming offers some possibilities for customization of the
  44   object system behaviour, those possibilities cannot extend
  45   arbitrarily in all directions.   There is still an expectation that
  46   functionality is implemented with methods on generic functions,
  47   acting on objects with slots.  [XXX find Paepke picture here?  Not
  48   Paepke; AMOP?].  XXX include typical examples of MOP: object
  49   persistence; maybe ref. Kizcales "MOPs: why we want them and what
  50   else they can do"? (Fig. 2 in that is good) ORMs; sparse slots.
  51
  52   One area of functionality where there is scope for customization by
  53   the metaprogrammer is in the mechanics and semantics of method
  54   applicability and dispatch.  While in principle AMOP allows
  55   customization of dispatch in various different ways (the
  56   metaprogrammer can define methods on protocol functions such as
  57   =compute-applicable-methods=,
  58   =compute-applicable-methods-using-classes=), for example, in
  59   practice implementation support for this was weak until relatively
  60   recently (ref. closer, also check how ContextL and filtered dispatch
  61   are implemented).
  62
  63   Another potential mechanism for customizing dispatch is implicit in
  64   the class structure defined by AMOP: standard specializer objects
  65   (instances of =class= and =eql-specializer=) are generalized
  66   instances of the =specializer= protocol class, and in principle
  67   there are no restrictions on the metaprogrammer constructing
  68   additional subclasses.  Previous work [Newton/Rhodes] has explored
  69   the potential for customizing generic function dispatch using
  70   extended specializers, but as of that work the metaprogrammer must
  71   override the entirety of the generic function invocation protocol
  72   (from =compute-discriminating-function= on down), leading to toy
  73   implementations and duplicated effort.
  74
  75   This paper introduces a protocol for efficient and controlled
  76   handling of arbitrary subclasses of =specializer=.  In particular,
  77   it introduces the =generalizer= protocol class, which generalizes
  78   (ahem) the return value of =class-of=, and allows the metaprogrammer
  79   to hook into cacheing schemes to avoid needless recomputation of
  80   effective methods for sufficiently similar generic function
  81   arguments.
  82
  83   The remaining sections in this paper can be read in any order.  We
  84   give some motivating examples in section XX, including
  85   reimplementations of examples from previous work, as well as
  86   examples which are poorly supported by previous protocols.  We
  87   describe the protocol itself in section YY, describing each protocol
  88   function in detail and, where applicable, relating it to existing
  89   protocol functions within the CLOS MOP.  We survey related work in
  90   more detail in section ZZ, touching on work on customized dispatch
  91   schemes in other environments.  Finally, we draw our conclusions
  92   from this work, and indicate directions for further development, in
  93   section WW; reading that section before the others indicates
  94   substantial trust in the authors' work.
  95 * Examples
  96   - [ ] =cons-specializer= (can be done using filtered dispatch)
  97   - [ ] factorial (like filtered dispatch)
  98   - [ ] HTTP Accept header
  99   - [ ] xpattern
 100   - [ ] prototype/multimethod
 101 ** car-of-cons
 102    NB this example can be done using filtered dispatch, with a filter
 103    calling =car= on cons arguments.
 104
 105    Note also that there's no real need for =cons-specializer= and
 106    =cons-generalizer= to be distinct classes (as with =class= and
 107    =class=).  Also true for =signum=, below; but more interesting
 108    dispatch reveals the need to split.
 109 #+begin_src lisp
 110 (defclass cons-specializer (specializer)
 111   ((%car :reader %car :initarg :car)))
 112 (defclass cons-generalizer (generalizer)
 113   ((%car :reader %car :initarg :car)))
 114 (defmethod generalizer-of-using-class ((gf cons-generic-function) arg)
 115   (typecase arg
 116     ((cons symbol) (make-instance 'cons-generalizer :car (car arg)))
 117     (t (call-next-method))))
 118 (defmethod generalizer-equal-hash-key ((gf cons-generic-function)
 119                                        (g cons-generalizer))
 120   (%car g))
 121 (defmethod specializer-accepts-generalizer-p ((gf cons-generic-function)
 122                                               (s cons-specializer)
 123                                               (g cons-generalizer))
 124   (if (eql (%car s) (%car g))
 125       (values t t)
 126       (values nil t)))
 127 (defmethod specializer-accepts-p ((s cons-specializer) o)
 128   (and (consp o) (eql (car o) (%car s))))
 129
 130 #| less interesting methods elided |#
 131
 132 #| XXX insert motivating example from Newton/Rhodes here |#
 133 #+end_src
 134 ** signum
 135    NB this example can definitely be done using filtered dispatch.
 136
 137    Point out obvious similarity between this and car-of-cons.  Note
 138    the subtlety, though, in generalizer-of-using-class / signum wrt
 139    rational vs floating point arguments
 140 #+begin_src lisp
 141 (defclass signum-specializer (specializer)
 142   ((%signum :reader %signum :initarg :signum)))
 143 (defclass signum-generalizer (generalizer)
 144   ((%signum :reader %signum :initarg :signum)))
 145 (defmethod generalizer-of-using-class ((gf signum-generic-function) arg)
 146   (typecase arg
 147     (real (make-instance 'signum-generalizer :signum (signum arg)))
 148     (t (call-next-method))))
 149 (defmethod generalizer-equal-hash-key ((gf signum-generic-function)
 150                                        (g signum-specializer))
 151   (%signum g)) ; this will create multiple entries for the same emf, but that's OK
 152 (defmethod specializer-accepts-generalizer-p ((gf signum-generic-function)
 153                                               (s signum-specializer)
 154                                               (g signum-generalizer))
 155   (if (= (%signum s) (%signum g)) ; or EQL?
 156       (values t t)
 157       (values nil t)))
 158 (defmethod specializer-accepts-p ((s signum-specializer) o)
 159   (and (realp o) (= (%signum s) (signum o))))
 160
 161 #| again elide more boring methods |#
 162
 163 (defgeneric fact (n)
 164   (:generic-function-class signum-generic-function))
 165 (defmethod fact ((n (signum 1))) (* n (fact (1- n))))
 166 (defmethod fact ((n (signum 0))) 1)
 167 (defmethod fact ((n (signum -1)))
 168   (error "factorial of negative number: ~D" n))
 169 #+end_src
 170 ** HTTP Accept header
 171    implement RFC2616 content negotiation
 172
 173    NB this definitely can't be done with filtered dispatch, except by
 174    generating anonymous classes with all the right mime-types as
 175    direct superclasses in dispatch order,so the filter does
 176 #+begin_src lisp
 177 (ensure-class nil :direct-superclasses '(text/html image/webp ...))
 178 #+end_src
 179    and dispatch is defined by using those classes.  And that's even
 180    more awkward than it sounds, because that means that in principle
 181    all the mime types in the universe need an existence as classes, to
 182    cater for arbitrary mime types in accept headers.  And handling
 183    wildcards is pretty much impossible, too.  See that in
 184    =specializer<= which involves a nontrivial ordering of methods
 185    (whereas in two above previous cases only a single extended
 186    specializer could be applicable to any given argument)
 187
 188    Also of interest: note that we can have these
 189    specializer/generalizers handle arbitrary objects: the string and
 190    tbnl:request methods are independent of each other; this
 191    generalizes to dealing with multiple web server libraries.
 192 #+begin_src lisp
 193 (defclass accept-specializer (extended-specializer)
 194   ((media-type :initarg :media-type :reader media-type)))
 195 (defclass accept-generalizer ()
 196   ((header :initarg :header :reader header)
 197    (tree)
 198    (next :initarg :next :reader next)))
 199 (defmethod generalizer-equal-hash-key
 200     ((gf accept-generic-function) (g accept-generalizer))
 201   `(accept-generalizer ,(header g)))
 202 (defmethod specializer-accepts-generalizer-p ((gf accept-generic-function) (s acc
 203 ept-specializer) (generalizer accept-generalizer))
 204   (values (q (media-type s) (tree generalizer)) t))
 205 (defmethod specializer-accepts-generalizer-p ((gf accept-generic-function) (s sb-
 206 mop:specializer) (generalizer accept-generalizer))
 207   (specializer-accepts-generalizer-p gf s (next generalizer)))
 208
 209 (defmethod specializer< ((gf accept-generic-function) (s1 accept-specializer) (s2
 210  accept-specializer) generalizer)
 211   (cond
 212     ((string= (media-type s1) (media-type s2)) '=)
 213     (t (let ((q1 (q (media-type s1) (tree generalizer)))
 214              (q2 (q (media-type s2) (tree generalizer))))
 215          (cond
 216            ((= q1 q2) '=)
 217            ((< q1 q2) '>)
 218            (t '<))))))
 219
 220 ;; here are the only methods that actually know about TBNL
 221 (defmethod generalizer-of-using-class ((gf accept-generic-function) (arg tbnl:request))
 222   (make-instance 'accept-generalizer
 223                  :header (tbnl:header-in :accept arg)
 224                  :next (class-of arg)))
 225 (defmethod specializer-accepts-p ((specializer accept-specializer) (obj tbnl:requ
 226 est))
 227   (q (media-type specializer) (parse-accept-string (tbnl:header-in :accept obj)))
 228 )
 229
 230 ;; we can define methods on STRING too, for debugging/simulation purposes
 231 (defmethod generalizer-of-using-class ((gf accept-generic-function) (s string))
 232   (make-instance 'accept-generalizer
 233                  :header s
 234                  :next (class-of s)))
 235 (defmethod specializer-accepts-p ((s accept-specializer) (string string))
 236   (q (media-type s) (parse-accept-string string)))
 237 #+end_src
 238 ** Pattern / xpattern / regex / optima
 239    Here's the /really/ interesting bit, but on the other hand we're
 240    probably going to run out of space, and the full description of
 241    these is going to take us into make-method-lambda territory.  A
 242    second paper?  Future work?  It would be really nice to put a
 243    marker in the sand.
 244 * Protocol
 245 ** Generalizer
 246    - [ ] =generalizer-of-using-class= (NB class of gf not class of object)
 247    - [ ] =compute-applicable-methods-using-generalizers=
 248    - [ ] =generalizer-equal-hash-key=
 249    - [ ] =specializer-accepts-generalizer-p=
 250    - [ ] =specializer-accepts-p=
 251    - [ ] =specializer<=
 252 ** Full protocol
 253    Description and specification left for reasons of space (we'll see?)
 254    - [ ] =same-specializer-p=
 255    - [ ] =parse/unparse-specializer-using-class=
 256    - [ ] =make-method-specializers-form=
 257    - [ ] =make-method-lambda= revision (use environment arg?)
 258 * Related Work
 259   - [ ] Newton/Rhodes
 260   - [ ] filtered dispatch
 261   - [ ] ContextL / context-oriented programming
 262   - [ ] http://soft.vub.ac.be/Publications/2010/vub-tr-soft-10-04.pdf
 263   - [ ] http://soft.vub.ac.be/lambic/files/lambic-ilc09.pdf
 264   - [ ] http://soft.vub.ac.be/Publications/2011/vub-soft-phd-11-03.pdf
 265   - [ ] Prototypes with Multiple Dispatch http://sauerbraten.org/lee/ecoop.pdf
 266   - [ ] Sheeple
 267 * Conclusions