C3 superclass linearization MRO

The C3 Method Resolution Order from A Monotonic Superclass Linearization for Dylan (1996) is increasingly popular. You can use it in CL via the CLOS MOP.

The comp.lang.lisp C3 linearization for CLOS thread from 2004 contains the following code by Paul Foley. There's also another version dylan.lisp in Paul Foley.

(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)))

Other

On scheme, c3 can be used with tinyclos.

Topics: MOP document

CLiki pages can be edited by anyone at any time. Imagine a fearsomely comprehensive disclaimer of liability. Now fear, comprehensively