From 465e7dad28398cbdaf3019d8e3350fb406be671a Mon Sep 17 00:00:00 2001 From: Christophe Rhodes Date: Sun, 2 Mar 2014 22:41:13 +0000 Subject: [PATCH] final first draft hooray, text text text. --- els-specializers.org | 262 +++++++++++++++++++++++++++---------------- specializers.bib | 58 ++++++++++ 2 files changed, 226 insertions(+), 94 deletions(-) diff --git a/els-specializers.org b/els-specializers.org index 5b5731c..6a7652b 100644 --- a/els-specializers.org +++ b/els-specializers.org @@ -6,6 +6,7 @@ #+LaTeX_HEADER: \DeclareTextFontCommand{\texttt}{\ttfamily\hyphenchar\font=45\relax} #+begin_src elisp :exports none +;;; use C-x C-e on this if org refuses to export (add-to-list 'org-latex-classes '("acm_proc_article-sp" "\\documentclass{acm_proc_article-sp}" ("\\section{%s}" . "\\section*{%s}") @@ -16,17 +17,20 @@ #+end_src #+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. +This paper introduces a new metaobject, the generalizer, which +complements the existing specializer metaobject. 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. We present our +modifications to the generic function invocation protocol from the +/Art of the Metaobject Protocol/; in combination with previous work, +this produces a fully-functional extension of the existing mechanism +for method selection and combination, including support for method +combination completely independent from method selection. We discuss +our implementation, within the SBCL implementation of Common Lisp, and +in that context compare the performance of the new protocol with the +standard one, demonstrating that the new protocol can be tolerably +efficient. #+end_abstract * Introduction @@ -45,8 +49,8 @@ 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 -- Lisp500? CCL?) + 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. @@ -83,7 +87,7 @@ =compute-applicable-methods=, =compute-applicable-methods-using-classes=), for example, in practice implementation support for this was weak until relatively - recently[fn:1]. + recently[fn:3]. Another potential mechanism for customizing dispatch is implicit in the class structure defined by AMOP: standard specializer objects @@ -480,7 +484,7 @@ variables. (q (q (media-type s) tree))) (and q (> q 0)))) #+end_src -** Pattern / xpattern / regex / optima +** 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 these is going to take us into =make-method-lambda= territory. @@ -499,10 +503,11 @@ variables. 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 to highlight the improvement that - this protocol can bring over a naïve implementation of generalized - dispatch, as well as highlighting the potential for further - improvement. + 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: @@ -598,6 +603,7 @@ variables. [XXX could we actually compute a suitable hash key using the generalizer's class name and initargs?] +*** COMMENT - [X] =generalizer-of-using-class= (NB class of gf not class of object) - [X] =compute-applicable-methods-using-generalizers= - [X] =generalizer-equal-hash-key= @@ -614,8 +620,10 @@ variables. efficiency that the memoization protocol described in section [[#Memoization]] achieves, by comparing it both to the same protocol with no memoization, as well as with equivalent dispatch - implementations in the context of methods with regular - specializers, and with implementation in straightforward functions. + 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. In the case of the =cons-specializer=, we benchmark the walker acting on a small but non-trivial form. The implementation @@ -633,8 +641,6 @@ variables. construction of a list of hash keys and simply use the key from the single active generalizer directly. - Refer to \cite{Kiczales.Rodriguez:1990} - | implementation | time (µs/call) | overhead | |-----------------------+----------------+----------| | function | 3.17 | | @@ -691,81 +697,131 @@ variables. calls for the generic cache; we discuss possible approaches in section [[#Conclusions]]. ** 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 - - ))) - `(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 + The protocol described in this paper is only part of a complete + protocol for =specializer= and =generalizer= metaobjects. Our + development of this protocol is as yet incomplete; the work + described here augments that in \cite{Newton.Rhodes:2008}, but is + yet relatively untested – and additionally our recent experience of + working with that earlier protocol suggests that there might be + useful additions to the handling of =specializer= metaobjects, + independent of the =generalizer= idea presented here. + +*** COMMENT ideas + 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 + + ))) + `(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 :PROPERTIES: :CUSTOM_ID: Related Work :END: - - [ ] Newton/Rhodes, \cite{Newton.Rhodes:2008} - - [ ] 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. Filtered dispatch works by having a custom - discriminating function which wraps the usual one, and augments - the set of applicable methods computed with applicable methods - from other (hidden) generic functions (one per filter group). It - then also has a custom method combination to handle combining - these applicable methods. \cite{Costanza.etal:2008} - - [ ] 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. \cite{Hirschfeld.etal:2008,Vallejos.etal:2010} - - [ ] 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. \cite{Salzman.Aldrich:2005} - - [ ] Sheeple - - [ ] Multiple dispatch in Clojure - http://clojure.org/multimethods -- seems to allow hierarchy-based, - eql and the equivalent of filtered dispatch + + The work presented here builds on specializer-oriented programming + described in \cite{Newton.Rhodes:2008}. Approximately + contemporaneously, filtered dispatch \cite{Costanza.etal:2008} was + introduced to address some of the same use cases: filtered dispatch + works by having a custom discriminating function which wraps the + usual one, where the wrapping function augments the set of + applicable methods with applicable methods from other (hidden) + generic functions, one per filter group; this step is not memoized, + and using =eql= methods to capture behaviours of equivalence classes + means that it is hard to see how it could be. The methods are then + combined using a custom method combination to mimic the standard + 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. + + In context-oriented programming + \cite{Hirschfeld.etal:2008,Vallejos.etal:2010}, context dispatch + occurs by maintaining the context state as an anonymous class with + the superclasses representing all the currently active layers; this + is then passed as a hidden argument to context-aware functions. The + set of layers is known and under programmer control, as layers must + be defined beforehand. + + In some sense, all dispatch schemes are specializations of predicate + dispatch \cite{Ernst.etal:1998}. The main problem with predicate + dispatch is its expressiveness: with arbitrary predicates able to + control dispatch, it is essentially impossible to perform any + substantial precomputation, or even to automatically determine an + ordering of methods given a set of arguments. Even Clojure's + restricted dispatch scheme provides an explicit operator for stating + a preference order among methods, where here we provide an operator + to order specializers; in filtered dispatch the programmer + implicitly gives the system an order of precedence, through the + lexical ordering of filter specification in a filtered function + definition. + + The Slate programming environment combines prototype-oriented + programming with multiple dispatch \cite{Salzman.Aldrich:2005}; in + that context, the analogue of an argument's class (in Common Lisp) + as a representation of the equivalence class of objects with the + same behaviour is the tuple of roles and delegations: objects with + the same roles and delegations tuple behave the same, much as + objects with the same generalizer have the same behaviour in the + protocol described in this paper. + + The idea of generalization is of course not new, and arises in other + contexts. Perhaps of particular interest is generalization in the + 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. * Conclusions :PROPERTIES: :CUSTOM_ID: Conclusions :END: - - 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 forms of dispatch not handled elsewhere; all - the usual niceties of redefinition, modularity, introspection + In this paper, we have presented a new generalizer metaobject + protocol allowing the metaprogrammer to implement in a + straightforward manner metaobjects to implement custom method + selection, rather than the standard method selection as standardized + in Common Lisp. This protocol seamlessly interoperates with the + rest of CLOS and Common Lisp in general; the programmer (the user of + the custom specializer metaobjects) may without constraints use + arbitrary method combination, intercede in effective method + combination, or write custom method function implementations. The + protocol is expressive, in that it handles forms of dispatch not + possible in more restricted dispatch systems, while not suffering + from the indeterminism present in predicate dispatch through the use + of explicit ordering predicates. + + The protocol is also reasonably efficient; the metaprogrammer can + indicate that a particular effective method computation can be + memoized, and under those circumstances much of the overhead is + 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 :PROPERTIES: :CUSTOM_ID: Future Work @@ -805,23 +861,41 @@ variables. 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:2], and over + such as implemented in the \textsf{Optima} library[fn:4], 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 repository at [[http://christophe.rhodes.io/git/specializable.git]], which will be updated with future developments. + + Finally, after further experimentation (and, ideally, non-trivial + use in production) if this protocol stands up to use as we hope, we + aim to produce a standards-quality document so that other + implementors of Common Lisp can, if they choose, independently + reimplement the protocol, and so that users can use the protocol + 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 - author's call for imaginative uses for generalized specializers. + author's request for imaginative uses for generalized specializers. \bibliographystyle{plain} \bibliography{crhodes,specializers} * Footnotes -[fn:1] the \textsf{Closer to MOP} project attempts to harmonize the - different implementations of the metaobject protocol in Common Lisp. +[fn:1] GNU CLISP, at http://www.clisp.org/ + +[fn:2] Clozure Common Lisp, at http://ccl.clozure.com/ + +[fn:3] 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:5] http://clojure.org/multimethods + -[fn:2] https://github.com/m2ym/optima diff --git a/specializers.bib b/specializers.bib index e641791..9ca12f0 100644 --- a/specializers.bib +++ b/specializers.bib @@ -194,3 +194,61 @@ OPTnote = {}, OPTannote = {} } + +@PhdThesis{Ruf:1993, + author = {Erik Ruf}, + title = "{Topics in Online Partial Evaluation}", + school = {Stanford}, + year = {1993}, + OPTkey = {}, + OPTtype = {}, + address = {California, USA}, + OPTmonth = {}, + OPTnote = {}, + OPTannote = {} +} + +@InCollection{Chambers:1993, + author = {Craig Chambers}, + title = "{Predicate Classes}", + booktitle = {ECOOP 1993 -- Object-Oriented Programming}, + OPTcrossref = {}, + OPTkey = {}, + publisher = {Springer}, + year = {1993}, + editor = {Oscar Nierstrasz}, + OPTvolume = {}, + number = {707}, + series = {LNCS}, + OPTtype = {}, + OPTchapter = {}, + pages = {268--296}, + OPTedition = {}, + OPTmonth = {}, + OPTaddress = {}, + OPTnote = {}, + OPTannote = {} +} + +@InCollection{Ernst.etal:1998, + author = {Michael Ernst and Craig Kaplan and Craig Chambers}, + title = "{Predicate dispatching: A unified theory of dispatch}", + booktitle = {ECOOP 1998 -- Object-Oriented Programming}, + OPTcrossref = {}, + OPTkey = {}, + publisher = {Springer}, + year = {1998}, + editor = {Eric Jul}, + OPTvolume = {}, + number = {1445}, + series = {LNCS}, + OPTtype = {}, + OPTchapter = {}, + pages = {186--211}, + OPTedition = {}, + OPTmonth = {}, + address = {Berlin}, + OPTnote = {}, + OPTannote = {} +} + -- 2.39.5