Refactoring class hierarchy into ADT

I started off with everything in one file, and I found it really confusing. Some of the methods contain delicate logic, and implementing an ADT which is many hundreds of lines long makes the file difficult to understand, and difficult to check by hand, ie., have I implemented all the methods I need for each of the classes. Additionally, having one class per leaf class, makes testing easier, as I also have one testing file per leaf class. I can easily find the tests, and I can easily figure out whether I’ve fully tested each of the classes.

WRT OO, I’m sure there are many ways to think about the problem, but in my case I have a limited number of primitives, and each of the primitives implements several methods. (I refer to these methods as a calculus, i.e., a set of operations which are available to instances, including how those operations interact) There is some behavior which is common to all the leaf classes, and there is behavior which distinguishes them, and in some cases those overlap. I.e., I have reduction rules which start attempting leaf specific reduction, and finally resort to more general reduction. In my thinking this is OO in nature—thinking from specific to general.

One reason that exhaustive pattern matching is really useful is that I define binary methods on many pairs of leaf classes. Since Scala lacks multiple dispatch, I have to include exhaustive pattern matching in several different classes. So I’d like to be sure that I’ve accounted for every combination of X x Y which X is a leaf class and Y is a leaf class.

ahh, I see your technique for emulating initialization arguments on traits. Perhaps this is the trick which Scala 3 uses?

So I see how to work around the lack of initialization parameters for traits. But I don’t see how this technique allows me to have a sealed class, and also put the implementations into their individual files. It seems like I’ll still need each leaf case class to inherit from two different classes 1) the …Impl class and also the sealed class. Right?

Yes, exactly.

You need both, that is my point.
Make everything a trait or a final class object.

And follow everything else mentioned in my other post, that way you can have an ADT splitted in many files.

So whats the advantage of avoiding abstract classes? I didn’t understand the motivation for doing that.

Because that seemed to be the root of your problem, that plus linearization order.

If all are traits, you an control the linearization order easily…

Ah no, scratch that, you need to override methods of the parent trait in the implementation traits.

Hum, no idea then, sorry.
It seems Scala tries very hard to avoid your design.

Yes, you commented earlier about how to split an ADT into separate files. I didn’t understand your concept at that time, as it is also using packages in a way I found confusing. I abandoned the attempt for several weeks until I thought about the scheme which is explained in the original post. I see now that your suggestion here was less complicated than I originally feared when I read it several weeks ago.

Many things in informatics are really complicated and confusing until you understand them, then they are easy.

I don’t think Scala tries to avoid my design. It is just that not many people understand the class precedence order. In CLOS we write OO code depending on the order of most specific to least specific, and relying on the fact that it works as specified. Two principles, a method on a class is more specific than a method on any of its superclasses. A method on a class mentioned earlier in a multiple inheritance list is more specific than one appearing later. I.e, if A inherits from X and Y in that order, then methods on X are more specific than methods on Y if the object is an A. and if B inherits from Y and X in that order, then methods on Y ore more specific than those on X if the object is a B.

In this case, even though I don’t understand the order Scala implements, it seems to work for my situation. The most specific and the least specific methods are intuitive. Just the intermediate methods are not.

No I do not mean about linearization, I mean about the fact that you need that, plus sealed guarantees, plus splitting into multiple files.

Your solution while apparently provides what you want, actually leaves the door open to external users to override things which may or may not be desired.
You may control that thought access control though.

…but why should an ADT be many hundreds of lines long? :slight_smile:

There’s the “OO” way where you have a hierarchy with classes implementing traits through methods. The traits specify the complete API surface of the implementing classes, and code for all responsibilities goes into the concrete class itself.

Then there’s the “FP” way using an ADT. Behavior is implemented by pattern matching inside external functions or type classes. Code is organized by concerns - there’ll be one file for rendering the ADT, one for evaluating, etc., where each file will contain the implementations for all the ADT’s constructors.

So, among other differences, that’s two different ways of organizing code hierarchically - by “dispatchee” or by concern. Which leaves me wondering… If you want the OO style, why have an ADT (in particular: a sealed trait) at all? Whatever concrete class implements the trait(s) in a semantically sound way could be welcome. OTOH, if you want an ADT, why not go all in and implement all (or most) functionality externally via pattern matching, leaving you with a small code base for the core ADT as a side effect?

Of course you can mix and match - Scala is a hybrid language, after all. :slight_smile: But this may introduce accidental complexity overhead just for balancing/merging the two approaches and require tradeoffs - e.g. in code organization. (Note that this usually shouldn’t be that much of an issue when mixing OO and FP approaches at different levels/layers of the code base.)

