Why is the method resolution order different from python,common lisp,...?

[thomas weidner]

Hello,

I am just learning Scala, but have experience in several other languages. Reading "Programming in Scala 3rd edition", I am a bit confused about trait inheritance. Though the author claims trait inheritance are not multiple inheritance, he may be right when he has C++ in his mind, but compared to languages like Common Lisp or Python trait inheritance in Scala is just multiple inheritance in these languages.

Nevertheless, computing the method resolution order (or class precedence list) is done differently in Scala. In CL or Python classes are ordered using two principles:

1. every class after it's superclasses (super traits)
2. If two classes appear in the same superclass list, their order is this list has to be preserved in the final class precedence list.

If these two relations induce a partial order, a linearization of this order is used as class precedence list. Scala seems to pursue a different approach, In a recursive approach it concatenates the previously constructed linearizations of all super classes in order, and just does not add any class again, which are already present. While this approach preserves property 1 from above, property 2 may be violated, for example:

class Base
trait A extends Base
trait B extends A
class Test extends Base with B with A

This results in the order Test, B, A, Base. Note that B actually is after A, although A is written after B in the superclass list of Test. Let's compare this to the same example in Python (Note that in Python the first superclass is the most important not the last one as in Scala):

class Base:pass
class A(Base):pass
class B(A):pass
class Test(A,B):pass

Entering this in the Python interpreter yields an exception: Cannot create a consistent method resolution order (MRO) for bases A, B. This is expected since A has to come before B as A is a superclass of B, but B has to come before A as A is after B in the superclass list of Test. This cycle cannot be linearized.

In my opinion the Python result is more natural and error safe as the superclass order always respects the way I specify it, if this is not possible an error occurs. In Scala, on the other hand, if a supertrait does something weird, my superclass order can get mixed and become unexpected. If I rely on the order some stacked behaviour, my code can become wrong and the error is very subtle and hard to track. (Imagine I add behaviour as a trait another trait already implements, even worse imagine this changes in some library version).

Nevertheless, if my supeclasses can be linearized in the Python sense, the obtained order seems to match the order Scala obtains for the same hierarchy, but I am not quite sure about this, I would have to prove this on paper.

So my question is: Why is Scala more relaxed than Python or Common Lisp constructing the class precedence list? Is there a good reason or is it just the way someone implemented it once (maybe because he was unaware of the issue)? Will this algorithm change to the Python version in the future (2.12/13/...)?

Thanks for reading my post,
Thomas

[martin odersky]

It is indeed a subtle distinction. I was well aware of the difference
when I designed Scala's linearization. It's true that Scala's
linearization does not satisfy property (2), so it not a "C3
linearization". However, it satisfies another property instead which
is not shared by CL or Python:

3. The linearization of the superclass of C is always a prefix of the
linearization of C.

In other words, subclassing of *classes* (not traits) does not change
the linearization order as observed by the superclass. This is
important for good code generation in the presence of separate
compilation. Only that way we can compile the linearization order of a
class once, without regard how it is inherited.

So, in a sense Scala has a distinction between classes and traits here
that CL and Python do not have. Classes are guaranteed to have the
same linearization order in all contexts, traits do not (in fact for
traits the observed linearization order can even flip, as you
noticed).

So, it's all a tradeoff in the end. I don't think the linearization
order of Scala will change at this point. And I have not yet come
across someone that reported having hit with the potential problem you
mention in practice. But of course, people might have had the problem
and not reported it.

Cheers

- Martin

> --
> You received this message because you are subscribed to the Google Groups
> "scala-language" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to scala-languag...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.



--

Martin Odersky
EPFL and Lightbend

[Lex Spoon]

As a developer, the sweet spot for writing a mixin is for cases where the linearization order doesn't matter. If the order matters, you are likely making things hard to reason about on whoever has to maintain that code next.

A case in point is the Ordering trait. It's really handy for developers, and it requires mixins with concrete methods.

Another example is a hypothetical Memoizing trait. Such a trait needs a field to work correctly. So you need almost any language feature to be possible to embed in a mixin.

As a parting note, while linearization systems seem to be very useful within a broad range of designs, the older style of non-linearized super() calls seem categorically worse. Both C++ and Java (with its default methods) use the older style. In such systems, the developer often ends up with an impossible choice. Linearization is a big step forward, whichever variant of it is used.

Lex Spoon