Potential copyright problem in EIEIO improvement

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

Re: Potential copyright problem in EIEIO improvement

[Eli Zaretskii]

> Date: Wed, 30 Dec 2009 03:49:00 +0100
> From: Jan Moringen <jan.moringen@uni-bielefeld.de>
> 
> 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).
> [...]
> Any thoughts on this issue would be greatly appreciated. I can try to
> provide additional information if required.

To my non-lawyer's eyes, the two implementations are so different in
form that they only share the same idea.  And ideas are not
copyrightable, AFAIK.

But IANAL.

Re: Potential copyright problem in EIEIO improvement

[Jan Moringen]

On Wed, 2009-12-30 at 00:42 -0500, Eli Zaretskii wrote:
> > Date: Wed, 30 Dec 2009 03:49:00 +0100
> > From: Jan Moringen <jan.moringen@uni-bielefeld.de>
> > 
> > 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).
> > [...]
> > Any thoughts on this issue would be greatly appreciated. I can try
> to
> > provide additional information if required.
> 
> To my non-lawyer's eyes, the two implementations are so different in
> form that they only share the same idea.  And ideas are not
> copyrightable, AFAIK.

Thanks for the assessment. That line of thought did not cross my mind. I
assumed one had to make the argument under the assumption that my code
is derived from the presented Dylan code (which it is).

Jan

Re: Potential copyright problem in EIEIO improvement

[Richard Stallman]

    > (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)))))

If that's the whole extent of the code in question,
about 7 lines, I don't think there's an issue to be concerned about.

Re: Potential copyright problem in EIEIO improvement

[Jan Moringen]

On Wed, 2009-12-30 at 20:45 -0500, Richard Stallman wrote:
> > (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)))))
> 
> If that's the whole extent of the code in question,
> about 7 lines, I don't think there's an issue to be concerned about.

Thank you for your opinion on this. Regarding the "if" part, there are
two parts: the canonical Dylan linearization, upon which the paper
(mentioned in my original message) is improving and the actual
improvement. The code above corresponds to the improvement. My patch
also has parts derived from the unchanged parts of the canonical
implementation.

I thought the part derived from the canonical implementation should not
be a problem since the canonical implementation is available under GPL
in Open Dylan.

Thanks again,
Jan

Re: Potential copyright problem in EIEIO improvement

[Richard Stallman]

    Thank you for your opinion on this. Regarding the "if" part, there are
    two parts: the canonical Dylan linearization, upon which the paper
    (mentioned in my original message) is improving and the actual
    improvement. The code above corresponds to the improvement. My patch
    also has parts derived from the unchanged parts of the canonical
    implementation.

You have lost me; I can't follow the scenario.

What I can say is that, in general, we do not want to incorporate
code into Emacs without a copyright assignment.

Re: Potential copyright problem in EIEIO improvement

[Jan Moringen]

On Thu, 2009-12-31 at 21:55 -0500, Richard Stallman wrote:
> Thank you for your opinion on this. Regarding the "if" part, there
> are
>     two parts: the canonical Dylan linearization, upon which the paper
>     (mentioned in my original message) is improving and the actual
>     improvement. The code above corresponds to the improvement. My
> patch
>     also has parts derived from the unchanged parts of the canonical
>     implementation.
> 
> You have lost me; I can't follow the scenario.

Sorry. Let me start over. 

I would like to contribute an improvement to EIEIO which consists of the
implementation of an algorithm (called c3 linearization) for computing
class precedence lists. My implementation in Emacs Lisp is based on an
implementation in Dylan that has been published in an academic paper
[1].

The Dylan code presented in that paper consists of two parts: the class
precedence list computation currently used in Dylan and an improved
version (the c3 linearization). Two thirds of the improved version are
identical to the old implementation. The old implementation is available
under GPL, for example in Open Dylan.

My code is derived from both parts of the Dylan code.

> What I can say is that, in general, we do not want to incorporate
> code into Emacs without a copyright assignment.

I have written all the code that would go into EIEIO and I have signed
the copyright assignment forms for both GNU Emacs and CEDET. The
copyright assignment should not be a problem. The question Eric and I
could not answer is whether incorporating my code and assigning the
copyright could lead to copyright problems because of the way that code
came into existence.

