0

I was trying to understand the use of multi-methods recently and saw several claims that they solve the Expression Problem. However, I ended concluding that it is not the multi-methods that solve it, but the open methods, which usually accompany the multi-methods. Open methods being the methods that are defined outside the objects body, but still perform dynamic dispatch on the object arguments. This is also claimed in this article https://eli.thegreenplace.net/2016/the-expression-problem-and-its-solutions/.

Because the Expression Problem is about a tradeoff in the way the code can be extended, my intuition was telling me that there must be some other tradeoff hidden with the open methods too. I was not able to identify any shortcomings related to them (beside the loss of object centered code auto-completion for methods and the dot syntax, but I do not think this is a programming language issue, but the code editor issue) and searching provided me no additional information.

Are there any shortcomings and tradeoffs for a programming language that uses open methods?

Nemanja
  • 119
  • 2

1 Answers1

3

The tradeoff in open methods is that they are tricky or impossible to implement efficiently. Thus, they are primarily featured in object systems that value flexibility over raw performance, e.g. various Lisp dialects. Another example is Julia, which then tries to get rid of as much overhead as possible using JIT compilation.

Open methods must be dispatched entirely at runtime, since the set of available methods is not known until runtime. In contrast, classic OOP systems such as those used by C++ and Java know at compile time which methods are available, just not what the target of a call will be. This enables techniques such as vtable based dispatch which are quite efficient. There are some approaches that appear to have open methods, e.g. typeclasses in Haskell, traits in Rust, and extension methods in C#. However, none of these amount to open methods within the meaning of this question. Haskell and Rust have coherence/orphan rules that limit which modules can implement traits/typeclasses. C#'s extension methods are purely static and don't participate in dynamic dispatch. In contrast, Go's interfaces can be used similarly to open methods. After all, the magic that makes Go work is based heavily on runtime reflection.

That open methods cannot use vtables generally indicates that there is a global registry of types and methods which is filled at runtime, and that most method calls must search this table for matching method implementations. This is the case especially when method dispatch doesn't just depend on the first argument, but on multiple arguments (multi-methods). A more limited alternative would be open classes à la Ruby. While such solutions make it possible to implement solutions to the expression problem, this still does not allow us to encode solutions of the expression problem in a type system.

While open methods often use functional notation method(object, arg), this is purely syntactic. There is no reason why dot-notation object.method(arg) would be impossible. Of course, while some autocomplete will be possible, it is not possible to know the entire set of available methods before run-time. In languages that are built around multi-methods, dot notation might be misleading since the first argument might not contribute to method dispatch.

amon
  • 132,749
  • 27
  • 279
  • 375
  • Thanks, this clears it up nicely. When you say "... this still does not allow us to encode solutions of the expression problem in a type system", do you mean the Ruby solution does not encode it, or it can not be encoded in general? – Nemanja Apr 14 '21 at 06:21
  • @Nemanja In that part, I'm trying to make a distinction between writing code that solves the expression problem in a very dynamic language (comparatively easy), and creating a proof in a static type system that a given approach solves the expression problem (type checks are automated proofs). This problem is very hard when static typing is involved, e.g. there was a multi-year debate whether Java's generics were expressive enough to encode a solution. I don't think a statically typed solution to the expression problem is impossible, but I haven't kept track of the literature on that problem. – amon Apr 14 '21 at 06:56