Potential copyright problem in EIEIO improvement

[Jan Moringen]

Hi,

while working on an EIEIO feature, Eric and I encountered a possible
legal problem we could not resolve. Eric suggested asking for help here.

Basically, I implemented an algorithm (c3 linearization) which is
described in an academic paper (see below). My implementation is very
close to the implementation presented in the paper (although that one is
written in Dylan).

Rather than explaining everything from scratch I just paste Eric's and
my conversation concerning the issue (the diff at the beginning is from
one part of my patch):

On Thu, 2009-12-17 at 03:08 +0100, Jan Moringen wrote: 
> 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

Any thoughts on this issue would be greatly appreciated. I can try to
provide additional information if required.

Many thanks in advance.

Jan