6 ms·

This article discusses details of trying to use language features to model a fairly basic problem but doesn’t discuss the fundamentals of the problem very much.

by amluto 1y ago

This article discusses details of trying to use language features to model a fairly basic problem but doesn’t discuss the fundamentals of the problem very much. If I have O operations (e.g. evaluate, stringify) and T types, then I need O•T implementations. If I fix O, I can add types until the cows come home by adding O implementations per new type. If I fix T, I can add new operations with T implementations per operation. If I want to let O and T vary, then the number of implementations I need to add per additional operation/type varies depending on what I’ve added before. No amount of programming language magic will change this basic count. ISTM what’s really going on in the article is that the author is using the programming language as a registry of implementations. Those O•T implementations need to be stored somewhere so their callers can find them. In C++ this can be done when very verbose inheritance and virtual calls. In other languages, it’s less verbose. If multiple dispatch is built in, then one can use it directly. One can, of course, also build an actual table indexed on operation and type as a data structure in just about any language and use it, and in a language like C++ the result may well be quite a bit nicer than using a class hierarchy.

kqr 1y ago
Huh, this is a very neat way to put it. Something about it seems... too neat? But I'm the wrong person to poke holes in it. Can I see other people debate it civilly?
- magnio 1y ago
  My first exposure to the expression problem is the book Crafting Interpreters, Section 5.3.1,[1] which is very similar to the GP comment. The subsection is a short few paragraphs, with one or two tables for illustration, and it was one of the most eureka moments of my programming career. Ever since then, I see this trade-off everywhere, and I get reminded that engineering is all about finding the best trade-off and that the holy-grail of a perfect language or design is a waste of time. [1]: https://craftinginterpreters.com/representing-code.html#the-expression-problem https://craftinginterpreters.com/representing-code.html#the-...
moelf 1y ago
this is counting it as if O only takes an argument, which is single dispatch, which OOP covers already (the `self` is the single argument). In practice, Multiple Dispatch shines when you have 1) more than one argument type (duh) 2) higher order `O` operation [1] [1]: think of a numerical routine that calls eigen or something, and you want eigen to exploit the matrix's type, such as symmetry or upper-triangular, and this is encoded as a matrix type)
- layer8 1y ago
  In the expression problem, the other argument is the operation to be invoked, which can vary at runtime as well. OOP doesn’t cover that.
HarHarVeryFunny 1y ago
Overloading operators like "+" to work on new types, and maybe mixed types, requires each desired combination of operator and operand types to be implemented (as one can easily do in a language like C++, and presumably also in more modern languages). If there is any commonality between types as to how these operators are meant to work, then generics such as C++'s templates can also be used to reduce the number of implementations to those that are actually distinct. I don't understand what problem the author is trying to solve here - maybe it's language specific? More related to dynamic typing and efficient dispatch? In any case, operator overloading, while it can make for cute-to-read code, isn't really a good idea for code readability and maintenance.
- Kranar 1y ago
  >I don't understand what problem the author is trying to solve here - maybe it's language specific? More related to dynamic typing and efficient dispatch? The expression problem only arises in statically typed programming languages, it does not exist in dynamically typed programming languages. Operating overloading has nothing to do with the problem and can not be used to resolve it. Operators are nothing more than a one-off syntax so we can use familiar childhood notation like a + b, etc... they are not particularly meaningful. The ability to overload operators or functions in general is also irrelevant since such overloads are resolved statically at compile time.
  - munificent 1y ago
    > The expression problem only arises in statically typed programming languages, it does not exist in dynamically typed programming languages. Wadler's list of requirements for solving the expression problem include "with static checking that all cases are covered", so in one sense, yes, dynamic languages don't have this "problem". But in another sense, dynamic languages simply have no chance to solve the problem because they don't statically check anything. It is true that it's much easier to do multiple dispatch and open-ended extension in dymamic languages. That's a nice benefit of them. But you do sacrifice all of the safety, code navigation, and performance of static types in order to get that. The problem Wadler is trying to solve is "how can we have this sort of open-ended extension in both directions without giving up static safety?"
