Is the "expression problem" solvable in F#?

Question

I've been watching an interesting video in which type classes in Haskell are used to solve the so-called "expression problem". About 15 minutes in, it shows how type classes can be used to "open up" a datatype based on a discriminated union for extension -- additional discriminators can be added separately without modifying / rebuilding the original definition.

I know type classes aren't available in F#, but is there a way using other language features to achieve this kind of extensibility? If not, how close can we come to solving the expression problem in F#?

Clarification: I'm assuming the problem is defined as described in the previous video in the series -- extensibility of the datatype and operations on the datatype with the features of code-level modularization and separate compilation (extensions can be deployed as separate modules without needing to modify or recompile the original code) as well as static type safety.

Answer 1

As Jörg pointed out in a comment, it depends on what you mean by solve. If you mean solve including some form of type-checking that the you're not missing an implementation of some function for some case, then F# doesn't give you any elegant way (and I'm not sure if the Haskell solution is elegant). You may be able to encode it using the SML solution mentioned by kvb or maybe using one of the OO based solutions.

In reality, if I was developing a real-world system that needs to solve the problem, I would choose a solution that doesn't give you full checking, but is much easier to use.

A sketch would be to use obj as the representation of a type and use reflection to locate functions that provide implementation for individual cases. I would probably mark all parts using some attribute to make checking easier. A module adding application to an expression might look like this:

[<Extends("Expr")>]  // Specifies that this type should be treated as a case of 'Expr'
type App = App of obj * obj

module AppModule = 
  [<Implements("format")>] // Specifies that this extends function 'format'
  let format (App(e1, e2)) =
    // We don't make recursive calls directly, but instead use `invoke` function
    // and some representation of the function named `formatFunc`. Alternatively
    // you could support 'e1?format' using dynamic invoke.
    sprintfn "(%s %s)" (invoke formatFunc e1) (invoke formatFunc e2)

This does not give you any type-checking, but it gives you a fairly elegant solution that is easy to use and not that difficult to implement (using reflection). Checking that you're not missing a case is not done at compile-time, but you can easily write unit tests for that.

Answer 2

See Vesa Karvonen's comment here for one SML solution (albeit cumbersome), which can easily be translated to F#.

Answer 3

I know type classes aren't available in F#, but is there a way using other language features to achieve this kind of extensibility?

I do not believe so, no.

If not, how close can we come to solving the expression problem in F#?

The expression problem is about allowing the user to augment your library code with both new functions and new types without having to recompile your library. In F#, union types make it easy to add new functions (but impossible to add new union cases to an existing union type) and class types make it easy to derive new class types (but impossible to add new methods to an existing class hierarchy). These are the two forms of extensibility required in practice. The ability to extend in both directions simultaneously without sacrificing static type safety is just an academic curiosity, IME.

Incidentally, the most elegant way to provide this kind of extensibility that I have seen is to sacrifice type safety and use so-called "rule-based programming". Mathematica does this. For example, a function to compute the symbolic derivative of an expression that is an integer literal, variable or addition may be written in Mathematica like this:

D[_Integer, _] := 0
D[x_Symbol, x_] := 1
D[_Symbol, _] := 0
D[f_ + g_, x_] := D[f, x] + D[g, x]

We can retrofit support for multiplication like this:

D[f_ g_, x_] := f D[g, x] + g D[f, x]

and we can add a new function to evaluate an expression like this:

E[n_Integer] := n
E[f_ + g_] = E[f] + E[g]

To me, this is far more elegant than any of the solutions written in languages like OCaml, Haskell and Scala but, of course, it is not type safe.