Re: Potential copyright problem in EIEIO improvement

[Jan Moringen <jan.moringen@uni-bielefeld.de>]

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