some benchmarketing.

[paper-els-specializers.git] / els-specializers.org

#+TITLE: Generalizers: New Metaobjects for Generalized Dispatch
#+AUTHOR: Christophe Rhodes, Jan Moringen, David Lichteblau
#+OPTIONS: toc:nil

#+LaTeX_HEADER: \usepackage[margin=1in]{geometry}

#+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.
  jmoringe:
  + introspection, e.g. documentation generation
  + programmatic construction of classes and generic functions
    e.g. for IDL compilers, model transformations

  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).
  jmoringe: filtered dispatch uses a custom method combination, i
  think

  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 (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 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: jmoringe: (un)parsing, specializer<?, more? |#

#| XXX insert motivating example from Newton/Rhodes here |#
#+end_src
** signum
   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)) ; 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)))

;; this method is perhaps interesting enough to talk about?
(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))))

#| 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:

#+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.

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 |

#+begin_src lisp
(progn (gc :full t) (time (dotimes (i 10000) (%fact 20))))
#+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.

   jmoringe: the name =accept-specializer=, while sensible, may
   confusing in this context because "accept" occurs as part of the
   protocol with a different semantic.

#+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

   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.

** 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
** 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<=
     jmoringe: If I remember correctly, closette has
     =method-more-specific-p= should we aim for parity with that and
     use =specializer-more-specific-p=? The downside would be that
     =-p= indicates a Boolean return value which is not the case here.
** 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 <name-is-interesting>
                <handle-interesting-specializer>
                <repeat-handling-of-standard-specializers>)))
       `(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
  - [ ] Newton/Rhodes
  - [ ] 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.
  - [ ] 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
  - [ ] 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.
  - [ ] Sheeple
* Conclusions
** Acknowledgments
   We thank Lee Salzman, Pascal Costanza, Mikel Evins for their
   helpful discussions