moron4hire 1y ago
I think the article as it stands makes that all pretty clear. But the point of the article is more that the language selection will determine how difficult it is to do that if you don't have control over the original definition of the operations or types.
naasking 1y ago
> One can, of course, also build an actual table indexed on operation and type as a data structure in just about any language and use it, and in a language like C++ the result may well be quite a bit nicer than using a class hierarchy. This requires unsafe casting and thus doesn't actually solve the expression problem, which is about how to do this without compromising safety. Your approach is what the solution to the expression problem in Haskell effectively does at runtime though, via type classes and the dictionary-passing translation that they undergo during compilation, but it's all type safe.
HarHarVeryFunny 1y ago
> In C++ this can be done when very verbose inheritance and virtual calls. No - in C++ you'd just define the operators (either as global functions, or member functions of the types/classes in question), and the language's overload resolution rules would select the right implementation for each usage. You could use inheritence (and virtual overrides if needed), or templates/generics, if you wanted to - C++ certainly gives you a lot of ways to make things more complex and shoot yourself in the foot, but the normal/obvious way would just be to define the overloaded operators and be done with it.
- layer8 1y ago
  The expression problem is about dynamic dispatch, not static dispatch. For example, you call a function F that returns an object of one of the relevant types, and another function G that returns one of the relevant operations, and then you apply the operation to the object. How can you have F extend the set of types, and also G extend the set of operations, without having to recompile the caller, or without F and G having to coordinate, and also avoid a runtime error due to a missing implementation of some operation for some type.
  - HarHarVeryFunny 1y ago
    I agree (although others in this thread do not), but the comment I was responding to was claiming that in C++ operator overloading requires inheritance and virtual methods, and I was just pointing out that this is not true.
    - layer8 1y ago
      The comment you responded to doesn’t mention overloading.
      - HarHarVeryFunny 1y ago
        > In C++ this can be done when very verbose inheritance and virtual calls Virtual methods overload the corresponding method in the parent class they are inheriting from. It could be a named method like "add()", or an operator like "+()". The author of that comment is implicitly assuming that all types are derived via inheritance from a common base type that defines all the (virtual) methods/operators being overloaded.
layer8 1y ago
The problem is how to statically ensure that you don’t run into the case of a missing implementation for some combination at runtime, in particular in languages with separate compilation. If you have a library A that defines a basic (T, O) set, and two libraries B and C that aren’t aware of each other but both use A, where B adds a new type and C adds a new operation, and finally you have a program D that uses both B and C, how do you statically detect or prevent the case where D tries to use the new type from B with the new operation from C, but no one has provided an implementation for that combination; while also supporting the case of the required implementation being present.
- HarHarVeryFunny 1y ago
  > The problem is how to statically ensure that you don’t run into the case of a missing implementation Static (compile-time) guarantees are only applicable to languages with static binding rules, in which case there is no problem - the compiler will just report "cannot resolve overloaded function" or something similar. This is of course one of the downsides to languages with dynamic types and dynamic binding ... that many errors can only be detected at runtime.

by amluto 1y ago

kqr 1y ago

Huh, this is a very neat way to put it. Something about it seems... too neat? But I'm the wrong person to poke holes in it. Can I see other people debate it civilly?

magnio 1y ago
My first exposure to the expression problem is the book Crafting Interpreters, Section 5.3.1,[1] which is very similar to the GP comment. The subsection is a short few paragraphs, with one or two tables for illustration, and it was one of the most eureka moments of my programming career. Ever since then, I see this trade-off everywhere, and I get reminded that engineering is all about finding the best trade-off and that the holy-grail of a perfect language or design is a waste of time. [1]: https://craftinginterpreters.com/representing-code.html#the-expression-problem https://craftinginterpreters.com/representing-code.html#the-...

moelf 1y ago

this is counting it as if O only takes an argument, which is single dispatch, which OOP covers already (the `self` is the single argument). In practice, Multiple Dispatch shines when you have 1) more than one argument type (duh) 2) higher order `O` operation [1] [1]: think of a numerical routine that calls eigen or something, and you want eigen to exploit the matrix's type, such as symmetry or upper-triangular, and this is encoded as a matrix type)

layer8 1y ago
In the expression problem, the other argument is the operation to be invoked, which can vary at runtime as well. OOP doesn’t cover that.

HarHarVeryFunny 1y ago

Overloading operators like "+" to work on new types, and maybe mixed types, requires each desired combination of operator and operand types to be implemented (as one can easily do in a language like C++, and presumably also in more modern languages). If there is any commonality between types as to how these operators are meant to work, then generics such as C++'s templates can also be used to reduce the number of implementations to those that are actually distinct. I don't understand what problem the author is trying to solve here - maybe it's language specific? More related to dynamic typing and efficient dispatch? In any case, operator overloading, while it can make for cute-to-read code, isn't really a good idea for code readability and maintenance.

