Полная, эффективная реализация модуля NumericLiteral

Question

Основываясь на обсуждении этого вопроса, может ли кто-нибудь предоставить код или ссылку на код, демонстрирующий полную реализацию NumericLiteralX модуль (такой как этот)? Я особенно заинтересован в эффективной реализации 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, К сожалению, с этим есть две проблемы. Во-первых, синтаксис недопустим - у вас не может быть конкретного типа (например, int) в части static-typars ограничения члена. Мы можем обойти это, определив вспомогательную функцию

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 (или моделируемой компилятором). Фактический вызов constrain() в FromInt32 должен быть оптимизирован во время компиляции.

При таком подходе (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 n):

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