5 ms·

I'm surprised that the article and none of the comments so far mentioned the "Expression Problem": http://c2.com/cgi/wiki?ExpressionProblem http://c2.com/cgi/wi

by ufo 10y ago

I'm surprised that the article and none of the comments so far mentioned the "Expression Problem": http://c2.com/cgi/wiki?ExpressionProblem http://c2.com/cgi/wiki?ExpressionProblem Basically, if you structure the control flow in object oriented style (or church encoding...) then its easy to extend your program with new "classes" but if you want to add a new methods then you must go back and rewrite all your classes. On the other hand, if you use if-statements (or switch or pattern matching ...) then its hard to add new "classes" but its very easy to add new "methods". I'm a bit disappointed that this isn't totally common knowledge by now. I think its because until recently pattern matching and algebraic data types (a more robust alternative to switch statements) were a niche functional programming feature and because "expression problem" is not a very catchy name.

jake-low 10y ago
I was familiar with the problem but didn't have a name for it; thanks for providing me with one. What kind of work has there been on creating programming paradigms that make it easy to both add new types and new methods? Is it a CAP-theorem-type problem where every solution is a trade-off, or is there a way to have your cake and eat it too?
- chenglou 10y ago
  There are languages (libraries) that solve it. For reference, check Clojure's multimethods and OCaml's polymorphic variants.
  - smallnamespace 10y ago
    The tradeoff is that techniques like multimethods significantly weaken the contract that people normally expect from methods/classes. For example, if I'm writing a normal Java class, I know where I go to find methods dealing specifically with instances Foo (namely Foo and its children and direct users); with multimethods, it's more likely that there is some multimethod out there in an unrelated class that looks for instances of Foo.
    - eru 10y ago
      Good tooling (think something along the lines of Hoogle) can help here.
  - edwintorok 10y ago
    The OCaml solution with polymorphic variants: http://www.math.nagoya-u.ac.jp/~garrigue/papers/fose2000.html http://www.math.nagoya-u.ac.jp/~garrigue/papers/fose2000.htm.... A very good summary of that paper is available here: http://lambda-the-ultimate.org/node/1518#comment-17566 http://lambda-the-ultimate.org/node/1518#comment-17566 Another alternative based on recursive modules: http://www.math.nagoya-u.ac.jp/~garrigue/papers/#privaterows http://www.math.nagoya-u.ac.jp/~garrigue/papers/#privaterows
- ufo 10y ago
  There is plenty of research out there about trying to solve the expression problem and the wikipedia article has links to some of them: https://en.wikipedia.org/wiki/Expression_problem https://en.wikipedia.org/wiki/Expression_problem That said, there is a complexity and readability trade-off (that is hard to quantify) because these more flexible programming patterns that can solve the expression problem are more complicated than plain method dispatching or switch statements.
- glibgil 10y ago
  The comments in this thread and the link to ltu in this thread talk about one of the simplest and most elegant solutions to the expression problem https://m.reddit.com/r/haskell/comments/4gjf7g/is_solving_the_expression_problem_worth_the_bother/ https://m.reddit.com/r/haskell/comments/4gjf7g/is_solving_th...
- optforfon 10y ago
  here was an interesting proposal for a solution in C++ https://channel9.msdn.com/Events/CPP/C-PP-Con-2014/0007-Accept-No-Visitors https://channel9.msdn.com/Events/CPP/C-PP-Con-2014/0007-Acce...
svanderbleek 10y ago
FP and particularly the Haskell community is very aware of the expression problem and you can find many blog posts and papers on solutions.
- eru 10y ago
  That 'ufo' knows about the name expression problem at all betrays that they are very aware of that work in the FP community.
