Re: [cedet-eieio] Yet another multiple inheritence problem From: Jan Moringen - 2009-12-17 02:09 ```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 :: ) local method tail? (l :: ) member?(c, tail(l)) end method tail?; ~any?(tail?, remaining-inputs) & c end method candidate, method candidate-at-head (l :: ) ~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 ```

 Re: [cedet-eieio] Yet another multiple inheritence problem From: Eric M. Ludlam - 2009-12-14 01:47 ```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 ```
 Re: [cedet-eieio] Yet another multiple inheritence problem From: Jan Moringen - 2009-12-14 02:19 ```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 ```
 Re: [cedet-eieio] Yet another multiple inheritence problem From: Eric M. Ludlam - 2009-12-14 12:42 ```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 ```
 Re: [cedet-eieio] Yet another multiple inheritence problem From: Jan Moringen - 2009-12-16 02:16 Attachments: cedet-eieio-c3.diff ```> > 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 ```
 Re: [cedet-eieio] Yet another multiple inheritence problem From: Eric M. Ludlam - 2009-12-16 03:43 ```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 ```
 Re: [cedet-eieio] Yet another multiple inheritence problem From: Jan Moringen - 2009-12-17 02:09 ```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 :: ) local method tail? (l :: ) member?(c, tail(l)) end method tail?; ~any?(tail?, remaining-inputs) & c end method candidate, method candidate-at-head (l :: ) ~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 ```