Completa y eficiente implementación del módulo NumericLiteral

Question

Sobre la base de una discusión en this question, ¿podría alguien proporcionar código, o un enlace al código, mostrando una implementación completa de un módulo NumericLiteralX (como)? Estoy especialmente interesado en una implementación eficiente de FromInt32/64 para un módulo NumericLiteralX que facilita las operaciones numéricas genéricas. He aquí una aplicación ineficiente quizá tomada de la pregunta antes mencionada:

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 

¿Cómo puede ser mejorado y completado?

Answer 1

Me limitaré a la dirección FromInt32. En un mundo ideal, podríamos definirlo como simplemente como

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

que utilizaría restricciones estáticas para asegurar que podríamos inline una conversión explícita de int. Desafortunadamente, hay dos problemas con esto. La primera es que la sintaxis no es válida: no se puede tener un tipo concreto (como int) en la parte "static-typars" de una restricción miembro. Podemos evitar esto definiendo una función auxiliar

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

Dado que ambas funciones son inline, esto no es menos eficiente que el primer intento, es sólo más prolijo.

Aquí es donde nos encontramos con el segundo problema: esto funcionará para las definiciones reales op_Explicit (o op_Implicit, que se trata especialmente por el compilador para que se subsume por op_Explicit). Por lo tanto, (10G : bigint) estará en línea como si hubiera escrito System.Numerics.BigInt.op_Implicit 10, que es lo más eficiente que podemos esperar. Sin embargo, F # también simula op_Explicit para muchos tipos primitivos (por ejemplo, para las conversiones de int a float, byte, etc.), y puesto que la definición de FromInt32 se basa en la existencia de estos miembros se producirá un error en tiempo de ejecución (es decir, (10G : float) e incluso (10G : int) compilará pero emitirá una excepción cuando se ejecute). Idealmente, una versión futura de F # podría permitir que esto funcione como está, pero a partir de F # 2.0, tendremos que encontrar una solución alternativa.

Sería bueno si pudiéramos utilizar un enfoque similar a la forma en la biblioteca # núcleo F maneja este tipo de problemas, lo que requeriría carcasa especial a todos los operadores implicados, pero resultaría en todo lo que se inline con una eficiencia perfecta:

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

Sin embargo, el F # compilador rechaza esto con un mensaje "Static optimization conditionals are only for use within the F# library" (y compilar con la bandera de --compiling-fslib secreto sólo empeora las cosas :)).

En su lugar, tenemos que usar algunas capas adicionales de direccionamiento indirecto para lograr algo similar en el tiempo de ejecución. En primer lugar, vamos a crear una asignación de tiempo de ejecución de los tipos de funciones de conversión mediante el uso de un miembro estático de un tipo genérico:

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 

Esto es similar a lo que estábamos tratando de lograr con los condicionales de optimización estática en el intento anterior , pero se difiere al tiempo de ejecución en lugar de que todo se evalúe en tiempo de compilación.Ahora solo falta definir algunos valores de usar este tipo:

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 

Aquí, la función constrain sólo se utiliza para asegurarse de que FromInt32 sólo se puede aplicar a tipos donde hay una conversión explícita de int (o uno simulado por el compilador). La llamada real al constrain() dentro de FromInt32 debería optimizarse durante la compilación.

Con este enfoque, (10G : bigint) obtendrá compilado a algo así como IntConverterDynamicImplTable<bigint>.Result 10 y IntConverterDynamicTable<bigint>.Result tendrá un valor equivalente a (System.Func<int,bigint>(bigint.op_Implicit)).Invoke (pero en caché, por lo que el delegado sólo se crea una vez). Del mismo modo, (10G : int64) se compilará en IntConverterDynamicImplTable<int64>.Result 10, y IntConverterDynamicTable<int64>.Result tendrá un valor equivalente a la función de conversión (int64 : int -> int64), por lo que hay gastos generales de algunas llamadas a métodos, pero el rendimiento general debería ser muy bueno.

EDITAR

Sin embargo, si estás buscando algo más eficiente que un ingenuo implementaciones de FromInt32 y FromInt64 tomar tiempo O (n), aquí está una versión que todavía es relativamente sencillo y sólo toma O (log n) tiempo:

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