prefer mechanism for protocols

[Chas Emerick]

Right now, there is no corollary to `prefer-method` for protocols. Thus, this:

=> (defprotocol Foo
(a [x]))
Foo
=> (extend-protocol Foo
java.io.Serializable
(a [x] "*")
CharSequence
(a [x] "s"))
nil
=> (a (StringBuilder. "blah"))
"*"

Not "wrong" behaviour, but a sharp edge for sure.

Multimethods have `prefer-method`, so a `prefer-type` (or somesuch) for protocols would be most welcome.

Anyway, by now I remember some brief discussion about this on irc, and I see it's been considered to some degree; e.g. there is the "TBD" note on the original design docs here:

http://www.assembla.com/wiki/show/clojure/Protocols

and there's this ticket:

http://dev.clojure.org/jira/browse/CLJ-295

I've found that the above situation is so easy to get into that I almost wish that the extend-* fns for protocols only worked over concrete types, so I can certainly sympathize with Rich's thought (ultimately rejected, along with the ticket) that an exception should be thrown when a protocol fn is asked to dispatch in such cases.

----

Is there any more recent movement/thought in this area?

- Chas

[Alex Miller]

I just ran into a variant of this yesterday and thought it was an interesting case where using multi-methods had more visible flexibility with hierarchies and preferences. 

Are there performance concerns with handling preferences for protocols?

---

From: Chas Emerick <ceme...@snowtide.com>
To: cloju...@googlegroups.com
Sent: Fri, December 10, 2010 12:16:42 AM
Subject: prefer mechanism for protocols

--
You received this message because you are subscribed to the Google Groups "Clojure Dev" group.
To post to this group, send email to cloju...@googlegroups.com.
To unsubscribe from this group, send email to clojure-dev+unsub...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/clojure-dev?hl=en.

[Chas Emerick]

