Coercing existing types for internal DSL in F#

Question

Given a DU for an AST (a very simple expression tree)

type Expression =
  | Add of list<Expression>
  | Var of string
  | Val of float

I want to write an operator + such that I can write

let x = "s" + 2.0

and have

x = Add [(Var "s"); (Val 2.0)]

Furthermore, I want this to be usable from other assemblies (by opening some stuff).

My real application is a similar but larger DU for a real AST. I am on F# 4.8.

What works so far is

let (+) a b =
    Add [a; b]
x = (Var "s") + (Val 2.0)

but here I still have to wrap "s" and "2.0" by hand. I want to avoid this wrapping.

I tried several other things:

Declaring type extensions and an interface and using both static type parameters and interface constraints:

First the interfaces

type IToExpression =
  abstract member ToExpression : Expression

type Expression with
  member this.ToExpression = this

type System.String with
  member this.ToExpression = Var this

type System.Double with
  member this.ToExpression = Val this

let (+++)
    (a : 'S when 'S :> IToExpression)
    (b : 'T when 'T :> IToExpression) =
    Add [a.ToExpression; b.ToExpression]

And then the same with statically resolved type parameters.

let (++) a b =
  let a = (^t : (member ToExpression: Expression) a)
  let b = (^t : (member ToExpression: Expression) b)
  Add [a; b]

Edit: But as pointed out in this answer (and due to sloppy copying by me) this approach needs more work to even get to the real problem.

But both ++ and +++ fail to typecheck in the wanted expression, i.e., the lines

let x = "s" ++ 2.0
let x = "s" +++ 2.0

I read through

• statically resolved type parameters | SO
• F# generic type constraints and duck typing | SO
• fsharp extension methods
• type extensions | MS docs/type-extensions
• statically resolved type parameters | MS docs

and my understanding is that with some extra code could convert everything, but refitting interfaces onto existing types and mixing that with statically resolved type parameters to apply member constraints is challenging.

Is there a way to solve this problem?

Answer 1

There are several subtle problems here.

First, SRTPs only work with inline functions. This is because they can't be compiled to IL (since IL doesn't support this kind of constraints), so they have to be resolved during compilation. Statically. That's why they're "statically resolved". The inline keyword enables the compiler to do that.

let inline (+) a b = ...

Second, what is this generic type ^t you're referencing? It's the type of what? I think you meant for it to be the type of a and b, but you haven't declared it as such, so it's just some random generic type floating around. It needs to be bound to the parameters:

let inline (+) (a: ^t) (b: ^t) = ...

Third, from your examples, it looks like you actually meant for a and b to be of different types, didn't you?

let inline (+) (a: ^a) (b: ^b) = ...

Fourth, extension methods don't count for statically resolved types, so you can't define ToExpression on String and float and expect it to work. The usual trick is to instead declare all your methods on a special class that exists just to hold those methods:

type ToExpressionStub() =
    static member ToExpression s = Var s
    static member ToExpression f = Val f

And then one might expect that this would work:

let inline (+) (a: ^a) (b: ^b) =
  let a = (ToExpression : (static member ToExpression: ^a -> Expression) a)
  let b = (ToExpression : (static member ToExpression: ^b -> Expression) b)
  Add [a; b]

But no, it won't. This is because statically resolved constraints cannot be applied to concrete types, only to type variables like ^a or ^b. So what to do?

Well, we can just give our function an extra parameter like this:

let inline (+) (dummy: ^c) (a: ^a) (b: ^b) =
  let a = (^c : (static member ToExpression: ^a -> Expression) a)
  let b = (^c : (static member ToExpression: ^b -> Expression) b)
  Add [a; b]

And then we'd have to pass a value of ToExpressionStub() on every call:

let x = (+) (ToExpressionStub()) "foo" 2.0

This is, of course, mighty inconvenient, so instead we will add another intermediate function with three parameters and call it from the operator (+):

let inline doAdd (dummy: ^c) (a: ^a) (b: ^b) =
  let a = (^c : (static member ToExpression: ^a -> Expression) a)
  let b = (^c : (static member ToExpression: ^b -> Expression) b)
  Add [a; b]

let inline (+) (a: ^a) (b: ^b) = doAdd (ToExpressionStub()) a b

Almost there! But this also doesn't quite work: on the line let b = ... we get a warning that "This construct makes the code less generic...", and then at use sites we get an error that we can't use either string or float, depending on which came first.

This happens for some very-very obscure reasons. The compiler sees the two constraints having the same shape and applied to the same type, and decides that they must be the same constraint, and therefore, ^a = ^b. To break this stalemate, we can simply change the shape of the constraints to make them different:

let inline doAdd (dummy: ^c) (a: ^a) (b: ^b) =
  let a = ((^a or ^c) : (static member ToExpression: ^a -> Expression) a)
  let b = ((^b or ^c) : (static member ToExpression: ^b -> Expression) b)
  Add [a; b]

Note that they are now applied to ^a or ^c and ^b or ^c respectively, not just ^c alone. This also has a bonus effect: we are no longer limited to just the types that we have enumerated in ToExpressionStub. We can use any type that has its own non-extension method ToExpression defined. For example, Expression itself:

type Expression =
  | Add of list<Expression>
  | Var of string
  | Val of float
  with
    static member ToExpression (e: Expression) = e

And that's it! This now works:

> let x = 2.0 + "foo"
Add [Val 2.0; Var "foo"]

> let y = x + "bar"
Add [Add [Val 2.0; Var "foo"]; Var "bar"]

Finally, to reduce runtime allocation costs, I usually have a singleton instance of ToExpressionStub rather than create a new one on every call:

type ToExpressionStub() = 
    static member val Value = ToExpressionStub()
    ...

let inline (+) (a: ^a) (b: ^b) = doAdd ToExpressionStub.Value a b

---

The bottom line is that yes, you can do it, but please carefully think about whether you should.

In actual practice this kind of trickery actually hinders development rather than help it. Sure, it may look all super neat and clever at first, but several months from now you will look at your own code and be unable to understand what's going on. Please trust my experience: having to wrap values in Val and Var is a feature, not a bug. Program code is read much more than it's written. Don't shoot yourself in the foot.