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
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.
-
- 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.
+ 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)))
(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
+#+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
#| 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:
+ 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)
(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 |
+ 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.
-#+begin_src lisp
-(progn (gc :full t) (time (dotimes (i 10000) (%fact 20))))
-#+end_src
-** HTTP Accept header
- implement RFC2616 content negotiation
+ 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)
- 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 ...))
+(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.
- jmoringe: the name =accept-specializer=, while sensible, may
- confusing in this context because "accept" occurs as part of the
- protocol with a different semantic.
+ | 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)
((= 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.
+
+ 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.
-;; we can define methods on STRING too, for debugging/simulation purposes
+#+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 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.
-
+ 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
think, we didn't finish the discussion regarding special
variables vs. environment vs. new protocol function
* Related Work
- - [ ] Newton/Rhodes
+ - [ ] 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
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