I don't *think* so.  AFAICT, the magic happens in find-protocol-impl; whatever fn is returned there (modulo the case where the object provided implements the protocol's interface) ends up being cached forever for that protocol fn, keyed on the concrete class of the object provided.  So, the semantics of find-protocol-impl (which should almost surely be a private var, no?) could be changed to support a preference mechanism without impacting perf one bit (outside of the initial lookup, for which I assume we'd be willing to take whatever hit that preference mechanism implied).

To demonstrate (still on 1.2.0 here, so all vars are dynamic):

(defprotocol Bar (a [x]))

Bar

(extend-protocol Bar

  String

  (a [s] "s")

  Number

  (a [n] "1"))

nil

(binding [find-protocol-impl (constantly (-> Bar :impls (get java.lang.String)))]

  (a 2.5))

"s"

(a 2.5)

"s"

(a 40)

"1"

In that binding form, we force the call to find-protocol-impl to return the protocol implementation map for String, regardless of the class of the first argument.  That result gets cached forever, so all calls to `a` with doubles (e.g. 2.5) from then on use String's implementations (for all protocol fns), with the dispatch coming from cache per usual.  Calls we make afterwards with an argument of a concrete type for which a dispatch hasn't yet been cached (e.g. Integers like `1`) get the result you'd expect from an unfettered call to `a`.

-----

I think that resolves the perf question.  That said, I don't think what the preference mechanism should look like is obvious.  prefer-method gets the job done, but it's not all roses, especially as hierarchies get complicated -- and interface/class hierarchies aren't any simpler.  I certainly don't think I have the vision at the moment to propose an approach or implementation.

- Chas

To unsubscribe from this group, send email to clojure-dev...@googlegroups.com.

[James Reeves]

On 10 December 2010 06:16, Chas Emerick <ceme...@snowtide.com> wrote:
> Right now, there is no corollary to `prefer-method` for protocols.  Thus, this:
>
> => (defprotocol Foo
>     (a [x]))
> Foo
> => (extend-protocol Foo
>     java.io.Serializable
>     (a [x] "*")
>     CharSequence
>     (a [x] "s"))
> nil
> => (a (StringBuilder. "blah"))
> "*"
>
> Not "wrong" behaviour, but a sharp edge for sure.

The problem is actually a little worse than that, as the output is not
predictable across JVM instances (at least in Clojure 1.2.0).

I encountered an issue with protocol that extended clojure.lang.IFn
and java.util.Map. When the protocol function was passed a
PersistentHashMap, then 90% of the time it would be treated as a Map,
but 10% of the time it would be treated as an IFn. The ancestor type
it chose to dispatch on seemed to be determined when the JVM is
started up.

Constantine Vetoshev describes the issue in more detail here:

http://groups.google.com/group/compojure/browse_thread/thread/113e0bc47d793d36/91def69b5a9444eb

- James

[Chas Emerick]

On Dec 10, 2010, at 10:37 AM, James Reeves wrote:

> On 10 December 2010 06:16, Chas Emerick <ceme...@snowtide.com> wrote:
>> Right now, there is no corollary to `prefer-method` for protocols.
>>

>> Not "wrong" behaviour, but a sharp edge for sure.
>
> The problem is actually a little worse than that, as the output is not
> predictable across JVM instances (at least in Clojure 1.2.0).
>
> I encountered an issue with protocol that extended clojure.lang.IFn
> and java.util.Map. When the protocol function was passed a
> PersistentHashMap, then 90% of the time it would be treated as a Map,
> but 10% of the time it would be treated as an IFn. The ancestor type
> it chose to dispatch on seemed to be determined when the JVM is
> started up.
>
> Constantine Vetoshev describes the issue in more detail here:
>
> http://groups.google.com/group/compojure/browse_thread/thread/113e0bc47d793d36/91def69b5a9444eb
>
> - James

"when the JVM is started up"? I presume it's flowing from hashmap entry order being undefined. In any case, your point is well taken.

- Chas

[James Reeves]

On 10 December 2010 15:40, Chas Emerick <ceme...@snowtide.com> wrote:
> "when the JVM is started up"?

I mean that individual JVM processes behaved consistently, e.g. it
would always prefer a Map over an IFn for the life of the process. But
sometimes a JVM would start where IFn was preferred over Map.

> I presume it's flowing from hashmap entry order being undefined.

Yes, that's probably the cause, come to think of it. If the types are
ambiguous, I guess it must use whatever type comes first when
iterating over the map passed to `extend`.

- James

[David Nolen]

On Fri, Dec 10, 2010 at 1:16 AM, Chas Emerick <ceme...@snowtide.com> wrote:

http://dev.clojure.org/jira/browse/CLJ-295

I've found that the above situation is so easy to get into that I almost wish that the extend-* fns for protocols only worked over concrete types, so I can certainly sympathize with Rich's thought (ultimately rejected, along with the ticket) that an exception should be thrown when a protocol fn is asked to dispatch in such cases.

----

Is there any more recent movement/thought in this area?

- Chas

I kind of see this as a variant of programmer error similar to when you extend both java.lang.Object and java.lang.String to the same protocol. Extending a protocol to an interface sounds like it was only intended for interop. 

It also makes sense to me that all implementations of a protocol should satisfy the same contract.

David 

[Chas Emerick]

On Dec 10, 2010, at 12:13 PM, David Nolen wrote:

> I kind of see this as a variant of programmer error similar to when you extend both java.lang.Object and java.lang.String to the same protocol. Extending a protocol to an interface sounds like it was only intended for interop.

I would doubt that -- there's no sense in not taking advantage of the type hierarchy that you find yourself within. Protocols and multimethods (via isa?) are entirely in lockstep in this regard.

That said, this raises in interesting tangential meta issue (and I'm probably putting words in your mouth here): do you really consider any use of interfaces to constitute interop? I would say just the opposite: Clojure seems to embrace interfaces wholeheartedly in a number of ways. I can see dimly though how one might characterize that embrace as entirely a result of practical concerns motivated by what the host offers (e.g. to support efficient polymorphic dispatch) rather than a proper endorsement of interfaces.

- Chas

[David Nolen]

On Fri, Dec 10, 2010 at 12:37 PM, Chas Emerick <ceme...@snowtide.com> wrote:

On Dec 10, 2010, at 12:13 PM, David Nolen wrote:

> I kind of see this as a variant of programmer error similar to when you extend both java.lang.Object and java.lang.String to the same protocol. Extending a protocol to an interface sounds like it was only intended for interop.

I would doubt that -- there's no sense in not taking advantage of the type hierarchy that you find yourself within.  Protocols and multimethods (via isa?) are entirely in lockstep in this regard.

I was just reiterating what was stated on the Assembla page: primarily intended for interop.

I note that in Clojure source prefer-method appears in only one file, core_print.clj.

While I might be wrong- prefer-method seems to me to make most sense in conjunction with side-effects where the contract is ambiguous and a hierarchy must be imposed. I just can't think of a scenario where extending all types under an interface to a protocol won't tend to introduce complexity. The interactions of hierarchies is just too subtle.

Which isn't to say I haven't found myself wanting this - I've ended up just explicitly enumerating all the types I want to extend a protocol to. But this ends up being easier to reason about as well.

 

That said, this raises in interesting tangential meta issue (and I'm probably putting words in your mouth here): do you really consider any use of interfaces to constitute interop?  I would say just the opposite: Clojure seems to embrace interfaces wholeheartedly in a number of ways.  I can see dimly though how one might characterize that embrace as entirely a result of practical concerns motivated by what the host offers (e.g. to support efficient polymorphic dispatch) rather than a proper endorsement of interfaces.

- Chas

Definitely putting words in my mouth :)

David 

[Alex Miller]

The case I had with multimethods was a multimethod where it was dispatched on class and subtly different methods provided for both ISeq and IPersistentList with a preference for the latter.  [The ISeq version forced creation of an explicit list.] 

In this case, it would probably be a bad idea (certainly no fun) to extend a protocol to all concrete types under ISeq to have the appropriate semantics, yet I think that's what you would need to do to make this unambiguous.  

In this case the "interop" is actually with the impl of Clojure itself which has a maze of capability and data structure interfaces.  If you're doing any protocol that deals with Clojure types seems like you'll run into this.  That's certainly not the common case for me with protocols, but it seems easy to run into.

---

From: David Nolen <dnolen...@gmail.com>
To: cloju...@googlegroups.com
Sent: Fri, December 10, 2010 1:07:58 PM
Subject: Re: prefer mechanism for protocols

--

[David Nolen]

On Fri, Dec 10, 2010 at 2:50 PM, Alex Miller <alexd...@yahoo.com> wrote:

In this case, it would probably be a bad idea (certainly no fun) to extend a protocol to all concrete types under ISeq to have the appropriate semantics, yet I think that's what you would need to do to make this unambiguous.  

In my experience, at least, this is not a bad idea and not even that painful- you have macros.

David

[Alex Miller]

Sure, until clojure core adds a new seq impl in 1.3 and retroactively opens an edge case in my protocol...  :)  Seems like a bad idea to ever explicitly call out a Clojure core *concrete class* in your own code, much less try to specify a complete set of subtypes under an interface.  

Why not leverage those inheritance relationships that already exist in those classes/interfaces in the core?  You can't proactively query reflection for those (can't ask for all impls of a type) and register those.  But you can leverage the upward (is my instance a foo?) question at runtime ala multimethods. 

