Is the "expression problem" solvable in F #?

Question

I watched an interesting video in which type classes in Haskell are used to solve the so-called "expression problem". After about 15 minutes, he shows how class types can be used to “open” a data type based on a discriminatory join for expansion. Additional discriminators can be added separately without changing / restoring the original definition.

I know that type classes are not available in F #, but is there a way to use other language functions to achieve such extensibility? If not, how close can we get to solving the problem of expression in F #?

Clarification: I assume that the problem is defined as described in the previous video in the series - data type extensibility and data type operations with modulation functions at the code level and separate compilation (extensions can be deployed as separate modules without the need to change or recompile the source code) as well as static type security.

Answer 1

As Jörg noted in a comment, it depends on what you mean by decision. If you mean a solution that involves some form of type checking that you are missing an implementation of a function for any case, then F # does not give you any elegant way (and I'm not sure if the Haskell solution elegantly). You can encode it using the SML solution mentioned by kvb, or perhaps using one of the OO solutions .

In fact, if I were developing a real system that should solve the problem, I would choose a solution that does not give you full verification, but is much easier to use.

A sketch would have to use obj as a type representation and use reflection to define functions that provide an implementation for individual cases. I would probably tag all parts using some attribute to simplify the check. A module that adds an 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 rather elegant solution that is easy to use and not so difficult to implement (using reflection). Verifying that you have not missed a case is not performed at compile time, but you can easily write unit tests for this.

Answer 2

See Vesa Karvonen's comment here for one SML solution (albeit cumbersome), which is easy to translate to F #.

Answer 3

I know that type classes are not available in F #, but is there a way to use other language functions to achieve such extensibility?

I don’t believe that, no.

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

The problem with the expression is to allow the user to expand 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 it's impossible to add new union cases to an existing union type), and class types make it easier to output new class types (but it's impossible to add new methods to an existing class hierarchy). These are two forms of extensibility required in practice . The ability to spread in both directions at the same time without compromising the static type is just academic curiosity, IME.

By the way, the most elegant way to provide such extensibility that I have seen is to sacrifice type security and use the so-called "rule-based programming". Mathematica does this. For example, to compute a symbolic derivative of an expression that is an integer literal, variable, or append, you can write in Mathematica as follows:

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

We can modify the support for multiplication as follows:

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

and we can add a new function to evaluate the expression as follows:

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

For me it is much more elegant than any of the solutions written in languages ​​such as OCaml, Haskell and Scala, but, of course, this is not a safe type.