From: Tim Bradshaw
Subject: C3 linearization for CLOS
Date: 
Message-ID: <fbc0f5d1.0404290719.3ae02b21@posting.google.com>
Has anyone done an implementation of Dylan's C3 linearization for
CLOS?  It seems to me it should be doable via a reasonably standard
MOP.

--tim
From: Matthias
Subject: Re: C3 linearization for CLOS
Date: 
Message-ID: <36wr7u5onpc.fsf@hundertwasser.ti.uni-mannheim.de>
··········@tfeb.org (Tim Bradshaw) writes:

> Has anyone done an implementation of Dylan's C3 linearization for
> CLOS?  It seems to me it should be doable via a reasonably standard
> MOP.

In the scheme world there's a short one for TinyCLOS:
http://www.call-with-current-continuation.org/eggs/c3.html
But I don't know how it relates to MOP.
From: Paul Foley
Subject: Re: C3 linearization for CLOS
Date: 
Message-ID: <m2r7u436yq.fsf@mycroft.actrix.gen.nz>
On 29 Apr 2004 08:19:07 -0700, Tim Bradshaw wrote:

> Has anyone done an implementation of Dylan's C3 linearization for

It's not "Dylan's C3 linearization"; Dylan doesn't use it.  (Python
does, though)

> CLOS?  It seems to me it should be doable via a reasonably standard
> MOP.

Yes.  I could have sworn I posted this here a couple of times now, but
Google can't find it...


(defclass dylan-class (standard-class) ())

