\\affaddr{Vilhonkatu 5 A}\\\\
\\affaddr{FI-00100 Helsinki}\\\\
\\email{david@lichteblau.com}
+}
+\\maketitle")
#+end_src
#+begin_abstract
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.
- Example of something not doable: handling "message not understood"
- message from message passing paradigm.
- Nevertheless, the MOP is flexible,
- and is used for a number of things, including: documentation
- generation (where introspective functionality in the MOP is used to
- extract information from a running system); object-relational
- mapping and other approaches to object persistence; alternative
- backing stores for slots (hash-tables or symbols); and programmatic
- construction of metaobjects, for example for IDL compilers and model
- transformations.
+ acting on objects with slots; it is not possible, for example, to
+ transparently implement support for “message not understood” as in
+ the message-passing paradigm, because the analogue of messages
+ (generic functions) need to be defined before they are used.
+
+ Nevertheless, the MOP is flexible, and is used for a number of
+ things, including: documentation generation (where introspection in
+ the MOP is used to extract information from a running system);
+ object-relational mapping and other approaches to object
+ persistence; alternative backing stores for slots (hash-tables or
+ symbols); and programmatic construction of metaobjects, for example
+ for IDL compilers and model transformations.
[ XXX: A picture on MOP flexibility here would be good; I have in my mind
one where an object system is a point and the MOP opens up a blob
there are no restrictions on the metaprogrammer constructing
additional subclasses. Previous work \cite{Newton.Rhodes:2008} 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.
+ using extended specializers, but there 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 new subclasses of =specializer=. In particular, it
implemented using our protocol, which we describe in section
[[#Protocol]]. 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.
+ run; complete implementations of each of these cases, along with the
+ integration of this protocol into the SBCL implementation
+ \cite{Rhodes:2008} of Common Lisp, 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
The programmer code using these specializers is unchanged from
\cite{Newton.Rhodes:2008}; the benefits of the protocol described
- here are centered on performance and generality:
-
- alternative suggestions: modularity/improved code reuse/separation
- of concerns since e.g. arbitrary method combinations can be used
-
- 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. We discuss this in more detail in
- section [[#Memoization]]; we present the metaprogrammer code below.
+ here are: that the separation of concerns is complete – method
+ selection is independent of method combination – and that the
+ protocol allows for efficient implementation where possible, even
+ when method selection is customized. 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. We discuss the efficiency aspects of the protocol in
+ more detail in section [[#Memoization]]; we present the metaprogrammer
+ code to implement the =cons-specializer= below.
#+begin_src lisp
(defclass cons-specializer (specializer)
(and (consp o) (eql (car o) (%car s))))
#+end_src
-The code above shows a minimal use of our protocol. We have
-elided some support code for parsing and unparsing specializers, and
-for handling introspective functions such as finding generic functions
-for a given specializer. We have also elided methods on the protocol
-function =specializer<=
-
-mention =same-specializer-p=? especially when "only one
-=cons-specializer=" touches on specializer equality.
-
-; for =cons-specializers= here, specializer
-ordering is trivial, as only one =cons-specializer= can ever be
-applicable to any given argument. See section [[#Accept]] for a case
-where specializer ordering is non-trivial.
+The code above shows a minimal use of our protocol. We have elided
+some support code for parsing and unparsing specializers, and for
+handling introspective functions such as finding generic functions for
+a given specializer. We have also elided methods on the protocol
+functions =specializer<= and =same-specializer-p=; for
+=cons-specializer= objects, specializer ordering is trivial, as only
+one =cons-specializer= (up to equality) can ever be applicable to any
+given argument. See section [[#Accept]] for a case where specializer
+ordering is non-trivial.
As in \cite{Newton.Rhodes:2008}, the programmer can use these
specializers to implement a modular code walker, where they define one
#+begin_src
(defgeneric walk (form env stack)
(:generic-function-class cons-generic-function))
-(defmethod walk ((expr (cons lambda)) env call-stack)
+(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)
+ ((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)
+(defmethod walk
+ ((expr (cons let)) env call-stack)
(flet ((let-binding (x)
- (walk (cadr x) env (cons (cadr x) call-stack))
- (cons (car x) (make-instance 'binding))))
+ (walk (cadr x) env
+ (cons (cadr x) call-stack))
+ (cons (car x)
+ (make-instance 'binding))))
(with-checked-bindings
- ((mapcar #'let-binding (cadr expr)) env call-stack)
+ ((mapcar #'let-binding (cadr expr))
+ env call-stack)
(dolist (form (cddr expr))
(walk form env (cons form call-stack))))))
#+end_src
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=
- (which we wrap in a distinct object);
-
- the previous sentence is rather long and hard to understand
-
- 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 [[#Accept]] an example
- of a case where filtered dispatch is incapable of straightforwardly
- expressing the dispatch, but first we present our implementation of
- the motivating case from \cite{Costanza.etal:2008}.
+ =cons-specializer= and =cons-generalizer= to be distinct classes.
+ In standard generic function dispatch, the =class= functions both
+ as the specializer for methods and as the generalizer for generic
+ function arguments; we can think of the dispatch implemented by
+ =cons-specializer= objects as providing for subclasses of the
+ =cons= class distinguished by the =car= of the =cons=. This
+ analogy 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 [[#Accept]] an example of a case where filtered
+ dispatch is incapable of straightforwardly expressing the dispatch,
+ but first we present our implementation of the motivating case from
+ \cite{Costanza.etal:2008}.
** SIGNUM specializers
:PROPERTIES:
:CUSTOM_ID: Signum
of the specializer implementation very similar to the =cons=
specializers in the previous section.
- The metaprogrammer may choose to?
- 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
+ The metaprogrammer has chosen in the example below 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/
((%signum :reader %signum :initarg :signum)))
(defclass signum-generalizer (generalizer)
((%signum :reader %signum :initarg :signum)))
-;; Not sure whether I am overlooking something but shouldn't this work:
(defmethod generalizer-of-using-class
((gf signum-generic-function) (arg real))
- (make-instance 'signum-generalizer
- :signum (signum arg)))
+ (make-instance 'signum-generalizer
+ :signum (signum arg)))
(defmethod generalizer-equal-hash-key
((gf signum-generic-function)
(g signum-generalizer))
((gf signum-generic-function)
(s signum-specializer)
(g signum-generalizer))
- ;; Would EQL work here? I'm thinking there might be an invariant of the form
- ;; (specializer-accepts-p gf o)
- ;; <=>
- ;; (specializer-accepts-generalizer-p gf s (generalizer-of-using-class gf o))
- ;; Or if that wrong, maybe we should explain why.
- (if (= (%signum s) (%signum g)) ; or EQL?
+ (if (= (%signum s) (%signum g))
(values t t)
(values nil t)))
(defmethod specializer-accepts-generalizer-p
((gf signum-generic-function)
- (s sb-mop:specializer)
+ (s specializer)
(g signum-generalizer))
(specializer-accepts-generalizer-p
gf s (class-of (%signum g))))
it has available to satisfy this request, and sends the best
matching resource in its response.
- For example, a graphical web browser might by default send an
- =Accept= header such as
- =text/html,application/xml;q=0.9,*/*;q=0.8=. This should be
- interpreted as meaning that if for a given resource the server can
- provide content of type =text/html= (i.e. HTML), then it should do
- so. Otherwise, if it can provide =application/xml= content
- (i.e. XML of any schema), then that should be provided; failing
- that, any other content type is acceptable.
+ For example, a graphical web browser might send an =Accept= header
+ of =text/html,application/xml;q=0.9,*/*;q=0.8= for a request of a
+ resource typed in to the URL bar. This should be interpreted as
+ meaning that: if the server can provide content of type =text/html=
+ (i.e. HTML) for that resource, then it should do so. Otherwise, if
+ it can provide =application/xml= content (i.e. XML of any schema),
+ then that should be provided; failing that, any other content type
+ is acceptable.
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
(values (q (media-type s) (tree g)) t))
(defmethod specializer-accepts-generalizer-p
((gf accept-generic-function)
- (s specializer) ; other listing has sb-mop:specializer
+ (s specializer)
(g accept-generalizer))
(specializer-accepts-generalizer-p
gf s (next g)))
#+end_src
The metaprogrammer can then add support for objects representing
- client requesting, such as instances of the =request= class in the
+ client requests, such as instances of the =request= class in the
Hunchentoot web server, by translating these into
=accept-generalizer= instances. The code below implements this, by
defining the computation of a =generalizer= object for a given
(and q (> q 0))))
#+end_src
- In the =next= slot in the previous listing and this listing is not
- discussed, I think.
-
This dispatch cannot be implemented using filtered dispatch, except
by generating anonymous classes with all the right mime-types as
direct superclasses in dispatch order; the filter would generate
(q (q (media-type s) tree)))
(and q (> q 0))))
#+end_src
+
+ The =next= slot in the =accept-generalizer= is used to deal with
+ the case of methods specialized on the classes of objects as well
+ as on the acceptable media types; there is a method on
+ =specializer-accepts-generalizer-p= for specializers that are not
+ of type =accept-specializer= which calls the generic function again
+ with the next generalizer, so that methods specialized on the
+ classes =tbnl:request= and =string= are treated as applicable to
+ corresponding objects, though less specific than methods with
+ =accept-specializer= specializations.
+
** COMMENT 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
applicability of a particular specializer against a given argument
using =specializer-accepts-p=, a new protocol function with
default implementations on =class= and =eql-specializer= to
- implement the expected behaviour. In order to order the methods,
- as required by the protocol, we define a pairwise comparison
- operator =specializer<= which defines an ordering between
- specializers for a given generalizer argument (remembering that
- even in standard CLOS the ordering between =class= specializers
- can change depending on the actual class of the argument).
+ implement the expected behaviour. To order the methods, as
+ required by the protocol, we define a pairwise comparison operator
+ =specializer<= which defines an ordering between specializers for
+ a given generalizer argument (remembering that even in standard
+ CLOS the ordering between =class= specializers can change
+ depending on the actual class of the argument).
The new =compute-applicable-methods-using-generalizers= is the
analogue of the MOP's =compute-applicable-methods-using-classes=.
answer fits in SBCL's 63-bit fixnums – in an attempt to measure the
worst case for generic dispatch, where the work done within the
methods is as small as possible without being meaningless, and in
- particular does not cause allocation or garbage collection to
+ particular does not cause heap allocation or garbage collection to
obscure the picture.
#+begin_src lisp :exports none
context of partial evaluation; for example, \cite{Ruf:1993}
considers generalization in online partial evaluation, where sets of
possible values are represented by a type system construct
- representing an upper bound. The relationship between generalizer
- metaobjects and approximation in type systems could be further
- explored.
+ representing an upper bound. Exploring the relationship between
+ generalizer metaobjects and approximation in type systems might
+ yield strategies for automatically computing suitable generalizers
+ and cache functions for a variety of forms of generalized dispatch.
* Conclusions
:PROPERTIES:
:CUSTOM_ID: Conclusions