Kranar 1y ago
>I don't understand what problem the author is trying to solve here - maybe it's language specific? More related to dynamic typing and efficient dispatch? The expression problem only arises in statically typed programming languages, it does not exist in dynamically typed programming languages. Operating overloading has nothing to do with the problem and can not be used to resolve it. Operators are nothing more than a one-off syntax so we can use familiar childhood notation like a + b, etc... they are not particularly meaningful. The ability to overload operators or functions in general is also irrelevant since such overloads are resolved statically at compile time.
- munificent 1y ago
  > The expression problem only arises in statically typed programming languages, it does not exist in dynamically typed programming languages. Wadler's list of requirements for solving the expression problem include "with static checking that all cases are covered", so in one sense, yes, dynamic languages don't have this "problem". But in another sense, dynamic languages simply have no chance to solve the problem because they don't statically check anything. It is true that it's much easier to do multiple dispatch and open-ended extension in dymamic languages. That's a nice benefit of them. But you do sacrifice all of the safety, code navigation, and performance of static types in order to get that. The problem Wadler is trying to solve is "how can we have this sort of open-ended extension in both directions without giving up static safety?"

moron4hire 1y ago

I think the article as it stands makes that all pretty clear. But the point of the article is more that the language selection will determine how difficult it is to do that if you don't have control over the original definition of the operations or types.

naasking 1y ago

> One can, of course, also build an actual table indexed on operation and type as a data structure in just about any language and use it, and in a language like C++ the result may well be quite a bit nicer than using a class hierarchy. This requires unsafe casting and thus doesn't actually solve the expression problem, which is about how to do this without compromising safety. Your approach is what the solution to the expression problem in Haskell effectively does at runtime though, via type classes and the dictionary-passing translation that they undergo during compilation, but it's all type safe.

HarHarVeryFunny 1y ago

> In C++ this can be done when very verbose inheritance and virtual calls. No - in C++ you'd just define the operators (either as global functions, or member functions of the types/classes in question), and the language's overload resolution rules would select the right implementation for each usage. You could use inheritence (and virtual overrides if needed), or templates/generics, if you wanted to - C++ certainly gives you a lot of ways to make things more complex and shoot yourself in the foot, but the normal/obvious way would just be to define the overloaded operators and be done with it.

layer8 1y ago
The expression problem is about dynamic dispatch, not static dispatch. For example, you call a function F that returns an object of one of the relevant types, and another function G that returns one of the relevant operations, and then you apply the operation to the object. How can you have F extend the set of types, and also G extend the set of operations, without having to recompile the caller, or without F and G having to coordinate, and also avoid a runtime error due to a missing implementation of some operation for some type.
- HarHarVeryFunny 1y ago
  I agree (although others in this thread do not), but the comment I was responding to was claiming that in C++ operator overloading requires inheritance and virtual methods, and I was just pointing out that this is not true.
  - layer8 1y ago
    The comment you responded to doesn’t mention overloading.
    - HarHarVeryFunny 1y ago
      > In C++ this can be done when very verbose inheritance and virtual calls Virtual methods overload the corresponding method in the parent class they are inheriting from. It could be a named method like "add()", or an operator like "+()". The author of that comment is implicitly assuming that all types are derived via inheritance from a common base type that defines all the (virtual) methods/operators being overloaded.

layer8 1y ago

The problem is how to statically ensure that you don’t run into the case of a missing implementation for some combination at runtime, in particular in languages with separate compilation. If you have a library A that defines a basic (T, O) set, and two libraries B and C that aren’t aware of each other but both use A, where B adds a new type and C adds a new operation, and finally you have a program D that uses both B and C, how do you statically detect or prevent the case where D tries to use the new type from B with the new operation from C, but no one has provided an implementation for that combination; while also supporting the case of the required implementation being present.

HarHarVeryFunny 1y ago
> The problem is how to statically ensure that you don’t run into the case of a missing implementation Static (compile-time) guarantees are only applicable to languages with static binding rules, in which case there is no problem - the compiler will just report "cannot resolve overloaded function" or something similar. This is of course one of the downsides to languages with dynamic types and dynamic binding ... that many errors can only be detected at runtime.