final first draft

hooray, text text text.

diff --git a/els-specializers.org b/els-specializers.org
index 5b5731c4fda94d428d46019fc4c0de539a229f80..6a7652bdae2d4da6e62e87cb310c4ac60791dff3 100644 (file)
--- 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
 #+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}")
 (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
 #+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
 #+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
   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.
 
   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
   =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
 
   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
          (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.
    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
   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:
 
 ** 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?]
 
     [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=
     - [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
    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
 
    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.
 
    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 |          |
    | 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
    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 <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
+   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 <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
   :PROPERTIES:
   :CUSTOM_ID: Related Work
   :END:
 
 * 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:
 * 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
 ** 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
    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.
    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
 ** 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
 
 
 \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 e6417913eb8a279ae9e3183f1f22794d97453c59..9ca12f08b965909d271af758059c8d5e0ddf63f1 100644 (file)
--- a/specializers.bib
+++ b/specializers.bib
@@ -194,3 +194,61 @@
   OPTnote =      {},
   OPTannote =    {}
 }
   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 =    {}
+}
+