I don’t yet see how, although I’m not claiming one way or another. How can the behavior of my sealed class be changed by other applications making some classes of abstract classes or traits, especially since I’m not inheriting any of their application code. I.e., allowing someone to inherit from my classes into their on applications, wont have any effect on my sealed ADT’s behavior. Right?

Sorry, I don’t yet see the problem.

An example let’s assume there are three leaf classes. And suppose I want to specify the behavior of a method foo which for all the classes, and further suppose that foo can take as argument an instance of any of the leaf classes.

A.foo(A), A.foo(B), A.foo(C)
B.foo(A), B.foo(B), B.foo(C)
C.foo(A), B.foo(C), C.foo(C)

So in my implementation in the foo method of the class A, I want to use pattern matching on the argument, and I’d like the compiler to tell me whether I’ve missed a case. Especially if I add another leaf class later.

The ADT itself no, but the implementation classes and the parent abstract class are open to external overriding. So at the end, it seems that won’t be a problem if you never ask for the parent abstract class but just for the parent sealed trait, and you may hide everything from externals through access control.

So yeah, after a second look, it does seems that your code is correct. It just feels weird, like it feels like the code the compiler of a higher level language would generate :slight_smile: (maybe Scala 3 does something similar with trait parameters?).
Actually, it is like my own suggestion just with additional tricks to allow parameters in the implementations and overriding parent methods; I would guess that if someday the compiler would support parameters on traits and multi-file ADTs it could generate code like this.

I would just again said the same as @sangamon your design feels like a complex hybrid, but whatever floats your boat.

each of the leaf classes implement several methods, some of which are delicate. The code is sometimes lengthy. When multiple classes share such code, I try to move that code up into the common parent class and make use of super.foo()

I agree. finding the right abstraction to make code correct, extensible, maintainable and testable is difficult, and may require several iterations. Often the implementation language provides some tools to make the job easier, sometimes the language’s feature become obstacles for the application to overcome.

Actually, what is the difference between an ADT and a sealed class? Perhaps, I shouldn’t call my construction an ADT, but rather just call it a sealed class? I’m not really relying on its algebraic properties, but only is closed-ness property.

ADT is an abstract concept that doesn’t have a direct representation in Scala, sealed classes/traits is a Scala language feature often used (in conjunction with others) to express this concept.

I was referring the difference between class/object (includes behavior, OO dispatch) and data type (no intrinsic behavior, pattern matching dispatch). Given that they imply different approaches to overall code organization, it shouldn’t come as a surprise if they don’t complement each other perfectly within one single “type family”.

1 Like

Yes, that is my understanding as well. So perhaps I should not refer to my construction as an ADT, but rather simply as a sealed class hierarchy. Referring to it as an ADT will lead to confusing as I’m not depending on any of the other algebraic properties an ADT implies.

More than what are properties of an ADT, in Scala it is common to split data from logic and sealed traits + case classes are commonly used to model data.

Whereas, you have a more OOP approach of mixing data and computation in the same entity.

I’m not really sure how to think about Boolean algebra in terms of data and logic. There is a very small amount of data. However, the logic is a mixture of mathematical correctness tempered with attempt to aid human understanding, testability, and not too badly performing.

I thought I would report back on this refactoring effort. I managed to refactor my code into a set of abstract classes (could have also been traits I supposed) and a sealed class having a small number of final case classes.

It was an interesting exercise, and I learned quite a lot about Scala’s concept of type-oriented programming. However, in the end, I think I will abandon this branch. There were indeed a few places I found where my pattern matching was non-exhaustive. However, to do this I had to do a lot of extra work, and I think the code is far less readable. Introducing extra classes just to satisfy the compiler, does not seem like an over all win.

One problem that kept happening was the following.
I have one abstract class, SimpleTypeDA, and a sealed class SimpleTypeD which extends it.
I, the programmer know, that every object of type SimpleTypeDA is also of type SimpleTypeD, the compiler does not know this. This mean I have to put in extra cases of either ??? or explicit exception raising, which makes the code obfuscated, or even works I have to pattern match SimpleTypeDA against a singleton case SimpleTypeDA to make the return value be sufficiently specific.

In the end, my conclusion, admittedly from one experiment, is that the Scala restriction that a sealed class can only be extended in a single file is annoying and counter productive. There ought to be some other mechanism such as perhaps allow extension within the same package, or within the same directory. Forcing code into a single file is unfortunate.

It would be great if sealed class hierarchies could be refactored across multiple files.