> // thanks to inheritance...

Ah ha! You're totally right. I totally forgot about using inheritance to deal with overlapping patterns even though I use it all the time in Java (you could do the same overlap with open unions, but there's other ergonomic reasons you don't want to do that if you have exhaustiveness checking.)

> In an OO language, the reason you'd prefer the Visitor pattern to downcasting is that it allows extending behavior by simply declaring new subtypes, instead of having to edit the central evaluator. This is why I keep insisting that the Visitor pattern is about double virtual dispatch, not about discriminated unions.

I don't think that's true. If you give up statically checked combinations I don't think you need double dispatch at all.

Here's a version that does everything with downcasting (and the accompanying error). One class has disappeared altogether because we don't need them anymore (ComplexExpression) and we don't need any classes for the evaluators (other than a container to hold them as a sort of utility class with a bunch of static methods). And we don't have visitors at all.

And it represents Addition(Multiplication(1, 2), 3) just fine.

Am I missing something here?

// ------ BEGIN : In some external library

interface Expression { // This could be empty
}
record Literal(int n) : Expression {}
record Addition(Expression x, Expression y) : Expression {}

// Your evaluator doesn't even need to be a true class anymore and can just be
// a bag of static methods
// You could if you wanted to, but there's isn't a lot of value
class BuiltInEvaluators {
public static string StringEvaluator(Expression expression) {
switch(expression) {
case Literal literal: return literal.n.ToString();
case Addition addition: return $"{StringEvaluator(addition.x)} + {StringEvaluator(addition.y)}";
// You could remove this boilerplate if you wanted by wrapping this in a true class
// and then throwing the exception in a wrapper method
default: throw new ArgumentException("Expression incompatible with evaluator!");
}
}
public static int ExecutionEvaluator(Expression expression) {
switch(expression) {
case Literal literal: return literal.n;
case Addition addition: return ExecutionEvaluator(addition.x) + ExecutionEvaluator(addition.y);
default: throw new ArgumentException("Expression incompatible with evaluator!");
}
}
}
// ------- END : No longer in some external library

// ------- BEGIN : My own code
record Multiply(Expression x, Expression y) : Expression {}

class MyOwnEvaluators {
public static string ExtendedStringEvaluator(Expression expression) {
switch(expression) {
case Multiply multiply: return $"{ExtendedStringEvaluator(multiply.x)} * {ExtendedStringEvaluator(multiply.y)}";
case Expression x: return BuiltInEvaluators.StringEvaluator(x);
default: throw new ArgumentException("Expression incompatible with evaluator!");
}
}
public static int ExtendedExecutionEvaluator(Expression expression) {
switch(expression) {
case Multiply multiply: return ExtendedExecutionEvaluator(multiply.x) * BuiltInEvaluators.ExecutionEvaluator(multiply.y);
case Expression x: return BuiltInEvaluators.ExecutionEvaluator(x);
default: throw new ArgumentException("Expression incompatible with evaluator!");
}
}
public static string HexadecimalEvaluator(Expression expression) {
switch(expression) {
// Our only interesting case
case Literal l: return l.n.ToString("x");
case Expression x: return ExtendedStringEvaluator(x);
default: throw new ArgumentException("Expression incompatible with evaluator!");
}
}
}
// ------- END : My own code