FSharpPlus divRem - 它是如何工作的？

Question

看看FSharpPlus我正在考虑如何创建一个用于的泛型函数

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

并提出了一个可能的(工作)解决方案

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

然后我看了FSharpPlus如何实现它,我发现:

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

我确信有充分的理由可以这样做; 但是我不喜欢为什么这样做,但是:

这是如何运作的？

是否有任何文档有助于理解这种语法是如何工作的,尤其是三个DivRem静态方法重载？

编辑

因此,FSharp +实现的优点是,如果divRem调用中使用的数字类型实现了DivRem静态成员(例如BigInteger),它将用于代替可能存在的算术运算符.假设DivRem比调用默认运算符更有效,这将使divRem在效率方面达到最佳.但问题仍然存在:

为什么我们需要引入"歧义"(o1)？

我们称之为三个重载o1,o2,o3

如果我们注释掉o1并使用其类型未实现DivRem的数字参数调用divRem(例如int或float),则由于成员约束而无法使用o3.编译器可以选择O2,但它并不像它说:"你有一个完美的签名匹配超载O3(所以我会忽略O2不到完美的签名),但该成员约束不满足".因此,如果我取消O1,我希望它说:"你有两个完美的签名重载(所以我会忽略O2不到完美的签名),但它们都有未了的约束".相反,它似乎说"你有两个完美的签名重载,但它们都有未完成的约束,所以我会采取o2,即使签名不完美,也可以完成这项工作".避免使用o1技巧并让编译器说"你完美的签名重载o3有一个未实现的成员约束,这样做是不正确的,所以我采取的o2虽然不是完美的签名但可以完成工作",即使在第一个实例？

Answer 1

首先让我们看一下有关重载方法的文档,这些方法没有多少说法:

重载方法是在给定类型中具有相同名称但具有不同参数的方法.在F#中,通常使用可选参数而不是重载方法.但是,如果参数是元组形式而不是curry形式,则允许在语言中使用重载方法.

(强调我的).之所以需要的参数是在元组的形式是因为编译器必须能够知道,在函数调用点,其过载被调用.例如,如果我们有:

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

然后编译器将无法编译该g函数,因为它在代码中此时不会知道f应该调用哪个版本.所以这段代码含糊不清.

现在,查看类中这三个重载的静态方法DivRem,它们有三种不同的类型签名:

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  )

此时,您可能会问自己编译器如何在这些静态重载之间进行选择:如果省略第三个参数,则第二个和第三个似乎无法区分,如果给出第三个参数但是是实例DivRem,那么第一次超载看起来很模糊.此时,将该代码粘贴到F#Interactive会话中可以提供帮助,因为F#Interactive将生成更具体的类型签名,可以更好地解释它.这是我将代码粘贴到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

DivRem这里的第一个实现是最容易理解的; 其类型签名与FSharpPlus源代码中定义的签名相同.查看有关约束的文档,null和struct约束相反:null约束意味着"提供的类型必须支持null文字"(不包括值类型),struct约束意味着"提供的类型必须是.NET值类型".因此,实际上永远不会选择第一个过载; 正如Gustavo在他的出色答案中指出的那样,它只存在以便编译器能够处理这个类.(尝试省略第一次重载并调用divRem 5m 3m:您会发现它无法使用错误进行编译:

"十进制"类型不支持运算符"DivRem"

所以第一个重载只是为了欺骗F#编译器做正确的事情.然后我们将忽略它并传递给第二次和第三次重载.

现在,第二个和第三个重载在第三个参数的类型上有所不同.第二个重载的参数是基类(Default1),第三个重载的参数是派生类(DivRem).这些方法总是以DivRem实例作为第三个参数调用,那么为什么要选择第二个方法呢？答案在于第三种方法的自动生成类型签名:

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

static member DivRem这里的参数约束是由以下行生成的:

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

这是因为F#编译器如何处理带out参数的函数调用.在C#中,DivRem这里要查找的静态方法是带参数的方法(a, b, out c).F#编译器将该签名转换为签名(a, b) -> c.因此,这种类型的约束看起来像一个静态方法BigInteger.DivRem与参数调用它(D, d, &r),其中&r在F#就像是out r在C#.该调用的结果是商,它将余数分配out给给定方法的参数.所以这个重载只是DivRem在提供的类型上调用静态方法,并返回一个元组quotient, remainder.

最后,如果提供的类型没有DivRem静态方法,那么第二个重载(Default1签名中的重载)是最终被调用的重载.这个看起来重载*,-和/运营商所提供的种类和使用它们来计算商和余数.

换句话说,正如古斯塔沃的更短的答案所解释的那样,这里的DivRem类将遵循以下逻辑(在编译器中):

• 如果DivRem对所使用的类型有静态方法,请调用它,因为它假定它可以针对该类型进行优化.
• 否则,计算出商数q为D / d,然后计算出其余部分D - q * d.

就是这样:在复杂的剩下的只是迫使F#编译器做正确的事,并用一个非常漂亮的最终divRem功能就是尽可能高效.

Answer 2

您的实现很好,它实际上与第二个重载相同,它对应于默认实现.

F#+是一个F#基础库,类似于F#核心,它也使用了回退机制.F#core使用静态优化并以非安全的方式伪造某些类型约束,但这种技术在F#编译器项目之外是不可能的,因此F#+通过对重载方法的特征调用实现相同的效果,而不需要伪造静态约束.

所以,你的实现和一个在F#+之间的唯一区别是,F#+会先看看(在编译时)一DivRem类中的数字类型的定义静态成员被使用,与标准.NET签名(使用返回值和引用,而不是元组),这是第3次重载.此方法可以具有优化的特定实现.我的意思是,假设如果存在这种方法,它将在最差的情况下与默认定义相同.

如果这个方法不存在,它将回退到默认定义,正如我所说,它是第二个重载.

第一个重载永远不会匹配,只是在重载集中创建必要的歧义.

目前还没有详细记录这种技术,因为微软的文档中的例子有点不幸,因为它没有真正起作用(可能是因为它没有足够的模糊性),但是@rmunn的答案非常有用.详细解释.

编辑

关于你的问题更新:这不是F#编译器的工作方式,至少现在是这样.在重载解析之后,静态约束正在被解决,并且当不满足这些约束时它不会回溯.

使用约束添加另一个方法会使问题变得足够复杂,迫使编译器在最终重载解析之前进行一些约束求解.

这些天我们正在讨论是否应该纠正这种行为,这似乎不是一件小事.