(I'm mostly just playing devil's advocate here to push this conversation over the design space.... in most cases I'm using protocols over a set of concrete types and that's perfect.)  

---

From: David Nolen <dnolen...@gmail.com>
To: cloju...@googlegroups.com

Sent: Fri, December 10, 2010 2:02:08 PM

Subject: Re: prefer mechanism for protocols

--

[David Nolen]

On Fri, Dec 10, 2010 at 3:24 PM, Alex Miller <alexd...@yahoo.com> wrote:

Sure, until clojure core adds a new seq impl in 1.3 and retroactively opens an edge case in my protocol...  :)  Seems like a bad idea to ever explicitly call out a Clojure core *concrete class* in your own code, much less try to specify a complete set of subtypes under an interface.

I don't see why it's a bad idea to call out a Clojure concrete class if you have a protocol that needs to be extended to them.

 

Why not leverage those inheritance relationships that already exist in those classes/interfaces in the core?  You can't proactively query reflection for those (can't ask for all impls of a type) and register those.  But you can leverage the upward (is my instance a foo?) question at runtime ala multimethods. 

Bringing a type to a protocol is easy. Bringing a protocol to a open set of types which have a open set of interfaces seems to me like you're asking for a world of trouble.

In the first case if you miss a type, just add it to the list. In the second case ... not sure how to get out of that particular tarpit.

