[GiNaC-devel] Custom power evaluation

[Sheplyakov Alexei]

Hello,

On Mon, Oct 30, 2006 at 06:05:52PM +0000, Vladimir Kisil wrote:
> 		It is a pity that this discussion is going round by round over the
>   same path and we all reiterate the previous arguments.

So, let me first give a short summary:

 1) I think adding more virtual methods to the `basic' class should be
    considered evil and used only as a last resort (if ever).

 2) Calling newly added methods from the eval() methods of core classes
    is even more evil.

 3) I think the proper way to implement the feature you need is to provide 
    support of polynomials (rational functions, algebraic expressions,
		etc.) over modular integers and and [finite] algebraic extensions.

 4) Until this is done, it is better to stick with subs(), map_function
    and visitors. As a "lower acceptable limit" it is possible to add
		new virtual method (sigh!) to the `basic' class (something like 
		eval_pow) which *never ever* gets called by power::eval (or any other
		core classes) and does whatever you want. Note that such a method
		must be called explicitly (like evalm, evalf, eval_integ, 
		simplify_indexed and so on). However, this is still dirty hack.
		It is just not that harmful.

Now I'll try to elaborate, so (hopefully) my point will be more clear.

>  ASh> What if someone else wants to insert another "pair of wires" to
>  ASh> implement another weird feature? 
 
>	Once more: the purpose of this wires *to avoid* implementation of
> weird features in the GiNaC kernel. 

It does not really matter if the actual code implementing $FEATURE resides
in GiNaC or there exist some hook in the core code. In general, explicitly
calling some method of the *derived class* from the parent one sounds very
anti-OO. Unfortunately, there are already a number of such hooks in
GiNaC (evalm, eval_integ, simplify_indexed, to name few). I have no idea
how to fix this, but at least we should stop adding new ones.

To re-iterate: clever overloading of existing virtual method[s] in 
a derived class is a good way to implement new features. Adding more
eval_foo virtual methods to the `basic' class is not.

> For any such a request to add anything to the core GiNaC with special
> property with respect to power::eval() will follow a polite answer: 
> "You can do it yourself in your own derived class."

[Just kidding]
So my polite answer is: "You can do it yourself with subs() without
modifying power::eval at all". 

Seriously, at some moment you will _certainly_ want to hack mul::eval
and/or add:eval (for more complete emulation of modular arithmetics)
and ask for more virtual methods in basic.
 
>     ASh> This sounds like modular arithmetics (in Z_3, to be more
>     ASh> specific).  It would be nice if GiNaC had support of such a
>     ASh> thing. CLN has modular integers, so _probably_ it is possible
>     ASh> to do such calculations in more natural way (so that
>     ASh> simplification of this kind are handled by CLN, just as I^2 ->
>     ASh> -1).
 
>	There are also symbols taking only values -1, 0, 1,

Yes, polynomials and rational functions over such rings (or fields,
as in your example) need to be handled too.

> with the property s^3=s, 

Modular arithmetics has in fact more generic property: for any
x \in Z_p (with p being a prime number) x^p = x. It would be nice
if power::eval handled such things (*without* evil hacks). For
proper support of modular polynomials/rational functions it is
also necessary to modify (at least) mul::eval and add::eval.
Once again, it would be really nice to have such a feature[s] (e.g.,
to have reasonably fast _ordinary_ polynomial operations).

> there are imaginary units for double and dual number
> (e^2=1, \epsilon^2=0), etc. 
> Adding all of them separately "in a more natural way" either to 
> GiNaC or CLN will really do it very cumbersome.

CLN _already_ supports modular integers. However, [finite] algebraic
extensions (except ordinary complex numbers) are not supported. 
Polynomials over arbitrary rings are supported by CLN too, but AFAIK
it implements primitive operations only (no GCD, no factorization, etc.).
Thus, there are indeed a lot of non-trivial work to be done. Let me
repeat once again: it is complicated, but _not_ cumbersome. BTW, I think
at some moment you will implement most (if not all) of these in order
to work with your "symbols which take only 3 values". So it is better
to do this properly instead of adding random hacks.

>     ASh> It depends. E.g., for someone who hardly ever uses complex
>     ASh> numbers this is not a big deal. On the other hand,
> 
>	Anyone who hardly use any differential geometry will vote for
> exclusion of all "indexed" part from GiNaC, so....

They are free to patch away all indexed classes and related methods.
However, doing so does not buy much: AFAIK, if the expression does
not contain indexed objects, neither indexed::eval, nor eval_indexed
& friends get called implicitly, so the only price is extra memory
for vtable entries and disk space for library code (some operating
systems won't even load to the RAM "unnecessary" portion of code).
On the other hand, your patch adds two unnecessary calls for _every_ 
power object (see more detailed explanation below). I think this is 
absolutely unacceptable.

>	Probably my real problem is that I am not a "[particle] physicist" ;-) 

I don't think this is problem :)

>    I was also mislead by the phrase from the GiNaC tutorial:
> 
>    "we...tried to fill the gap by writing GiNaC. But of course its
>   applications are in no way restricted to theoretical physics." 

Tutorial also warns: "First of all, GiNaC's name must be read literally."
And introductory paper (http://www.ginac.de/csSC-0004015.pdf) clearly
states that minimalistic design of GiNaC (as opposed to "can do everything
equally bad") _is a feature_.

However, this does not prevent people from using GiNaC for other tasks.
For example, Ecco (http://sourceforge.net/projects/echempp) has very
little to do with high-energy physics.


>     ASh> The main point is not validity of those rules. Your
>     ASh> implementation complicates things even for those who are not
>     ASh> going to use any of such rules.
> 
>	Untrue. Anyone who do not need them may safely assume that they do
> not exist at all.

Only modulo two unnecessary virtual method calls in power::eval.
To be more precise, I mean this hunk:

> +	// user defined classes may provide their own virtual methods for power evaluation
> +	if (ebasis.info(info_flags::is_power_basis))
> +		return ebasis.eval_power_basis(eexponent);
> +
> +	if (eexponent.info(info_flags::is_power_exponent))
> +		return eexponent.eval_power_exponent(ebasis);

E.g. evaluation of a simple x^2 now takes several cycles longer (to
call symbol::info and numeric::info methods  and check that no custom
evaluation rules exist). Evaluation of monomial like x^2*y^3*z^4 now
takes a little bit longer. Evaluation of polynomial like 
x^99 + y x^98 + y^2 x^97 + ... + y^99
now takes...  oops, somewhat longer. Given the fact that large and ugly
intermediate expressions are quite common in [multivariate] GCD 
calculation, this slowdown is not appreciated at all. "Things I do not use
should not harm me".

> Virtual methods basic::eval_power_base() and basic::eval_power_exponent()
> are not ever called from the core GiNaC.

First of all, it does not really matter if you call info() or directly 
eval_power_{base,exponent} -- in any case there are two extra calls 
[in the fast code path].

Secondly, checking if there is non-trivial implementation of virtual
method is a bad thing on its own. It is best to provide sensible (e.g.,
no-op) default implementation and overload the method in the derived
class. This way there is no need in bogus extra entries in info_flags
(IMHO these should provide some mathematical details, not implementation
ones), and users need not to implement custom info method.

> And they will not be ever called by any user code unless the user will
> take specific steps to call them.

Unfortunately, this is not completely correct (see my explanation
above).


Best regards,
 Alexei

-- 
All science is either physics or stamp collecting.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 827 bytes
Desc: Digital signature
URL: <http://www.ginac.de/pipermail/ginac-devel/attachments/20061031/246ae015/attachment.sig>