Implementazione del modulo NumericLiteral completa ed efficiente

Question

Sulla base di una discussione nel numero this question, chiunque può fornire un codice o un collegamento al codice che mostri un'implementazione completa di un modulo NumericLiteralX (ad esempio this one)? Sono particolarmente interessato a un'implementazione efficiente di FromInt32/64 per un modulo NumericLiteralX che facilita operazioni numeriche generiche. Ecco un'implementazione forse inefficiente preso dalla questione di cui sopra:

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 

come potrebbe essere migliorato e completato?

Answer 1

Mi occuperò solo dello FromInt32. In un mondo ideale, potremmo definire nel modo più semplice

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

che utilizzare i vincoli statici per garantire che potremmo inline una conversione esplicita da int. Sfortunatamente, ci sono due problemi con questo. Il primo è che la sintassi non è valida - non è possibile avere un tipo concreto (come int) nella parte "typars statici" di un vincolo membro. Siamo in grado di ovviare a questo definendo una funzione di supporto

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

Poiché entrambe queste funzioni sono inline, questo non è meno efficiente rispetto al primo tentativo, è solo wordier.

Ecco dove ci imbattiamo nel secondo problema: questo lavoro per veri op_Explicit definizioni (o op_Implicit, che è un trattamento speciale dal compilatore in modo che sia sussunto da op_Explicit). Pertanto, (10G : bigint) sarà in linea come se fosse stato scritto System.Numerics.BigInt.op_Implicit 10, che è il più efficiente possibile. Tuttavia, F # simula anche op_Explicit per molti tipi primitivi (ad esempio per le conversioni da int a float, byte, ecc), e dal momento che la definizione di FromInt32 si basa sull'esistenza di questi membri non riuscirà in fase di esecuzione (cioè, (10G : float) e anche (10G : int) verrà compilato ma genererà un'eccezione quando eseguito). Idealmente una versione futura di F # potrebbe consentire a questo di funzionare così com'è, ma a partire da F # 2.0, avremo bisogno di una soluzione alternativa.

Sarebbe bello se potessimo utilizzare un approccio simile a come la libreria # nucleo F gestisce questo tipo di problema, che richiederebbe involucro speciale tutti gli operatori implicite, ma si tradurrebbe in tutto ciò che viene inline con perfetta efficienza:

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

Tuttavia, il compilatore F # rifiuta questo con un messaggio "Static optimization conditionals are only for use within the F# library" (e la compilazione con il segreto --compiling-fslib bandiera non fa che peggiorare le cose :)).

Invece, è necessario utilizzare alcuni livelli aggiuntivi di riferimento indiretto per ottenere qualcosa di simile in fase di esecuzione. In primo luogo, creeremo una mappatura runtime di tipi di funzioni di conversione tramite un membro statico di un tipo generico:

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 

Questo è simile a quello che stavamo cercando di realizzare con i condizionali di ottimizzazione statiche nel tentativo precedente , ma è rinviato al runtime invece di tutto ciò che viene valutato in fase di compilazione.Ora abbiamo solo bisogno di definire alcuni valori di utilizzare questo 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 

Qui, la funzione constrain è solo utilizzato per fare in modo che FromInt32 può essere applicato solo ai tipi dove c'è una conversione esplicita da int (o uno simulato dal compilatore). La chiamata effettiva a constrain() all'interno di FromInt32 dovrebbe essere ottimizzata durante la compilazione.

Con questo approccio, (10G : bigint) otterrà compilato a qualcosa come IntConverterDynamicImplTable<bigint>.Result 10, e IntConverterDynamicTable<bigint>.Result avrà un valore equivalente a (System.Func<int,bigint>(bigint.op_Implicit)).Invoke (ma nella cache, in modo che il delegato è stato creato solo una volta). Allo stesso modo, (10G : int64) verrà compilato a IntConverterDynamicImplTable<int64>.Result 10 e IntConverterDynamicTable<int64>.Result avrà un valore equivalente alla funzione di conversione (int64 : int -> int64), quindi ci sono overheads di alcune chiamate di metodo, ma le prestazioni generali dovrebbero essere molto buone.

EDIT

Tuttavia, se siete solo in cerca di qualcosa di più efficiente di un ingenuo implementazioni di FromInt32 e FromInt64 prendere tempo O (n), ecco una versione che è ancora relativamente semplice e solo prende O (log n) tempo:

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