David

[Chas Emerick]

I agree with Alex, though this is far from a future hypothetical.  When extending protocols to types from third parties, you generally don't *want* to know about (nevermind directly reference) concrete classes, and often there's no sane way to determine what the full domain is of those concrete classes – e.g. in the case where there's a factory method / function somewhere that emits implementations of some interface.  There, you absolutely want to extend to that interface.

The fact we run into this in pure-Clojure code is largely a side effect of (a) the standard data structures having a large interface "footprint", and (b) the (correct, IMO) desire to extend protocol implementations to high-level interfaces rather than concrete types.  The situation will not get prettier as defrecord gets more and more usage, especially in conjunction with third-party interfaces…

- Chas

[Meikel Brandmeyer]

Hi,

Am 10.12.2010 um 20:50 schrieb Alex Miller:

> In this case, it would probably be a bad idea (certainly no fun) to extend a protocol to all concrete types under ISeq to have the appropriate semantics, yet I think that's what you would need to do to make this unambiguous.

Hmm.. It is my understanding, that things like ISeq will turn into a PSeq – a protocol. Then you can't extend another protocol to a PSeq thing. Because PSeq then is not a type anymore. Then you would have to catch all concrete types.

Is that correct?

Sincerely
Meikel

[Meikel Brandmeyer]

Hi,

Am 10.12.2010 um 21:42 schrieb Chas Emerick:

> I agree with Alex, though this is far from a future hypothetical. When extending protocols to types from third parties, you generally don't *want* to know about (nevermind directly reference) concrete classes, and often there's no sane way to determine what the full domain is of those concrete classes – e.g. in the case where there's a factory method / function somewhere that emits implementations of some interface. There, you absolutely want to extend to that interface.

Here again, we have the question: who defines the extension of a protocol. You should only extend a protocol to third-party types if you are the „owner“ of that protocol. You basically do it on behalf of the third party. And then you have to understand how these classes work inside.

> The fact we run into this in pure-Clojure code is largely a side effect of (a) the standard data structures having a large interface "footprint", and (b) the (correct, IMO) desire to extend protocol implementations to high-level interfaces rather than concrete types. The situation will not get prettier as defrecord gets more and more usage, especially in conjunction with third-party interfaces…

Again, I think protocols are taking over the part of interfaces. There will be the need to reference concrete types there. I think that is the reason, why Object and String are not a problem – there we have an hierarchy. This is not the case with interfaces. But this will go away (for clojure code at least) as protocols replace interfaces, since you can't extend a protocol to a protocol. (A protocol also defines an interface, but this is not enough, because the protocol could be extended to any existing type, which does not implement the interface.)

Please correct me in case I got something terribly wrong about protocols.

Sincerely
Meikel

[David Nolen]

On Fri, Dec 10, 2010 at 3:42 PM, Chas Emerick <ceme...@snowtide.com> wrote:

I agree with Alex, though this is far from a future hypothetical.  When extending protocols to types from third parties, you generally don't *want* to know about (nevermind directly reference) concrete classes, and often there's no sane way to determine what the full domain is of those concrete classes.

