CEDET

Hi Jan,

I was hoping to better understand what's going on with your patch before 
responding, but that hasn't happened yet, so I figured I'd just respond.

I don't know anything about c3, but providing additional method 
invocation orders sounds nifty to me.

An alternative possible solution if you don't get c3 "complete" as you 
like it is that we could make eieio-default-superclass special in that 
it always shows up last on any invocation order.  In that way, you could 
sort your own classes to avoid problems without worrying about the 
default superclass.

Eric

Jan Moringen wrote:
> Hi,
> 
> I'm back with yet another multiple inheritance problem (too many mixins,
> I guess) ;)
> 
> My class graph looks like this:
> 
>                         eieio-default-superclass
>                                    |
>                +-------------------+-------------------+
>                |                   |                   |
>           rudel-state    rudel-impersonator    rudel-delegator
>                |                   |                   |
>                +-------------------+-------------------+
>                                    |
>                             rudel-obby-state     e-def-sup
>                                    |                |
>                   +----------------+                |
>                   |                                 |
>    rudel-obby-client-connection-state    rudel-obby-document-handler
>                   |                                 |
>                   +----------------+----------------+
>                                    |
>                   rudel-obby-client-state-subscribing
> 
> [In case the diagram gets messed up:
> 
> (defclass rudel-state ()
> (defclass rudel-impersonator () 
> (defclass rudel-delegator ()
> (defclass rudel-obby-state (rudel-state rudel-impersonator
> rudel-delegator)
> (defclass rudel-obby-client-connection-state (rudel-obby-state)
> (defclass rudel-obby-document-handler ()
> (defclass rudel-obby-client-state-subscribing
> (rudel-obby-client-connection-state rudel-obby-document-handler)
> 
> ]
> 
> The problem appears with an invocation of the generic function
> `no-applicable-method'. There is a method installed for
> `rudel-delegator' and, of course, for `eieio-default-superclass'. I
> expected the method for `rudel-delegator' to be called, since it is on
> the most specific class. On second thought, the breadth-first method
> resolution order cannot really do that, so the behavior is as expected.
> However, I would like a different behavior better.
> 
> Despite my current problem, I think the breadth-first search may not be
> optimal. A little searching yielded [1] in which the so-called C3
> algorithm is described. The points made there seem very logical to me.
> So much in fact, that I ported the implementation to Elisp and engaged
> in some experiments. As expected, my problem could be solved, were :c3
> available as a :method-invocation-order.
> 
> In my opinion, it would be very useful to include a :c3 method
> resolution order in EIEIO, or even make it the default.
> 
> I attached some code to reproduce the original problem, my c3
> implementation experiments and a patch that allows :c3 as
> a :method-invocation-order (it is not a complete implementation,
> though).
> 
> What do you think?
> 
> Kind regards,
> Jan
> 
> [1] http://192.220.96.201/dylan/linearization-oopsla96.html
> 
> 
> ------------------------------------------------------------------------
> 
> ------------------------------------------------------------------------------
> Return on Information:
> Google Enterprise Search pays you back
> Get the facts.
> http://p.sf.net/sfu/google-dev2dev
> 
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> cedet-eieio mailing list
> cedet-eieio@...
> https://lists.sourceforge.net/lists/listinfo/cedet-eieio

Hi Eric,

thanks for concerning yourself with another obscure problem :)

> I was hoping to better understand what's going on with your patch
> before 
> responding, but that hasn't happened yet, so I figured I'd just
> respond.

Currently, the attached code just prints method resolution orders for
some class graphs (the second half of eieio-c3.el does that).

> I don't know anything about c3, but providing additional method 
> invocation orders sounds nifty to me.

If you agree, I would definitely want to incorporate it.

> An alternative possible solution if you don't get c3 "complete" as you
> like it 

I am currently working on changes concerning `eieiomt-method-list' and
`eieiomt-sym-optimize' to work with arbitrary class precedence orders.
However, despite being almost complete, the code is not currently in a
usable state. :(

> is that we could make eieio-default-superclass special in that
> it always shows up last on any invocation order.  In that way, you
> could 
> sort your own classes to avoid problems without worrying about the 
> default superclass.

That would be a nice improvement regardless of possible new method
resolution orders.

I hope to get the code for generic class precedence orders working
within a few days. Could we delay the decision until then?

Jan

Jan Moringen wrote:
>
> 
> I hope to get the code for generic class precedence orders working
> within a few days. Could we delay the decision until then?
>

That is fine with me.

Eric

> > I hope to get the code for generic class precedence orders working
> > within a few days. Could we delay the decision until then?
> >
> 
> That is fine with me.

I got to fixing my patch. The updated version (no extra -c3 file, unit
tests) is attached.

What do you think?

Jan

Jan Moringen wrote:
>>> I hope to get the code for generic class precedence orders working
>>> within a few days. Could we delay the decision until then?
>>>
>> That is fine with me.
> 
> I got to fixing my patch. The updated version (no extra -c3 file, unit
> tests) is attached.

+;;
+;; Note: the implementation of the c3 algorithm is based on:
+;;   Kim Barrett et al.: A Monotonic Superclass Linearization for Dylan
+;;   Retrieved from:
+;;   http://192.220.96.201/dylan/linearization-oopsla96.html

Hi Jan,

Could you elaborate on what this comment means?  More specifically, did 
you translate code directly (presumably from Dylan), and could they 
claim copyright in some way on your work?

If you aren't sure we should check with the FSF copyright clerk as I'm 
not that clear on the rules here either.

Thanks
Eric

On Tue, 2009-12-15 at 22:43 -0500, Eric M. Ludlam wrote:
> +;;
> +;; Note: the implementation of the c3 algorithm is based on:
> +;;   Kim Barrett et al.: A Monotonic Superclass Linearization for
> Dylan
> +;;   Retrieved from:
> +;;   http://192.220.96.201/dylan/linearization-oopsla96.html
> 
> Could you elaborate on what this comment means?  

Sure.

> More specifically,did you translate code directly (presumably from
> Dylan)

Pretty much. The Dylan code uses lots local methods and some other minor
things are different, but the structure is still very similar.

> , and could they claim copyright in some way on your work?

Bottom line: I don't know. However, I can present some details:

The note refers to the paper "A Monotonic Superclass Linearization for
Dylan" (a full citation is in the Wikipedia article
http://en.wikipedia.org/wiki/C3_linearization). In that paper, the
authors present the Dylan code of the canonical Dylan linearization and
they present their modified candidate method.

The novel code in the paper is this (comments stripped):

local method candidate (c :: <class>)
  local method tail? (l :: <list>)
    member?(c, tail(l))
  end method tail?;

  ~any?(tail?, remaining-inputs)
    & c
end method candidate,

method candidate-at-head (l :: <list>)
  ~empty?(l) & candidate(head(l))
end candidate-at-head;

let next = any?(candidate-at-head, remaining-inputs);

The equivalent code in eieio.el would be:

(defun eieio-c3-candidate (class remaining-inputs)
  "Returns CLASS if it can go in the result now, otherwise nil"
  ;; Ensure CLASS is not in any position but the first in any of the
  ;; element lists of REMAINING-INPUTS.
  (and (not (some (lambda (l) (member class (rest l)))
		  remaining-inputs))
       class))

and later:

(let ((next (some (lambda (c) (eieio-c3-candidate c remaining-inputs))
		      (mapcar #'first
			      (remove-if #'null remaining-inputs)))))

The copyright notice of the online version of the paper reads as
follows:

Copyright © 1996 by the Assocation for Computing Machinery. Permission
to copy and distribute this document is hereby granted provided that
this notice is retained on all copies, that copies are not altered, and
that ACM is credited when the material is used to form other copyright
policies. See the ACM Interim Copyright Policy for details.

The canonical algorithm was probably implemented in GPLed code before
the publication. For example sources/dylan/class-dynamic.dylan:573 of
Open Dylan.

According to Wikipedia, the algorithm itself is in moderate use:

      * Python 2.3's use of C3 MRO
      * Perl 6 will use C3 MRO
      * Parrot uses C3 MRO
      * C3 MRO available in Perl 5.10

I would assume it to be safe to derive an equivalent program in another
programming language (like we would). But I'm not sure.

> If you aren't sure we should check with the FSF copyright clerk as I'm
> not that clear on the rules here either.

If the elaboration did not help, we should resort to that measure.

> Thanks

Thank you for concerning yourself so much with this very small potential
improvement.

Jan