(defun dylanesque-cpl-computer (class tie-breaker)
  (let* ((supers (mop:class-direct-superclasses class))
	 (classes (list* class supers))
	 (constraints (mapcar #'cons (list* class supers) supers)))
    (dolist (cpl (mapcar #'mop:class-precedence-list supers))
      (setf classes (append cpl classes))
      (setf constraints (nconc (mapcar #'cons cpl (cdr cpl)) constraints)))
    (setf classes (delete-duplicates classes))
    (setf constraints (delete-duplicates constraints :test #'equal))
    (kernel::topological-sort classes constraints tie-breaker)))

(defmethod mop:compute-class-precedence-list ((class dylan-class))
  (dylanesque-cpl-computer class #'kernel::std-cpl-tie-breaker))

(defmethod mop:validate-superclass ((class dylan-class)
				    (new-super pcl::standard-class))
  t)

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(defclass c3-class (standard-class) ())

(defun c3-tie-breaker (free-classes rev-cpl)
  (dolist (super (mop:class-direct-superclasses (car (last rev-cpl))))
    (dolist (item free-classes)
      (when (member item (mop:class-precedence-list super))
	(return-from c3-tie-breaker item)))))

(defmethod mop:compute-class-precedence-list ((class c3-class))
  (dylanesque-cpl-computer class #'c3-tie-breaker))

(defmethod mop:validate-superclass ((class c3-class)
				    (new-super pcl::standard-class))
  t)

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; A test case which is non-monotonic under CLOS rules
;; The CPL for C-PEDALO should be
;;   C-PEDALO, C-PEDAL-WHEEL-BOAT, C-ENGINE-LESS, C-WHEEL-BOAT,
;;   C-SMALL-CATAMARAN, C-SMALL-MULTIHULL, C-DAY-BOAT, C-BOAT, ...
;; The CPL for D-PEDALO should be
;;   D-PEDALO, D-PEDAL-WHEEL-BOAT, D-ENGINE-LESS, D-SMALL-CATAMARAN,
;;   D-SMALL-MULTIHULL, D-DAY-BOAT, D-WHEEL-BOAT, D-BOAT, ...
#+(or)
(progn
  (defclass c-boat () ())
  (defclass c-day-boat (c-boat) ())
  (defclass c-wheel-boat (c-boat) ())
  (defclass c-engine-less (c-day-boat) ())
  (defclass c-small-multihull (c-day-boat) ())
  (defclass c-pedal-wheel-boat (c-engine-less c-wheel-boat) ())
  (defclass c-small-catamaran (c-small-multihull) ())
  (defclass c-pedalo (c-pedal-wheel-boat c-small-catamaran) ())

  (defclass d-boat () ()                             (:metaclass dylan-class))
  (defclass d-day-boat (d-boat) ()                   (:metaclass dylan-class))
  (defclass d-wheel-boat (d-boat) ()                 (:metaclass dylan-class))
  (defclass d-engine-less (d-day-boat) ()            (:metaclass dylan-class))
  (defclass d-small-multihull (d-day-boat) ()        (:metaclass dylan-class))
  (defclass d-pedal-wheel-boat (d-engine-less d-wheel-boat) ()
						     (:metaclass dylan-class))
  (defclass d-small-catamaran (d-small-multihull) () (:metaclass dylan-class))
  (defclass d-pedalo (d-pedal-wheel-boat d-small-catamaran) ()
						     (:metaclass dylan-class)))

;; A test case for the C3 ordering
;; The CPL for C-EDITABLE-SCROLLABLE-PANE should be
;;   C-EDITABLE-SCROLLABLE-PANE, C-SCROLLABLE-PANE, C-EDITABLE-PANE,
;;   C-PANE, C-EDITING-MIXIN, C-SCROLLING-MIXIN, ...
;; The CPL for X-EDITABLE-SCROLLABLE-PANE should be
;;   X-EDITABLE-SCROLLABLE-PANE, X-SCROLLABLE-PANE, X-EDITABLE-PANE,
;;   X-PANE, X-SCROLLING-MIXIN, X-EDITING-MIXIN, ...
#+(or)
(progn
  (defclass c-pane () ())
  (defclass c-scrolling-mixin () ())
  (defclass c-editing-mixin () ())
  (defclass c-scrollable-pane (c-pane c-scrolling-mixin) ())
  (defclass c-editable-pane (c-pane c-editing-mixin) ())
  (defclass c-editable-scrollable-pane (c-scrollable-pane c-editable-pane) ())

  (defclass x-pane () ()                             (:metaclass c3-class))
  (defclass x-scrolling-mixin () ()                  (:metaclass c3-class))
  (defclass x-editing-mixin () ()                    (:metaclass c3-class))
  (defclass x-scrollable-pane (x-pane x-scrolling-mixin) ()
						     (:metaclass c3-class))
  (defclass x-editable-pane (x-pane x-editing-mixin) ()
						     (:metaclass c3-class))
  (defclass x-editable-scrollable-pane (x-scrollable-pane x-editable-pane) ()
						     (:metaclass c3-class)))


-- 
Allwissend bin ich nicht; doch viel ist mir bewisst.            -- Goethe

(setq reply-to
  (concatenate 'string "Paul Foley " "<mycroft" '(··@) "actrix.gen.nz>"))
From: Tim Bradshaw
Subject: Re: C3 linearization for CLOS
Date: 
Message-ID: <fbc0f5d1.0405030404.21d33b1c@posting.google.com>
Paul Foley <···@below.invalid> wrote in message news:<··············@mycroft.actrix.gen.nz>...

> 
> It's not "Dylan's C3 linearization"; Dylan doesn't use it.  (Python
> does, though)

I was confused...  Is the received wisdom that C3 is better than the
linearization that Dylan does use?  It looks to me from the paper on
it by Barrett et al that they think it probably is better but diverges
from standard CLOS too far.

Thanks for the code (I haven't played with it yet, but will, and I
guess I can then decide for myself which one I think is better...)

--tim
From: Bruce Hoult
Subject: Re: C3 linearization for CLOS
Date: 
Message-ID: <bruce-31F885.09131904052004@copper.ipg.tsnz.net>
In article <····························@posting.google.com>,
 ··········@tfeb.org (Tim Bradshaw) wrote:

> Paul Foley <···@below.invalid> wrote in message 
> news:<··············@mycroft.actrix.gen.nz>...
> 
> > 
> > It's not "Dylan's C3 linearization"; Dylan doesn't use it.  (Python
> > does, though)
> 
> I was confused...  Is the received wisdom that C3 is better than the
> linearization that Dylan does use?  It looks to me from the paper on
> it by Barrett et al that they think it probably is better but diverges
> from standard CLOS too far.

I've been wanting to change Gwydion d2c to use C3 for some time, but 
incompatability with Functional-Developer has been a concern.

Fun-Dev uses the linearization described in the DRM (as does d2c), but 
in the event of ambiguity falls back to the CLOS method for 
compatability with some of their legacy code ported from CLOS.

Now that Fun-Dev is open-sourced and in the Gwydion cvs server we can 
consider changing both at once.

I haven't looked at the details for a while, but I think C3 helps make 
fast table-based GF dispatch easier.

-- Bruce
comp.lang.lisp / 2004 / apr