FSharpPlus divRem - how does it work?

Question

Looking at FSharpPlus I was thinking to how to create a generic function to be used in

let qr0  = divRem 7  3
let qr1  = divRem 7I 3I
let qr2  = divRem 7. 3.

and came out with a possible (working) solution

let inline divRem (D:^T) (d:^T): ^T * ^T = let q = D / d in q,  D - q * d

then I looked at how FSharpPlus implemented it and I found:

open System.Runtime.InteropServices

type Default6 = class end
type Default5 = class inherit Default6 end
type Default4 = class inherit Default5 end
type Default3 = class inherit Default4 end
type Default2 = class inherit Default3 end
type Default1 = class inherit Default2 end

type DivRem =
    inherit Default1
    static member inline DivRem (x:^t when ^t: null and ^t: struct, y:^t, _thisClass:DivRem) = (x, y)
    static member inline DivRem (D:'T, d:'T, [<Optional>]_impl:Default1) = let q = D / d in q,  D - q * d
    static member inline DivRem (D:'T, d:'T, [<Optional>]_impl:DivRem  ) =
        let mutable r = Unchecked.defaultof<'T>
        (^T: (static member DivRem: _ * _ -> _ -> _) (D, d, &r)), r

    static member inline Invoke (D:'T) (d:'T) :'T*'T =
        let inline call_3 (a:^a, b:^b, c:^c) = ((^a or ^b or ^c) : (static member DivRem: _*_*_ -> _) b, c, a)
        let inline call (a:'a, b:'b, c:'c) = call_3 (a, b, c)
        call (Unchecked.defaultof<DivRem>, D, d)    

let inline divRem (D:'T) (d:'T) :'T*'T = DivRem.Invoke D d

I am sure that there are good reasons to make it as such; however I am not interested in why it's been done like that, but:

How does this work?

Is there any documentation helping to understand how this syntax works, especially the three DivRem static method overloads?

EDIT

So, the FSharp+ implementation has the advantage that, if the numeric type used in the divRem call implements a DivRem static member (like BigInteger for example), it will be used in place of the possibly existing arithmetic operators. This, assuming that DivRem is more efficient than calling the default operators, would make divRem optimal in efficiency. Yet a question remains:

why do we need to introduce the "ambiguity" (o1)?

Let's call the three overloads o1, o2, o3

If we comment out o1 and call divRem with a numeric parameter whose type doesn't implement DivRem (e.g. int or float), then o3 can't be used because of the member constraint. The compiler could choose o2, but it doesn't, like it said "you have a perfect signature matching overload o3 (so I will ignore the less than perfect signature in o2) but the member constraint is not fulfilled". Therefore, if I uncomment o1, I would expect it to say "you have two perfect signature overloads (so I will ignore the less than perfect signature in o2) but both of them have unfulfilled constraints". Instead it appears to say "you have two perfect signature overloads but both of them have unfulfilled constraints, so I will take o2 that, even with a less than perfect signature, can do the job". Wouldn't it be more correct to avoid the o1 trick and let the compiler say "your perfect signature overload o3 has an unfulfilled member constraint, so I take o2 which is less than perfect in signature but can do the job" even in the first instance?

Answer 1

First let's look at the documentation on overloaded methods, which doesn't have that much to say:

Overloaded methods are methods that have identical names in a given type but that have different arguments. In F#, optional arguments are usually used instead of overloaded methods. However, overloaded methods are permitted in the language, provided that the arguments are in tuple form, not curried form.

(Emphasis mine). The reason for requiring the arguments to be in tuple form is because the compiler must be able to know, at the point where the function is called, which overload is being called. E.g., if we had:

let f (a : int) (b : string) = printf "%d %s" a b
let f (a : int) (b : int) = printf "%d %d" a b

let g = f 5

Then the compiler wouldn't be able to compile the g function since it wouldn't know at this point in the code which version of f should be called. So this code would be ambiguous.

Now, looking at those three overloaded static methods in the DivRem class, they have three different type signatures:

static member inline DivRem (x:^t when ^t: null and ^t: struct, y:^t, _thisClass:DivRem)
static member inline DivRem (D:'T, d:'T, [<Optional>]_impl:Default1)
static member inline DivRem (D:'T, d:'T, [<Optional>]_impl:DivRem  )

At this point, you might be asking yourself how the compiler would choose between these static overloads: the second and third would seem to be indistinguishable if the third parameter is omitted, and if the third parameter is given but is an instance of DivRem, then it looks ambiguous with the first overload. At this point, pasting that code into an F# Interactive session can help, as F# Interactive will generate more specific type signatures that might explain it better. Here's what I got when I pasted that code into F# Interactive:

type DivRem =
  class
    inherit Default1
    static member
      DivRem : x: ^t * y: ^t * _thisClass:DivRem -> ^t *  ^t
                 when ^t : null and ^t : struct
    static member
      DivRem : D: ^T * d: ^T * _impl:Default1 -> ^a *  ^c
                 when ^T : (static member ( / ) : ^T * ^T -> ^a) and
                      ( ^T or  ^b) : (static member ( - ) : ^T * ^b -> ^c) and
                      ( ^a or  ^T) : (static member ( * ) : ^a * ^T -> ^b)
    static member
      DivRem : D: ^T * d: ^T * _impl:DivRem -> 'a * ^T
                 when ^T : (static member DivRem : ^T * ^T * byref< ^T> -> 'a)
    static member
      Invoke : D: ^T -> d: ^T -> ^T *  ^T
                 when (DivRem or ^T) : (static member DivRem : ^T * ^T * DivRem -> ^T * ^T)
  end

The first DivRem implementation here is the easiest to understand; its type signature is the same as the one defined in the FSharpPlus source code. Looking at the documentation on constraints, the null and struct constraints are opposite: the null constraint means "the provided type must support the null literal" (which excludes value types), and the struct constraint means "the provided type must be a .NET value type". So the first overload can never actually be chosen; as Gustavo points out in his excellent answer, it only exists so that the compiler will be able to handle this class. (Try omitting that first overload and calling divRem 5m 3m: you'll find that it fails to compile with the error:

The type 'decimal' does not support the operator 'DivRem'

So the first overload exists only to trick the F# compiler into doing the right thing. We'll then ignore it and pass on to the second and third overloads.

Now, the second and third overloads differ in the type of the third parameter. The second overload has the parameter being a base class (Default1), and the third overload has the parameter being a derived class (DivRem). These methods will always be called with a DivRem instance as the third parameter, so why would the second method ever be chosen? The answer lies in the automatically-generated type signature for the third method:

static member
  DivRem : D: ^T * d: ^T * _impl:DivRem -> 'a * ^T
             when ^T : (static member DivRem : ^T * ^T * byref< ^T> -> 'a)

The static member DivRem parameter constraint here was generated by the line:

(^T: (static member DivRem: _ * _ -> _ -> _) (D, d, &r)), r

This happens because of how the F# compiler treats calls to functions with out parameters. In C#, the DivRem static method that's being looked for here is one with parameters (a, b, out c). The F# compiler turns that signature into the signature (a, b) -> c. So this type constraint looks for a static method like BigInteger.DivRem and calls it with the parameters (D, d, &r) where &r in F# is like out r in C#. The result of that call is the quotient, and it assigns the remainder to the out parameter given to the method. So this overload just calls the DivRem static method on the provided type, and returns a tuple of quotient, remainder.

Finally, if the provided type doesn't have a DivRem static method, then the second overload (the one with Default1 in its signature) is the one that ends up being called. This one looks for overloaded *, - and / operators on the provided types and uses them to calculate a quotient and remainder.

In other words, as Gustavo's much shorter answer explains, the DivRem class here will follow the following logic (in the compiler):

• If there is a static DivRem method on the types being used, call it since it's assumed that it may be optimized for that type.
• Otherwise, calculate the quotient q as D / d, then calculate the remainder as D - q * d.

That's it: the rest of the complexity is just to force the F# compiler to do the right thing, and end up with a nice-looking divRem function that's as efficient as possible.

Answer 2

Your implementation is just fine, it's actually the same as the 2nd overload, which correspond to the default implementation.

F#+ is an F# base library, similar to F# core, and it also uses a fallback mechanism. F# core uses static optimizations and fakes some type constraints in a non-safe way, but this technique is not possible outside the F# compiler project, so F#+ achieve the same effect with a trait call to an overloaded method, without need to fake static constraints.

So, the only difference between your implementation and the one in F#+ is that F#+ will first look (at compile-time) for a DivRem static member defined in the class of the numeric type being used, with a standard .NET signature (using a return value and a reference, instead of a tuple) which is the 3rd overload. This method could have an optimized, specific implementation. I mean, it is assumed that if this method exists it will be at worst equally optimal than the default definition.

If this method does not exists, it will fallback to the default definition, which as I said it's the 2nd overload.

The 1st overload will never match and it's there only to create the necessary ambiguity in the overload set.

This technique, is not well documented at the moment, as the example in the docs from Microsoft is a bit unfortunate since it doesn't really work, (probably because it doesn't have enough ambiguity), but @rmunn answer has a very detailed explanation.

EDIT

Regarding your question update: That's not the way the F# compiler works, at least right now. Static constraints are being solved after overload resolution, and it doesn't backtrack when these constraints are not fulfilled.

Adding another method with constraints complicates enough the problem in a way that forces the compiler to do some constraint solving before the final overload resolution.

These days we're having some discussions questioning whether this behavior should be corrected, which doesn't seem to be a trivial thing.