3 ms·

That's the classic "Expression Problem" (aptly named wrt its common appearance in ASTs). Note that it's relatively straight forward to express the function-ext

by Nitramp 14y ago

That's the classic "Expression Problem" (aptly named wrt its common appearance in ASTs). Note that it's relatively straight forward to express the function-extensibility through the visitor pattern in an OO language; in a functional language, you could probably implement your own dynamic dispatch technique to get the type-extensibility. In both cases, you'll end up with some boilerplate, depending on your language. E.g. for a complex language with lots of different AST node types, you'll end up with lots of tiny classes, mostly just implementing stupid constructors.

barrkel 14y ago
Function-extensibility using the visitor pattern in OO sucks compared to functional pattern matching. It is almost unusable except for the most trivial tree traversals. Frequently you want to be able to pass arguments down and return values up the tree traversal. Using visitors, you need a whole separate class for each unique function arity, or you have to use tedious little data carrier instances. Sometimes you want to switch between them half-way through the traversal, e.g. use your constant-folding visitor during an optimization visit, and the visual overhead of constructing visitors and keeping track of them, making sure they're all linked together properly, is really ugly. Don't even think about matching the visitor method on more than one parameter type, like you might do with e.g. overload resolution of binary operators. I've been there working on a commercial compiler, and I don't want to go back there again. Haskell can implement the OO style using existential types (forall), a bit like Go's interfaces, except once you put a value into an existential type variable, you can't typecast it back out again.
- pacala 14y ago
  > Function-extensibility using the visitor pattern in OO sucks compared to functional pattern matching. Not only that, but using the visitor pattern tilts the extend types / extend functions into extend functions realm, soundly defeating the supposed advantage of being open to extend on types. As such, visitor pattern is precisely the same as a switch statement. The only difference left is language specific. In Java, adding a new type will make your compiler whine if you have abstract methods in the visitor. That's because javac can't tell when a switch over enums is exhaustive.
- ufo 14y ago
  > Haskell can implement the OO style using existential types (forall), Although on emight say that passing functions (closures) or records of functions explicitly might be a more idiomatic pattern.

by Nitramp 14y ago

barrkel 14y ago

Function-extensibility using the visitor pattern in OO sucks compared to functional pattern matching. It is almost unusable except for the most trivial tree traversals. Frequently you want to be able to pass arguments down and return values up the tree traversal. Using visitors, you need a whole separate class for each unique function arity, or you have to use tedious little data carrier instances. Sometimes you want to switch between them half-way through the traversal, e.g. use your constant-folding visitor during an optimization visit, and the visual overhead of constructing visitors and keeping track of them, making sure they're all linked together properly, is really ugly. Don't even think about matching the visitor method on more than one parameter type, like you might do with e.g. overload resolution of binary operators. I've been there working on a commercial compiler, and I don't want to go back there again. Haskell can implement the OO style using existential types (forall), a bit like Go's interfaces, except once you put a value into an existential type variable, you can't typecast it back out again.

pacala 14y ago
> Function-extensibility using the visitor pattern in OO sucks compared to functional pattern matching. Not only that, but using the visitor pattern tilts the extend types / extend functions into extend functions realm, soundly defeating the supposed advantage of being open to extend on types. As such, visitor pattern is precisely the same as a switch statement. The only difference left is language specific. In Java, adding a new type will make your compiler whine if you have abstract methods in the visitor. That's because javac can't tell when a switch over enums is exhaustive.
ufo 14y ago
> Haskell can implement the OO style using existential types (forall), Although on emight say that passing functions (closures) or records of functions explicitly might be a more idiomatic pattern.