完整，高效的NumericLiteral模块实现 [英] Complete, efficient NumericLiteral module implementation
问题描述
基于这个问题的讨论，可以任何人都提供代码或代码链接，显示 NumericLiteralX 模块的完整实现（例如这一个）？我对 FromInt32 / 64 对 NumericLiteralX code>模块，以方便通用数值操作。这可能是从上述问题中无效的实现：
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 ig =
if i = n then g
else loop（i + n_incr）（g + g_incr）
loop 0零
如何改进和完成？
我只会介绍 FromInt32 。在理想的世界中，我们可以简单地将它定义为：
let inline FromInt32 i =
（（^ t或int）：（static member op_Explicit：int - > ^ t）i）
约束条件来确保我们可以内联从 int 的显式转换。不幸的是，这有两个问题。首先是语法无效 - 在成员约束的static-typars部分中不能有具体类型（如 int ）。我们可以通过定义一个帮助函数来解决这个问题。
let inline cvt i =（（^ t或^ u）：（static成员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＃也为许多基本类型（例如，对于从 int 到 float的转换）模拟甚至 op_Explicit ， byte 等），并且由于 FromInt32 的定义依赖于存在（10G：float）（10G：int）将会编译但执行时会抛出异常）。理想情况下，未来版本的F＃可能会使其按原样运行，但从F＃2.0开始，我们需要提出一个解决方法。
如果我们可以使用类似的方法来处理这种类型的问题，那么需要特殊的框架来隐藏所有隐含的操作符，但是会导致所有内容都以完美的效率进行内联：
let inline FromInt32（i：int）：^ t =
cvt i
当^ t：int = int时
当^ t：byte = byte i
...
$ b时，^ t：float = float i
$ b
但是，F＃编译器用拒绝了这个静态优化条件只在F＃库中使用消息（并且用秘密<$ c
$ b
相反，我们需要使用一些额外的图层间接在运行时实现类似的东西。首先，我们将通过使用泛型类型的静态成员创建类型到转换函数的运行时映射：
类型IntConverterDynamicImplTable< ;'t>（）=
static let result：int - > 't =
let ty = typeof< T> //'
if ty.Equals（typeof< sbyte>）then sbyte |>框|> unbox
elif ty.Equals（typeof< int16>）then int16 |>框|> unbox
elif ty.Equals（typeof< int32>）then int |>框|> unbox
elif ty.Equals（typeof< int64>）然后int64 |>框|> unbox
elif ty.Equals（typeof< nativeint>）then nativeint |>框|> unbox
elif ty.Equals（typeof< byte>）然后byte |>框|> unbox
elif ty.Equals（typeof< uint16>）然后uint16 |>框|> unbox
elif ty.Equals（typeof< char>）然后char |>框|> unbox
elif ty.Equals（typeof< uint32>）then uint32 |>框|> unbox
elif ty.Equals（typeof< uint64>）然后uint64 |>框|> unbox
elif ty.Equals（typeof< unativeint>）然后unativeint |>框|> unbox
elif ty.Equals（typeof< decimal>）然后是decimal |>框|> unbox
elif ty.Equals（typeof< float>）然后float |>框|> unbox
elif ty.Equals（typeof< float32>）然后float32 |>框|> unbox
else
let m =
尝试ty.GetMethod（op_Implicit，[| typeof< int> |]）
with _ - > （）函数返回一个类型为int的类型，其中包含一个类型为int的类型，
：？> System.Func< INT， T>
del.Invoke |>框|> unbox
static member Result = result
这与我们试图用上一次尝试中的静态优化条件，但是它延迟到运行时而不是在编译时评估的所有内容。现在我们只需要定义几个值来使用这种类型：
let inline constrain< ^ t，^ u当（^ t或^ u）：（静态成员op_Explicit：^ t - > ^ u）> （）=（）
let inline FromInt32 i：^ t =
constrain< int，^ t>（）
IntConverterDynamicImplTable.Result i
这里， constrain 函数仅用于确保 FromInt32 只能应用于从int（或由编译器模拟的）显式转换的类型。实际在 FromInt32 内调用 constrain（）应该在编译期间被优化掉。
通过这种方法，（10G：bigint）将被编译为类似于 IntConverterDynamicImplTable< bigint>的类似结果。 code>和 IntConverterDynamicTable< bigint> .Result 的值将等于（System.Func< int，bigint>（bigint。 op_Implicit））。调用（但是缓存，所以委托只创建一次）。同样，（10G：int64）会被编译为 IntConverterDynamicImplTable< int64> .Result 10 和 IntConverterDynamicTable< int64> .Result 将具有等价于转换函数（int64：int - > int64）的值，的几个方法调用，但总体表现应该是非常好的。
编辑
然而，如果你只是在寻找一种比
FromInt32 和 FromInt64 time O（n），这是一个相对简单的版本，只需要 O（log n）时间：内联（+）（x：'a）：'a = -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
模块NumericLiteralG =
open SymmetricOps
let inline FromOne（）= LanguagePrimitives.GenericOne
let inline FromZero（）= LanguagePrimitives.GenericZero
让rec计算零一个二（/）（％）两个（+）（ - ）（*） pow2休息n =
如果n =零然后休息
else
让休息'=
让nmod2 = n％two
如果nmod2 =零然后休息$ b $ （+）（ - ）（*）（Two * pow2）rest'（n（n））（n） /）
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（））
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?
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
这篇关于完整，高效的NumericLiteral模块实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
