8 ms·

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,

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...

dfgdghdf 6y ago
It's particularly weird because most statically-type functional languages have discriminated unions as a practical alternative to the visitor pattern anyway.
- jameshart 6y ago
  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.
  - dfgdghdf 6y ago
    I know in F# it is much better to use a discriminated union because you get automatic comparison and equals implementations. You can't use functions as map keys, for example.
  - Twisol 6y ago
    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. [0] https://oleksandrmanzyuk.wordpress.com/2014/06/18/from-object-algebras-to-finally-tagless-interpreters-2/ https://oleksandrmanzyuk.wordpress.com/2014/06/18/from-objec...
    - matt-noonan 6y ago
      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.
    - kaba0 6y ago
      Just a heads-up, but sealed classes (basically sum types) and proper pattern matching is coming to Java.
      - Twisol 6y ago
        After many years of not having them ;) I'll be very glad to be able to retire this well-used gripe.
- dboreham 6y ago
  Is that the same thing as algebraic data types?
  - Twisol 6y ago
    "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.
    - dboreham 6y ago
      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.
      - kaba0 6y ago
        Some languages have sealed classes for this reason.
- 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 ago
    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
- Gabriel439 6y ago
  Author here: Go does not have support for discriminated unions. The trick is not limited to functional programming languages but it is limited to languages that support generic programming / polymorphism
xaedes 6y ago
Python: import math def Circle(x, y, r): return (lambda visitCircle, visitRectangle : visitCircle(x, y, r)) def Rectangle(x, y, w, h): return (lambda visitCircle, visitRectangle : visitRectangle(x, y, w, h)) def area(shape): return shape( lambda x, y, r : math.pi * r * r, 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
- scaraffe 6y ago
  can someone explain how this works? or where I can learn more about this.
  - ajoseps 6y ago
    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.
  - deleted 6y ago
    [deleted]
  - kaba0 6y ago
    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.
haskellandchill 6y ago
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_encoding 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.
- jimmaswell 6y ago
  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.
Ericson2314 6y ago
"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.
- skybrian 6y ago
  That is changing the problem definition, which may or may not be a feasible move. "Double dispatch" is indeed a problem when the language you're allowed to use has to be taken as given, as it usually is.
  - Gabriel439 6y ago
    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.
  - dragonwriter 6y ago
    > "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.)
    - skybrian 6y ago
layer8 6y ago
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.
- tsimionescu 6y ago
  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.
  - layer8 6y ago
    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.
    - deleted 6y ago
      [deleted]
titzer 6y ago
It's worthwhile noting that the example makes use of more than just typed lambdas. It uses first-class polymorphism right off the bat.
brundolf 6y ago
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.
jimbokun 6y ago
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: https://www.joelonsoftware.com/2005/12/29/the-perils-of-javaschools-2/ https://www.joelonsoftware.com/2005/12/29/the-perils-of-java... 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.
guerrilla 6y ago
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.

dfgdghdf 6y ago

It's particularly weird because most statically-type functional languages have discriminated unions as a practical alternative to the visitor pattern anyway.

jameshart 6y ago
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.
- dfgdghdf 6y ago
  I know in F# it is much better to use a discriminated union because you get automatic comparison and equals implementations. You can't use functions as map keys, for example.
- Twisol 6y ago
  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. [0] https://oleksandrmanzyuk.wordpress.com/2014/06/18/from-object-algebras-to-finally-tagless-interpreters-2/ https://oleksandrmanzyuk.wordpress.com/2014/06/18/from-objec...
  - matt-noonan 6y ago
    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.
  - kaba0 6y ago
    Just a heads-up, but sealed classes (basically sum types) and proper pattern matching is coming to Java.
    - Twisol 6y ago
      After many years of not having them ;) I'll be very glad to be able to retire this well-used gripe.
dboreham 6y ago
Is that the same thing as algebraic data types?
- Twisol 6y ago
  "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.
  - dboreham 6y ago
    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.
    - kaba0 6y ago
      Some languages have sealed classes for this reason.
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 ago
  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
Gabriel439 6y ago
Author here: Go does not have support for discriminated unions. The trick is not limited to functional programming languages but it is limited to languages that support generic programming / polymorphism

xaedes 6y ago

Python: import math def Circle(x, y, r): return (lambda visitCircle, visitRectangle : visitCircle(x, y, r)) def Rectangle(x, y, w, h): return (lambda visitCircle, visitRectangle : visitRectangle(x, y, w, h)) def area(shape): return shape( lambda x, y, r : math.pi * r * r, 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

scaraffe 6y ago
can someone explain how this works? or where I can learn more about this.
- ajoseps 6y ago
  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.
- deleted 6y ago
  [deleted]
- kaba0 6y ago
  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.

haskellandchill 6y ago

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_encoding 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.

jimmaswell 6y ago
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.

Ericson2314 6y ago

"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.

skybrian 6y ago
That is changing the problem definition, which may or may not be a feasible move. "Double dispatch" is indeed a problem when the language you're allowed to use has to be taken as given, as it usually is.
- Gabriel439 6y ago
  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.
- dragonwriter 6y ago
  > "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.)
  - skybrian 6y ago

layer8 6y ago

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.

tsimionescu 6y ago
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.
- layer8 6y ago
  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.
  - deleted 6y ago
    [deleted]

titzer 6y ago

It's worthwhile noting that the example makes use of more than just typed lambdas. It uses first-class polymorphism right off the bat.

brundolf 6y ago

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.

jimbokun 6y ago

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: https://www.joelonsoftware.com/2005/12/29/the-perils-of-javaschools-2/ https://www.joelonsoftware.com/2005/12/29/the-perils-of-java... 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.

guerrilla 6y ago

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.