I agree with Meikel and I honestly see this as an analog to the lack of import * in Clojure. You're bringing an unknown set of types with an unknown set of interfaces which you do not own into your protocol. Expect breakage.

Clojure will give you meaningful errors when you call a protocol on concrete type that does not extend it. Just add the type to the list.

David 

[Alex Miller]

Interesting. 

---

From: David Nolen <dnolen...@gmail.com>

To: cloju...@googlegroups.com

Sent: Fri, December 10, 2010 2:39:44 PM

Subject: Re: prefer mechanism for protocols

On Fri, Dec 10, 2010 at 3:24 PM, Alex Miller <alexd...@yahoo.com> wrote:

Sure, until clojure core adds a new seq impl in 1.3 and retroactively opens an edge case in my protocol...  :)  Seems like a bad idea to ever explicitly call out a Clojure core *concrete class* in your own code, much less try to specify a complete set of subtypes under an interface.

I don't see why it's a bad idea to call out a Clojure concrete class if you have a protocol that needs to be extended to them.

I think we'll just have to agree to disagree on that one.

 

Why not leverage those inheritance relationships that already exist in those classes/interfaces in the core?  You can't proactively query reflection for those (can't ask for all impls of a type) and register those.  But you can leverage the upward (is my instance a foo?) question at runtime ala multimethods. 

Bringing a type to a protocol is easy. Bringing a protocol to a open set of types which have a open set of interfaces seems to me like you're asking for a world of trouble.

I think that's an insightful comment. But I don't buy that a (potentially open in the future) set of classes is better than a (potentially open in the future) set of interfaces.  I would expect the interface set to be more stable than the class set.  But maybe we're bikeshedding.

In the first case if you miss a type, just add it to the list. In the second case ... not sure how to get out of that particular tarpit.

In the second case, you either have conflict which you can resolve after the fact with preferences OR you have an unhandled type which you can handle via the trick Rich mentioned during the Sean's protocol talk at the conj.  That is, extend Object and have that impl notice that you fell through the protocol dispatch and dynamically extend a protocol to the type you just encountered (after which you will route directly, not through Object).  My colleague Dave McNeil did this recently and it worked great.

David

[Chas Emerick]

On Dec 10, 2010, at 3:39 PM, David Nolen wrote:

On Fri, Dec 10, 2010 at 3:24 PM, Alex Miller <alexd...@yahoo.com> wrote:

Sure, until clojure core adds a new seq impl in 1.3 and retroactively opens an edge case in my protocol...  :)  Seems like a bad idea to ever explicitly call out a Clojure core *concrete class* in your own code, much less try to specify a complete set of subtypes under an interface.

I don't see why it's a bad idea to call out a Clojure concrete class if you have a protocol that needs to be extended to them.

They're implementation details, subject to change.  Surely intimate knowledge of them shouldn't be required in order to reliably get desired dispatch behaviour from a protocol.

 

Why not leverage those inheritance relationships that already exist in those classes/interfaces in the core?  You can't proactively query reflection for those (can't ask for all impls of a type) and register those.  But you can leverage the upward (is my instance a foo?) question at runtime ala multimethods. 

Bringing a type to a protocol is easy. Bringing a protocol to a open set of types which have a open set of interfaces seems to me like you're asking for a world of trouble.

I think it's instructive to look at where protocols need to go.  Consider `seq` in the context of stringy things (defined by the CharSequence interface).  Surely we wouldn't want `seq` to fail on previously-unknown implementations of CharSequence (of which there are many)?

- Chas

[Alex Miller]

My "hrm?" detectors go off when I hear the word "only".  For example, it seems equally like to define an IOC style contract with a protocol and expect external parties to be the ones that extend a protocol and I as the creator of the protocol would never extend it.  So far, I've seen several useful ways to leverage protocols and they don't all fall under your description below.

---

From: Meikel Brandmeyer <m...@kotka.de>
To: cloju...@googlegroups.com
Sent: Fri, December 10, 2010 2:51:23 PM

Subject: Re: prefer mechanism for protocols

