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
+ 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
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
(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.
+ 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
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
- NB this example can be done using filtered dispatch, with a filter
- calling =car= on cons arguments.
+ 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=.
- 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.
+ 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)))
(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 |#
+#| 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
- NB this example can definitely be done using filtered dispatch.
+ 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.
- 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
+ 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)))
(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 1))) (* n (fact (1- n))))
(defmethod fact ((n (signum 0))) 1)
-(defmethod fact ((n (signum -1)))
- (error "factorial of negative number: ~D" n))
+(defmethod fact ((n (signum 1))) (* n (fact (1- 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
+ 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
-(ensure-class nil :direct-superclasses '(text/html image/webp ...))
+(progn (gc :full t) (time (dotimes (i 10000) (%fact 20))))
#+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.
+
+ | 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)))
(next :initarg :next :reader next)))
(defmethod generalizer-equal-hash-key
((gf accept-generic-function) (g accept-generalizer))
- `(accept-generalizer ,(header g)))
+ `(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))
((= q1 q2) '=)
((< q1 q2) '>)
(t '<))))))
+#+end_src
-;; here are the only methods that actually know about TBNL
+#+begin_src
(defmethod generalizer-of-using-class ((gf accept-generic-function) (arg tbnl:request))
(make-instance 'accept-generalizer
:header (tbnl:header-in :accept arg)
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.
-;; we can define methods on STRING too, for debugging/simulation purposes
+ 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
(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? It would be really nice to put a
- marker in the sand.
+ 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)
- [ ] =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
- - [ ] ContextL / context-oriented programming
+ - [ ] 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
+ - [ ] 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
projects / paper-els-specializers.git / blobdiff