From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Jan Moringen Newsgroups: gmane.emacs.devel Subject: Re: Potential copyright problem in EIEIO improvement Date: Sun, 03 Jan 2010 19:52:07 +0100 Message-ID: <3504_1262544732_ZZg0O73~B6ki9.00_1262544727.3761.1636.camel@localhost.localdomain> References: <23751_1262141343_ZZg0N7E3ZcBp~.00_1262141340.11263.18.camel@localhost.localdomain> <5533_1262229939_ZZg0N6K4nOGuV.00_1262229938.3761.46.camel@localhost.localdomain> <28416_1262371970_ZZg0N5T~46u9H.00_1262371969.3761.1205.camel@localhost.localdomain> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7BIT X-Trace: ger.gmane.org 1262545780 20015 80.91.229.12 (3 Jan 2010 19:09:40 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Sun, 3 Jan 2010 19:09:40 +0000 (UTC) Cc: emacs-devel@gnu.org To: rms@gnu.org Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Sun Jan 03 20:09:33 2010 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([199.232.76.165]) by lo.gmane.org with esmtp (Exim 4.50) id 1NRVpS-0006sh-Ua for ged-emacs-devel@m.gmane.org; Sun, 03 Jan 2010 20:09:31 +0100 Original-Received: from localhost ([127.0.0.1]:50097 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1NRVpT-0006IK-ET for ged-emacs-devel@m.gmane.org; Sun, 03 Jan 2010 14:09:31 -0500 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1NRVYt-0006Zy-5y for emacs-devel@gnu.org; Sun, 03 Jan 2010 13:52:23 -0500 Original-Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1NRVYn-0006ZM-3m for emacs-devel@gnu.org; Sun, 03 Jan 2010 13:52:21 -0500 Original-Received: from [199.232.76.173] (port=45339 helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1NRVYm-0006ZJ-TP for emacs-devel@gnu.org; Sun, 03 Jan 2010 13:52:16 -0500 Original-Received: from mux1-unibi-smtp.hrz.uni-bielefeld.de ([129.70.204.65]:36131) by monty-python.gnu.org with esmtp (Exim 4.60) (envelope-from ) id 1NRVYj-0003Lb-M8; Sun, 03 Jan 2010 13:52:14 -0500 Original-Received: from pmxchannel-daemon.mux1-unibi-smtp.hrz.uni-bielefeld.de by mux1-unibi-smtp.hrz.uni-bielefeld.de (Sun Java(tm) System Messaging Server 6.3-6.03 (built Mar 14 2008; 32bit)) id <0KVO00900PR0XE00@mux1-unibi-smtp.hrz.uni-bielefeld.de>; Sun, 03 Jan 2010 19:52:12 +0100 (CET) Original-Received: from [192.168.2.102] ([92.39.21.54]) by mux1-unibi-smtp.hrz.uni-bielefeld.de (Sun Java(tm) System Messaging Server 6.3-6.03 (built Mar 14 2008; 32bit)) with ESMTPPSA id <0KVO00M0FPQYFO90@mux1-unibi-smtp.hrz.uni-bielefeld.de>; Sun, 03 Jan 2010 19:52:11 +0100 (CET) In-reply-to: X-Mailer: Evolution 2.29.3.2 X-EnvFrom: jan.moringen@uni-bielefeld.de X-PMX-Version: 5.5.1.360522, Antispam-Engine: 2.6.1.350677, Antispam-Data: 2010.1.3.184217, pmx8 X-Connecting-IP: 92.39.21.54 X-detected-operating-system: by monty-python.gnu.org: Solaris 10 (beta) X-Mailman-Approved-At: Sun, 03 Jan 2010 14:09:26 -0500 X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:119318 Archived-At: 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 :: ) => (cpl :: ) local method merge-lists (reversed-partial-result :: , remaining-inputs :: ) if (every?(empty?, remaining-inputs)) reverse!(reversed-partial-result) else // start of selection rule local method candidate (c :: ) // returns c if it can go in the result now, otherwise false local method head? (l :: ) c == head(l) end method head?, method tail? (l :: ) member?(c, tail(l)) end method tail?; any?(head?, remaining-inputs) & ~any?(tail?, remaining-inputs) & c end method candidate, method candidate-direct-superclass (c :: ) 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 :: ) 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(, all-superclasses(c)) end method cpl-list; merge-lists(list(c), concatenate(map(cpl-list, c-direct-superclasses), list(as(, 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 :: , u :: ) => cpl :: ; let convert = scu-converter(u); local method merge-lists (partial-cpl :: , remaining-lists :: ) // 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 :: = scu-entry(s, u); local method s-in-and-unconstrained-in? (l :: ) head(l) == s end method, method s-unconstrained-in? (l :: ) 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 :: ) any?(unconstrained-class, direct-superclasses(c)) end method; let next = any?(unconstrained-class-in-superclasses, partial-cpl); if (next) local method remove-next (l :: ) 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(, format-string: "Inconsistent precedence graph")) end end end; let c-direct-superclasses = map-as(, 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 :: ) // returns c if it can go in the result now, otherwise false 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); === 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