another train journey's worth of changes

[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
  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
   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)))
(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? |#
#+end_src
#+begin_src
(defgeneric walk (form env vars)
  (:generic-function-class cons-generic-function))
(defmethod walk ((expr (cons lambda)) env call-stack)
  (let ((lambda-list (cadr expr))
        (body (cddr expr)))
    (with-checked-bindings ((bindings-from-ll lambda-list) env call-stack)
      (dolist (form body)
        (walk form env (cons form call-stack))))))
(defmethod walk ((expr (cons let)) env call-stack)
  (with-checked-bindings ((mapcar (lambda (x) (walk (cadr x) env (cons (cadr x) call-stack)) (cons (car  x) (make-instance 'binding))) (cadr expr)) env call-stack)
    (dolist (form (cddr expr))
      (walk form env (cons form call-stack)))))
#+end_src

   | implementation        | time (ms / 100k calls) | overhead |
   |-----------------------+------------------------+----------|
   | cons-gf/no-cache      |                   9000 |   +2700% |
   | cons-gf               |                   1500 |    +370% |
   | cons-gf/one-arg-cache |                    740 |    +130% |
   | gf/methods            |                    360 |     +14% |
   | function              |                    317 |          |

   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
   \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)

#+begin_src lisp
(progn (gc :full t) (time (dotimes (i 10000) (%fact 20))))
#+end_src

   | implementation          | time (ms/10k calls) | overhead |
   |-------------------------+---------------------+----------|
   | signum-gf/no-cache      |                2400 |  +41000% |
   | signum-gf               |                 230 |   +3800% |
   | signum-gf/one-arg-cache |                  75 |   +1100% |
   | gf/fixnum               |                  12 |    +100% |
   | function                |                 6.0 |          |

   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= slot to represent the information in
   the accept header (generated by =parse-accept-string=), 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)
  ((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 '<))))))
#+end_src

#+begin_src
(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)))
)
#+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; the filter would generate
#+begin_src lisp
(ensure-class nil :direct-superclasses '(text/html image/webp ...))
#+end_src
   and dispatch the operates using those anonymous classes.

   While this is possible to do, it is awkward to express content-type
   negotiation in this way, as it means that the dispatcher must know
   about the universe of mime-types that clients might declare that
   they accept, rather than merely the set of mime-types that a
   particular generic function is capable of serving; handling
   wildcards in accept strings is particularly awkward in the
   filtering paradigm.

   Note that in this example, the method on =specializer<= involves a
   nontrivial ordering of methods based on the =q= values specified in
   the accept header (whereas in sections XX.1 and XX.2 only a single
   extended specializer could be applicable to any given argument).

   Also note that the accept specializer protocol is straightforwardly
   extensible to other suitable objects; for example, one simple
   debugging aid is to define that an =accept-specializer= should be
   applicable to =string= objects.  This can be done in a modular
   fashion (see source example NN), and generalizes to dealing with
   multiple web server libraries, so that content-negotiation methods
   are applicable to each web server's request objects.

#+begin_src lisp
(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 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
   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, obv
  - [ ] 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
  - protocol for straightforward definition of custom dispatch
    + interoperates seamlessly with rest of CLOS: method combination,
      etc.
    + tolerably efficient: two extra standard gf invokations and one
      hash table lookup per call on the fast path (but more to be
      done)
    + expressive: handles foms of dispatch not handled elsewhere; all
      the usual niceties of redefinition, modularity, introspection
** Future Work
   - compute-cache-handling-functions (and general speed issues)
   - automatic pattern-specializer generalizer computation
   - prototype-oriented progamming a la Slate.
** Acknowledgments
   We thank Lee Salzman, Pascal Costanza, Mikel Evins for their
   helpful discussions