> Those don't really count though. Heck if you allow that I can write the code way shorter in true Haskell (not pseudo-Haskell) as well.
We could get rid of those base cases; we would then have to make ComplexExpression not a subtype of ExpressionOpen, and that in turn would mean we can't extend any of the extended evaluators from the old evaluators. This would just add the same boilerplate you have (copying the StringEvaluator implementation in StringEvaluatorExtended etc), all to prevent multiply.accept(printEvaluator). I'm not sure this extra bit of type safety would be worth it, but it certainly depends on the specifics.
> The whole point of the visitor pattern is to prevent you from being able to put unsupported combinations together.
While that is an important part, this is not an all-or-nothing problem. Type safety is a spectrum, and we can choose where to give up some safety to gain something else.
> Type safety is a spectrum, and we can choose where to give up some safety to gain something else.
I agree, but I'm saying that if you're willing to give up the type safety of verified combinations, you can have a solution that is just as (or even more) extensible as the visitor pattern (or discriminated unions) that is fewer lines of code and might even perform faster. Namely you can just downcast in the evaluator to the cases you can handle and then just bail if the downcast fails. This is the exact same functionality, can be extended in the same way (and in fact in more ways), and is fewer lines of code.
As far as I can tell the only reason you'd want to use the visitor pattern (or discriminated unions) here is some notion of "purity," e.g. in the case of OO that you're violating some notion of the Liskov Substitution principle by explicitly downcasting and in the case of FP that you're violating parametric polymorphism. But neither notions of purity feel particularly convincing to me.
As an aside
> This would just add the same boilerplate you have
In fact I think in the C# version it would be even more code because you can't reuse the same match patterns; you'd have to repeat way more of each evaluator.
> As far as I can tell the only reason you'd want to use the visitor pattern (or discriminated unions) here is some notion of "purity," e.g. in the case of OO that you're violating some notion of the Liskov Substitution principle by explicitly downcasting and in the case of FP that you're violating parametric polymorphism. But neither notions of purity feel particularly convincing to me.
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.
> In fact I think in the C# version it would be even more code because you can't reuse the same match patterns; you'd have to repeat way more of each evaluator.
Here is the C# version without the default NotImplementedException escape hatch:
// ------ BEGIN : In some external library
interface ExpressionOpen { T accept<T>(Evaluator<T> eval); }
record Literal(int n) : ExpressionOpen{
public T accept<T>(Evaluator<T> eval) => eval.visitLiteral(this);
}
record Addition(ExpressionOpen x, ExpressionOpen y) : ExpressionOpen {
public T accept<T>(Evaluator<T> eval) => eval.visitAddition(this);
}
interface Evaluator<T> {
T visitLiteral(Literal l);
T visitAddition(Addition a);
}
class StringEvaluator : Evaluator<string> {
public virtual string visitLiteral(Literal l) => l.n.ToString();
public string visitAddition(Addition a) => a.x.accept(this) + "+" + a.y.accept(this);
}
class ExecutionEvaluator : Evaluator<int> {
public int visitLiteral(Literal l) => l.n;
public int visitAddition(Addition a) => a.x.accept(this) + a.y.accept(this);
}
// ------ END : No longer in some external library
// ------ BEGIN : My own code
//note: no need for ComplexEvaluator here
class HexadecimalEvaluator : StringEvaluator {
public override string visitLiteral(Literal x) => x.n.ToString("x");
// thanks to inheritance, the existing expressions can already accept this
// so no need for an equivalent for extendedEvaluator;
// we're also inheriting visit(Addition) but that is not fundamental
}
interface ComplexExpressionOpen { T accept<T>(ComplexEvaluator<T> eval); }
record Multiplication(ExpressionOpen x, ExpressionOpen y) : ComplexExpressionOpen {
public T accept<T> (ComplexEvaluator<T> eval) => eval.visitMultiplication(this);
}
//but we do need ComplexEvaluator to go with ComplexExpression
interface ComplexEvaluator<T> : Evaluator<T> { T visitMultiplication(Multiplication x); }
class StringEvaluatorExtended : ComplexEvaluator<string> {
public virtual string visitLiteral(Literal l) => l.n.ToString();
public string visitAddition(Addition a) => a.x.accept(this) + "+" + a.y.accept(this);
public string visitMultiplication(Multiplication m) => m.x.accept(this) + " * " + m.y.accept(this);
}
class ExecutionEvaluatorExtended : ComplexEvaluator<int> {
public int visitLiteral(Literal l) => l.n;
public int visitAddition(Addition a) => a.x.accept(this) + a.y.accept(this);
public int visitMultiplication(Multiplication m) => m.x.accept(this) * m.y.accept(this);
}
class HexadecimalEvaluatorExtended: StringEvaluatorExtended {
public string visit(Multiplication m) => m.x.accept(this) + " * " + m.y.accept(this);
public override string visitLiteral(Literal x) => x.n.ToString("x");
}
//we don't need any kind of boilerplate similar to evaluateExtendedExpression.
// ------ END : Finished with my own code
However, this version has a major problem that neither your version nor my initial one do: I can't represent something like Addition(Multiplication(1,2),3). I don't think this problem is fixable in .NET, since you can't construct generic types that depend on runtime values, such as an ExpressionOpen<V> where V is anything which implements Evaluator<T>. We could probably hack around it with a lot more boilerplate and some convention (an associated Evaluator interface that Evaluator<T> extends, and explicit casts from Evaluator to Evaluator<T> in the accept methods, plus a convention that no one should implement Evaluator except Evaluator<T>).
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
Well, one thing that this solution misses is virtual dispatch - HexadecimalEvaluator won't work for Addition(Literal(1),Literal(2)) for example, because ExtendedStringEvaluator doesn't know to call HexadecimalEvaluator back.
Still, this is easily fixable by transforming the static functions into virtual methods on a class:
//keeping all of the definitions so far the same
class ExtendedStringEvaluator : BuiltInEvaluators.StringEvaluator {
public override string visit(Expression expression) {
switch(expression) {
case Multiply multiply: return $"{ExtendedStringEvaluator(multiply.x)} * {ExtendedStringEvaluator(multiply.y)}";
default : return super(expression);
}
}
}
class HexadecimalEvaluator : ExtendedStringEvaluator {
public override string visit(Expression expression) {
switch(expression) {
case Literal literal: return return l.n.ToString("x");
default : return super(expression);
}
}
}
Still, this switch on the class type is essentially exactly a virtual call on the type of Expression, just controlled by someone other than the original class. That is, the Expression doesn't "know" any more that it is being visited, so you couldn't create a LoggingExpression let's say. On the other hand, the Visitor now has more control over the way it interprets expression subtypes. So even here we are doing double dispatch: we are dispatching manually based on the runtime type of `expression`, and then allowing the language to dispatch based on the runtime type of `this`.
> Well, one thing that this solution misses is virtual dispatch - HexadecimalEvaluator won't work for Addition(Literal(1),Literal(2)) for example, because ExtendedStringEvaluator doesn't know to call HexadecimalEvaluator back.
Ah of course, I accidentally switched back into closed recursion rather than open recursion (that was ExpressionOpen). This indeed is exactly analogous to early binding vs late binding. You can't exactly write the same form of open recursion I wrote earlier because C# doesn't have higher-kinded generics (so for example you can't write
), but that's a language-specific thing. If you had higher-kinded generics you could exactly model virtual dispatch with open recursion because they're the same thing.
> That is, the Expression doesn't "know" any more that it is being visited, so you couldn't create a LoggingExpression let's say. On the other hand, the Visitor now has more control over the way it interprets expression subtypes. So even here we are doing double dispatch: we are dispatching manually based on the runtime type of `expression`, and then allowing the language to dispatch based on the runtime type of `this`.
You can call it visitor, but at this point it really is the same as discriminated unions (indeed this is exactly analogous to the first iteration of code just without the last bit to ensure that combinations matched up). And you can exactly replicate `LoggingExpression` in the evaluator, there is no difference in expressivity.
This shouldn't be surprising; after all the whole thing that kicked off all of this is that there is an isomorphism between discriminated unions and the visitor pattern. It should not be a surprise that it is possible to interpret one in the other.
My point at the beginning of all this was to object to the statement that this was not an isomorphism. Anything you can do with the visitor pattern you can do with discriminated unions and vice versa. The only differences are in ancillary language support (e.g. virtual dispatch and higher-kinded generics). Hence in a very real real sense the visitor pattern is just discriminated unions and vice versa.
The only preference for one or the two comes down to issues of code size and maintenance.
We could get rid of those base cases; we would then have to make ComplexExpression not a subtype of ExpressionOpen, and that in turn would mean we can't extend any of the extended evaluators from the old evaluators. This would just add the same boilerplate you have (copying the StringEvaluator implementation in StringEvaluatorExtended etc), all to prevent multiply.accept(printEvaluator). I'm not sure this extra bit of type safety would be worth it, but it certainly depends on the specifics.
> The whole point of the visitor pattern is to prevent you from being able to put unsupported combinations together.
While that is an important part, this is not an all-or-nothing problem. Type safety is a spectrum, and we can choose where to give up some safety to gain something else.