Let's build from partial solutions using the Scala language, then end with Haskell.
Add Function but not Case
Given a preexisting supertype Interface and subtype Case, with a function.
/*sealed */trait Interface
case class Case extends Interface
object function {
def apply : Interface => … = { case Case … case _ => error }
}
Without modifying the preexisting code above, below a function2 can be added to the preexisting subtype Case (and potentially to a new subtype Case2).
But a new subtype Case2 can't be added to the pattern matching of the preexisting function above. Thus a runtime typing error for the default case in function above would occur if we create the new subtype Case2 below (thus violating the static type requirement of the Expression Problem).
The runtime typing error is eliminated by declaring above sealed trait Interface, which would generate a compiler error if the case class Case2 extends Interface declaration is attempted below.
// case class Case2 extends Interface
object function2 {
def apply : Interface => … = { case Case … /*case Case2 … */case _ => error }
}
Add Case but not Function
Given a preexisting supertype Interface and subtype Case, with a function.
trait Interface {
def function : …
}
class Case extends Interface {
override def function : …
}
Without modifying the preexisting code above, below subtyping can add a new subtype Case2 to the preexisting supertype Interface, and it can add a new Interface2 and function2 to the new subtype Case2 but not to the preexisting subtype Case above.
trait Interface2 {
def function2 : …
}
class Case2 extends Interface with Interface2 {
override def function : …
override def function2 : …
}
Immutable Partial Solution
Given the preexisting subtype Case is an immutable algebraic type.
class Case( val field ) extends Interface {
override def function : …
}
Without modifying the preexisting code above, below a conversion to a subtype of Case can add function2.
class CaseWithInterface2( field ) extends Case( field ) with Interface2 {
override def function2 : …
}
implicit def convert : Case => CaseWithInterface2
= (x) => new CaseWithInterface2( x.field )
Any function that is going to call function2 must be supplied an argument that is a subtype of an Interface with Interface2, or a Case which can be implicitly converted.
With some compiler and VM tricks, it might not even be necessary to create a copy of the fields to view a Case as a CaseWithInterface2. I have had some private discussions with Andrey Breslav about this. Basically the vtable needs to swappable and orthogonal to the data fields of the class.
However, there is no surjective mapping (i.e. see the error case below) from Interface to Interface with Interface2, because in order to map it, Interface will need to be decomposed at runtime into its infinite possible runtime concrete implementations.
implicit def convert : Interface => Interface with Interface2 =
{
case x : Case => x
case x : Case2 => x
case _ => error
}
Mutable Partial Solution
Note that a mutable Case couldn't be copied to a subtype CaseWithInterface2 because the mutable state may not be referentially transparent (e.g. open file handle, closure in stored function, etc). Instead it would be wrapped in an adapter pattern class, which has the performance drawback that all methods must be doubly-dispatched. And any inheritance tree of Case is hidden in the wrapper.
As with the immutable solution, it is possible to subtype every type in the inheritance tree below and including the type that is extended with a new method (e.g. trait Exp[1]). Scala facilitates this pattern[1].
But the problem remains of how to adapt a runtime object of the preexisting type Case to the extended subtype CaseWithInterface2. Scala's implicit views don't help, because the adaption problem remains, regardless that views are also not a bijective contract.
The issue of a default case in new methods, applies because for example an Interface might not have a conversion defined for the concrete class of the object referenced at runtime, as shown in the previous section.
One strategy is that every function that wants to interopt can input the union type, e.g. of Interface ∨ (Interface with Interface2) (or the boxed Either[Interface,Interface with Interface2]), and provide a legacy functionality for Interface or return None (where None is analogous to a default case).
There is simply no way of avoiding that if there is virtual inheritance, and the family of possible subtypes is open, then there is no way to add functions that won't have a default case, and interopt fully. You will see this rule holds true for Haskell in the next section, as it gives up virtual inheritance in order to get global compile-time detection (as a compile error) of these default cases.
[1] Independently Extensible Solutions to the Expression Problem, Zenger, Odersky, section 3.3 Operation Extension.
Typeclass Solution Can't Virtually Inherit
Haskell's class (a.k.a. typeclass) and data are roughly analogous to Java's interface and class respectively. A typeclass declaration can inherit from one or more typeclass(es), e.g. (Super1 x, Super2 x) => class Sub x.
The data type specifies the immutable field(s), if any, for each named constructor and optionally includes multiple constructors. The name of each constructor is analogous to a distinct Java class. Thus data type doesn't define method functions. The method signatures are declared in the typeclass and an instance attaches a typeclass and provides the implementation for a data type.
class Interface x where
function :: x -> …
data Case = Case field
instance Interface Case where
function (Case field) …
Without modifying the preexisting code above, below employing an instance declaration, a new function2 can be added to a new Case2 and preexisting Case data types, declaring each to be a subtype of a new typeclass Interface2.
class (Interface x) => class Interface2 x where
function2 :: x -> …
instance Interface2 Case where
function2 (Case field) …
data Case2 = Case2 -- constructor with no field
instance Interface2 Case2 where
function Case2 …
function2 Case2 …
The new Interface2 has been inserted into the inheritance hierarchy between the preexisting supertype Interface and subtype Case, yet this typeclass pattern[2] allows for “ separate compilation ” (i.e. doesn't require recompilation of the preexisting Interface and Case), because in Haskell an interface isn't attached to the runtime object (of a data type). There is no runtime VTable dispatch and all function calls are statically resolved at compile-time.
This flexibility is available because Haskell can't do virtual inheritance.
Thus, lists elements cannot be heterogeneously subtyped, without complex constructions such as the non-extensible existential types, convoluted HList[3], or union types.
Also, for example an Ord(ering) of Int “ can only be done one way ”. An OrdDivisible can't be inserted in the inheritance hierarchy between a supertype Ord and subtype Int (to provide an alternative implementation of the methods of Ord). Thus an Int can't be an argument for a function that expects a parameter of type OrdDivisible. This breaks compositionality, which is afaik one possible reason some functions in the Haskell Prelude have boilerplate (multiple definitions) to handle specific types.
“ A typeclass declaration can inherit from one or more typeclass(es),
e.g. (Super1 x, Super2 x) => class Sub x. ”
This is a compile-time constraint on the type parameter x, not runtime virtual inheritance, i.e there is no (cf. “ such as a ” ) VTable.
(Tangentially, where the => constrains a type parameter of a data type, it is roughly analogous to Scala's >: upper bound.)
To achieve this, the multiple inheritance of interface must flatten to a single implementation and not even single-inheritance of implementations.
In addition to providing the benefit of “ separate compilation ” of extension, this eliminates (compile-time and runtime) ambiguity caused by overloading, thus facilitating global type inference and the performance benefit of eliminating invokevirtual (respectively).
And a significant violation of single-point-of-truth in Haskell, is type parameter bounds for subtypes must match those of the supertype interface, i.e. the type parameter of the subtype may not have a more restrictive bound[4].
[2] Software Extension and Integration with Type Classes, Lämmel, Ostermann, section 2.4 The expression problem.
[3] Software Extension and Integration with Type Classes, Lämmel, Ostermann, section 4.4 Explicit vs. implicit subtyping.
[4] Generics of a Higher Kind, Moors, Piessens, Odersky, section 7.3 Exceeding type classes.
