Hello All,
I recently happened upon the paper Prototypes with Multiple Dispatch by
Salzman[1], and I decided to try implementing my own version of the PMD
model he described in Scheme. As an extension to his model, I've added
in support for CLOS[2] style Method Combinations, such as the :after,
:around, :before, and :standard dispatch orders.
Now, as near as I can tell, there haven't been any white-papers written
on the subject of combining PMD with Method Combinations, so I thought
I'd ask you guys: Have you heard of anything like this? Even if you
haven't, are there any pitfalls or opportunities that you might be able
to point out regarding this?
Even better, what would you like to see in such a system to make it usable?
Thanks,
Ryan Kaulakis
PS: This message is cross-posted with Lambda The Ultimate
(http://lambda-the-ultimate.org/node/1667) and comp.lang.scheme, I hope
no one minds; I just thought that this was a much more active forum to
get opinions.
References:
1) http://www.springerlink.com/index/540HUJ0BNH8KTCTV.pdf
2) http://www.dreamsongs.com/NewFiles/ECOOP.pdf
rmk216 wrote:
> Hello All,
> I recently happened upon the paper Prototypes with Multiple Dispatch by
> Salzman[1], and I decided to try implementing my own version of the PMD
> model he described in Scheme. As an extension to his model, I've added
> in support for CLOS[2] style Method Combinations, such as the :after,
> :around, :before, and :standard dispatch orders.
>
> Now, as near as I can tell, there haven't been any white-papers written
> on the subject of combining PMD with Method Combinations, so I thought
> I'd ask you guys: Have you heard of anything like this?
The question is a bit unspecific - what do you mean by "like this"? I am
not aware of another prototype-based system that has method
combinations, but I could be missing something. If you don't want to see
this restricted to prototype-based systems, it may be helpful to be more
specific.
> Even if you
> haven't, are there any pitfalls or opportunities that you might be able
> to point out regarding this?
>
> Even better, what would you like to see in such a system to make it
usable?
One element in CLOS-style method combinations that makes them practical
is that they can be precomputed and/or memoized. See the CLOS
specification on method selection and method combination (aka
"determining the effective method"), and especially note that the
effective method may depend only on the classes or identities of the
arguments passed to a generic function. If, for example, the effective
method could depend on the state of the running system then a CLOS
implementation would have to determine the effective method on each
generic function invocation. However, as it is specified now, once an
effective method has been determined, it can be reused whenever the same
kinds of arguments are passed.
Another element that may be interesting to take into account account is
the concept of a "discriminating function" which is part of the CLOS
metaobject protocol. That's the function that performs the actual method
dispatch (selection + combination), but it's not a fixed function but
one that is determined whenever the set of methods defined for a generic
function is changed. Since the discriminating function is recomputed in
this manner, it can be customized based on an analysis of the methods
defined for a generic function to avoid any unnecessary overhead. For
example, if none of defined methods specialize a specific argument, it
never has to be taken into account for method dispatch, etc.
Because of this "staged" nature of the generic function invocation
protocol, the actual invocations can be as computationally cheap as
possible. For very simple generic functions (with few methods and few
specializations) this can be very close to regular function calls, and
for complex generic functions (with many methods and many
specializations), it's unlikely that the manual dispatch that you would
have to write yourself in a regular function would be any simpler and
more efficient.
I think there is a realistic chance that a prototype-based system can
gain similar benefits if designed right. You may also want to read
http://people.csail.mit.edu/jrb/Projects/partial-dispatch.htm
Pascal
--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
Thanks for getting back to me (I was starting to worry that this topic
was to esoteric even for comp.lang.lisp! ;-).
...
>
> The question is a bit unspecific - what do you mean by "like this"? I am
> not aware of another prototype-based system that has method
> combinations, but I could be missing something. If you don't want to see
> this restricted to prototype-based systems, it may be helpful to be more
> specific.
>
Yes, I was specifically asking about prototype system with both Multiple
Dispatch, and Method Combinations. I've found plenty on Prototypes with
Multiple Dispatch (Us, Slate, etc.), but very few (currently none) on
including Method Combinations as well.
>
> One element in CLOS-style method combinations that makes them practical
...
> kinds of arguments are passed.
Sadly, when using a Prototype based system, the "types" of the objects
is subject to change, as are the slots they contain. Thus there is only
opportunity for precomputed dispatch tables when the objects are not
modified in certain ways which would change the inheritance order.
>
> Another element that may be interesting to take into account account is
> the concept of a "discriminating function" which is part of the CLOS
...
> example, if none of defined methods specialize a specific argument, it
> never has to be taken into account for method dispatch, etc.
That's an interesting idea there, and I have a rather crufty version of
it myself. In my system, the generic functions are dispatched only on a
subset of their arguments (which is defined by the user during function
definition), and the rest are just carried along as baggage. However, I
would be interested in finding out more about how CLOS does it. Do you
have any references I could take a look at?
>
> Because of this "staged" nature of the generic function invocation
> protocol, the actual invocations can be as computationally cheap as
> possible. For very simple generic functions (with few methods and few
> specializations) this can be very close to regular function calls, and
> for complex generic functions (with many methods and many
> specializations), it's unlikely that the manual dispatch that you would
> have to write yourself in a regular function would be any simpler and
> more efficient.
>
> I think there is a realistic chance that a prototype-based system can
> gain similar benefits if designed right. You may also want to read
> http://people.csail.mit.edu/jrb/Projects/partial-dispatch.htm
Now, correct me if I'm wrong, but it seems to me that their idea of
"Partial Dispatch" is mostly concerned with pruning out method calls
from the dispatch order based on disjointness and concreteness. Which
seems rather redundant to me, since both cases would automatically be
excluded from the total ordered dispatch sequence if you generate the
ordering using bfs to grab the inheritance tree, and depth with lexical
ordering to sort it.
The way that I've implemented prototype objects, methods are external to
objects, and thus "abstract" objects are simply ones for which a
generic function has no dispatch orders. Thus making the "pruning" step
occur automatically while the dispatch order is being calculated, since
a parent cannot be upcast to a child during dispatch, but children can
downcast to parents.
As for disjointness, while doing a bfs on the inheritance tree, you will
only encounter members of the dispatch hierarchy. Thus, if any of the
dispatch signatures contain any objects not included in the tree, they
can be immediately discarded.
>
>
> Pascal
>
Thanks for getting back to me,
Ryan Kaulakis
PS: If anyone is interested, I can throw the source of my prototype
implementation up somewhere publicly accessible.
rmk216 wrote:
> Thanks for getting back to me (I was starting to worry that this topic
> was to esoteric even for comp.lang.lisp! ;-).
> ...
>> The question is a bit unspecific - what do you mean by "like this"? I am
>> not aware of another prototype-based system that has method
>> combinations, but I could be missing something. If you don't want to see
>> this restricted to prototype-based systems, it may be helpful to be more
>> specific.
>>
> Yes, I was specifically asking about prototype system with both Multiple
> Dispatch, and Method Combinations. I've found plenty on Prototypes with
> Multiple Dispatch (Us, Slate, etc.), but very few (currently none) on
> including Method Combinations as well.
OK, it's good to better understand the context of your question.
Is there any prototyped-based language that claims to provide
aspect-oriented extensions? That would also be quite close.
>> One element in CLOS-style method combinations that makes them practical
> ...
>> kinds of arguments are passed.
>
> Sadly, when using a Prototype based system, the "types" of the objects
> is subject to change, as are the slots they contain. Thus there is only
> opportunity for precomputed dispatch tables when the objects are not
> modified in certain ways which would change the inheritance order.
That's actually the same in CLOS. CLOS allows you to change inheritance
hierarchies (at the class level) at runtime, so whenever this happens,
precomputed effective methods have to be invalidated as well.
>> Another element that may be interesting to take into account account is
>> the concept of a "discriminating function" which is part of the CLOS
> ...
>> example, if none of defined methods specialize a specific argument, it
>> never has to be taken into account for method dispatch, etc.
>
> That's an interesting idea there, and I have a rather crufty version of
> it myself. In my system, the generic functions are dispatched only on a
> subset of their arguments (which is defined by the user during function
> definition), and the rest are just carried along as baggage. However, I
> would be interested in finding out more about how CLOS does it. Do you
> have any references I could take a look at?
No, I don't think anyone has written this up. There is some information
about one specific CLOS implementation in
http://www2.parc.com/csl/groups/sda/publications/papers/Kiczales-Andreas-PCL/
but it doesn't provide a lot of details in this regard.
The best you can do is to study existing CLOS implementations which,
however, are typically quite complex beasts.
FYI,
http://www.lisp.org/mop/concepts.html#generic-function-invocation-protocol
describes the protocol which is used to separate generic function calls
into discriminating functions. That would be the starting place in the
source code of a CLOS implementation to look for.
>> Because of this "staged" nature of the generic function invocation
>> protocol, the actual invocations can be as computationally cheap as
>> possible. For very simple generic functions (with few methods and few
>> specializations) this can be very close to regular function calls, and
>> for complex generic functions (with many methods and many
>> specializations), it's unlikely that the manual dispatch that you would
>> have to write yourself in a regular function would be any simpler and
>> more efficient.
>>
>> I think there is a realistic chance that a prototype-based system can
>> gain similar benefits if designed right. You may also want to read
>> http://people.csail.mit.edu/jrb/Projects/partial-dispatch.htm
> Now, correct me if I'm wrong, but it seems to me that their idea of
> "Partial Dispatch" is mostly concerned with pruning out method calls
> from the dispatch order based on disjointness and concreteness. Which
> seems rather redundant to me, since both cases would automatically be
> excluded from the total ordered dispatch sequence if you generate the
> ordering using bfs to grab the inheritance tree, and depth with lexical
> ordering to sort it.
>
> The way that I've implemented prototype objects, methods are external to
> objects, and thus "abstract" objects are simply ones for which a
> generic function has no dispatch orders. Thus making the "pruning" step
> occur automatically while the dispatch order is being calculated, since
> a parent cannot be upcast to a child during dispatch, but children can
> downcast to parents.
>
> As for disjointness, while doing a bfs on the inheritance tree, you will
> only encounter members of the dispatch hierarchy. Thus, if any of the
> dispatch signatures contain any objects not included in the tree, they
> can be immediately discarded.
I don't know the exact details of that paper. I have referred to it
because it says something about efficient multiple dispatch, but it's a
somewhat different approach than in CLOS. CLOS (and its MOP) is designed
in a way such that all decisions are made inside a generic function,
whereas that paper describes an approach where call sites can already
make (some) decisions about method dispatch, which can improve
efficiency as has been shown in Self, Strongtalk and the HotSpot VM for
Java. The CLOS MOP is, unfortunately, not that advanced in this regard.
Pascal
--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
Pascal Costanza wrote:
...
> OK, it's good to better understand the context of your question.
>
> Is there any prototyped-based language that claims to provide
> aspect-oriented extensions? That would also be quite close.
>
Interestingly enough, Lee Salzman (the guy who wrote the paper on Slate
and PMD that I cited earlier in this thread) pointed out that although
PMD and Method Combination are orthogonal, having one rather makes the
other redundant (see
http://lambda-the-ultimate.org/node/1667#comment-20428 for details). As
hard as I've tried, I haven't been able to come up with a
counter-example. (Any takers?)
>>> One element in CLOS-style method combinations that makes them practical
...
>
> That's actually the same in CLOS. CLOS allows you to change inheritance
> hierarchies (at the class level) at runtime, so whenever this happens,
> precomputed effective methods have to be invalidated as well.
>
Good point, I had forgotten the MOP lets you change things like that
during runtime. (Shows you how often I used that particular feature)
However, I think it's rather more common to change inheritance during
runtime in Prototype based languages (common to the point of being a
design pattern of sorts). That doesn't bode too well for trying to use
precomputed caches to up the efficiency of my implementation.
>>> Another element that may be interesting to take into account account is
...
>
>
> Pascal
>
Ryan Kaulakis
rmk216 wrote:
> Pascal Costanza wrote:
> ...
>> OK, it's good to better understand the context of your question.
>>
>> Is there any prototyped-based language that claims to provide
>> aspect-oriented extensions? That would also be quite close.
>>
> Interestingly enough, Lee Salzman (the guy who wrote the paper on Slate
> and PMD that I cited earlier in this thread) pointed out that although
> PMD and Method Combination are orthogonal, having one rather makes the
> other redundant (see
> http://lambda-the-ultimate.org/node/1667#comment-20428 for details). As
> hard as I've tried, I haven't been able to come up with a
> counter-example. (Any takers?)
Mumble. Method combinations aren't exactly necessary in CLOS either.
Consider the following method definitions:
(defmethod foo ((object some-class))
(some-primary-code))
(defmethod foo :around ((object some-class))
(some-auxiliary-code)
(call-next-method))
This could as well be expressed with a single method:
(defmethod foo ((object some-class))
(some-auxiliary-code)
(some-primary-code))
But language design is never about necessity, but exclusively about
convenience. If it were about necessity, then programming in assembly
language would be sufficient. See the CLOS overview papers at
http://www.dreamsongs.com/CLOS.html for some reasons why method
combinations can be useful - they should apply to prototype-based
languages as well.
Having said that, some people argue that method combinations in CLOS are
harmful because they allows for uncalled extendibility. It's indeed not
always the case that you actually want other code to add
before/after/around methods on your generic functions, but unfortunately
that's the default option. I think it would be preferable if the
standard method combination would allow only primary methods (like the
'nil method combination in ISLISP) and before/after/around methods would
require an "announcement" in a respective defgeneric form. Note for
example that method combinations were dropped in Dylan which is a
successor of CLOS. (I definitely think that method combinations are
useful, so don't get me wrong here!)
>>>> One element in CLOS-style method combinations that makes them practical
> ...
>> That's actually the same in CLOS. CLOS allows you to change inheritance
>> hierarchies (at the class level) at runtime, so whenever this happens,
>> precomputed effective methods have to be invalidated as well.
>
> Good point, I had forgotten the MOP lets you change things like that
> during runtime. (Shows you how often I used that particular feature)
> However, I think it's rather more common to change inheritance during
> runtime in Prototype based languages (common to the point of being a
> design pattern of sorts). That doesn't bode too well for trying to use
> precomputed caches to up the efficiency of my implementation.
I don't know. Colleagues who use prototype-based languages claim that
changing parent relationships in such languages is rare. Aren't the
parent links in some prototype-based languages even fixed?
Anyway, I guess for CLOS it's indeed very rare that user-defined class
hierarchies change at runtime. I guess it's more useful for
program-generated class hierarchies, though.
Pascal
--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
Pascal Costanza wrote:
>
> Mumble. Method combinations aren't exactly necessary in CLOS either.
> Consider the following method definitions:
>
> (defmethod foo ((object some-class))
> (some-primary-code))
>
> (defmethod foo :around ((object some-class))
> (some-auxiliary-code)
> (call-next-method))
>
> This could as well be expressed with a single method:
>
> (defmethod foo ((object some-class))
> (some-auxiliary-code)
> (some-primary-code))
That isn't exactly the same. A subclass of `some-class' would run the
auxiliary code in the first case and wouldn't in the second.
> Anyway, I guess for CLOS it's indeed very rare that user-defined class
> hierarchies change at runtime.
Not true! Haven't you ever reloaded a file containing a class
definition? Ever wonder exactly how that could possibly work?
Joe Marshall wrote:
> Pascal Costanza wrote:
>> Mumble. Method combinations aren't exactly necessary in CLOS either.
>> Consider the following method definitions:
>>
>> (defmethod foo ((object some-class))
>> (some-primary-code))
>>
>> (defmethod foo :around ((object some-class))
>> (some-auxiliary-code)
>> (call-next-method))
>>
>> This could as well be expressed with a single method:
>>
>> (defmethod foo ((object some-class))
>> (some-auxiliary-code)
>> (some-primary-code))
>
> That isn't exactly the same. A subclass of `some-class' would run the
> auxiliary code in the first case and wouldn't in the second.
OK, you're right. But still, there is always a way to make the code work
the same without method combinations. It's just not as convenient to do so.
>> Anyway, I guess for CLOS it's indeed very rare that user-defined class
>> hierarchies change at runtime.
>
> Not true! Haven't you ever reloaded a file containing a class
> definition?
Of course.
> Ever wonder exactly how that could possibly work?
Not anymore, since I know how it works. ;)
Still, I guess it's rare that this feature is used. I rather think that
it's mostly used during development and then probably during upgrades of
a running program, but that apart from that, class hierarchies are
stable most of the time. Evidence for this is that Dylan and ISLISP have
left out anything that has to do with redefinition of classes and
generic functions at runtime in their specifications. [1]
Of course, the only thing I know for sure about most programs is that I
haven't seen them. ;)
Pascal
[1] Not that I think that this is a good idea. When changes at runtime
are useful, they can be indeed extremely useful.
--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/