[GiNaC-devel] GiNaC is not a C compiler [Was: Optimized C-style output]

Sheplyakov Alexei varg at theor.jinr.ru
Mon Mar 26 08:02:22 CEST 2007


Dear Stefan,

On Thu, Mar 22, 2007 at 03:26:40PM +0100, Stefan Weinzierl wrote:
> 
> thinking about it, we probably want the following: a data structure
> consisting of two lists,
>  lhs = lst(t0,t1,...)
>  rhs = lst(expr0,expr1,...)
> with the understanding that this should represent something like
>  ...
>  t1 = expr1;
>  t0 = expr0;

There is a type which represents such objects, it is called exmap
(std::map<ex, ex_is_less>). Is new type really necessary? 
 
> There is a consistency condition which needs to be fulfilled: The right
> hand side of the (j+1)-th entry cannot refer to symbols t0,...,tj, which
> would be defined later.
> 
> One can consider two such structures equivalent, if the values of
> t0,...,tn would be the same after execution of the corresponding code
> fragments. In most cases we are just interested in n=0.
> This is actually an equivalence relation in the mathematical sense.
> 
> For this structure we can have methods, which transform the structure into
> an equivalent one.
> These methods can add or remove entries from the two lists, or change the
> order.
> Methods, which just transform the rhs are in some sense trivial and not
> considered here.
> 
> Examples of such methods could be:
>  - replace common subexpressions of type T1, T2, ...  in the rhs.
>  - split containers with more than n_max arguments
>  - (eliminate redundant variables)
> 
> This structure has then a print method, which simply prints
>  ...
>  double t1 = expr1;
>  double t0 = expr0;
> 
> Everybody happy with this concept ?

No. There are 3 different _independent_ transformations: 1) finding
commong subexpressions, 2) splitting an expression into a smaller parts,
3) generating code. Each of them is useful on its own, so it would be nice
to keep them separate.

E.g.

/**
 * Attempt to find common subexpressions and replace them with symbols
 */
const ex find_common_subex(const ex& e, exmap& repls);

I've already described suggested semantics in the previous mail.

/**
 * Split large sums and products in @e with number of operands bigger
 * then @threshold, replace obtained subexpressions with symbols
 */
const ex split_large_subex(const ex& e, exmap& repls, const size_t threshold);

Example: 

ex e = x1+...+x1000;
exmap repls;
e = split_large_subex(e, repls, 500);
cout << e << endl;
// Should print, for instance:
// symbol100 + symbol101
for (exmap::const_iterator i=repls.begin(); i!=repls.end(); ++i)
	cout << i->first << " => " << i->second << endl;
// should be something like
// symbol100 => x1+...+x500
// symbol101 => x501+...+x1000 
	

void generate_code(const& ex e, const exmap& repls, std::ostream& os);

Example:

generate_code(e, repls, std::cout);

should print

const double f(const double[] x) {
double symbol100 = x[0]+...+x[499];
double symbol101 = x[500]+...+x[999];
double ret = symbol100 + symbol101;
return ret;
}

N.B. I don't insist on this particular kind of interface, I just give
examples to clarify what I mean. You are wellcome to suggest something
better.

Best regards,
 Alexei

-- 
All science is either physics or stamp collecting.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 827 bytes
Desc: Digital signature
Url : http://www.cebix.net/pipermail/ginac-devel/attachments/20070326/3e07909f/attachment.pgp


More information about the GiNaC-devel mailing list