4 ms·
The visitor pattern is only helpful when you have two polymorphic types and want to write code which needs to dispatch on the real type of BOTH arguments. For
by tsimionescu 6y ago
The visitor pattern is only helpful when you have two polymorphic types and want to write code which needs to dispatch on the real type of BOTH arguments.
For example, you have a an expression tree, where each node can have a different type that is a subtype of Expression; and you have an Evaluator type with many subtypes of evaluators.
At runtime, every specific subtype of Evaluator may need different code for every specific subtype of Expression. Furthermore, new Expression types and new Evaluator types can be created by libraries that you don't have access to. Discriminated unions don't solve this problem.
- dwohnitmok 6y agoDiscriminated unions exactly solve this problem (just "inside out" in the same way that Church encodings are algebraic datatypes "inside out"). It's only a matter of whether you have closed or open unions. That then just governs whether you have to nest types or not. In fact, you can get even more code reuse than with your standard visitor pattern using openly recursive unions. // This is all pseudo code with open unions to reduce nesting. // Doable with closed unions, just more cluttered // Note these are all type aliases, since open unions imply structural types, // but nonetheless these are truly (open) discriminated unions // ------ BEGIN : In some external library type alias Evaluator = PrintEvaluator or ExecutionEvaluator // Open here is referring to open recursion rather than open unions // This gives us even more reuse than the standard visitor pattern type alias ExpressionOpen a = Literal Int or Addition a a stringEvaluator : ExpressionOpen String -> String stringEvaluator (Literal n) = intToString n stringEvaluator (Addition x y) = x ++ " + " ++ y executionEvaluator : ExpressionOpen Int -> Int executionEvaluator (Literal n) = n executionEvaluator (Addition x y) = x + y evaluate : Evaluator -> Fix ExpressionOpen -> String // This fold is a generalized version of the usual fold on list, meant to work on fixed point types evaluate PrintEvaluator expr = fold stringEvaluator expr evaluate ExecutionEvaluator expr = intToString (fold executionEvaluator expr) // ------ END : No longer in some external library // ------ BEGIN : My own code type alias ComplexEvaluator = HexadecimalEvaluator or Evaluator hexadecimalEvaluator : ExpressionOpen String -> String hexadecimalEvaluator (Literal n) = intToHexString n hexadecimalEvaluator (Addition x y) = x ++ " + " ++ y type alias ComplexExpressionOpen a = BasicExpressionOpen a or Multiplication a a extendedEvaluator : ComplexEvaluator -> Fix ExpressionOpen -> String // This may look like dynamic dispatch but it isn't // ": Evaluator" expands out to a case match on the union tags of Evaluator // In both branches of the match we then just call evaluate extendedEvaluator (evaluator : Evaluator) expr = evaluate evaluator expr extendedEvaluator HexadecimalEvaluator expr = fold hexadecimalEvaluator expr stringEvaluatorExtended : ComplexExpressionOpen String -> String stringEvaluatorExtended (expr : ExpressionOpen String) = stringEvaluator expr stringEvaluatorExtended (Multiplication x y) = x ++ " * " ++ y executionEvaluatorExtended : ComplexExpressionOpen Int -> Int executionEvaluatorExtended (expr : ExpressionOpen Int) = executionEvaluator expr executionEvaluatorExtended (Multiplication x y) = x * y hexadecimalEvaluatorExtended : ComplexExpressionOpen String -> String hexadecimalEvaluatorExtended (expr : ExpressionOpen String) = hexadecimalEvaluator expr hexadecimalEvaluatorExtended (Multiply x y) = x ++ " * " ++ y // If you want to extend both evaluator and expression at the same time you need // to repeat yourself a little // But you would need to repeat even more with the visitor pattern! // Namely none of your old evaluators work nor do any of your old expression trees! evaluateExtendedExpression : ComplexEvaluator -> Fix ComplexExpressionOpen -> String evaluateExtendedExpression PrintEvaluator expr = fold stringEvaluatorExtended expr evaluateExtendedExpression ExecutionEvaluator expr = fold executionEvaluatorExtended expr evaluateExtendedExpression HexadecimalEvaluator expr = fold hexadecimalEvaluatorExtended expr // ------ END : Finished with my own code
- tsimionescu 6y agoThat doesn't look like an alternative to the visitor pattern, that basically IS the visitor pattern. If you replaced the magic of Fix T + fold with an equivalent to accept(), you would end up having written exactly the Visitor pattern just with pattern matching instead of virtual dispatch and sum types instead of subtypes. Here is the exact same example in fully working C# (you can do the same in Java or C++, C# is just a little more terse; you could do it in Go as well, but it would be much uglier because you don't have generics). // ------ BEGIN : In some external library interface ExpressionOpen { T accept<T>(Evaluator<T> eval) => throw new NotImplementedException("Unsupported combination"); } 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 : ExpressionOpen { T accept<T>(ComplexEvaluator<T> eval) => throw new NotImplementedException("Unsupported combination"); } 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 : StringEvaluator, ComplexEvaluator<string> { public string visitMultiplication(Multiplication m) => m.x.accept(this) + " * " + m.y.accept(this); } class ExecutionEvaluatorExtended : ExecutionEvaluator, ComplexEvaluator<int> { public int visitMultiplication(Multiplication m) => m.x.accept(this) * m.y.accept(this); } class HexadecimalEvaluatorExtended: HexadecimalEvaluator, ComplexEvaluator<string> { public string visitMultiplication(Multiplication m) => m.x.accept(this) + " * " + m.y.accept(this); } class HexadecimalEvaluatorExtended: HexadecimalEvaluator, ComplexEvaluator<string> { public string visit(Multiplication m) => m.x.accept(this) + " * " + m.y.accept(this); //if C# supported multiple inheritance, we wouldn't have needed to repeat ourselves here: //we could have just inherited both HexadecimalEvaluator and StringEvaluatorExtended } //we don't need any kind of boilerplate similar to evaluateExtendedExpression. // ------ END : Finished with my own code You'll notice that (disregarding how verbose the language still is) we have actually written significantly less code - we haven't repeated a single line of code. Also note that your example only works in languages which have discriminated unions, pattern matching, compiler macros, and support for recursive types. Without any of these, it becomes even more verbose and harder to extend than the actual visitor pattern.