Like a lot of functional programming writing, this piece seems impenetrable because it comes at a problem from a peculiar angle: given that I have this hammer, what nails can I hit?
Starting from the recognition that there’s a trick you can do with typed lambdas to represent ‘types’, it then proceeds to show that you can use pattern matching on those ‘types’ to implement something like the visitor pattern.
It never even comes close to showing what that wins you. We found a gang-of-four shaped nail. Done.
But the thing is the visitor pattern is a response to a particular problem: double dispatch. You have some logic that needs to vary based on two different types. The classic example is a game where you want to calculate damage effects for different kinds of attack against different kinds of monsters.
If you start from a problem like that, the visitor pattern turns out to be useful (but is not the only way to solve it).
It’s possible - hard to tell from first reading - that what this article is actually suggesting is that Church Encoding can be used to solve double dispatch problems, by letting you encode a visitor pattern in a particularly elegant way.
Which would be a much more interesting insight!
It’s far more likely that you are facing a double dispatch problem and looking for a programming tool to solve it with, than that you have elected to use Church encoding to build some types for some reason and are now looking to determine which gang-of-four patterns you can implement in your new type calculus...
"double dispatch" is not a problem. It's OO epicycles. "Deciding what to do based on the sort of input" is the problem.
The point of these realizations not that "oh, just use church encoding". Church encoding, like the visor pattern, is annoying an obtuse: get a language with pattern marching.
Rather, the point is to show that the theory is legit because it shows up even among the work of those ignorant of it. And church encoding remains useful theory because sometimes it's advantageous to boil everything down to functions.
Author here: it's not changing the problem definition. I can confirm that the original motivation for writing the post was to show the theoretical underpinnings of the visitor pattern, not to encourage people to gratuitously use double dispatch.
> "Double dispatch" is indeed a problem when the language you're allowed to use has to be taken as given.
No, it's not, at least with most modern real OO languages, because most support functional style as well.
It's the low impedance solution course for certain problems when you have a preexisting idiomatic code base in some languages, though. But that's a different thing than being the problem.
(Also, whether the language is usually an advance constraint rather than a trade-off depends on a lot of things, including your role; certainly, polyglot runtimes and the ability to link code from different languages are common enough that even “must integrate in-process with existing code base in language X” is usually not a technical constraint that narrows the solution space to language X.)
We should distinguish between "double dispatch" in the abstract and a concrete problem being solved with it. The concrete problem often has more constraints, not mentioned when talking about it abstractly.
For example, using a different language means that the build system needs to support the other language, which can significantly complicate the difficulty for users of a library compared to a "pure" version written in the same language as the rest of the ecosystem. It may also limit portability, if the original language and the other language you pick don't support the same platforms. This isn't a good thing to inflict on users of your library.
To be a bit more concrete about it, suppose you are writing code in Rust to target WebAssembly. Pure Rust libraries are more likely to work than those written in a different language.
There are other ways to avoid this. In Go, you can use the "go generate" command to generate Go code from code written in another language, and check in the Go code, so downstream users of your library don't need any special tools. That's probably okay for private dependency on code written in another language, but less useful for datatypes used in public API's.
Someone talking about OO "epicycles" is ignoring most of the constraints that library maintainers face. It seems unsympathetic and out of touch.
It's fine to justify how we write code based on the code we've already written, but that is the very "hammer-first" reasoning the original comment was disparaging!
Even if we can't rewrite everything up front, it's used to think about the problem at hand from first principles, ignoring the constraints of any particular language. From the vantage point "double dispatch" will never arise.
If this Church-encoding workaround were useful, there would need to be at least one concrete situation where you find it useful.
It's apparently not useful in languages with sum types, and it doesn't seem useful in an object-oriented language either (where you'd use the normal visitor pattern). So, when is it useful? The author doesn't have a practical example.
I guess there might be a language somewhere that has neither sum types nor methods? It's kind of a reach.
But, maybe it's useful educationally, as a good way to think about problems? That doesn't seem particularly likely either, considering that you can apply the visitor pattern just fine without knowing about Church encodings at all.
Disparaging "double dispatch" as "epicycles" while promoting Church encoding as "legit" just seems out of touch with how practical programmers think. I can't think of any reason why I'd want to use Church encoding to explain what's going on to a newbie.
Maybe there is some other situation where it's useful, but it's not explained.
The point of the post wasn't to explain that Church encoding is a replacement for the visitor pattern. The purpose of the post was to explain that the visitor pattern is essentially the same thing as Church encoding (thus the title of the post), because I noticed a lot of people were not appreciating that connection between the two.
That's fine, but it seems like some of the confusion comes from unclear expectations? There is a vague promise at the beginning of the post that this will somehow be useful for programming:
"This post also explains how you can usefully employ the visitor pattern / Church encoding / Böhm-Berarducci encoding to expand your programming toolbox."
Church encoding is not a good way to write real-world programs. There, I said it.
I said it was useful theory. E.g. a way to shrink a programming language to remove data types so there's less drudgery in proofs about that language. That's not a regular programming task in the slightest.
Maybe the fundamental problem isn’t double dispatch itself, fair.
The fundamental problem is that you need to teach the computer how to choose which of a number of computations to run depending on two enumerable dimensions, and you need to embed that into your program in a way that covers all the possibilities, is bug free and maintainable.
Like, I need to be able to add shapes to my program, and things I can calculate about shapes to my program, and whenever I do so I need to either add all the new calculations for my new shape, or add my calculation for every existing shape.
That’s the essential complexity at the heart of this problem.
Double dispatch is the problem you then get when, in looking to solve that problem, you want to express the operations you want to run as functions that take every pairwise combination of types, and you are at a point in your code where you have a couple of objects and need to choose which of those functions to run. Like, I have an operation I want to run (could be calculate area, could be calculate perimeter), and a shape I want to run it on (could be a square, could be a circle) and I need the computer to go and run the correct one of four possible bits of code for me right now.
This is a double dispatch problem no matter what facilities your language has to address it. If your language can pattern match on typed tuples you can use pattern matching to dispatch to the right piece of code. If not, maybe you need to use something like the visitor pattern.
> Like, I need to be able to add shapes to my program, and things I can calculate about shapes to my program, and whenever I do so I need to either add all the new calculations for my new shape, or add my calculation for every existing shape.
> That’s the essential complexity at the heart of this problem.
Agreed
> This is a double dispatch problem no matter what facilities your language has to address it. If your language can pattern match on typed tuples you can use pattern matching to dispatch to the right piece of code. If not, maybe you need to use something like the visitor pattern.
But the "double" part refers to the OO solution to that. With pattern matching, there is nothing that sicks out as "double". Pattern matching on two arguments is the same as pattern matching on a single pair.
and update the area function, I also need to update every existing type like
def Rectangle(x, y, w, h):
return (lambda visitCircle, visitRectangle, visitTriangle : visitRectangle(x, y, w, h))
Am I understanding this correctly? How is this a win? What if I have a hundred different shapes, now every shape definition is just a list of a hundred parameters and hopefully I called the correct one in my copy&paste-fest.
That's why we usually group all of these handlers into a single Visitor interface. Then you only add one class and one extra method to the Visitor, and all the other variants stay the same.
You're brushing up against the so-called "expression problem", though, where you can choose between adding types easily or adding algorithms easily, but not usually both.
import math
def Circle(x, y, r):
return (lambda d : d['visitCircle'](x, y, r))
def Rectangle(x, y, w, h):
return (lambda d : d['visitRectangle'](x, y, w, h))
def area(shape):
return shape({
'visitCircle': lambda x, y, r : math.pi * r * r,
'visitRectangle': lambda x, y, w, h : w * h
})
exampleCircle = Circle(2, 1.4, 4.5)
exampleRectangle = Rectangle(1.3, 3.1, 10.3, 7.7)
print(area(exampleCircle))
print(area(exampleRectangle))
# 63.61725123519331
# 79.31
1. each case of the pattern matching is encoded by a lambda (the ones passed to "shape" in function "area")
2. each possible shape instance is a function that will accept these case lambdas, picking the one corresponding to it and passing its constructor arguments to it
3. the constructors ("Circle", "Rectangle") create the shape instances
I think it's best understood if you work backwards from the print calls
1. print is fairly straightforward, prints to stdout what is inputted
2. def area(shape) returns the result of shape call with the two lambda parameters representing the area of a circle as the first parameter, and the second representing the area of a rectangle.
3. def Circle(x,y,r) & def Rectangle(x, y, w, h) are functions which return a lambda that both accepts two parameters, visitCircle and visitRectangle. visitCircle corresponds to the lambda x, y, r : math.pi * r * r in def area(shape). visitRectangle corresponds to the lambda x, y, w, h : w *h in def area(shape). So the def Circle(x, y, r) returns a lambda that takes as input these two formulas, but chooses the formula for calculating a circle's area, whereas def Rectangle(x, y, w, h) takes as input the same two formulas, but chooses the formula for calculating a rectangle's area.
This is basically what the blog post explains, though without some Haskell knowledge it is probably hard to understand. (Sorry if I explain something you already know)
The basic idea is that types can be “recreated” in an untyped way with only functions. It is also important to note the distinction between sum types and product types. A sum type is basically a (disjunct) set of types, for example Shape is a sum type on Rectangles and Circles (in this case only these things are considered the available shapes and every shape is either one or another). A product type is more straight-forward, basically any struct/class with multiple fields is an example, for example Circle is a product type with a radius and an x and y coord of its centerpoint.
For example here the two-ary methods represents the two types:
return (lambda visitCircle, visitRectangle : visitCircle(x, y, r))
Is going to represent circles, by awaiting two functions that work as constructors, and dispatching to the first one. Rectangle is similarly defined, only dispatching to the second function.
The part that corresponds to pattern matching/the second dispatch is basically where we would like to use our sum-types (either a circle or a rectangle). It provides both implementation in the form of a pair of functions, the first one corresponds to the circle’s area-definition the second to the rectangle’s.
The “magic” happens at calling area(exampleSomething). The area function will return as seen a pair of functions, basically every possible implementation on the possible types. Now that pair of functions will go to either a Circle ‘constructor’ function or a Rectangle one, and as we defined those, it will use up respectively the first or the second function in the pair based on its “type”. Also note that the correct arity of parameters will be passed to the selected function.
The good explanations you received lack a fundamental definition that will help those without formal CS education or some experience in FP to understand that code :
A lambda is a function that take two arguments:
- a list of arguments A
- a block of code C
And return an anonymous function having the arguments in A and C as a body.
In python lambda is an expression and the syntax is :
#A is the part before the : and C the part after
lambda a1 a2 a3 : a1 + a2 + a3
Not everything is about hitting nails. This is more about thinking about what hammers and nails are made of. If you don't know Church Encodings already, well typed church encodings are going to be a bad place to start. Personally I would look at the https://en.wikipedia.org/wiki/Mogensen%E2%80%93Scott_encodin... it is simpler to teach as a first functional encoding of data types.
The fact that it is a visitor pattern is linking insight from functional and object oriented design patterns together. I can see the confusion if one only views those design patterns on a practical level. The article is really teaching the Böhm-Berarducci encoding to more experienced functional programmers as a concept not as a hammer to solve problems.
Right, these things are still interesting and valuable even if not immediately practical for a certain use. Like a regex being equivalent to a finite state machine or lots of other connections between seemingly disparate concepts in math.
It's particularly weird because most statically-type functional languages have discriminated unions as a practical alternative to the visitor pattern anyway.
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.
Discriminated 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
That 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.
interface ExpressionOpen { T accept<T>(Evaluator<T> eval) => throw new NotImplementedException("Unsupported combination"); }
interface ComplexExpressionOpen : ExpressionOpen { T accept<T>(ComplexEvaluator<T> eval) => throw new NotImplementedException("Unsupported combination"); }
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.
In particular
//we don't need any kind of boilerplate similar to evaluateExtendedExpression.
That was purely for combinatorial safety. You could remove it altogether if you wanted.
The whole point of the visitor pattern is to prevent you from being able to put unsupported combinations together. If you get rid of that requirement you don't need types at all and there are far far easier ways of doing this than either with the visitor pattern or with discriminated unions (just do it all with nested dictionaries for a fraction of the code).
Throwing this exception is basically a cheat is it not?
> support for recursive types
I think every statically typed language I know has support for recursive types. Certainly C# does.
> pattern matching
Eh... I'm not really using pattern matching in any real sense here. They could be replaced by if statements. The only reason it's there is because there's total type erasure in Haskell so runtime dynamic dispatch isn't really a thing in the same way it is in C#.
> 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.
Forgot one other important distinction: if we wanted to add a new expression subtype that can behave like one of the existing types for existing operations, that is not possible with the discriminated union variant. Say we wanted to add an SmallAddition, that stores its two numbers as bytes, but converts them to int when needed. We could add this without modifying any code in the visitors in the C# version (well, technically we may have a problem because we accessed the fields directly, but that's inconsequential). In the pseudo-Haskell version, we would need to modify all 6 evaluation functions just to handle the new Expression subtype.
> In the pseudo-Haskell version, we would need to modify all 6 evaluation functions just to handle the new Expression subtype.
That's not true. I think you may be misunderstanding open unions (or polymorphic variants) here. Tags are types in and of themselves. That's why these are all `type alias`es. You could decide to modify the type alias if you'd like, but you don't have to. You can add the additional tag just to the call site.
There wouldn't be a subtype of Addition because Haskell doesn't have a notion of subtyping in the same way C# does. It would depend on the particulars of what the difference between SmallNumberAddition and Addition look like (in particular which parts are kept with the same functionality and which are different). The answer could be either a simple function or a typeclass depending on that.
Right. I don’t have well-developed enough Haskell taste to tell whether this approach leads towards a more elegant or alternatively beneficial way of representing this kind of scenario than matching over a discriminated union type.
My takeaway from the article is that you almost always want a proper sum (discriminated union) type, but if you find yourself in a world without (hello, Java), here's a way to encode them precisely. As the OP notes, though, this still relies on having generics in your language, so you can't even perform this encoding if you don't have generics.
For a counterpoint, take a look at the relationship between object algebras and final tagless style [0]. It goes well beyond the basic visitor pattern, but gives you a lot of expressivity in exchange.
This is exactly right. The relevant quote from the article is this:
> The reason we care about Church-encoding is because not all programming languages natively support sum types or recursion (although most programming languages support product types in the form of records / structs).
> However, most programming languages do support functions, so if we have functions then we can use them as a “backdoor” to introduce support for sum types or recursion into our language. This is the essence of the visitor pattern: using functions to Church-encode sum types or recursion into a language that does not natively support sum types or recursion.
That's contrived. If you're in Java, you would use a visitor pattern.
It is weird to given an example in Haskell of something you don't need to do in Haskell, but would theoretically want to do in some other language, but actually in these other languages you'd do something different.
I'm not sure I follow your point, because the thing you don't need to do in Haskell is precisely the visitor pattern, and you don't need to do it in Haskell because you have sum types; but you don't have sum types in Java, so of course you'd use the visitor pattern -- you have no other option.
I meant that you wouldn't use a Church encoding workaround for a visitor pattern. (That's what you seemed to mean by "here's a way to encode them precisely.") Instead, you'd use the visitor pattern in the normal way. So the Church encoding workaround is useful in neither Haskell nor Java.
The point of the original article is that the Visitor pattern is the Church encoding of sum types. It sounds like you see a stronger difference between what the article describes and what I understand the Visitor pattern to be. There might be light differences in how you organize various elements (such as grouping all the handlers into a single interface or taking them as individual parameters), but I see those as all within the same overall Visitor aegis.
The core of the Visitor pattern is a CPS transform, where you provide the value the code to run "next". Because this puts the sum type on the input side instead of the output side, you can distribute the types and get a pair of functions instead of a sum of values. Is there another difference I'm not accounting for?
I’ve seen the visitor pattern used mostly in compilers where there might be 50 cases in the AST for a compiler for a production language. So when looking at how the code is written for a visitor pattern, I think about how the code might look in a compiler if you had a lot of cases. Does it scale? The amount of boilerplate you need matters because it’s multiplied by 50.
The examples I’ve seen of Church encoding don’t look like code I’d want to read or write. Who wants to write a function that takes 50 functions as parameters? At least use a struct of functions. The struct serves as a vtable, so you might as well use an object-oriented language’s built-in vtables.
(Although I suppose in C, you’d need to implement the vtable yourself. Structs of functions are how OOP is commonly done in C.)
I understand how mathematically they’re equivalent but that’s ignoring practical differences in how they appear on the screen. It was neat when in Structure and Interpretation of Computer Programming they showed how you could implement data structures using only functions but that doesn’t make it a design pattern you want to use, it’s just trivia.
> Who wants to write a function that takes 50 functions as parameters? At least use a struct of functions. The struct serves as a vtable, so you might as well use an object-oriented language’s built-in vtables.
Okay, I think I see where we're missing each other. Church encoding doesn't have to be an all-or-nothing -- you don't have to commit to only function types and no other types. It's still useful when you apply it in localized contexts.
The key idea with the visitor pattern is that `A + B` is not a type you have in most languages. You can get an equivalent with generics and functions, but that doesn't mean you can't use products if it makes sense. The equivalent is an object with a method `<T> T visit(Visitor<T> v)`, where `Visitor<T>` is a pair of two methods, `T onA(A a)` and `T onB(B b)`.
Sure, you can always replace `(X, Y) -> Z` with `X -> Y -> Z` to get rid of even the product type, but that's not what anyone is proposing fundamentally here. It's just currying; it's not essential to the encoding being discussed.
The original blog post is using Haskell norms, and in Haskell, currying is very normal. But that doesn't mean it's a necessary ingredient of the demonstration. The key idea is to use a continuation-passing transform, to move the `A + B` value into the negative position of a function type (`forall T. (A + B -> T) -> T`), and then distribute over the function type so you're not relying on having a primitive sum type at all (`forall T. (A -> T, B -> T) -> T`). The extra step of currying (`forall T. (A -> T) -> (B -> T) -> T`) is unnecessary; it's just common in Haskell.
As you say:
> Who wants to write a function that takes 50 functions as parameters? At least use a struct of functions.
That's what `(A -> T, B -> T)` is. I suppose it could be confused for an argument list, but in Haskell, functions only take one argument. The type `(A -> T, B -> T)` is literally the type of a pair of two functions. It's isomorphic to a record type like `data Handlers { onA :: A -> T, onB :: B -> T }` -- you're just changing the indices from 0,1 to onA,onB.
If you ignore the details of implementation by treating isomorphic code refactorings as equivalent, it all looks kind of the same and there is no new technique here? In Java you would notice that a struct of functions can be replaced with methods and inheritance, and we’re back to the visitor pattern.
I guess maybe it’s that you could implement the visitor pattern in Haskell using a record that contains functions. But that’s a straightforward vtable implementation, and you wouldn’t really want to anyway.
> I guess maybe it’s that you could implement the visitor pattern in Haskell using a record that contains functions. But that’s a straightforward vtable implementation, and you wouldn’t really want to anyway.
On the contrary: typeclasses are exactly "records that contain functions", and Haskell desugars typeclass constraints to vtable-passing (if it can't otherwise inline the typeclass for known call sites). Pushing in this direction leads to the final tagless representation, which compares favorably with object algebras, a mild generalization of the idea of the Visitor pattern. [1]
I maintain that the core idea here is the replacement of `A + B -> T` with `(A -> T, B -> T)` to erase the sum type, and the use of the CPS transform from `A + B` to `forall T. ((A + B) -> T) -> T` to get the sum into a negative position in the first place. How you actually organize the resulting handler functions is a far smaller distinction. Even the Gang of Four is clear that their patterns are islands within a broader spectrum, and that each pattern has related variants based on the same idea. Currying (`(A, B) -> C` vs. `A -> B -> C`) is a separate and orthogonal idea from CPS, and I just don't see the value in including a choice of currying style in the Visitor pattern when it's an inessential flavoring.
> it all looks kind of the same and there is no new technique here?
Yes, that really is the point. The OP is explaining how these two different things in two different paradigms are actually the same thing, under the hood, and illustrates exactly how that's the case. It illuminates precisely where the Visitor pattern is useful: anywhere you'd use a sum type. Because both model closed families of options.
I find it fascinating that while we mostly understand each other, it seems like we still disagree on what sort of knowledge is useful. There is a weird gap here.
It seems like this is starting with something I basically knew? The visitor pattern in an object-oriented language is used for same things that a sum type and pattern-matching are used for in a functional language.
And then re-explaining it using a lot of mathematical jargon, which makes it considerably more obscure than the more hand-wavy explanation. And then saying "isn't that useful?"
But I was happy just informally knowing that they were equivalent, and I would be happier explaining this to someone else informally, using examples of the same code written in Java (say) and Haskell. I don't feel like the mathematical jargon helped? I guess it's sort of neat that you can explain it that way.
(Thanks for continuing to engage on this. It's a fun conversation :) )
Yes, I suspect the blog post is more interesting if you already have a theoretical background, and are interested in the various ways that theory plays out in applications. I certainly doubt the post was written with the HN audience in mind in particular.
For me, theory is like a compression algorithm for knowledge. The more I can interrelate things, the less I have to duplicate the commonalities, and the more I can focus on remembering (and judging based on) the differences. So I get a lot out of this kind of thing.
(Personally, I use these kinds of transforms all the time -- especially "defunctionalize the continuation", which is lovely for mechanically making a simple recursive algorithm into an iterative one more suitable for something like Java. The theoretical background makes me more comfortable going between different representations and keeping track of precisely what is changing and what is being held fixed.)
I guess it's more about fluency in changing code than fluency in reading or writing code. Dynamics rather than statics. I think I can appreciate that if you're just looking at Visitor or sum types in isolation, it's not worth getting into the weeds over. But it's comforting to me to know that if I need to change various parts of a system, I know exactly what and where my degrees of freedom are. I can redefine the module boundaries one step at a time, and relatively smoothly and slowly shift the mass of the codebase around.
I agree that the "defunctionalize the continuation" refactoring is neat and non-obvious.
My feeling about refactorings is that you can use a tool that does it automatically (preferred, when available) or you can do it by hand (when not). I'm not sure I need to be thinking abstractly in math to do the hand-refactoring though. If I know where I'm starting from and where I want to end up then I can informally pattern-match. But I guess it's a more intuitive approach and it sounds like you prefer to think about it a different way.
Refactoring in small mechanical steps is generally less risky, though good tests can also reduce the risk.
Possibly one difference is that in Haskell, you're close to thinking in math already.
We got Streams that don't short-circuit properly and Optionals that throw NullPointerExceptions, what creative fuck-ups do you reckon we'll get with sum types & pattern matching?
"Algebraic data types" refers to having both product and sum types, where products are the records/structs that just about every language has, and sums are indeed the "discriminated unions" under discussion.
Most languages don't have built-in syntax for sum types, so most developers are familiar with sum types only by the shadows cast by a variety of encodings. One of them is the subject of the OP, the Visitor pattern. Another is the "tagged union" seen in C, effectively:
struct Rectangle { int x, y, w, h; }
struct Circle { int x, y, r; }
struct Shape {
enum {
RectangleTag,
CircleTag,
} tag;
union {
struct Rectangle rectangle;
struct Circle circle;
};
};
Which doesn't look too bad until you realize I haven't explained how to use the thing, and then it's similarly involved and even more delicate than the Visitor pattern.
Ah, very interesting thanks. I've seen sum types implemented in terms of inheritance (or fancy modern inheritance such as traits). Doesn't get you exclusive case enforcement, which imho is the thing that's actually useful here.
This is just the kind of thing you file away in the back of your head as "huh, interesting", that may or may not have a practical application down the line. But occasionally the pay off for having a different way of thinking about a problem can be really big.
For example, Joel Spolsky argued a long time ago that Google was able to solve some problems faster than Microsoft because their programmers understood functional programming:
Will this article have a similar payoff for someone someday? Hard to say, but it was probably not clear to the CS students learning map and reduce it would lead to an elegant solution to how to run computations across a massive computing infrastructure someday, either.
The core essence of the visitor pattern is to implement case distinction on sum types in languages that do not natively support sum types. Double dispatch is merely the mechanism by which the visitor pattern achieves this.
Double virtual dispatch is the core goal of the visitor pattern. If you don't have two families of types and subtypes (different subtypes of visitors and different subtypes of expressions), there are much simpler alternatives to the Visitor Pattern even in something like Java.
In particular, if you have a single closed sum type, function overloading is the best way to handle distinctions. If you want it to be open, single virtual dispatch is a common option.
It's only when you get two different sum types, with one or both being open, that you start benefitting from the visitor pattern.
The benefit is that you can decouple the implementation of the operation from the implementation of the sum type. For example, a library can provide a sum type, and users of the library can implement their own operations on it. This is often necessary for proper separation of concerns. For example, the sum type may be a domain object, and the operations may be database operations, UI operations, or other I/O or conversion operations. You don’t want the domain layer to have dependencies on the database, UI, I/O, etc., which it would have if those operations were implemented in the sum type itself.
It’s exactly the same benefits provided by language-native sum types with ADT pattern matching (aside from the visitor pattern requiring more boilerplate).
The operation can itself be a polymorphic operation on a different type hierarchy or sum type, which is the scenario you are thinking of, but that’s not necessary for being able to benefit from the visitor pattern.
Read the original description of the visitor pattern in the GoF book. It’s about implementing operations on an existing type hierarchy without having to modify the code of that type hierarchy.
To illustrate how to implement what you are describing without a visitor pattern if we don't care about subtypes:
//library code
sealed class TreeNode{
Object[] children;
}
sealed class LeafNode {
int value
}
//application code
int sumTree(Object o) {
if(o instanceof TreeNode) {
var tn = (TreeNode)o;
sum += sumTree(tn);
} else if (o instanceof LeafNode) {
var ln = (LeafNode) o;
sum += sumTree(ln) ;
}
}
int sumTree(TreeNode a) {
var sum = 0;
for (Object o in a.Children) {
sum += sumTree(o) ;
}
return sum;
}
int sumTree(LeafNode ln) {
return ln.value;
}
For some added type safety, we could use a marker interface instead of Object, but the code would be equivalent. You don't need visitors or ADTs even if you're working with Java 1.0 (you could actually write this in C pretty easily).
Now, if you start adding actual subtypes to TreeNode and LeafNode, this will quickly stop working, especially if you want more than one operation.
For example, if you wanted to add a DictionaryTreeNode that stores its children in a dictionary instead of a list, the visitor-based version would not require any change to the SumTree visitor, as DictionaryTreeNode can just call visitTreeNode in its accept() method.
ADTs and pattern matching don't solve this problem in any way - you can't add a new node subtype, because the operation explicitly decides what to do based on the variant.
Ifs and type checks are not a substitute for the visitor pattern, at least in statically typed languages, because they don't give you compile-time checks (exhaustiveness checking, as you say).
The visitor pattern doesn't require you to have a hierarchy of operations. It doesn't even require the sum type options to form a public type hierarchy. For example, the following Java code implements the typical binary-tree sum type:
public abstract class Tree<V>
{
public abstract <R> R apply(Visitor<? super V, R> visitor);
public interface Visitor<V, R>
{
public R whenLeaf(V value);
public R whenNode(Tree<? extends V> left, Tree<? extends V> right);
}
public static <V> Tree<V> leaf(V value)
{
return new Tree<V>()
{
@Override
public <R> R apply(Visitor<? super V, R> visitor)
{
return visitor.whenLeaf(value);
}
};
}
public static <V> Tree<V> node(Tree<? extends V> left, Tree<? extends V> right)
{
return new Tree<V>()
{
@Override
public <R> R apply(Visitor<? super V, R> visitor)
{
return visitor.whenNode(left, right);
}
};
}
private Tree() { }
}
This is what I'm describing.
(Incidentally, that design also allows you to replace the implementation by a tagged-union approach. The result wouldn't be the full visitor pattern anymore, of course.)
EDIT: Another way to put this: The visitor pattern abstracts away the case-distinction mechanism into a single implementation. In your code example, every operation (like sumTree) has to re-implement the case-distinction mechanism, that is, the ifs and the type checks. The visitor pattern decouples the case-distinction mechanism from the concrete case distinctions.
The example you're showing is what I would call over complicated. It does an awful lot of work just to gain a little bit of extra type safety compared to mine. You are introducing an extra type parameter (V is good, I was just lazy, but R is only needed because of the Visitor formalism) and 3 extra methods (accept, whenLeaf and whenNode). This all makes the code much harder to follow, and all it gets you is a little bit of extra type safety. It's true that this code in particular is easily and even better replaced with a discriminated union.
But I maintain my opinion that this is not the purpose of the Visitor pattern. I would go so far as to say that this is an anti-pattern. The visitor pattern is only useful when your model actually needs double dispatch - when you have a hierarchy of types with proper subtypes that need to be handled by a hierarchy of operations. If you do have this problem, the only solutions are the visitor pattern or native multiple dispatch like in CLOS. ADTs and pattern matching can't solve this problem.
A less-general but arguably more useful connection I've seen drawn is that the Visitor pattern is basically exchangeable with union types + pattern-matching (for languages that have these features); in the same way that objects can be exchanged with closures and iteration can be exchanged with recursion.
Which one of the two is "better" probably comes down to personal preference and/or the language being used, but it's good to know that you have the option.
I think you missed the angle of the article. It's just pointing out the isomorphism between Church encoding, the visitor pattern and GADTs. You wouldn't use anything but GADTs in Haskell today, it's just an interesting curiosity unless you're actually a type theorist or something.
#include <concepts>
#include <iostream>
#include <numbers>
template<class shape>
concept Shape = requires(
shape s,
shape (&&circle)(double, double, double),
shape (&&rectangle)(double, double, double, double)) {
{ s(circle, rectangle) } -> std::same_as<shape>; };
auto Circle = [](double x, double y, double r) -> Shape auto {
return [=](auto&& circle, auto&& rectangle) { return circle(x, y, r); }; };
auto Rectangle = [](double x, double y, double w, double h) -> Shape auto {
return [=](auto&& circle, auto&& rectangle) { return rectangle(x, y, w, h); }; };
Shape auto exampleCircle = Circle(2.0, 1.4, 4.5);
Shape auto exampleRectangle = Rectangle(1.3, 3.1, 10.3, 7.7);
auto area = [](Shape auto shape) -> double { return shape(
[](auto, auto, auto r) { return std::numbers::pi * r * r; },
[](auto, auto, auto w, auto h) { return w * h; }); };
int main() {
std::cout << area(exampleCircle) << std::endl;
std::cout << area(exampleRectangle) << std::endl;
}
Of course, this is missing type-erasure, which you'd need to pass `Shape` across TU boundaries, but that's unnecessary if you're happy to use parametric polymorphism.
Yeah, I recognize the lambda expressions and not much else. How does the new stuff even interact with the older features? I can't even tell if something is recommended or deprecated anymore. Can you imagine the sheer work of maintaining a compiler for this thing? Really makes me appreciate the relative simplicity of C.
On a positive note, it looks like the standard library became amazing. It seems really well designed. Contains things that used to be preprocessor definitions, lots of very popular functionality, good symbol names and no cryptic abbreviations anywhere. Did it absorb some of boost?
In addition to the other TypeScript examples, here's one that I would actually use. Now, it's not encoding the types not as positional, but named arguments via objects. Allows me to destructure them, for added clarity.
This feels like a pattern where the naming choices obscure the intent. The ‘Shape’ type doesn’t capture the essence of a ‘shape’ - it captures the essence of being ‘visitable by a visitor that knows about shapes’ or ‘able to handle shapes’. The things which are instances of Shape are functions that accept circles or rectangles, not actual circles or rectangles. So maybe call it ‘VisitableShape’, or ‘ShapeHandler’; and instead of calling its functions ‘circle’ and ‘rectangle’, call them ‘visitCircle’ or ‘handleCircle’...
Also, you seem to have created functions and types with the same names (Circle and Rectangle) which seems dangerous.
> The things which are instances of Shape are functions that accept circles or rectangles, not actual circles or rectangles.
The naming is confusing, but it's misled you in the opposite direction. Things that are instances of Shape are functions that accept handlers of circles or rectangles. The handlers, unfortunately, are named `circle` and `rectangle`. I would prefer `onCircle` and `onRectangle` in this context, because we're lacking the context of a true `match` expression to disambiguate the naming.
> Also, you seem to have created functions and types with the same names (Circle and Rectangle) which seems dangerous.
I think this is an idiom for defining a canonical constructor for a type. It's a little funky here because they're returning Shape, not Circle or Rectangle, and the latter are not subtypes of Shape. But it mostly tracks alongside the rest of the encoding.
You're speaking at the level of the code, while I'm speaking at the level of the domain. Neither of us are wrong, but we're talking past each other.
The Shape class itself is formally the sum of Circle and Rectangle -- you can think of this as a "prefer composition over inheritance" principle, but it's still a way of relating Circle to Shape. In particular, the Circle and Rectangle factories are canonical injections of these two classes into the Shape class. The naming of the factories is a little suspect, but if the only use of Circle and Rectangle is meant to be in the context of Shape, it mostly flies.
> Now, in order for it to work, a language has to support closures, not just functions.
Objects are a reasonable stand-in for closures. Pass in the first batch of arguments to the constructor, and store them as fields. Access them from the method (which plays the role of the "returned" closure) when it's called later.
(This is effectively the same as "closure conversion" in the literature, but we're taking advantage of the implicit-receiver convention to hide the parameter by which we're passing the prepared fields.)
interface Shape<T> {
interface _Circle<T> {
T apply(int x, int y, int r);
}
interface _Rectangle<T> {
T apply(int x, int y, int w, int h);
}
T apply(_Circle<T> circle, _Rectangle<T> rectangle);
static <T> Shape<T> Circle(int x, int y, int r) {
return (circle, rectangle) -> circle.apply(x, y, r);
}
static <T> Shape<T> Rectangle(int x, int y, int w, int h) {
return (circle, rectangle) -> rectangle.apply(x, y, w, h);
}
static double area(Shape<?> shape) {
var s = (Shape<Double>) shape;
return s.apply(
(x, y, r) -> Math.PI * r * r,
(x, y, w, h) -> 1. * w * h
);
}
static void main(String[] args) {
var exampleCircle = Circle(2, 1, 4);
var exampleRectangle = Rectangle(1, 3, 10, 7);
System.out.println(area(exampleCircle));
System.out.println(area(exampleRectangle));
}
}
BTW, you can use the same encoding when you write a Promise in JS.
As with the TypeScript examples, we can make the top-level apply method generic instead of the whole class to avoid some casts. In particular, notice that the <T> inferred from calling Circle() and Rectangle() is the unmeaningful <Object>.
The downside is that Java doesn't let you implement generic methods with lambdas, which is silly, so you have to use an anonymous subclass. But at least the call-side uses stay the same.
(And then, combining the `_Circle` and `_Rectangle` interfaces gets you to a more canonical visitor pattern, at the expense of lambdas at the call-site.)
public interface Shape {
interface _Circle<T> {
T apply(int x, int y, int r);
}
interface _Rectangle<T> {
T apply(int x, int y, int w, int h);
}
<T> T apply(_Circle<T> circle, _Rectangle<T> rectangle);
static Shape Circle(int x, int y, int r) {
return new Shape() {
public <T> T apply(_Circle<T> circle, _Rectangle<T> rectangle) {
return circle.apply(x, y, r);
}
};
}
static Shape Rectangle(int x, int y, int w, int h) {
return new Shape() {
public <T> T apply(_Circle<T> circle, _Rectangle<T> rectangle) {
return rectangle.apply(x, y, w, h);
}
};
}
static double area(Shape shape) {
return shape.apply(
(x, y, r) -> Math.PI * r * r,
(x, y, w, h) -> 1. * w * h
);
}
static void main(String[] args) {
var exampleCircle = Circle(2, 1, 4);
var exampleRectangle = Rectangle(1, 3, 10, 7);
System.out.println(area(exampleCircle));
System.out.println(area(exampleRectangle));
}
}
> The downside is that Java doesn't let you implement generic methods with lambdas ...
yes, that exactly why i've chosen to make the type parametric and not the method apply, but you're right that the classical visitor pattern uses a polymorphic method (accept) not a polymorphic class.
Sure. Then, if you're set on using lambdas, I'd recommend this, to at least take away the ability to choose <T> from the caller.
static Shape<?> Circle(int x, int y, int r) {
return (circle, rectangle) -> circle.apply(x, y, r);
}
static Shape<?> Rectangle(int x, int y, int w, int h) {
return (circle, rectangle) -> rectangle.apply(x, y, w, h);
}
The boolean lets us separate how to make a decision (which we define in function1), from how to handle a decision (which we define in function2). We can always eliminate this data by bringing those two things together, e.g.
// Inline function1 into function2
void function3(...) {
FOO
BAR
if (true) {
BAZ
} else {
QUUX
}
}
// Simplify the if/then/else
void function4(...) {
FOO
BAR
BAZ
}
Of course, it's very useful to keep things separate and to pass data around (modularity, readability, etc.). My point is that the computer/language doesn't care about these things, so we can use refactorings like this to 'distill the essence' of what data 'really is' (from this one perspective, at least).
So what can we do with a boolean?
- We can discard it. Such code can always be refactored to eliminate the boolean (it's dead code).
- Pass it to some other code. We can always refactor this to remove such intermediate steps, e.g. above we inlined 'function1' to avoid passing the boolean around.
- Construct them. We do this by using the "constructors" 'true' or 'false', AKA the "introduction forms".
- Branch on them using if/then/else. This is also called "destructing", where if/then/else is a "destructor" or "elimination form".
- Simplify 'if(true) ...' and 'if(false) ...'. Here we are 'destructing a constructor', which can always be replaced by the relevant branch.
If we apply these refactorings over and over we can eventually simplify-away every boolean value in a program. There are a couple of things to keep in mind:
- Some languages have special-case boolean operations like '!foo'. Those are equivalent to functions containing branches, which can be refactored as above, e.g.
boolean not(boolean x) {
if (x) {
return false;
} else {
return true;
}
}
boolean and(boolean x, boolean y) {
if (x) {
return y;
} else {
return false;
}
}
boolean or(boolean x, boolean y) {
if (x) {
return true;
} else {
return y;
}
}
- To fully eliminate data, we need to include any 'external' code, e.g. 'inlining' external libraries, system calls, third-party APIs, etc. For simplicity I'll just assume we're using a single program in a single language, but the principle still holds in general.
Note that inlining intermediate steps and removing unused parameters have nothing to do with booleans themselves; they apply to all forms of data. Hence the 'essence' of booleans is the simplification of 'if(true)...' and if(false)...'.
We can do this with booleans since they are a "sum type", i.e. there are a few distinct forms of boolean (namely "true" and "false"). This is similar to the article's "Shape" type, which has a "Circle" form and a "Rectangle" form.
OOP languages don't tend to support sum types directly; instead we can 'fake it' using subtypes. Here's an example, where I've implemented the simplification behaviour using subtype polymorphism:
abstract class Boolean {
T ifThenElse(T t, T e);
}
class True extends Boolean {
T ifThenElse(T t, T e) {
return t;
}
}
class False extends Boolean {
T ifThenElse(T t, T e) {
return e;
}
}
There's a slight wrinkle here, since calling 'ifThenElse(foo, bar)' will execute both 'foo' and 'bar'; we'll just get one of them returned back to us. If this is a problem, we can wrap our branches in zero-argument functions, pass those to 'ifThenElse', and call whichever function gets returned. Note that this is actually how Smalltalk implements boolean branching! https://rosettacode.org/wiki/Conditional_structures#Smalltal...
Hopefully I've demonstrated that the three classed defined above are a complete implementation of booleans: we have the constructors ('new True()' and 'new False()'), the destructor 'ifThenElse(thenBranch, elseBranch)', and we don't need anything else. To drive this point home, here's how we can define boolean algebra, translated from the above:
// not(x)
x.ifThenElse(new False(), new True())
// and(x, y)
x.ifThenElse(y, new False())
// or(x, y)
x.ifThenElse(new True(), y)
This implementation of Boolean is a rather simple form of "visitor pattern": the implementation of the "ifThenElse algorithm" is spread out amongst different implementations of the method, where each subclass knows how to handle its own case, and we just dispatch on whatever Boolean object we happen to have.
The point of Church Encoding is that we don't actually need these classes and polymorphism at all: rather than wrapping up these methods into classes, defining a class hierarchy, constructing instances of these subclasses, invoking methods on those instances, dynamically dispatching on the vtables, etc.; we can just pass the functions around directly!
Switching to JS, since it has first-class functions, here's my first example again:
If we want to avoid executing both BAZ and QUUX, we could wrap them up in functions like 'function1(...)(() => BAZ, () => QUUX)()'. We could also rename these functions to simply 'true' and 'false', since they're completely equivalent to those values (although that would be a syntax error in JS).
So now we've seen that (a) booleans can be completely implemented using if/then/else (b) the behaviour of if/then/else can be implemented using subclass polymorphism (c) subclass polymorphism can be emulated by passing around first-class functions. Note that we could have skipped all the OOP stuff and gone straight to functions, but I thought it might help some people, and it's also interesting in its own right.
This also extends to sum types with any number of distinct forms (which we now know are "constructors"). The rule is simple: a type with N constructors can be represented as a function which takes N arguments, and returns one of them. For example, we could represent Colour, with Red/Green/Blue like this:
const red = (r, g, b) => r;
const green = (r, g, b) => g;
const blue = (r, g, b) => b;
function printColour(c) {
console.log(c("Received red", "Given green", "Bestowed with blue"));
}
There are two other sorts of data to consider:
"Product types" contain multiple sub-values, e.g. 'Coordinate(x, y, z)'. For these, the rule is that we call the corresponding argument as a function, passing it the sub-values as arguments. For example:
const mkCoord = (x, y, z) => f => f(x, y, z);
function showCoord(c) {
c((x, y, z) => console.log(
"x: " + x.toString + " y:" + y.toString + " z: " + z.toString
));
}
const origin = mkCoord(0, 0, 0);
showCoord(origin);
Note that I'm using raw JS numbers and strings for simplicity; we can implement these using Church Encoding (e.g. using 64 booleans to emulate a double-precision float), but it would be tedious for this example.
We can combine sums and products, i.e. each constructor can contain sub-values. This is what the "Shape" example from the article does. We just need to combine the two rules: take N arguments (once for each constructor), and call the appropriate argument with the sub-values. For example:
const circle = (x, y, r) => (ifCirc, ifRect) => ifCirc(x, y, z)
const rectangle = (x, y, w, h) => (ifCirc, ifRect) => ifRect(x, y, w, h)
const unitCircle = circle(0, 0, 1);
const unitSquare = rectangle(0, 0, 1, 1);
function drawShape(s) {
s(
(x, y, r) => console.log("Circle of radius " + r.toString),
(x, y, w, h) => console.log("Rect of area " (w * h).toString)
);
}
The final possibility is recursive data, where the sub-values can be of the same type we're defining. The article uses a binary tree as an example, but a list is easier. In OOP:
abstract class List<T> {
U reduce(U init, Function<U, Pair<U, T>> f);
}
class Nil<T> extends List<T> {
U reduce(U init, Function<U, Pair<U, T>> f) {
return init;
}
}
class Cons<T> extends List<T> {
private T head;
private List<T> tail;
public Cons(T head, List<T> tail) {
this.head = head;
this.tail = tail;
}
U reduce(U init, Function<U, Pair<U, T>> f) {
return this.tail.reduce(
f(new Pair<U, T>(init, this.head)),
f
);
}
}
With first-class functions (this might be slightly off; it's been a while!):
So the trick to recursive data is that whenever we need to pass a sub-value to one of our N given functions, if that sub-value is of our recursive type (like the 'tail' of a list is another list) then we first call that sub-value with the same N functions we've been given. That way, the structure 'reduces' down to a single result.
Here's a slightly different Java example, for variety in the examples you're getting ;) I also recommend checking out the paper on object algebras [0], which takes this approach much further.
Notice that in some sense, the structure of the type is inferable from just the visitor interface. Everything else is just an explosion of boilerplate. (This is somewhat explained in the object algebras framework, as you can have multiple types accepting these visitors, just as much as having multiple visitors for the same type. In other words, this is related to the "expression problem".)
// An "external visitor", with the recursion external to the type being visited.
// The visitor is responsible for visiting each of the children.
public interface ExprVisitor1<Result> {
Result lit(double x);
Result add(Expr left, Expr right);
Result sub(Expr left, Expr right);
}
// An "internal visitor", with the recursion internal to the type being visited.
// I like these best, because the recursion can be turned into a tight loop
// (defunctionalize the continuation!) in a single place (in Expr).
// But you lose some expressivity, e.g. no short-circuiting the recursion.
// You can elaborate the recursion scheme of course, e.g.
// Result add(Supplier<Result> left, Supplier<Result> right);
// (but now it might be impossible to flatten the stack)
public interface ExprVisitor2<Result> {
Result lit(double x);
Result add(Result left, Result right);
Result sub(Result left, Result right);
}
public abstract class Expr {
private Expr() {}
public abstract <Result> Result visit(ExprVisitor2<Result> visitor);
public static Expr lit(final double x) {
return new Expr() {
public @Override <Result> Result visit(final ExprVisitor2<Result> visitor) {
return visitor.lit(x);
}
}
}
public static Expr add(final Expr left, final Expr right) {
return new Expr() {
public @Override <Result> Result visit(final ExprVisitor2<Result> visitor) {
return visitor.add(left.visit(visitor), right.visit(visitor));
}
}
}
public static Expr sub(final Expr left, final Expr right) {
return new Expr() {
public @Override <Result> Result visit(final ExprVisitor2<Result> visitor) {
return visitor.sub(left.visit(visitor), right.visit(visitor));
}
}
}
}
The code you've selected is not "for circles", per se. This is classic double-dispatch -- the function itself represents a circle (via the `x, y, r` values it closes over), and it chooses which receiver to invoke based on its identity. (The parameters in the selected function may be better named `onCircle` and `onRectangle`.)
If you just have a Shape, and you need to do something specific depending on the kind of Shape you have, you need some way to tell what kind of Shape you have. You can use `instanceof` and casting, but there's no guarantee that you've handled all cases(^). Moreover, it's painful in some languages (like Java) to extract the subclass-specific fields, as you need to rebind the value to a new variable of the right type first.
The Visitor pattern is a classic object-oriented solution to this problem, typically using double dispatch. The Shape itself knows what kind of shape it is, so rather than asking it what type it is, you provide it a set of _strategies_ (no relation to the Strategy pattern), one for each type of Shape. The Shape doesn't know what you want to do with it, so it calls you right back, invoking the circle- or rectangle-specific logic depending on what kind of shape it is. (Hence, double-dispatch.)
Gabriel (OP) observes that the Visitor pattern is exactly the Boehm-Berarducci encoding of a sum type. The Visitor pattern is very common in OO programming (see, for instance, abstract syntax trees), so the fact that we're so often using an encoding of a more direct concept is worth remarking on. I know I'd much rather use sum types in general than use the Visitor pattern.
(^) As an aside, I've never found "Shape" to be a very convincing example of sum types, as it's much easier to imagine as an open family than as a closed family. In an open family of shapes, there is no "all cases", and instanceof/casting is inappropriate from the beginning. I think object algebras (see my other comment) give a more motivating class of examples of closed families, including ASTs.
I would like to support your comment and add that I enjoy these articles because I like programming languages and thinking about program execution.
However, I think what delibes is getting at is that this is article exhibits a classic trigger for most developers because it starts with naming some language (i.e. Haskell) and then it is filled with assertions that are always "What If": what if your language doesn't support sum types or recursion or algebraic data types or ... Most devs are looking for practical applications for their language of choice so there is a natural inclination toward a critical comparison of "their" language and "my" language.
But we should follow Twisol here and not read this article as "language X is better than language Y" or, more precisely, "throw out unnecessary features from language X because you can still perform some task Z".
Just take the article for what it is: a great "explanation"[1] of the relation between mathematical foundations and language features or characteristics. This article isn't some heretical tantrum so just sit back and enjoy the learning.
The purpose of the OP post is not to provide an introduction to the visitor pattern. It's to explain the relationship of the visitor pattern with something else.
Did you miss this part of the post?
> I’m not going to provide a standalone explanation of the visitor pattern since the linked Wikipedia page already does that.
Obviously, not. Not even apples versus oranges. Church encoding shows you that "all you need is lambda", which is the same to say all you need is a membrane in biology.
Even further, Lambda calculus shows you that function creation and application are necessary and sufficient for everything, with obvious parallels to biology (enzymes are just proteins).
Visitor pattern is just some wired wrapping to satisfy a rigid type system, which composition of Traits or typeclasses would solve. One just pass a function which knows the structure.
Formally, `A + B` is isomorphic to `forall T. (A -> T, B -> T) -> T`, where the inner `(A -> T, B -> T)` is the type of a visitor.
a + b
-- CPS transform
= forall t. ((a + b) -> t) -> t
-- distribute -> over +
= forall t. (a -> t, b -> t) -> t
-- if you want to drop even the product, distribute -> over *
-- but this loses you the ability to name a separable Visitor
= forall t. (a -> t) -> (b -> t) -> t
type Visitor a b t = (a -> t, b -> t)
type Sum a b = forall t. Visitor a b t -> t
iso :: Sum a b -> (a + b)
iso s = s (Left, Right)
osi :: (a + b) -> Sum a b
osi (Left a) = \(onA, onB) -> onA a
osi (Right b) = \(onA, onB) -> onB b
A and B are free to be chosen by a producer of the generic Sum type. However, T can be chosen "late", by a consumer of Sum; a value of type Sum A B must work for any T you decide to use down the line.
You're right that there is no benefit in creating another abstraction, but the point of the post is sometimes the language doesn't have support for the original abstraction (e.g. sum types), so in some cases the other abstraction (e.g. visitor pattern or Church encoding) is the only available abstraction.
Look, I never tried to be offensive or even bully. But I care about the principle of calling things by its proper names and precise language usage. I am describing things exactly how I see them.
And I have reasons to do so. Like so many others I have traveled that road, from Haskell basics up to the latest writings and courses of that self-propelled category theory expert - Bartosz, for whom I have great respect.
However, at the end of the journey I came to different conclusions, that the whole subfield is nothing but a sect (the definition is a consensus based group of eager supporters) and the whole set of nested abstractions is empty of meaning, except in producing deeper and deeper nested abstractions. I cold provide analogies with Eastern religious sects, which I have studied too, where abstract things are described in minute details, and the merit is in the knowledge of these minute details, but I won't. It will only complicate this discussion.
So I don't see any meaning, and I see socially constructed interested, identical to esoteric teachings, which is even better definition of what Bartosz and others are doing.
Oh, I forgot to mention, that "enzymes are proteins" is isomorphic (lol) to "procedures are list structures" (or "code is data") which explains the miracle of Lisp and it's macros and connects Lisp to life itself, and justifies why MIT folks ware so fascinated with it.
I use Church encoding quite a lot in Java for a poor mans pattern matching / ADTs. It's one of the more useful patterns I use.
import java.util.function.Function;
public abstract class Tree {
// Constructor private so the type is sealed.
private Tree() {}
public abstract <T> T match(Function<Empty, T> a, Function<Leaf, T> b, Function<Node, T> c);
public static final class Empty extends Tree {
public <T> T match(Function<Empty, T> a, Function<Leaf, T> b, Function<Node, T> c) {
return a.apply(this);
}
public Empty() {}
}
public static final class Leaf extends Tree {
public final int n;
public <T> T match(Function<Empty, T> a, Function<Leaf, T> b, Function<Node, T> c) {
return b.apply(this);
}
public Leaf(int n) { this.n = n; }
}
public static final class Node extends Tree {
public final Tree left;
public final Tree right;
public <T> T match(Function<Empty, T> a, Function<Leaf, T> b, Function<Node, T> c) {
return c.apply(this);
}
public Node(Tree left, Tree right) {
this.left = left; this.right = right;
}
}
}
If the author is here, just a very minor nitpick: You could have done without the shadowing in the examples as that might be confusing to people not entirely awake or not familiar with Haskell.
Thank you for the feedback. I was conscientious of that shadowing issue when writing it, but I just wasn't sure what to change on either side to differentiate them.
Starting from the recognition that there’s a trick you can do with typed lambdas to represent ‘types’, it then proceeds to show that you can use pattern matching on those ‘types’ to implement something like the visitor pattern.
It never even comes close to showing what that wins you. We found a gang-of-four shaped nail. Done.
But the thing is the visitor pattern is a response to a particular problem: double dispatch. You have some logic that needs to vary based on two different types. The classic example is a game where you want to calculate damage effects for different kinds of attack against different kinds of monsters.
If you start from a problem like that, the visitor pattern turns out to be useful (but is not the only way to solve it).
It’s possible - hard to tell from first reading - that what this article is actually suggesting is that Church Encoding can be used to solve double dispatch problems, by letting you encode a visitor pattern in a particularly elegant way.
Which would be a much more interesting insight!
It’s far more likely that you are facing a double dispatch problem and looking for a programming tool to solve it with, than that you have elected to use Church encoding to build some types for some reason and are now looking to determine which gang-of-four patterns you can implement in your new type calculus...