Why can't the Scala compiler give pattern matching warning for nonsealed classes/traits?

Question

If I use an unsealed trait or abstract class in Scala and then use pattern matching, I wonder, does the compiler not know at compile time for this particular patternmatch what possible implementations of this trait/class are available? So, if it does, could it not give pattern match warnings even though that the trait/abstract class is not sealed because he knows which types could be used, by checking all the possible dependencies/imports?

E.g. if I have an Option[A] and I do pattern matching only for Some[A] but not for None, the compiler will complain, because Option is sealed.

If the compiler can't know/resolve that, then why can't he? And if the compiler (theoretically) can do that, what are the reasons for that it is not used in Scala? Are there other languages which support that kind of behaviour?

Answer 1

Figuring out all subclasses of a class is called Class Hierarchy Analysis, and doing static CHA in a language with dynamic code loading is equivalent to solving the Halting Problem.

Plus, one of the goals of Scala is separate compilation and deployment of independent modules, so the compiler simply cannot know whether or not a class is subclassed in another module, because it never looks at more than one module. (After all, you could compile a module against the interface of some other module without that module even existing on your system!) That's why sealed requires all subclasses to be defined in the same compilation unit.

That's also one of the reasons why JVMs can compete so favorably with C++ compilers: C++ compilers are typically static compilers, so they can't in general figure out whether a method is overridden or not, and thus can't inline it. JVMs OTOH, typically are dynamic compilers, they don't need to perform CHA to figure out whether a method is overridden or not, they can just look at the Class Hierarchy at runtime. And even if at a later point in the execution of the program a new subclass comes along that wasn't there before, no big deal, just recompile that piece of code without inlining.

Note: all of this only applies within Scala. The JVM has no notion of sealed, so it is perfectly possible to subclass sealed classes from another JVM language, since there is no way to communicate this to another language. The sealed property is recorded in the ScalaSig annotation, but other languages' compilers don't take those annotations into account, obviously.

Answer 2

It can be done (at least for all classes known at compile time), it's just expensive. You'd completely destroy incremental compilation, because everything that contains a pattern match would effectively have to be recompiled every time any other file changed.

And what are you buying? It's a code smell to write pattern matches that need to change frequently when a new derived class is added. It's a violation of the open/closed principle. Use inheritance properly and you won't need to write those kinds of pattern matches. And yes, the open/closed principle also applies to functional languages without class-based inheritance. In fact between features like type classes, multimethods, and just plain higher-order functions, functional languages make extension without modification much easier.