--
You received this message because you are subscribed to the Google Groups "Clojure Dev" group.
To post to this group, send email to cloju...@googlegroups.com.

To unsubscribe from this group, send email to clojure-dev+unsub...@googlegroups.com.

[David Nolen]

On Fri, Dec 10, 2010 at 4:08 PM, Chas Emerick <ceme...@snowtide.com> wrote:

They're implementation details, subject to change.  Surely intimate knowledge of them shouldn't be required in order to reliably get desired dispatch behaviour from a protocol.

Basing a protocol on intimate knowledge of concrete types is not what I'm suggesting at all.

I may for example have a custom iteration protocol on all iterable Clojure data structures that simply calls first/next and my *own* types use a custom first/next.  

I think it's instructive to look at where protocols need to go.  Consider `seq` in the context of stringy things (defined by the CharSequence interface).  Surely we wouldn't want `seq` to fail on previously-unknown implementations of CharSequence (of which there are many)?

- Chas

I don't see the point here. Either you implemented all of CharSequence or you didn't. If you did, seq will work just fine.

David

[David Nolen]

On Fri, Dec 10, 2010 at 4:04 PM, Alex Miller <alexd...@yahoo.com> wrote:

In the first case if you miss a type, just add it to the list. In the second case ... not sure how to get out of that particular tarpit.

In the second case, you either have conflict which you can resolve after the fact with preferences OR you have an unhandled type which you can handle via the trick Rich mentioned during the Sean's protocol talk at the conj.  That is, extend Object and have that impl notice that you fell through the protocol dispatch and dynamically extend a protocol to the type you just encountered (after which you will route directly, not through Object).  My colleague Dave McNeil did this recently and it worked great. 

preferences reintroduce explicit ordering in the hierarchy, which Clojure in general seems to either avoid or downplay. 

David 

[Alex Miller]

Actually, I want to bring a *known* set of interfaces but an *unknown* set of classes under those interfaces.  For certain use cases (like the one I described), I think that's quite reasonable.  The multi-method version of this code works great.  

If "protocols just don't do that", then I would just use multimethods for that case or use dynamic protocol extension via Object.  If protocols did handle this though, I'd probably use a protocol b/c there's not actually one multimethod, there are really three related multimethods with this same issue, which is perfect for a protocol.  But it would be nice if protocols "just don't do that" because there's a really good reason, not just because we didn't get around to it.

---

From: David Nolen <dnolen...@gmail.com>
To: cloju...@googlegroups.com

Sent: Fri, December 10, 2010 3:00:36 PM

Subject: Re: prefer mechanism for protocols

--

[Rich Hickey]

Sorry for the delay:

The key question is, what should be the basis of choosing one over the
other? Clearly, the ambiguity is inherent. Java allows multiple
inheritance of interfaces, and by hanging implementations off of
interfaces one gets multiple inheritance of implementation. It could
be resolved:

a) as an error - MI is bad, no MI for you

b) mechanically - I don't see a mechanical solution significantly more
meaningful than alphabetical order of classname, given the information
we have available, and it is unlikely to please anyone

c) using external information

Multimethods encountered the same problem and chose (c), using the
prefer system. While that usually enables you to proceed, proceed in
what is a good question. MI is inherently difficult to reason about.
Adding preferences ad hoc and dynamically begets a race to determine
what to prefer, and there is no good way to arbitrate conflicting
preferences. In addition, they are not at all declarative, so one has
to do dynamic querying to see what the relationships are (at the
moment). Finally, as Meikel has pointed out in this thread, moving
forward there will be fewer interfaces and more protocols, so there
won't necessarily be interfaces to hang things from. As we move away
from concrete static type hierarchy, to what should we attach any
categorization/disambiguation system (and can it be made fast)?

It seems weird to complain about having to connect the abstraction
(protocol) to a concrete class, when that is exactly what the author
of the concrete class had to do in choosing its interfaces (once and
for all). In one sense, all protocols do is open up that capability.
Defining concrete behavior for abstractions themselves (rather than
their concrete instances) is somewhat broken from a logic standpoint.
I see the appeal (define something once to cover an open set of
cases), but when combined with interface MI, the logic problem
remains. Preferences just patch up the logic by inserting sequentially
considered conditionals.

