16 ms·
Generally the enum vs polymorphic class debate is actually a subset of a better known trade-off between OO style inheritance and FP style use of sum types. The
by simiones 5y ago
Generally the enum vs polymorphic class debate is actually a subset of a better known trade-off between OO style inheritance and FP style use of sum types.
The trade-off is between ease of extension in two cases:
- adding new types to the sum type / new subclasses
- adding new methods that can operate on all types / subclasses
In a classic OO design, it's easy for any client to add new subclasses that implement the same API as the existing classes. However, adding a new API means that all subclasses need to be changed.
Conversely, in an FP design, adding a new type to the sum type (a new enum value) means that all places pattern matching on the sum types (switching on the enum) need to be changed. However, adding a new operation that works with the existing types is trivial.
To give a more specific example, let's say we want to model an expression tree.
An OO design might look like this:
abstract class BaseExpression {
abstract evaluate()
subexpressions()
}
class SumExpression extends BaseExpression {
evaluate() = map(evaluate, subexpressions()).Sum()
}
class NumberExpression extends BaseExpression {
int x
subexpressions() = [x]
evaluate() = x
}
An FP design might look like
type ExpressionTree a = SumExpresssion [ExpressionTree] | NumberExpression a
evaluate :: ExpressionTree a -> a
evaluate SumExpression xs = sum map evaluate xs
evaluate NumberExpression x = x
subexpressions :: ExpressionTree a -> [a]
subexpressions SumExpression xs = map union xs
subexpressions NumberExpression x = [x]
Equivalently, an enum based design would have
enum ExprType {
Sum
Number
}
struct SumExpression {
ExprType
*void[] Subexpressions
}
struct NumberExpression {
ExprType
int x
}
evaluate(e) {
switch(e->ExprType) {
case Sum: (SumExpression)e.Subexpressions.map(evaluate).Sum()
case Number: (NumberExpression)e.x
}
}
subexpressions(e) {
switch(e->ExprType) {
case Sum: return (SumExpression)e.subexpressions
case Number: void*[]{(NumberExpression)e.x}
}
}
Now, if we want to add support for MultiplyExpression, in the OO program we add a new file and we define evaluate() for MultiplyExpression. In the FP program we have to modify the definitions of ExpressionTree, SumExpression and NumberExpression.
Conversely, if we want to add support to print an ExpressionTree, in the FP version we just add a new function in a new file and describe how to print each type of ExpressionTree. In the OO program, we need to modify the implementations of each existing BaseExpression subclass to add support for printing.
- Zababa 5y agoI think it's usually refered as "the expression problem". Here's a good post about it: https://eli.thegreenplace.net/2016/the-expression-problem-and-its-solutions/ https://eli.thegreenplace.net/2016/the-expression-problem-an.... The idea is that when you have existing data and operations on them, how can you add more data and more operations without controlling the original code. There's also a part about early and late binding. In statically typed FP programming, the compiler will warn you where you forgot enum cases when you add one. This is because this information is known at compile time. If you want to generate classes at runtime while keeping the same code, you may prefer the late-binding approach of having the class itself handle how it reacts to an operation.
- couchand 5y agoThis is called the Expression Problem because, as you allude to in your example, it comes up all the time in compilers and interpreters when dealing with expressions. If you're looking for an elegant solution (the first I've ever seen), check out the work by Kiselyov on tagless final encodings. The core idea is to invert the interface. Instead of the expression types being objects that implement an interface consist ing of operations, or the expression types being enum values and the operations being total functions of those enums, the interface is the abstract logic of the operation, and the interface methods are the expression types. Adding new operations is easy, it's a new interface implementation. Adding new expression types is easy, too. You create a new interface for the new type, and implement that interface for each compatible operation. It does require typeclasses or traits or something like that, and if you want the full power you need language support for higher-kinded types. Look at the papers for full examples, but here's a teaser in pseudocode: interface BoolLogic { fn bool(bool) -> Self; fn if(Self, Self, Self) -> Self; } struct Eval { value: Anything } implement BoolLogic for Eval { fn bool(value) -> Eval { Eval { value } } fn if(condition, consequent, alternate) -> Eval { if (conditon.value) consequent else alternate } } struct Print { text: String } implement BoolLogic for Print { fn bool(value) -> Print { let text = value.toString() Print { text } } fn if(condition, consequent, alternate) Print { let text = "if (" + condition.text + ") {" + consequent.text + "} else {" + alternate.text + "}" Print { text } } } interface NumLogic { fn num(int) -> Self fn add(Self, Self) -> Self fn eq(Self, Self) -> Self } implement NumLogic for Eval { fn num(value) -> { Eval { value } } fn add(left, right) -> Self { let value = left.value + right.value Eval { value } } fn eq(left, right) -> Self { let value = left.value == right.value Eval { value } } } fn munge<T: BoolLogic + NumLogic>() -> T { T.if(T.eq(T.add(T.nu.(2), T.num(2)), T.num(4)), T.num(42), T.num(0)) } If you're curious I'd highly recommend reading and implementing the papers yourself. Have fun writing a typechecker, it's surprisingly easy! (with HKTs...)