C3 linearization for CLOS
Tim Bradshaw
CLOS? It seems to me it should be doable via a reasonably standard
MOP.
--tim
Matthias
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.
Paul Foley
> 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>"))
Tim Bradshaw
>
> 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
Bruce Hoult
tfb+g...@tfeb.org (Tim Bradshaw) wrote:
> Paul Foley <s...@below.invalid> wrote in message
> news:<m2r7u43...@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