A is true of Xs
B is true of Ys
Fred is an X and a Y, but only A true of Fred.

In short, I think preferences are an ok idea, very much tied to
interfaces, and I'd like to see something better for protocols. Until
then, I've been punting and waiting to see what people really need.

Brilliant ideas welcome,

Rich

[Steve Miner]

On Feb 28, 2011, at 10:44 AM, Rich Hickey wrote:

> b) mechanically - I don't see a mechanical solution significantly more meaningful than alphabetical order of classname, given the information we have available, and it is unlikely to please anyone

I'm sure you're familiar with how CLOS deals with multiple inheritance (of classes). I can't say I've investigated this deeply, but I remember that the Dylan folks came up with an improved method [1], and suggested another algorithm that Python implemented (C3 Linearization) [2].

I'm thinking the Dylan paper might inspire an approach that would work for Java interface multiple inheritance. The basic idea is that, for a given type, you compute a class/interface precedence list -- a linearization of the superclass and inherited interfaces. The precedence list is used to resolve conflicts from multiple inheritance such that the most "specific" one is preferred. The Dylan paper explains why a monotonic linearization is desirable.

Linearization is similar in spirit to the earlier suggestion that result of supers should be sorted. The C3 Linearization is a specific way of sorting the precedence list so that the preferences are in some sense "natural".

A Monotonic Superclass Linearization for Dylan
[1] http://www.webcom.com/haahr/dylan/linearization-oopsla96.html

> As described above, the Dylan linearization merges the local precedence order of a class with the linearizations of its direct superclasses. When there are several possible choices for the next element of the linearization, the class that has a direct subclass closest to the end of the output sequence is selected.
>
> It should be clear that the Dylan linearization is monotonic, because the merge procedure never reorders the linearizations of superclasses when producing the linearization. Similarly, it obeys local precedence order because the merge explicitly takes local precedence into account, and the local precedence orders of superclasses are propagated by the linearizations.
>

The Python 2.3 Method Resolution Order
[2] http://www.python.org/download/releases/2.3/mro/

Steve Miner
stev...@gmail.com

[Meikel Brandmeyer]

Hi,

Am 01.03.2011 um 19:07 schrieb Steve Miner:

> I'm sure you're familiar with how CLOS deals with multiple inheritance (of classes). I can't say I've investigated this deeply, but I remember that the Dylan folks came up with an improved method [1], and suggested another algorithm that Python implemented (C3 Linearization) [2].
>
> I'm thinking the Dylan paper might inspire an approach that would work for Java interface multiple inheritance. The basic idea is that, for a given type, you compute a class/interface precedence list -- a linearization of the superclass and inherited interfaces. The precedence list is used to resolve conflicts from multiple inheritance such that the most "specific" one is preferred. The Dylan paper explains why a monotonic linearization is desirable.
>
> Linearization is similar in spirit to the earlier suggestion that result of supers should be sorted. The C3 Linearization is a specific way of sorting the precedence list so that the preferences are in some sense "natural".

I have no clue how a linearization works; let alone a monotonic or C3 one. I would prefer a more „obvious“ solution than some obscure algorithm however nifty and cunning it might be. Be it erroring out or some kind of preference declaration.

Consider the „sorting“ mentioned above. How to sort things? Alphabetically on the name? The Dylan link said, that the order of class names was significant. How do you control this with protocols? Think of the load order of namespaces. A change in a sublibrary might suddenly change your order of protocol extension; and hence your precedence list. So we have to come up with an even more cunning algorithm?

Whatever the final solution looks like: I hope, it's (relatively) easy to understand and to reason about.

Sincerely
Meikel

[Sean Devlin]

If we design in an explicit preference mechanism like multimethods, you can the just macro-fu your own MI system, right?