[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Potential copyright problem in EIEIO improvement
From: |
Jan Moringen |
Subject: |
Re: Potential copyright problem in EIEIO improvement |
Date: |
Sun, 03 Jan 2010 19:52:07 +0100 |
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, Jan Moringen, 2010/01/01
- Re: Potential copyright problem in EIEIO improvement, Richard Stallman, 2010/01/02
- Re: Potential copyright problem in EIEIO improvement,
Jan Moringen <=
- Re: Potential copyright problem in EIEIO improvement, Richard Stallman, 2010/01/03
- Re: Potential copyright problem in EIEIO improvement, Jan Moringen, 2010/01/04
- Re: Potential copyright problem in EIEIO improvement, Richard Stallman, 2010/01/04
- Re: Potential copyright problem in EIEIO improvement, Jan Moringen, 2010/01/04
- Re: Potential copyright problem in EIEIO improvement, Richard Stallman, 2010/01/05
- Re: Potential copyright problem in EIEIO improvement, David Kastrup, 2010/01/06
- Re: Potential copyright problem in EIEIO improvement, Richard Stallman, 2010/01/30
- Re: Potential copyright problem in EIEIO improvement, Jan Moringen, 2010/01/31