Kind regards,
Jan

[1] Kim Barrett et al.: A Monotonic Superclass Linearization for Dylan
    http://192.220.96.201/dylan/linearization-oopsla96.html

Re: Potential copyright problem in EIEIO improvement

[Richard Stallman]

Please show the whole of the Dylan code you want to adapt.
To judge this issue
we need to see the facts.

Re: Potential copyright problem in EIEIO improvement

[Jan Moringen]

On Sat, 2010-01-02 at 10:45 -0500, Richard Stallman wrote:
> Please show the whole of the Dylan code you want to adapt.
> To judge this issue
> we need to see the facts.

Sure.

The following piece of code is from the paper "A Monotonic Superclass
Linearization for Dylan". It is labeled "Appendix A: Implementation of
the Dylan Linearization" there. This code implements the Dylan
linearization *without* the improvement presented in the paper.

=== Begin Appendix A ===
define constant compute-class-linearization =
    method (c :: <class>) => (cpl :: <list>)
      local method merge-lists (reversed-partial-result :: <list>,
                                remaining-inputs :: <sequence>)

              if (every?(empty?, remaining-inputs))
                reverse!(reversed-partial-result)
              else

                // start of selection rule
                local method candidate (c :: <class>)
                        // returns c if it can go in the result now, otherwise false

                        local method head? (l :: <list>)
                                c == head(l)
                              end method head?,

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

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

                      method candidate-direct-superclass (c :: <class>)
                        any?(candidate, direct-superclasses(c))
                      end method candidate-direct-superclass;

                let next = any?(candidate-direct-superclass,
                                reversed-partial-result);
                // end of selection rule

                if (next)
                  local method remove-next (l :: <list>)
                          if (head(l) == next) tail(l) else l end
                        end method remove-next;
                  merge-lists(pair(next, reversed-partial-result),
                              map(remove-next, remaining-inputs))
                else
                  error("Inconsistent precedence graph");
                end if
              end if
            end method merge-lists;

      let c-direct-superclasses = direct-superclasses(c);
      local method cpl-list (c)
              as(<list>, all-superclasses(c))
            end method cpl-list;
      merge-lists(list(c),
                  concatenate(map(cpl-list, c-direct-superclasses),
                              list(as(<list>, c-direct-superclasses))));

    end method; // compute-class-linearization
=== End Appendix A ===

The code from Appendix A above is available (in a very similar form)
under GPL for example in Open Dylan:

=== Begin sources/dylan/class-dynamic.dylan ===
define function compute-implementation-class-precedence-list 
(c :: <implementation-class>, u :: <subjunctive-class-universe>) 
  => cpl :: <list>;
  let convert = scu-converter(u);
  local method merge-lists (partial-cpl :: <list>, remaining-lists :: <list>)
	  // The partial-cpl is in reverse order at this point.
	  if (every?(empty?, remaining-lists))
	    reverse!(partial-cpl)
	  else
	    local 
	      method unconstrained-class (s)
		let s :: <implementation-class> = scu-entry(s, u);
		local 
		  method s-in-and-unconstrained-in? (l :: <list>)
		    head(l) == s
		  end method,

		  method s-unconstrained-in? (l :: <list>)
		    head(l) == s | ~member?(s, tail(l))
		  end method;

		any?(s-in-and-unconstrained-in?, remaining-lists) 
		  & every?(s-unconstrained-in?, remaining-lists) 
		  & s
	      end method,

	      method unconstrained-class-in-superclasses (c :: <implementation-class>)
		any?(unconstrained-class, direct-superclasses(c))
	      end method;
	    
	    let next = any?(unconstrained-class-in-superclasses, partial-cpl);
	    
	    if (next)
	      local method remove-next (l :: <list>)
		      if (head(l) == next) tail(l) else l end
		    end method;
	      merge-lists(pair (next, partial-cpl),
			  map-into(remaining-lists, remove-next, remaining-lists))
	    else
	      error(make(<inconsistent-precedence-class-error>,
			 format-string: "Inconsistent precedence graph"))
	    end
	  end
	end;
  
  let c-direct-superclasses = map-as(<list>, convert, direct-superclasses(c));
  merge-lists(list(c),
              add(map(rcurry(all-iclass-superclasses, u), c-direct-superclasses),
                  c-direct-superclasses))
  
