4 ms·

What is so bad about OO for compilers? An AST can naturally be modeled as a class hierarchy. Visitor pattern for AST transformations.

by qznc 13y ago

rayiner 13y ago
> What is so bad about OO for compilers? See my comment about the expression problem in another thread: https://news.ycombinator.com/item?id=6783075 https://news.ycombinator.com/item?id=6783075, as well as this response: https://news.ycombinator.com/item?id=6784057 https://news.ycombinator.com/item?id=6784057. A compiler is a program that consists of lots of different algorithms (operations) that operates on a pretty well-defined set of data (an AST or an IR). Changes to the data representation are rare compared to changes to the operations on that data. What OO does in a compiler is totally obscure the control flow of each algorithm by spreading the logic out over dozens of classes. You can look at an AST node and see at a glance how it participates in constant folding or code generation, but if you're trying to optimize the constant folding algorithm or the code generator, you've got to follow control flow across dozens of different classes. Using visitor pattern mitigates this somewhat, because you can have ConstFolder::visitBinaryOperation, ConstFolder::visitFunctionCall, etc, all in one file, but note that visitor pattern is just a really verbose, roundabout way of writing a switch statement! If you add a new type of AST node, you have to add a visitNewAstNode call to the visitor interface, and then go update every class that implements the visitor interface. This is no easier, and a lot more verbose, than simply adding a new variant to an AST ADT then fixing up all the places where the compiler complains that your pattern match is no longer exhaustive. For a good example, look at how LLVM does instruction simplification: http://llvm.org/docs/doxygen/html/InstructionSimplify_8cpp_source.html#l03023 http://llvm.org/docs/doxygen/html/InstructionSimplify_8cpp_s.... A good old switch statement, no "simplify" method in the "Instruction" class nor visitor pattern.
- seanmcdirmid 13y ago
  Scala, use traits and type variables, the problem is really easy to solve through what I call an open class pattern. See "new age components for old fashioned java" OOPSLA 2001, note I'm using Flatt's term "extensibility problem" which is the same as Wadler's "expression problem" term. But if you want your control flow to be in place, then a 10,000 line case match ala scalac should be right up your alley. Frankly, I'd rather divide and conquer, which is what OOP is good at.

What is so bad about OO for compilers? An AST can naturally be modeled as a class hierarchy. Visitor pattern for AST transformations.

by qznc 13y ago

What is so bad about OO for compilers? An AST can naturally be modeled as a class hierarchy. Visitor pattern for AST transformations.

rayiner 13y ago

> What is so bad about OO for compilers? See my comment about the expression problem in another thread: https://news.ycombinator.com/item?id=6783075 https://news.ycombinator.com/item?id=6783075, as well as this response: https://news.ycombinator.com/item?id=6784057 https://news.ycombinator.com/item?id=6784057. A compiler is a program that consists of lots of different algorithms (operations) that operates on a pretty well-defined set of data (an AST or an IR). Changes to the data representation are rare compared to changes to the operations on that data. What OO does in a compiler is totally obscure the control flow of each algorithm by spreading the logic out over dozens of classes. You can look at an AST node and see at a glance how it participates in constant folding or code generation, but if you're trying to optimize the constant folding algorithm or the code generator, you've got to follow control flow across dozens of different classes. Using visitor pattern mitigates this somewhat, because you can have ConstFolder::visitBinaryOperation, ConstFolder::visitFunctionCall, etc, all in one file, but note that visitor pattern is just a really verbose, roundabout way of writing a switch statement! If you add a new type of AST node, you have to add a visitNewAstNode call to the visitor interface, and then go update every class that implements the visitor interface. This is no easier, and a lot more verbose, than simply adding a new variant to an AST ADT then fixing up all the places where the compiler complains that your pattern match is no longer exhaustive. For a good example, look at how LLVM does instruction simplification: http://llvm.org/docs/doxygen/html/InstructionSimplify_8cpp_source.html#l03023 http://llvm.org/docs/doxygen/html/InstructionSimplify_8cpp_s.... A good old switch statement, no "simplify" method in the "Instruction" class nor visitor pattern.

seanmcdirmid 13y ago
Scala, use traits and type variables, the problem is really easy to solve through what I call an open class pattern. See "new age components for old fashioned java" OOPSLA 2001, note I'm using Flatt's term "extensibility problem" which is the same as Wadler's "expression problem" term. But if you want your control flow to be in place, then a 10,000 line case match ala scalac should be right up your alley. Frankly, I'd rather divide and conquer, which is what OOP is good at.