4
$\begingroup$

The Expression Problem refers to add new representations and new behaviors to the original data types without modifying the source code.

This restriction is very common, the interface may be a precompiled library, or from an upstream module, or it is inconvenient to modify due to license and other reasons.

The functional programming and object-oriented programming cannot directly solve this problem.

Functional languages is easy to add new behaviors but difficult to add new representations.

Object-oriented languages is easy to add new representations but difficult to add new behaviors.


I also encountered this troublesome problem in language design.

Some complex design models are raised to regulate this problem, and requires quite a bit of code.

But I want to know if anyone has tried to solve this problem from the language level?

For example, some additional magic annotation to greatly reduce the amount of code required for these extension.

$\endgroup$

2 Answers 2

7
$\begingroup$

But I want to know if anyone has tried to solve this problem from the language level?

Sure! Bruno C. d. S. Oliveira is working on this for ages! He's best-known for work on Object Algebras which are akin to Final Tagless approach.

Their more recent Compositional Programming paper greatly expands upon Object Algebras addressing many shortcomings. The authors propose both (Scala-like) syntax and semantics for a compositional language. An implementation of the CP language in PureScript is available on the Github.


Update

I forgot to mention pretty obvious and well-known: Multiple Dispatch aka Multi-methods in languages like Common Lisp, Clojure and Julia solve Expression Problem for a long time. Wikipedia page has several examples and many further references.

Multi-methods are not very popular and seldom used (particularly in Clojure) due to poor performance. But Julia made them run very fast thanks to run-time type specialization, devirtualization and aggressive inlining. So they are the main abstraction mechanism, and this way Julia indeed successfully avoids the Expression Problem and achieves high level of library interoperability most of the time.

Unfortunately Multi-methods rely on run-time dispatch and thus do not provide type-safety and do not necessarily adhere to the Liskov Substitution Principle. That's why I'm more interested in statically typed approaches like Compositional Programming mentioned above.

$\endgroup$
2
  • $\begingroup$ Several of these links don't work for me. Are they perhaps internal to your institution? Is one of them cs.utexas.edu/~wcook/Drafts/2012/ecoop2012.pdf $\endgroup$ Jun 7, 2023 at 7:45
  • $\begingroup$ @BruceAdams unfortunately I have no idea what might be the problem. I'm not in an institution, but still can freely access all the links. At the very least you can try to search for alternative links on Google Scholar, I think... $\endgroup$ Jun 7, 2023 at 10:39
4
$\begingroup$

I think of it like a table where the rows are the data types, and the columns are the behaviours. (So e.g. rows are classes, columns are interfaces; or rows are algebraic data types, columns are functions which accept those types.)

An object-oriented language is organised by the "rows":

  • For every behaviour associated with a class, the implementation of that behaviour is written within the class.
  • Adding a new "row" is easy: you just write a new class and implement whatever interfaces it needs.
  • Adding a new "column" is hard: if you add a method to an interface, or create a new interface, you have to edit every class all over the project.

A functional language is organised by the "columns":

  • For every data type that a behaviour is implemented for, the implementation of that behaviour is written where the function is declared.
  • Adding a new "column" is easy: you just write a new function and make it handle whatever data types it needs to.
  • Adding a new "row" is hard: e.g. if you add a new variant to some enum type, you have to edit every function that consumes that enum type.

Of course this is just the broad idea, both OO and FP languages have design patterns which allow organising in the opposite way. For example, in an OO language the visitor pattern groups by the implementations of one behaviour for many classes; in an FP language, first-class functions can be included as fields in a data type so that these functions are implemented together where the type is constructed. It's just that these design patterns are only needed when you want to organise code in a way that isn't directly encouraged by the paradigm you're writing in.


So this is a fundamental problem in language design, and I don't think it can really be "solved", there are just different options with different trade-offs. Ultimately, if one module in a program can add a new "row" and another can add a new "column" to the big "table", then someone needs to decide who is responsible for filling in the "cell" where the new row and the new column overlap.

That is, when there is a new type and a new function, and the new type has to work with the new function, then the behaviour has to be defined somewhere.


All of that said, there are some approaches in existing languages which do address the problem, even if they don't outright solve it. I'll mention traits in Rust: in the analogy, types (structs and enums) are the "rows", and traits are the "columns".

  • A trait can be implemented on multiple types, and a type can implement multiple traits. So you can add either a new row or a new column.
  • An implementation for a trait can be written either where the type is declared, or where the trait is declared ─ or elsewhere, within reasonable limits. You aren't allowed to implement third-party traits for third-party types, because this would cause the code to break if one of those third parties ever decided to implement the same trait for the same type themselves.
  • There's no free lunch: the "new row, new column" problem still requires an implementation to be written somewhere. But at least it never requires changing third-party code, unless both the new "row" and the new "column" are in third-party libraries.

On the other hand, this allows code to be organised neither by "row" nor by "column", at least within a project you can scatter trait implementations across many files, which can lead to a messy project structure. This isn't exactly a language design flaw, because it's the user's responsibility to organise their code in a logical way; and it's also attenuated by modern IDEs which can efficiently locate all implementations of a trait. Still, some people might consider it a drawback that the language allows users to make more of a mess if they don't organise their code well.

$\endgroup$
7
  • 1
    $\begingroup$ "You aren't allowed to implement third-party traits for third-party types, because this would cause the code to break if one of those third parties ever decided to implement the same trait for the same type themselves." -- This is allowed in Swift, but it's discouraged because the linker decides which implementation "wins" and that can cause problems. See forums.swift.org/t/retroactive-conformances-vs-swift-in-the-os/… $\endgroup$
    – Bbrk24
    Jun 6, 2023 at 20:07
  • $\begingroup$ "So this is a fundamental problem in language design, and I don't think it can really be "solved"" — you already mentioned Visitor pattern that basically solves the problem. Another approach if Final Tagless. Thus the obvious answer is to provide better syntax to define visitors. And that's just the tip of the iceberg, you can learn much more from Oliveira's papers linked from my answer. $\endgroup$ Jun 7, 2023 at 10:45
  • $\begingroup$ @AlexChichigin The visitor pattern doesn't "solve" the expression problem, it merely flips it along a diagonal axis. Adding a new behaviour (i.e. a new column) becomes easy, you just write one more visitor ─ but then adding a new representation (i.e. a new row) becomes difficult because you need to change every visitor. The visitor pattern in OOP (or function-valued fields in FP) only address the problem by letting the programmer choose which kind of extension is easy and which is hard; they don't make both easy. $\endgroup$
    – kaya3
    Jun 7, 2023 at 13:33
  • $\begingroup$ @kaya3 well, yeah, but visitor does solve the issues you mention with a bit of care. :) First, to solve the Expression Problem you can't change the old code, but you obviously allowed to add new one. So you can't go back and stick a new field into "data objects" you already have, you have to subclass them. Now your old visitors can't handle new subclasses but you're allowed to subclass them to add new behaviour. Now if you use your new visitors everywhere instead of the old ones, you solved the problem. And if you had "catch all" branch in all the visitors that "forwards" you can use them too. $\endgroup$ Jun 7, 2023 at 14:46
  • 1
    $\begingroup$ @AlexChichigin It doesn't solve them, as I explained. Adding a new field to an existing type (i.e. changing a representation, not adding a new representation) is orthogonal to the expression problem. $\endgroup$
    – kaya3
    Jun 7, 2023 at 14:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .