Re: [boost] Domain library

From: John Bytheway (jbytheway+boost_at_[hidden])
Date: 2008-07-31 17:57:46

Brook Milligan wrote:
> John Bytheway writes:
>  > I'm concerned about the behaviour of standard algorithms in this 
>  > context.  For example, consider a general 'power' function
<snip>
> There are some benefits deriving from the Domain library that I hope
> will reduce your concern.
> 
> - Use of the generic power() is guarranteed to give the correct
>   answer, regardless of the choice made for T.  Perhaps that
>   guarrantee is worth something.

Indeed.  It's always a good first step! :)

> - A reasonable implementation of power() would use operator*=() and a
>   reasonable implementation of polynomial_c (as described) would not
>   define that.  Thus, the user code you describe would never compile
>   and a search for the reason why would quickly lead to the
>   polynomial_pv type which gives the minimal conversions you seek.

A good point, but the implementation I was looking at (from the gcc 
4.3.1 header ext/numeric) doesn't, because it actually supports 
arbitrary MonoidOperations, not just multiply (and that in turn makes me 
think that there's something missing in that implementation, but that's 
another issue).

> - Developing a Domain-aware specialization of the power() algorithm
>   could resolve the performance issues altogether.  The algorithm
>   would be generic and thus applicable to all types based upon the
>   library, not just polynomials.

Could you easily write it such a way as to work well for both 
Domain-based types and other types?  (Clearly this is possible with 
sufficient metaprogramming, but is it easy?)

>  > I'm not sure what the best solution is, but one possibility is this:
>  > 
>  > Support a runtime-domained type, which acts something like a 
>  > variant<polynomial_c, polynomial_pv>, but with operators defined on it. 
> 
> Rather than have this runtime cost, the library has a type deduction
> system that determines the appropriate return types based upon the
> axioms that govern the library's design.  Thus, a Domain-aware
> implementation of the power() function can guarrantee that the
> argument is transformed at most once[1] and then only when necessary.
> This, I believe, offers the best possibility: any Domain-based
> argument type works, the minimum number of conversions is performed,
> there are no runtime costs associated with deciphering the types, and
> the algorithm is still completely generic.

Indeed.  I agree that's the best solution, but it might be 
overoptimistic to assume it's always a practical one.  I feel runtime 
typing has its uses, but I can't come up with a concrete example, so 
perhaps I'm being too pessimistic.

John