5 Jun 2003 pfdietz   » (Master)

I've concluded the Dylan superclass linearization algorithm is preferable to the Common Lisp (CLOS) algorithm.

A refresher: in a hierarchy with multiple inheritance, some means must be found to determine which superclass a class should inherit entities from. One approach is to have an algorithm for totally ordering (linearizing) the superclasses ('computing the class precedence list (CPL)', as one might say in CL), and inheriting each entity from the first superclass in the list in which the entity occurs. Algorithms are allowed to reject certain hierarchies if they cannot be linearized in some acceptable way.

The CL and Dylan algorithms are similar, except that the Dylan algorithm is slightly more strict in the hierarchies it accepts. In return Dylan's orderings have the property of monotonicity: if C1 is a subclass of C2, then the linearized superclasses of C2 occur in the same order in the CPL of C1.

Why do I care about this? I was writing CL compliance tests for the class precedence orderings specified in the ANSI CL spec. To do this, I wrote a generic function with the LIST method combination, and added a method for each standardized class that return that class's name. This should yield the names of the standardized superclasses of the class of a value, in the order they appear in the CPL.

BUT... there's in general no guarantee that if some object is in type C (C a class) that it's also an instance of C. It could be an instance of a subclass of C, and that subclass could have a different CPL. Lack of monotonicity means I cannot presume the superclasses of C still occur in the specified order.

This reconfirms my belief that writing a test suite tests not only an implementation, but also a specification. Untestable requirements are bugs.

cmm: yes, that's the algorithm.

Latest blog entries     Older blog entries

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!