Re: [Boost-users] [Proto] implementing an computer algebra system with proto

Subject: Re: [Boost-users] [Proto] implementing an computer algebra system with proto
From: alfC (alfredo.correa_at_[hidden])
Date: 2009-01-30 16:15:02

> I think the attached program solves that problem.
>  eq_solver.cpp

Thank you for posting the compile-time solver code. Specially thanks
to Eric N. for writing proto and proposing the sketch of the solution.

I few years ago, I tried to experiment writing a mini computer algebra
in-C++-for-C++. Think for example, if we want to *implicitly* define a
differential equation in the C++-code to  be solved numerically by any
existing routine which only takes *explicit* differential equation.

There were two approaches: A) Every expression could be dynamic (like
an dynamic expression-tree generated from a C++-code via a DSEL) and
the solver in this case was some run-time transformation between
expression-trees. But then I was missing the compile-time efficiency
of simple operations (like passing addition terms as described in this
topic).  In order to improve that, very soon I realized that, *in
principle*, B) many (if not all) of the operations could be done at
compile-time (using metaprogramming) provided that the problem is well
defined at compile time.

For the static version (case B), the code became very obfuscated very
soon and the my code itself began to be unmanageable. I guess that to
really go forward I should have to have invented Proto first. That was
of course in the pre-Proto era.

It seems that having Proto now opens the opportunity to enjoyably
continuing with that project. But I see two problems ahead,  1) The
(meta-)code is still obfuscated (but may be the best we can do, at
worst it looks like LISP), 2) Even if we manage to write a fairly
complete (compile-time) computer algebra there will be two problems
2a) the compilation can become really slow if not overflown (compilers
are not yet optimized to do this kind of job). Imagine for example, an
automatic derivation meta-code, it will create an unmanageable number
of template-expressions very rapidly. (Think of the fourth derivative
of sin(exp(x^2)) ) For an automatic integrator is even worst.
2b) as soon as we want to introduce some run-time aspect to the
problem, all the static expression-templates should be converted to
some dynamic-expression.

In case I am not missing something (let me know), it seems that a
completely compile-time solution is doomed to become unusable except
for very simple operation and difficult to extend. On the other hand a
completely dynamic solution is more of what we already have (e.g.
maple, mathematica, reduce) and will be no better than them (in any
single aspect), an will not take advantage of compilation
optimizations (think of interfacing the results with numeric
libraries)

So I think that a combination of a compile-time solvers and dynamic-
time solvers is the only way to make something useful and innovative.
Say for example, if we transform template expression only to some
degree during compilation and as soon as the problem becomes too
complicated (e.g. the expression is too long, or there are many
expressions in the compilation stack) we let the run-time code handle
the rest of the problem.
Any one has any ideas on how to do this in practice?

For example, in the original example of this posting, we can handle
the outer-most sums at compile time and the product at runtime
1) at compile-time transform "2+var_*5=4" into this "var_*5=4-2"
2) at run-time transform the type "var_*5=4-2" (expression template)
into a dynamic-tree (not expression template) representing the same
equation"var_*5 = 4-2"  and then this into another dynamic-tree "var_=
(4-2)/5".

It will naturally look like a runtime extension of Proto plus some
transformation rules (some of them duplicated from the meta-program
part). From the few features I understood from the Proto manual, there
is a printing of expression capability that gives me the clue that
constructing a run-time tree of an expression is doable. Is that
dynamic tree-generation implemented in Proto? Am I trying to reinvent
the wheel here?

Thanks,
Alfredo

On Jan 30, 8:38 am, "Dave Jenkins" <da..._at_[hidden]> wrote:
> "Kim Kuen Tang" <kuent..._at_[hidden]> wrote in messagenews:497F760C.1030408_at_vodafone.de...
>
> > The next step will be to extend the grammar with the feature of
> > transforming such expression "1+2+var_+3=4" into
> > this "var_=4-1-2-3".
>
> Hi Kim Tang,
>
> I think the attached program solves that problem.
>
> The problem I've been working on is to use the distributive law to simplify
> expressions at compile time.
> For example, I'd like to transform "var_ * 2 + var_ * 3 = 4" to "var_ * (2 +
> 3) = 4".
> Then, you could transform it to "var_ = 4 / (2 + 3)", all at compile time.
> Wouldn't that be cool? I think it's possible using Proto, but I haven't
> worked out the details yet.
> Any suggestions are welcome.
>
> Regards,
> Dave Jenkins
>
>  eq_solver.cpp
> 3KViewDownload
>
> _______________________________________________
> Boost-users mailing list
> Boost-us..._at_[hidden]http://lists.boost.org/mailman/listinfo.cgi/boost-users