Re: class precedence list

From: Anthony Beurive' <beurive_at_labri.u-bordeaux.fr>
Date: Wed, 3 Nov 1999 21:55:57 +0100

Hi!

...
> I have tried your algorithm for a while now and I have even integrated
> it in my version of STklos. It is far better than the original STklos
> algorithm. However there are points which are not clear for me (they
> are all related with "transitivity edge")
>
> For instance, when you define
>
> (define (cpl C) (map class-name (class-precedence-list c)))
>
> (define-class B () ())
> (define-class DB (B) ())
> (define-class WB (B) ())
> (define-class EL (DB) ())
> (define-class SMH (DB) ())
> (define-class PWB (EL WB) ())
> (define-class SC (SMH) ())
> (define-class P (PWB SC DB WB) ()) ; preferring DB over WB
>
> (cpl p) ==> (p pwb sc el smh db wb b <object> <top>)

Indeed, the above example is confusing. By (define-class P (PWB SC DB
WB) ()), everyone reads: "the direct superclasses of P are PWB, SC,
DB, and WB, in that very specific order." But I gave this example
after the example corresponding to Figure 2 in the aforementioned
paper. Let me recall it:

  (define-class B () ())
  (define-class DB (B) ())
  (define-class WB (B) ())
  (define-class EL (DB) ())
  (define-class SMH (DB) ())
  (define-class PWB (EL WB) ())
  (define-class SC (SMH) ())
  (define-class P (PWB SC) ())

In which case:

  (cpl p) ==> (p pwb sc el wb smh db b <object> <top>)

Here, WB comes before DB. Following that, what I mean with
(define-class P (PWB SC DB WB) ()) is: "ok, the direct superclasses of
P are PWB and SC, and obviously DB and WB are superclasses of at least
one of PWB and SC, and WB will monotonically come before DB; but I
really prefer DB over WB, even though the result is no more monotonic;
and oh yes! it still should be consistent with the class hierarchy."
Enough to say, this meaning (which corresponds to how my algorithm
currently works) differs from the previous one :-)

> As stated in the paper, using a transitive edge can be used to have
> fine control over the inheritance mechanism. It seems to me that it
> should be
> (p pwb sc db wb ...)
>
> I suppose that we can easily be non monotonic in this case, but since
> this is the user which has fixed the inheritance to use, it is
> probably a good thing to not change his/her choices. Of course it is
> always possible to change explicitly the cpl by hand but it is probably
> not suitable for common uses. What do you think of that?

What you suggest is: (p pwb sc db wb el smh b <object> <top>). This
result is not monotonic. Unfortunately, neither is it consistent with
the class hierarchy, so it breaks the first rule of class precedence.
In the paper, the authors *never* break that rule, even when they use
transitivity edges (e.g., Figure 4) that break monotonicity.

IMHO, it is a good policy never to break the first rule. What if a
method "f" calling (next-method) is defined for DB and for EL?

BTW, as far as the user knows exactly what he/she does, it is possible
to allow him to break monotonicity *and* the first rule. (Maybe we
could warn him/her in such cases.)

Obviously, we could have both algorithms: one to allow monotonicity
breaks only, and one to allow first rule breaks also. This may be
provided by new stklos procedures.

What is your opinion?

> BTW, I have tried to modify your algorithm for taking into account
> this and was not able to do so without breaking the rest. Should it be
> easy to modify it to do so?

Yes, I think it is. Only the start condition should be changed. The
algorithm follows. (Actually, I just tried it on the above examples.)

What do you mean by "breaking the rest"? Do you mean, as I guessed,
the body of the algorithm?

Thank you for your interest!

Stay in touch!
              ,
Anthony BEURIVE

--------------------------------------------------------------------------------

(define (compute-cpl class)

  (define (reduce sequences cpl)
    (define (aux sequence)
      (if (and (pair? sequence) (memq (car sequence) cpl))
          (aux (cdr sequence))
          sequence))
    (map aux sequences))

  (define (delete-null-lists sequences)
    (if (pair? sequences)
        (let ((first (car sequences)))
          (if (pair? first)
              (cons first (delete-null-lists (cdr sequences)))
              (delete-null-lists (cdr sequences))))
        '()))

  (define (select-candidate candidate sequences)
    (if (pair? sequences)
        (and (not (memq candidate (cdr (car sequences))))
             (select-candidate candidate (cdr sequences)))
        candidate)) ; Selected candidate.

  (define (filter-candidates candidates sequences)
    (if (pair? candidates)
        (or (select-candidate (car candidates) sequences)
            (filter-candidates (cdr candidates) sequences))
        #f)) ; No valid candidate (inconsistency).

  (define (next-class sequences)
    (let ((candidates (map car sequences)))
      (or (filter-candidates candidates sequences)
          (car candidates)))) ; Arbitrarily break the inconsistency.

  (define (step cpl sequences)
    (if (pair? sequences)
        (let ((new-cpl (cons (next-class sequences) cpl)))
          (step new-cpl (delete-null-lists (reduce sequences new-cpl))))
        (reverse cpl)))

  (let* ((supers (slot-ref class 'direct-supers))
         (beginning-cpl (reverse (cons class supers)))
         (super-cpls (map (lambda (super) (slot-ref super 'cpl)) supers)))
    (step beginning-cpl (delete-null-lists (reduce super-cpls beginning-cpl)))))
Received on Wed Nov 03 1999 - 21:56:10 CET