end function compute-implementation-class-precedence-list;
=== End sources/dylan/class-dynamic.dylan ===

The contribution of the paper is an improved version of the "candidate"
method. This code is called "Appendix B: Implementation of the C3
Linearization" in the paper:

=== Begin Appendix B ===
local method candidate (c :: <class>)
          // returns c if it can go in the result now, otherwise false

          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);
=== End Appendix B ===

Finally, the code I derived from Appendix A and Appendix B:

=== Begin Jan's EIEIO improvement ===
(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))

(defun eieio-c3-merge-lists (reversed-partial-result remaining-inputs)
  "Merge REVERSED-PARTIAL-RESULT REMAINING-INPUTS in a consistent order, if possible.
If a consistent order does not exist, signal an error."
  (if (every #'null remaining-inputs)
      ;; If all remaining inputs are empty lists, we are done.
      (nreverse reversed-partial-result)
    ;; Otherwise, we try to find the next element of the result. This
    ;; is achieved by considering the first element of each
    ;; (non-empty) input list and accepting a candidate if it is
    ;; consistent with the rests of the input lists.
    (let ((next (some (lambda (c) (eieio-c3-candidate c remaining-inputs))
		      (mapcar #'first
			      (remove-if #'null remaining-inputs)))))
      (if next
	  ;; The graph is consistent so far, add NEXT to result and
	  ;; merge input lists, dropping NEXT from their heads where
	  ;; applicable.
	  (eieio-c3-merge-lists
	   (cons next reversed-partial-result)
	   (mapcar (lambda (l) (if (eq (first l) next) (rest l) l))
		   remaining-inputs))
	;; The graph is inconsistent, give up
	(error "Inconsistent precedence graph"))))
  )

(defun eieio-class-precedence-c3 (class)
  "Return all parents of CLASS with direct ones in c3 order."
  (let ((parents (or (class-parents-fast class)
		     '(eieio-default-superclass))))
    (eieio-c3-merge-lists
     (list class)
     (append
      (mapcar
       (lambda (x)
	 (cons x (class-precedence-list x)))
       parents)
      (list parents))))
  )
=== End Jan's EIEIO improvement ===

I hope, this clarifies the situation. Thanks for your patience.

Kind regards,
Jan

Re: Potential copyright problem in EIEIO improvement

[Richard Stallman]

    The following piece of code is from the paper "A Monotonic Superclass
    Linearization for Dylan". It is labeled "Appendix A: Implementation of
    the Dylan Linearization" there. This code implements the Dylan
    linearization *without* the improvement presented in the paper.

That is 50 lines, which is far more than enough that we would
normally want papers.

Can we make an exception for this case?  Maybe.  I will ask a lawyer.

Which GPL versions does Open Dylan's license allow?

Re: Potential copyright problem in EIEIO improvement

[Jan Moringen]

On Sun, 2010-01-03 at 23:09 -0500, Richard Stallman wrote:
> The following piece of code is from the paper "A Monotonic
> Superclass
>     Linearization for Dylan". It is labeled "Appendix A:
> Implementation of
>     the Dylan Linearization" there. This code implements the Dylan
>     linearization *without* the improvement presented in the paper.
> 
> That is 50 lines, which is far more than enough that we would
> normally want papers.

I think, the most important part is the code in Appendix B since code
very similar to Appendix A is available in Open Dylan (I included both
in my last email). My code could have been derived from the Open Dylan
code except for the improvement presented in Appendix B.

> Can we make an exception for this case?  Maybe.  I will ask a lawyer.

Thank you for spending so much time on this.

> Which GPL versions does Open Dylan's license allow?

It is dual-licensed such that LGPL is one possible license:

=== Begin header of class-dynamic.dylan from Open Dylan ===
module:    internal
Author:    Jonathan Bachrach
Copyright:    Original Code is Copyright (c) 1995-2004 Functional Objects, Inc.
              All rights reserved.
License:      Functional Objects Library Public License Version 1.0
Dual-license: GNU Lesser General Public License
Warranty:     Distributed WITHOUT WARRANTY OF ANY KIND
=== End header of class-dynamic.dylan from Open Dylan ===

Kind regards,
Jan

Re: Potential copyright problem in EIEIO improvement

[Richard Stallman]

    I think, the most important part is the code in Appendix B since code
    very similar to Appendix A is available in Open Dylan (I included both
    in my last email). My code could have been derived from the Open Dylan
    code except for the improvement presented in Appendix B.

I'm talking about the code from Open Dylan.  That is 50 lines, and
normally we would not install 50 lines without getting papers for
them.  I will ask whether we can make an exception, once I have enough
info.

    Dual-license: GNU Lesser General Public License

Does it say what version?

Re: Potential copyright problem in EIEIO improvement

[Jan Moringen]

On Mon, 2010-01-04 at 11:23 -0500, Richard Stallman wrote:
> I think, the most important part is the code in Appendix B since
> code
>     very similar to Appendix A is available in Open Dylan (I included
> both
>     in my last email). My code could have been derived from the Open
> Dylan
>     code except for the improvement presented in Appendix B.
> 
> I'm talking about the code from Open Dylan.  That is 50 lines, and
> normally we would not install 50 lines without getting papers for
> them.  I will ask whether we can make an exception, once I have enough
> info.

So in order to derive GPLed code from the GPLed Open Dylan code and
assign the copyright of the new code to the FSF, the Open Dylan authors
have to sign papers. I wasn't aware of that. Thanks for pointing it out.

>     Dual-license: GNU Lesser General Public License
> 
> Does it say what version?

I found a license file in the Open Dylan project root directory which
says:

GNU LESSER GENERAL PUBLIC LICENSE
Version 2.1, February 1999

Kind regards,
Jan

Re: Potential copyright problem in EIEIO improvement

[Richard Stallman]

    So in order to derive GPLed code from the GPLed Open Dylan code and
    assign the copyright of the new code to the FSF, the Open Dylan authors
    have to sign papers.

Right.  However, it would be obnoxious to ask them to assign their
copyright to the FSF, because they didn't intend it as a contribution
to GNU Emacs.  Therefore, we must not ask.  That puts us in a bit of a
bind.

So I will ask our lawyers if it is ok if we use taht Dylan code
without getting papers for it.  Now I know all the facts I need to
tell them.

Thanks.

Re: Potential copyright problem in EIEIO improvement

[David Kastrup]

Richard Stallman <rms@gnu.org> writes:

>     So in order to derive GPLed code from the GPLed Open Dylan code and
>     assign the copyright of the new code to the FSF, the Open Dylan authors
>     have to sign papers.
>
> Right.  However, it would be obnoxious to ask them to assign their
> copyright to the FSF, because they didn't intend it as a contribution
> to GNU Emacs.  Therefore, we must not ask.  That puts us in a bit of a
> bind.

I think that in this case asking for a disclaimer should be more than
sufficient: after all, the code in question has been used as a template
but not used verbatim.  So at most an original code citation in the
comment should not be covered by Emacs copyright, but the resulting
Elisp code should be sufficient original expression.

But since the original code has been released under the GPL (which
one?), a separate disclaimer should likely not even be necessary: the
GPL _is_ a license to "relicense" under the GPL.

> So I will ask our lawyers if it is ok if we use taht Dylan code
> without getting papers for it.  Now I know all the facts I need to
> tell them.

Likely.

-- 
David Kastrup

Re: Potential copyright problem in EIEIO improvement

[Richard Stallman]

Our lawyer says we can use that adaptation of the code from Open Dylan.

Re: Potential copyright problem in EIEIO improvement

[Jan Moringen]

On Sat, 2010-01-30 at 16:32 -0500, Richard Stallman wrote:
> Our lawyer says we can use that adaptation of the code from Open
> Dylan.

Thank you for resolving this issue.

Eric and I can now continue to integrate the patch.

Thanks again,
Jan