userbinator 10y ago
Another alternative is "table-oriented programming", where you define the "classes" and "methods" as an m-by-n structure of code pointers; to add either "methods" or "classes", you would just add a new row/column to the table along with the appropriate code definitions. and because "expression problem" is not a very catchy name. It's also not particularly descriptive either, but the page mentions that it's a form of "cross-cutting concern", to which the table-oriented approach basically says "do not explicitly separate the concerns." (More discussion and an article on that approach here: https://news.ycombinator.com/item?id=9406815 https://news.ycombinator.com/item?id=9406815 ) As a bit of a fun fact, doing table-oriented stuff in C is one of the few actual uses for a triple-indirection. :-)
- juped 10y ago
  Is that you, TopMind? I used to be on Wiki years ago too...
  - jwdunne 10y ago
    As a side note, I was pretty surprised that the name isn't as in "I have a great mind" but rather "I have a table oriented programming mind". At first, I had a knee jerk "wow arrogant" reaction and then felt guilty when I realised!
runeks 10y ago
> I think its because until recently pattern matching and > algebraic data types (a more robust alternative to > switch statements) [...] Could you elaborate a bit on what this accomplishes, eg. pattern matching vs a "case" statement? As I've programmed in Haskell for the past year or two, I've observed exactly this change in my style of writing - that I've started to get rid of "case" statements inside function definitions, and have moved them into the pattern-matching part instead ("outside" the function definition). But I have to admit, I'm not entirely sure why I do this. It just feels more robust to me in some way.
- sundarurfriend 10y ago
  Just FYI, I asked a pretty similar question a few months ago here [1]. The main arguments for pattern matching seemed to be that: * [at least some] compilers will check for exhaustiveness * "Pattern matching isn't just conditional matching. It's also binding, and even some common operations. " [1] https://news.ycombinator.com/item?id=11159321 https://news.ycombinator.com/item?id=11159321
- ufo 10y ago
  I was just comparing the pattern matching from FP languages with the more primitive C-like switch statement. The big advantage comes from the algebraic data types (tagged unions), which let you model data with many "cases" in a type-safe manner. For example, in Haskell we don't have null pointers because we can use the Maybe type instead. The case-expression vs function-definition difference you mentioned from Haskell is just syntactic sugar. In both situations you are doing exactly the same pattern matching under the hood.

by ufo 10y ago

jake-low 10y ago

I was familiar with the problem but didn't have a name for it; thanks for providing me with one. What kind of work has there been on creating programming paradigms that make it easy to both add new types and new methods? Is it a CAP-theorem-type problem where every solution is a trade-off, or is there a way to have your cake and eat it too?

chenglou 10y ago
There are languages (libraries) that solve it. For reference, check Clojure's multimethods and OCaml's polymorphic variants.
- smallnamespace 10y ago
  The tradeoff is that techniques like multimethods significantly weaken the contract that people normally expect from methods/classes. For example, if I'm writing a normal Java class, I know where I go to find methods dealing specifically with instances Foo (namely Foo and its children and direct users); with multimethods, it's more likely that there is some multimethod out there in an unrelated class that looks for instances of Foo.
  - eru 10y ago
    Good tooling (think something along the lines of Hoogle) can help here.
- edwintorok 10y ago
  The OCaml solution with polymorphic variants: http://www.math.nagoya-u.ac.jp/~garrigue/papers/fose2000.html http://www.math.nagoya-u.ac.jp/~garrigue/papers/fose2000.htm.... A very good summary of that paper is available here: http://lambda-the-ultimate.org/node/1518#comment-17566 http://lambda-the-ultimate.org/node/1518#comment-17566 Another alternative based on recursive modules: http://www.math.nagoya-u.ac.jp/~garrigue/papers/#privaterows http://www.math.nagoya-u.ac.jp/~garrigue/papers/#privaterows
ufo 10y ago
There is plenty of research out there about trying to solve the expression problem and the wikipedia article has links to some of them: https://en.wikipedia.org/wiki/Expression_problem https://en.wikipedia.org/wiki/Expression_problem That said, there is a complexity and readability trade-off (that is hard to quantify) because these more flexible programming patterns that can solve the expression problem are more complicated than plain method dispatching or switch statements.
glibgil 10y ago
The comments in this thread and the link to ltu in this thread talk about one of the simplest and most elegant solutions to the expression problem https://m.reddit.com/r/haskell/comments/4gjf7g/is_solving_the_expression_problem_worth_the_bother/ https://m.reddit.com/r/haskell/comments/4gjf7g/is_solving_th...
optforfon 10y ago
here was an interesting proposal for a solution in C++ https://channel9.msdn.com/Events/CPP/C-PP-Con-2014/0007-Accept-No-Visitors https://channel9.msdn.com/Events/CPP/C-PP-Con-2014/0007-Acce...

svanderbleek 10y ago

FP and particularly the Haskell community is very aware of the expression problem and you can find many blog posts and papers on solutions.

eru 10y ago
That 'ufo' knows about the name expression problem at all betrays that they are very aware of that work in the FP community.

userbinator 10y ago

Another alternative is "table-oriented programming", where you define the "classes" and "methods" as an m-by-n structure of code pointers; to add either "methods" or "classes", you would just add a new row/column to the table along with the appropriate code definitions. and because "expression problem" is not a very catchy name. It's also not particularly descriptive either, but the page mentions that it's a form of "cross-cutting concern", to which the table-oriented approach basically says "do not explicitly separate the concerns." (More discussion and an article on that approach here: https://news.ycombinator.com/item?id=9406815 https://news.ycombinator.com/item?id=9406815 ) As a bit of a fun fact, doing table-oriented stuff in C is one of the few actual uses for a triple-indirection. :-)

juped 10y ago
Is that you, TopMind? I used to be on Wiki years ago too...
- jwdunne 10y ago
  As a side note, I was pretty surprised that the name isn't as in "I have a great mind" but rather "I have a table oriented programming mind". At first, I had a knee jerk "wow arrogant" reaction and then felt guilty when I realised!

runeks 10y ago

> I think its because until recently pattern matching and > algebraic data types (a more robust alternative to > switch statements) [...] Could you elaborate a bit on what this accomplishes, eg. pattern matching vs a "case" statement? As I've programmed in Haskell for the past year or two, I've observed exactly this change in my style of writing - that I've started to get rid of "case" statements inside function definitions, and have moved them into the pattern-matching part instead ("outside" the function definition). But I have to admit, I'm not entirely sure why I do this. It just feels more robust to me in some way.

sundarurfriend 10y ago
Just FYI, I asked a pretty similar question a few months ago here [1]. The main arguments for pattern matching seemed to be that: * [at least some] compilers will check for exhaustiveness * "Pattern matching isn't just conditional matching. It's also binding, and even some common operations. " [1] https://news.ycombinator.com/item?id=11159321 https://news.ycombinator.com/item?id=11159321
ufo 10y ago
I was just comparing the pattern matching from FP languages with the more primitive C-like switch statement. The big advantage comes from the algebraic data types (tagged unions), which let you model data with many "cases" in a type-safe manner. For example, in Haskell we don't have null pointers because we can use the Maybe type instead. The case-expression vs function-definition difference you mentioned from Haskell is just syntactic sugar. In both situations you are doing exactly the same pattern matching under the hood.