完整、高效的NumericLiteral模块实现

Question

在this question讨论的基础上，是否有人可以提供代码或代码链接，显示NumericLiteralX模块(如this one)的完整实现？我特别感兴趣的是FromInt32/64的NumericLiteralX模块的高效实现，它简化了一般的数字运算。下面是从上述问题中提取的一个可能低效的实现：

module NumericLiteralG = 
    let inline FromZero() = LanguagePrimitives.GenericZero
    let inline FromOne() = LanguagePrimitives.GenericOne
    let inline FromInt32 (n:int) =
        let one : ^a = FromOne()
        let zero : ^a = FromZero()
        let n_incr = if n > 0 then 1 else -1
        let g_incr = if n > 0 then one else (zero - one)
        let rec loop i g = 
            if i = n then g
            else loop (i + n_incr) (g + g_incr)
        loop 0 zero 

如何改进和完成这一点？

Answer 1

我就写给FromInt32吧。在理想世界中，我们可以简单地将其定义为

let inline FromInt32 i = 
  ((^t or int) : (static member op_Explicit : int -> ^t) i)

它将使用静态约束来确保我们可以从int内联显式转换。不幸的是，这有两个问题。第一个是语法无效-在成员约束的"static-typars“部分不能有具体的类型(比如int)。我们可以通过定义一个helper函数来解决这个问题

let inline cvt i = ((^t or ^u) : (static member op_Explicit : ^u -> ^t) i)
let inline FromInt32 (i:int) = cvt i

由于这两个函数都是内联的，所以这并不比第一次尝试的效率低，只是更简洁。

这就是我们遇到第二个问题的地方:这将适用于真正的op_Explicit定义(或op_Implicit，编译器对其进行特殊处理，以便将其包含在op_Explicit中)。因此，(10G : bigint)将被内联，就像您已经编写了System.Numerics.BigInt.op_Implicit 10一样，这与我们所希望的一样高效。然而，F#还为许多原语类型模拟op_Explicit (例如，从int转换为float、byte等)，由于FromInt32的定义依赖于这些成员的存在，因此它将在运行时失败(即，(10G : float)甚至(10G : int)将进行编译，但在执行时将抛出异常)。理想情况下，未来版本的F#可能会让它按原样工作，但是从F# 2.0开始，我们需要想出一个变通办法。

如果我们可以使用类似于F#核心库处理此类问题的方法，这将需要特殊的格式化所有隐含操作符，但将导致一切都以完美的效率内联：

let inline FromInt32 (i : int) : ^t =
  cvt i
  when ^t : int   = int i
  when ^t : float = float i
  when ^t : byte  = byte i
  ...

但是，F#编译器会用一条"Static optimization conditionals are only for use within the F# library"消息来拒绝它(并且使用秘密--compiling-fslib标志进行编译只会让事情变得更糟：)。

相反，我们需要使用一些额外的间接层来在运行时实现类似的功能。首先，我们将使用泛型类型的静态成员创建类型到转换函数的运行时映射：

type IntConverterDynamicImplTable<'t>() =
  static let result : int -> 't =
    let ty = typeof< 't> //'
    if   ty.Equals(typeof<sbyte>)      then sbyte      |> box |> unbox
    elif ty.Equals(typeof<int16>)      then int16      |> box |> unbox
    elif ty.Equals(typeof<int32>)      then int        |> box |> unbox
    elif ty.Equals(typeof<int64>)      then int64      |> box |> unbox
    elif ty.Equals(typeof<nativeint>)  then nativeint  |> box |> unbox
    elif ty.Equals(typeof<byte>)       then byte       |> box |> unbox
    elif ty.Equals(typeof<uint16>)     then uint16     |> box |> unbox
    elif ty.Equals(typeof<char>)       then char       |> box |> unbox
    elif ty.Equals(typeof<uint32>)     then uint32     |> box |> unbox
    elif ty.Equals(typeof<uint64>)     then uint64     |> box |> unbox
    elif ty.Equals(typeof<unativeint>) then unativeint |> box |> unbox
    elif ty.Equals(typeof<decimal>)    then decimal    |> box |> unbox
    elif ty.Equals(typeof<float>)      then float      |> box |> unbox
    elif ty.Equals(typeof<float32>)    then float32    |> box |> unbox
    else 
      let m = 
        try ty.GetMethod("op_Implicit", [| typeof<int> |])
        with _ -> ty.GetMethod("op_Explicit", [| typeof<int> |])
      let del =
        System.Delegate.CreateDelegate(typeof<System.Func<int,'t>>, m)
        :?> System.Func<int,'t>
      del.Invoke |> box |> unbox
  static member Result = result

这与我们在上一次尝试中试图使用静态优化条件实现的目标类似，但它被推迟到运行时，而不是在编译时计算所有内容。现在我们只需要定义几个值来使用这个类型：

let inline constrain< ^t, ^u when (^t or ^u) : (static member op_Explicit : ^t -> ^u)> () = ()
let inline FromInt32 i : ^t = 
  constrain<int, ^t>()
  IntConverterDynamicImplTable.Result i

这里，constrain函数只是用来确保FromInt32只能应用于从int显式转换(或由编译器模拟)的类型。在FromInt32中对constrain()的实际调用应该在编译过程中进行优化。

使用这种方法，(10G : bigint)将被编译成类似于IntConverterDynamicImplTable<bigint>.Result 10的形式，而IntConverterDynamicTable<bigint>.Result将具有一个与(System.Func<int,bigint>(bigint.op_Implicit)).Invoke等同的值(但已缓存，因此委托只创建一次)。类似地，(10G : int64)将编译为IntConverterDynamicImplTable<int64>.Result 10，并且IntConverterDynamicTable<int64>.Result将有一个等同于转换函数(int64 : int -> int64)的值，因此有一些方法调用的开销，但总体性能应该非常好。

编辑

然而，如果你只是在寻找比简单的FromInt32和FromInt64实现花费O(n)时间更有效的方法，这里有一个版本，它仍然相对简单，只需要O(log )时间：

module SymmetricOps =
  let inline (~-) (x:'a) : 'a = -x
  let inline (+) (x:'a) (y:'a) : 'a = x + y
  let inline (-) (x:'a) (y:'a) : 'a = x - y
  let inline (*) (x:'a) (y:'a) : 'a = x * y
  let inline (/) (x:'a) (y:'a) : 'a = x / y
  let inline (%) (x:'a) (y:'a) : 'a = x % y

module NumericLiteralG = 
  open SymmetricOps
  let inline FromOne() = LanguagePrimitives.GenericOne
  let inline FromZero() = LanguagePrimitives.GenericZero
  let rec compute zero one two (/) (%) Two (+) (-) (*) pow2 rest n =
    if n = zero then rest
    else 
      let rest' =
        let nmod2 = n % two
        if nmod2 = zero then rest
        elif nmod2 = one then rest + pow2
        else rest - pow2
      compute zero one two (/) (%) Two (+) (-) (*) (Two * pow2) rest' (n / two)
  let inline FromInt32 i = compute 0  1  2  (/) (%) (FromOne() + FromOne()) (+) (-) (*) (FromOne()) (FromZero()) i
  let inline FromInt64 i = compute 0L 1L 2L (/) (%) (FromOne() + FromOne()) (+) (-) (*) (FromOne()) (FromZero()) i