#+LaTeX_CLASS: acm_proc_article-sp
#+LaTeX_HEADER: \DeclareTextFontCommand{\texttt}{\ttfamily\hyphenchar\font=45\relax}
+#+LaTeX_HEADER: \renewcommand{\baselinestretch}{0.99}
#+begin_src elisp :exports none
;;; use C-x C-e on this if org refuses to export
("\\subsubsection{%s}" . "\\subsubsection*{%s}")
("\\paragraph{%s}" . "\\paragraph*{%s}")
("\\subparagraph{%s}" . "\\subparagraph*{%s}")))
+(add-to-list 'org-latex-classes
+ '("sig-alternate" "\\documentclass{sig-alternate}"
+ ("\\section{%s}" . "\\section*{%s}")
+ ("\\subsection{%s}" . "\\subsection*{%s}")
+ ("\\subsubsection{%s}" . "\\subsubsection*{%s}")
+ ("\\paragraph{%s}" . "\\paragraph*{%s}")
+ ("\\subparagraph{%s}" . "\\subparagraph*{%s}")))
+(set (make-local-variable 'org-latex-pdf-process)
+ '("latexmk -f -pdf -bibtex %f"))
(set (make-local-variable 'org-latex-title-command)
"\\numberofauthors{3}
\\author{
#+end_abstract
#+begin_LaTeX
+\begin{flushleft}
+Report-No.:~\url{http://eprints.gold.ac.uk/id/eprint/9924}
+\end{flushleft}
\category{D.1}{Software}{Programming Techniques}[Object-oriented Programming]
\category{D.3.3}{Programming Languages}{Language Constructs and Features}
\terms{Languages, Design}
final standard; the third chapter, 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 largely from-scratch
- reimplementations of CLOS (in CLISP[fn:1] and CCL[fn:2], at least)
- incorporating substantial fractions of the Metaobject Protocol as
- described.
+ Nevertheless, the CLOS MOP continued to be developed, and the
+ version documented in \cite{AMOP} has proven to be a reasonably
+ robust design. 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 largely
+ from-scratch reimplementations of CLOS (in CLISP[fn:1] and
+ CCL[fn:2], at least) incorporating substantial fractions of the
+ Metaobject Protocol as described.
+
+ #+CAPTION: MOP Design Space
+ #+LABEL: fig:mopdesign
+ #+ATTR_LATEX: width=\linewidth float
+ [[file:figures/mop-design-space.pdf]]
Although it has stood the test of time, the CLOS MOP is neither
without issues (e.g. semantic problems with =make-method-lambda=
implement all conceivable variations of object-oriented behaviour.
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; 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.
+ arbitrarily in all directions (conceptually, if a given object
+ system is a point in design space, then a MOP for that object system
+ allows exploration of a region of design space around that point;
+ see figure \ref{fig:mopdesign}). In the case of the CLOS MOP, there is
+ still an expectation that functionality is implemented with methods
+ on generic functions, 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 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.
-
- [ 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
- around that point, and I'm sure I've seen it somewhere but I can't
- remember where. Alternatively, there's Kiczales et al "MOPs: why we
- want them and what else they can do", fig. 2 ]
- [AMOP, page 5] paints that picture, but again, only using words :)
+ things, including: documentation generation (where introspection in
+ the MOP is used to extract information from a running system[fn:3]);
+ object-relational mapping[fn:4] and other approaches to object
+ persistence \cite{Paepke:1988}; alternative backing stores for slots
+ (hash-tables \cite{Kiczales.etal:1993} or symbols
+ \cite{Costanza.Hirschfeld:2005}); and programmatic construction of
+ metaobjects, for example for interoperability with other language
+ runtimes' object systems.
One area of functionality where there is scope for customization by
the metaprogrammer is in the mechanics and semantics of method
=compute-applicable-methods=,
=compute-applicable-methods-using-classes=), for example, in
practice implementation support for this was weak until relatively
- recently[fn:3].
+ recently[fn:5].
Another potential mechanism for customizing dispatch is implicit in
the class structure defined by AMOP: standard specializer objects
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
#+CAPTION: Dispatch Comparison
#+LABEL: fig:dispatch
- #+ATTR_LATEX: width=0.9\linewidth float
- [[file:figures/dispatch-comparison.pdf]]
+ #+ATTR_LATEX: width=\linewidth float
+ [[file:figures/dispatch-relationships.pdf]]
The remaining sections in this paper can be read in any order. We
give some motivating examples in section [[#Examples]], including
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 the authors'
+ repository[fn:6].
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”).
+ “metametaprogrammer”, or more likely “we”).
** CONS specializers
:PROPERTIES:
:CUSTOM_ID: Cons
\cite{Newton.Rhodes:2008}; the benefits of the protocol described
here are: that the separation of concerns is complete – method
selection is independent of method combination – and that the
- protocol allows where possible for efficient implementation even
+ 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
#+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
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
+ Here, dispatch will be performed 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
+ will be applicable to any given argument, which makes the structure
of the specializer implementation very similar to the =cons=
specializers in the previous section.
(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.
+ The programmer does 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.
** Accept HTTP header specializers
:PROPERTIES:
:CUSTOM_ID: Accept
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
#+end_src
The metaprogrammer can then add support for objects representing
- client requesting, such as instances of the =request= class in the
- Hunchentoot web server, by translating these into
+ client requests, such as instances of the =request= class in the
+ Hunchentoot[fn:7] 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
request, and specifying how to compute whether the specializer
(arg tbnl:request))
(make-instance 'accept-generalizer
:header (tbnl:header-in :accept arg)
- :next (class-of arg)))
+ :next (call-next-method)))
(defmethod specializer-accepts-p
((s accept-specializer)
(o tbnl:request))
(ensure-class nil :direct-superclasses
'(text/html image/webp ...))
#+end_src
- and dispatch operates using those anonymous classes. While
+ and dispatch would operate 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
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 [[#Cons]] and [[#Signum]] only a
+ non-trivial ordering of methods based on the =q= values specified
+ in the accept header (whereas in sections [[#Cons]] and [[#Signum]] only a
single extended specializer could be applicable to any given
argument).
(s string))
(make-instance 'accept-generalizer
:header s
- :next (class-of s)))
+ :next (call-next-method)))
(defmethod specializer-accepts-p
((s accept-specializer) (o string))
(let* ((tree (parse-accept-string o))
(and q (> q 0))))
#+end_src
- The =next= slot in the =accept-generalizer= is present to deal with
+ 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
:END:
In section [[#Examples]], we have seen a number of code fragments as
- partial implementations of particular non-standard method dispatch,
- using =generalizer= metaobjects to mediate between the methods of
- the generic function and the actual arguments passed to it. In
- section [[#Generalizer metaobjects]], we go into more detail regarding
- these =generalizer= metaobjects, describing the generic function
- invocation protocol in full, and showing how this protocol allows a
- similar form of effective method cacheing as the standard one does.
- In section [[#Generalizer performance]], we show the results of some
- simple performance measurements on our implementation of this
- protocol in the SBCL implementation \cite{Rhodes:2008} of Common
- Lisp to highlight the improvement that this protocol can bring over
- a naïve implementation of generalized dispatch, as well as
- to make the potential for further improvement clear.
+ partial implementations of particular non-standard method dispatch
+ strategies, using =generalizer= metaobjects to mediate between the
+ methods of the generic function and the actual arguments passed to
+ it. In section [[#Generalizer metaobjects]], we go into more detail
+ regarding these =generalizer= metaobjects, describing the generic
+ function invocation protocol in full, and showing how this protocol
+ allows a similar form of effective method cacheing as the standard
+ one does. In section [[#Generalizer performance]], we show the results
+ of some simple performance measurements on our implementation of
+ this protocol in the SBCL implementation \cite{Rhodes:2008} of
+ Common Lisp to highlight the improvement that this protocol can
+ bring over a naïve implementation of generalized dispatch, as well
+ as to make the potential for further improvement clear.
** Generalizer metaobjects
:PROPERTIES:
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=.
- Instead of calling it with the =class-of= each argument, we compute
- the generalizers of each argument using the new function
+ Instead of calling it with the =class-of= each argument, we
+ compute the generalizers of each argument using the new function
=generalizer-of-using-class= (where the =-using-class= refers to
the class of the generic function rather than the class of the
- object), and call it with the list of generalizers. As with the
- standard function, a secondary return value indicates whether the
- result of the function is definitive for that list of generalizers.
+ object), and call =compute-applicable-methods-using-generalizers=
+ with the generic function and list of generalizers. As with
+ =compute-applicable-methods-using-classes=, a secondary return
+ value indicates whether the result of the function is definitive
+ for that list of generalizers.
Thus, in generic function invocation, we first compute the
generalizers of the arguments; we compute the ordered set of
applicable methods, either from the generalizers or (if that is
not definitive) from the arguments themselves; then the normal
effective method computation and call can occur. Unfortunately,
- the nature of an effective method object is not specified, so we
+ the nature of an effective method function is not specified, so we
have to reach into implementation internals a little in order to
call it, but otherwise the remainder of the generic function
invocation protocol is unchanged from the standard one. In
One issue is what to use as the key for that cache. We cannot use
the generalizers themselves, as two generalizers that should be
considered equal for cache lookup will not compare as =equal= –
- and indeed even the standard generalizer, the =class=, cannot be
- used as we must be able to invalidate cache entries upon class
- redefinition. The issue of =class= generalizers we can solve as
- in \cite{Kiczales.Rodriguez:1990} by using the =wrapper= of a
- class, which is distinct for each distinct (re)definition of a
- class; for arbitrary generalizers, however, there is /a priori/ no
- good way of computing a suitable hash key automatically, so we
+ and indeed even the standard generalizer, the =class=, cannot
+ easily be used as we must be able to invalidate cache entries upon
+ class redefinition. The issue of =class= generalizers we can
+ solve as in \cite{Kiczales.Rodriguez:1990} by using the =wrapper=
+ of a class, which is distinct for each distinct (re)definition of
+ a class; for arbitrary generalizers, however, there is /a priori/
+ no good way of computing a suitable hash key automatically, so we
allow the metaprogrammer to specify one by defining a method on
=generalizer-equal-hash-key=, and combining the hash keys for all
required arguments in a list to use as a key in an =equal=
hash-table.
- [XXX could we actually compute a suitable hash key using the
+#+begin_comment
+ [could we actually compute a suitable hash key using the
generalizer's class name and initargs?]
+#+end_comment
*** COMMENT
- [X] =generalizer-of-using-class= (NB class of gf not class of object)
implementations in the context of methods with regular specializers
(in an implementation similar to that in
\cite{Kiczales.Rodriguez:1990}), and with implementation in
- straightforward functions.
+ straightforward functions. We performed our benchmarks on a
+ quad-core X-series ThinkPad with 8GB of RAM running Debian
+ GNU/Linux, and took the mean of the 10 central samples of 20 runs,
+ with the number of iterations per run chosen so as to take
+ substantially over the clock resolution for the fastest case.
+ Despite these precautions, we advise against reading too much into
+ these numbers, which are best used as an order-of-magnitude
+ estimate.
In the case of the =cons-specializer=, we benchmark the walker
acting on a small but non-trivial form. The implementation
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
one; in principle implementors of other method combinations could
cater for filtered dispatch, but they would have to explicitly
modify their method combinations. The Clojure programming language
- supports multimethods[fn:5] with a variant of filtered dispatch as
- well as hierachical and identity-based method selectors.
+ supports multimethods[fn:8] with a variant of filtered dispatch as
+ well as hierarchical and identity-based method selectors.
In context-oriented programming
\cite{Hirschfeld.etal:2008,Vallejos.etal:2010}, context dispatch
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
amortized (though there remains a substantial overhead compared with
standard generic-function or regular function calls). We discuss
how the efficiency could be improved below.
-** Future Work
+** Future work
:PROPERTIES:
:CUSTOM_ID: Future Work
:END:
widespread demand (in as much as any language extension can be said
to be in “demand”). In particular, we have preliminary work
towards supporting efficient dispatch over pattern specializers
- such as implemented in the \textsf{Optima} library[fn:4], and over
+ such as implemented in the \textsf{Optima} library[fn:9], and over
a prototype object system similar to that in Slate
\cite{Salzman.Aldrich:2005}. Our current source code for the work
described in this paper can be seen in the git source code
with confidence that the semantics will not change in a
backwards-incompatible fashion.
** Acknowledgments
- We thank Lee Salzman, Pascal Costanza and Mikel Evins for helpful
- and informative discussions, and all the respondents to one
+ We thank the anonymous reviewers for their helpful suggestions and
+ comments on the submitted version of this paper. We also thank Lee
+ Salzman, Pascal Costanza and Mikel Evins for helpful and
+ informative discussions, and all the respondents to the first
author's request for imaginative uses for generalized specializers.
\bibliographystyle{plain}
[fn:2] Clozure Common Lisp, at http://ccl.clozure.com/
-[fn:3] the \textsf{Closer to MOP} project, at
+[fn:3] as in many of the systems surveyed at
+https://sites.google.com/site/sabraonthehill/lisp-document-generation-apps
+
+[fn:4] e.g. CLSQL, at http://clsql.b9.com/
+
+[fn:5] the \textsf{Closer to MOP} project, at
http://common-lisp.net/project/closer/, attempts to harmonize the
different implementations of the metaobject protocol in Common
Lisp.
-[fn:4] https://github.com/m2ym/optima
+[fn:6] the tag =els2014-submission= in
+http://christophe.rhodes.io/git/specializable.git corresponds to the
+code repository at the point of submitting this paper.
+
+[fn:7] Hunchentoot is a web server written in Common Lisp, allowing
+the user to write handler functions to compute responses to requests;
+http://weitz.de/hunchentoot/
+
+[fn:8] http://clojure.org/multimethods
+
+[fn:9] https://github.com/m2ym/optima
+
-[fn:5] http://clojure.org/multimethods
projects / paper-els-specializers.git / blobdiff