generics - Complete, efficient NumericLiteral module implementation

Question

Building on a discussion in this question, could anyone provide code, or a link to code, showing a complete implementation of a NumericLiteralX module (such as this one)? I'm especially interested in an efficient implementation of FromInt32/64 for a NumericLiteralX module that facilitates generic numeric operations. Here's a perhaps inefficient implementation taken from the aforementioned question:

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 

How could this be improved and completed?

Answer 1

I'll just address FromInt32. In an ideal world, we could define it as simply as

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

which would use static constraints to ensure that we could inline an explicit conversion from int. Unfortunately, there are two problems with this. The first is that the syntax is invalid - you can't have a concrete type (like int) in the "static-typars" portion of a member constraint. We can work around this by defining a helper function

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

Since both of these functions are inlined, this isn't any less efficient than the first attempt, it's just wordier.

Here's where we run into the second problem: this will work for real op_Explicit definitions (or op_Implicit, which is treated specially by the compiler so that it is subsumed by op_Explicit). So (10G : bigint) will be inlined as if you had written System.Numerics.BigInt.op_Implicit 10, which is as efficient as we can hope for. However, F# also simulates op_Explicit for many primitive types (e.g. for conversions from int to float, byte, etc.), and since the definition of FromInt32 relies on the existence of these members it will fail at runtime (that is, (10G : float) and even (10G : int) will compile but will throw an exception when executed). Ideally a future version of F# might enable this to work as-is, but as of F# 2.0, we'll need to come up with a workaround.

It would be nice if we could use a similar approach to how the F# core library handles this kind of problem, which would require special casing all of the implied operators but would result in everything being inlined with perfect efficiency:

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

However, the F# compiler rejects this with a "Static optimization conditionals are only for use within the F# library" message (and compiling with the secret --compiling-fslib flag only makes things worse :)).

Instead, we need to use a few additional layers of indirection to achieve something similar at runtime. First, we'll create a runtime mapping of types to conversion functions by using a static member of a generic type:

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

This is similar to what we were trying to achieve with the static optimization conditionals in the previous attempt, but it's deferred to runtime instead of everything being evaluated at compile time. Now we just need to define a few values to use this type:

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

Here, the constrain function is just used to make sure that FromInt32 can only be applied to types where there's an explicit conversion from int (or one simulated by the compiler). The actual call to constrain() within FromInt32 should get optimized away during compilation.

With this approach, (10G : bigint) will get compiled to something like IntConverterDynamicImplTable<bigint>.Result 10, and IntConverterDynamicTable<bigint>.Result will have a value equivalent to (System.Func<int,bigint>(bigint.op_Implicit)).Invoke (but cached, so that the delegate is only created once). Similarly, (10G : int64) will compile to IntConverterDynamicImplTable<int64>.Result 10, and IntConverterDynamicTable<int64>.Result will have a value equivalent to the conversion function (int64 : int -> int64), so there are overheads of a few method calls, but the overall performance should be very good.

EDIT

However, if you're just looking for something more efficient than a naive implementations of FromInt32 and FromInt64 taking time O(n), here's a version which is still relatively simple and only takes O(log n) time:

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