libevaluator library and GSL

libevaluator library and GSL

[Aleksandar B. Samardzic]

I've written a library
(http://savannah.nongnu.org/projects/libevaluator/) that makes possible
to parse strings representing mathematical functions over single or
multiple variables and later to evaluate these functions for different
variable values (also to create representation of function derivative
over specified variable etc.).  I've submitted this library for
evaluation regarding inclusion in GNU project and was told by my
evaluator that they would rather like to see my library as part of GSL
than to publish it as separate library.  My library is written in C, but
offers also Fortran 77 and Gule interfaces (as well as Fortran 90
interface).  Note also that my library has simple interface that I could
easily change to behave in spirit of GSL.  Something that could make it
possible to write code like this:

  gsl_integration_workspace * w = gsl_integration_workspace_alloc (1000);
  gsl_function F;
  double result, error;
  gsl_evaluator *evaluator; /* type provided by my library */

  evaluator = gsl_evaluator_create("x^7-3*x^2+x");
  F.function = &gsl_evaluator_evaluate_x; /* function provided by my library */
  F.params = evaluator;
  gsl_integration_qags (&F, 0, 1, 0, 1e-7, 1000, w, &result, &error);

  /* now interested in integrating function derivative (just for fun)? */
  F.params = evaluator_derivative_x (evaluator);
  gsl_integration_qags (&F, 0, 1, 0, 1e-7, 1000, w, &result, &error);

So, main idea is to have user to provide string representing
mathematical function instead of to write C function representing
mathematical function.  Any interest for alike functionality in GSL?

Regards,
Alex

Re: libevaluator library and GSL

[Martin Jansche]

On Thu, 4 Sep 2003, Aleksandar B. Samardzic wrote:

> I've written a library
> (http://savannah.nongnu.org/projects/libevaluator/) that makes
> possible to parse strings representing mathematical functions over
> single or multiple variables and later to evaluate these functions
> for different variable values (also to create representation of
> function derivative over specified variable etc.).

I'm only speaking for myself here: I'd like to have some of this
functionality available, but in a different form.  Specifically, I'd
prefer a formula-to-code translator which, given a symbolic formula,
would generate C code with calls to GSL functions (and could possibly
have other backends in addition).  That way, I can manually change the
generated code if necessary, plus it would presumably speed things up
if one were to use optimized compiled code instead of formulas that
need to be interpreted online.

Could you tell us more about what your evaluator does?  How does it
compute derivatives?  Symbolically or numerically?  Does it simplify
formulas?  Does it look for common subexpressions?  A number of the
optimizations one might want to do could be done by a compiler
(another reason to generate C source code).

For me, what it boils down to is this: if I want to quickly optimize
or integrate a symbolic function, I use Mathematica or some other
symbolic algebra system.  I use GSL for fixed, narrow tasks that have
to be run many times; in that case I need the code to be as efficient
as possible.  Now if there were a forumla translator that could read
Mathematica formulas (it uses a nice XML encoding) or Octave formulas
etc. and spit out GSL C code, that would be very useful.

- martin

Re: libevaluator library and GSL

[Aleksandar B. Samardzic]

On Thu, Sep 04, 2003 at 02:26:30PM -0400, Martin Jansche wrote:
> On Thu, 4 Sep 2003, Aleksandar B. Samardzic wrote:
> 
> > I've written a library
> > (http://savannah.nongnu.org/projects/libevaluator/) that makes
> > possible to parse strings representing mathematical functions over
> > single or multiple variables and later to evaluate these functions
> > for different variable values (also to create representation of
> > function derivative over specified variable etc.).
> 
> I'm only speaking for myself here: I'd like to have some of this
> functionality available, but in a different form.  Specifically, I'd
> prefer a formula-to-code translator which, given a symbolic formula,
> would generate C code with calls to GSL functions (and could possibly
> have other backends in addition).  That way, I can manually change the
> generated code if necessary, plus it would presumably speed things up
> if one were to use optimized compiled code instead of formulas that
> need to be interpreted online.
> 
> Could you tell us more about what your evaluator does?  How does it
> compute derivatives?  Symbolically or numerically?  Does it simplify
> formulas?  Does it look for common subexpressions?  A number of the
> optimizations one might want to do could be done by a compiler
> (another reason to generate C source code).

My library is parsing string and creating tree representation of it in
memory.  For example, after parsing string "x+2", following tree is
created in memory:

      +
     / \
    /   \
   x     2

When evaluating function for given variable values (e.g. x=1), subtree
of each node is evaluated recursively and then node operation is
applied (in above example, leaf containing variable x is evaluated to 1
and leaf containing constant is evaluated to 2 and then in plus node
addition is performed giving result 3.

Derivatives are computed symbolically, again applying recursion.  For
example, from above tree, following tree representing derivative of
function over variable x is created:

      +
     / \
    /   \
   1     0

Basic tree simplifications are also implemented, so for example library
is able to simplify above tree to tree containing only one constant leaf
with value 1.  Common subexpressions and other advanced simplifications
are not implemented yet, but this is something I'd be willing to work
on.

 
> For me, what it boils down to is this: if I want to quickly optimize
> or integrate a symbolic function, I use Mathematica or some other
> symbolic algebra system.  I use GSL for fixed, narrow tasks that have
> to be run many times; in that case I need the code to be as efficient
> as possible.  Now if there were a forumla translator that could read
> Mathematica formulas (it uses a nice XML encoding) or Octave formulas
> etc. and spit out GSL C code, that would be very useful.

It would be certainly possible to implement back-end generating C code
from tree representation of function.  For now, only simple mathematical
functions are allowed in expressions (exp, ln, sqrt, sin, cos, tan,
ctan, arcsin, arcsin, arctan, arcctan, sh, ch, th, cth, arsh, arch,
arth, arcth, abs), but parser and whole library could be easily extended
to recognize any function (it is only necessary for function to have
symbolic derivative defined).  Also, I can imagine a front-end that
could parse XML encoded Mathematica formulas you mentioned; I'm using
Lex-Yacc for parsing now, but SAX XML parser could be used for alike
input. So - there are certainly many ways to extend and improve existing
library and sure I'd be willing to further work along some of them, but
as first step I'm asking is there interest to incorporate libevaluator
in GSL as-is?

Regards,
Alex

Re: libevaluator library and GSL

[Kenneth Geisshirt]

Aleksandar B. Samardzic wrote:

>>I'm only speaking for myself here: I'd like to have some of this
>>functionality available, 

Me too. But I don't care whether it's a seperate library or not. 
Aleksandar: great initiative.

>>Could you tell us more about what your evaluator does?  How does it
>>compute derivatives?  Symbolically or numerically?  Does it simplify
>>formulas?  Does it look for common subexpressions? 

I wrote a similar library about 10 years ago. Derivatives are not too 
difficult to implement, but the expressions become really ugly. Try to 
derive sin(x)^cos(x) w.r.t. x to see what I mean :-).

Simplifying expressions is a much harder job. Of course you can do 
simple things like (x-x) -> 0 and (1*x) -> x but (x+y)-x is not that easy.

> My library is parsing string and creating tree representation of it in
> memory.  

Tree representation is straight forward but might not be the most 
efficient representation. At least in the 1980's and 1990's I believe 
that most compilers used DAGs (Directed Acyclic Graphs). The Dragon book 
by Aho et al. outlines the algorithms.

> It would be certainly possible to implement back-end generating C code
> from tree representation of function.

Easy using recursion. But C suddently comes very Lisp like: lots of 
irritating parenthesis.

Kneth

-- 
Kenneth Geisshirt, M.Sc., Ph.D.         http://kenneth.geisshirt.dk
Grøndals Parkvej 2A, 3. sal                    kenneth@geisshirt.dk
DK-2720 Vanløse                                     +45 38 87 78 38

Re: libevaluator library and GSL

[Brian Gough]

Aleksandar B. Samardzic writes:
 > I've written a library
 > (http://savannah.nongnu.org/projects/libevaluator/) that makes possible
 > to parse strings representing mathematical functions over single or
 > multiple variables and later to evaluate these functions for different
 > variable values (also to create representation of function derivative
 > over specified variable etc.).  I've submitted this library for
 > evaluation regarding inclusion in GNU project and was told by my
 > evaluator that they would rather like to see my library as part of GSL
 > than to publish it as separate library.  My library is written in C, but
 > offers also Fortran 77 and Gule interfaces (as well as Fortran 90
 > interface). 

Hello,

Thanks for your email.  I've had a look at your package from CVS.
Here are my comments, which you may pass on to the GNU evaluator.

The question of having an expression parser in GSL came up once
before.

My opinion was that a library to do this could be useful in many
C programs, including those which do not require anything else in
GSL.

Having a standalone evaluator package, with minimal dependencies,
that is very easy for people to integrate into their program
could be a good strategy for encouraging people to use the GPL
for their software -- in the same way that the Readline library
does.

If the evaluator is part of GSL then it reduces the effectiveness
of this approach, because GSL is so big (probably much larger
than the application the evaluator would be used in) and could
not be distributed with the program very easily.

So, I would recommend having a single standalone library under
the GPL, standardising on ANSI C expressions, and having no
external dependencies (except for the standard c library), to
maximise the potential userbase.

best regards

-- 
Brian Gough
(GSL Maintainer)

Re: libevaluator library and GSL

[Alberto Manuel Brandão Simões]

On Fri, 2003-09-05 at 09:00, Kenneth Geisshirt wrote:
> Aleksandar B. Samardzic wrote:
> 
> >>I'm only speaking for myself here: I'd like to have some of this
> >>functionality available, 
> 
> Me too. But I don't care whether it's a seperate library or not. 
> Aleksandar: great initiative.
> 
> >>Could you tell us more about what your evaluator does?  How does it
> >>compute derivatives?  Symbolically or numerically?  Does it simplify
> >>formulas?  Does it look for common subexpressions? 
> 
> I wrote a similar library about 10 years ago. Derivatives are not too 
> difficult to implement, but the expressions become really ugly. Try to 
> derive sin(x)^cos(x) w.r.t. x to see what I mean :-).

I have such a system in Numexp-core (http://numexp.sf.net), but as
Kenneth said, derivatives become very ugly.
> 
> Simplifying expressions is a much harder job. Of course you can do 
> simple things like (x-x) -> 0 and (1*x) -> x but (x+y)-x is not that easy.

I am doing some of these simple simplifications. Started writing a
better simplifier by patter matching in Perl. It gives some interesting
results, but is not a decent way.
> 
> > My library is parsing string and creating tree representation of it in
> > memory.  
> 
> Tree representation is straight forward but might not be the most 
> efficient representation. At least in the 1980's and 1990's I believe 
> that most compilers used DAGs (Directed Acyclic Graphs). The Dragon book 
> by Aho et al. outlines the algorithms.

I am using trees, too!

Alberto

Re: libevaluator library and GSL

[Aleksandar B. Samardzic]

On Fri, Sep 05, 2003 at 11:38:33AM +0100, Brian Gough wrote:
> Aleksandar B. Samardzic writes:
>  > I've written a library
>  > (http://savannah.nongnu.org/projects/libevaluator/) that makes possible
>  > to parse strings representing mathematical functions over single or
>  > multiple variables and later to evaluate these functions for different
>  > variable values (also to create representation of function derivative
>  > over specified variable etc.).  I've submitted this library for
>  > evaluation regarding inclusion in GNU project and was told by my
>  > evaluator that they would rather like to see my library as part of GSL
>  > than to publish it as separate library.  My library is written in C, but
>  > offers also Fortran 77 and Gule interfaces (as well as Fortran 90
>  > interface). 
> 
> Hello,
> 
> Thanks for your email.  I've had a look at your package from CVS.
> Here are my comments, which you may pass on to the GNU evaluator.
> 
> The question of having an expression parser in GSL came up once
> before.
> 
> My opinion was that a library to do this could be useful in many
> C programs, including those which do not require anything else in
> GSL.
> 
> Having a standalone evaluator package, with minimal dependencies,
> that is very easy for people to integrate into their program
> could be a good strategy for encouraging people to use the GPL
> for their software -- in the same way that the Readline library
> does.
> 
> If the evaluator is part of GSL then it reduces the effectiveness
> of this approach, because GSL is so big (probably much larger
> than the application the evaluator would be used in) and could
> not be distributed with the program very easily.
> 
> So, I would recommend having a single standalone library under
> the GPL, standardising on ANSI C expressions, and having no
> external dependencies (except for the standard c library), to
> maximise the potential userbase.


Brian,

Thank you for your effort and suggestions.  Since I guess you have best
perspective here, I'll follow your suggestion and approach my evaluator
again to re-consider having libevaluator to be separate part of GNU
project.  Anyway, whether it will become part of GNU project or not, it
is already available at mentioned location
(http://savannah.nongnu.org/projects/libevaluator/) and is already under
GPL, so if anyone interested - feel free to utilize it.  I'd like also
to thank other people that responded to my message for very useful
suggestions regarding further work on this library.

Regards,
Alex

Re: libevaluator library and GSL

[Juan Jose Gomez Cadenas]

Hi Alkesandar, just to let you know that I will include your library in my
teaching course this year. I teach a Numerical methods course for 
third-year physics students. The language is C++ and having an evaluator 
in C, easily wrapable to C++ is a very welcome tool.

Thanks for the effort. Best regards,
J.J. Gomez-Cadenas.

On Fri, 5 Sep 2003, Aleksandar B. Samardzic wrote:

> On Fri, Sep 05, 2003 at 11:38:33AM +0100, Brian Gough wrote:
> > Aleksandar B. Samardzic writes:
> >  > I've written a library
> >  > (http://savannah.nongnu.org/projects/libevaluator/) that makes possible
> >  > to parse strings representing mathematical functions over single or
> >  > multiple variables and later to evaluate these functions for different
> >  > variable values (also to create representation of function derivative
> >  > over specified variable etc.).  I've submitted this library for
> >  > evaluation regarding inclusion in GNU project and was told by my
> >  > evaluator that they would rather like to see my library as part of GSL
> >  > than to publish it as separate library.  My library is written in C, but
> >  > offers also Fortran 77 and Gule interfaces (as well as Fortran 90
> >  > interface). 
> > 
> > Hello,
> > 
> > Thanks for your email.  I've had a look at your package from CVS.
> > Here are my comments, which you may pass on to the GNU evaluator.
> > 
> > The question of having an expression parser in GSL came up once
> > before.
> > 
> > My opinion was that a library to do this could be useful in many
> > C programs, including those which do not require anything else in
> > GSL.
> > 
> > Having a standalone evaluator package, with minimal dependencies,
> > that is very easy for people to integrate into their program
> > could be a good strategy for encouraging people to use the GPL
> > for their software -- in the same way that the Readline library
> > does.
> > 
> > If the evaluator is part of GSL then it reduces the effectiveness
> > of this approach, because GSL is so big (probably much larger
> > than the application the evaluator would be used in) and could
> > not be distributed with the program very easily.
> > 
> > So, I would recommend having a single standalone library under
> > the GPL, standardising on ANSI C expressions, and having no
> > external dependencies (except for the standard c library), to
> > maximise the potential userbase.
> 
> 
> Brian,
> 
> Thank you for your effort and suggestions.  Since I guess you have best
> perspective here, I'll follow your suggestion and approach my evaluator
> again to re-consider having libevaluator to be separate part of GNU
> project.  Anyway, whether it will become part of GNU project or not, it
> is already available at mentioned location
> (http://savannah.nongnu.org/projects/libevaluator/) and is already under
> GPL, so if anyone interested - feel free to utilize it.  I'd like also
> to thank other people that responded to my message for very useful
> suggestions regarding further work on this library.
> 
> Regards,
> Alex
> 

Re: libevaluator library and GSL

[James Amundson]

On Fri, 2003-09-05 at 03:14, Alberto Manuel Brandão Simões wrote:

> > I wrote a similar library about 10 years ago. Derivatives are not too 
> > difficult to implement, but the expressions become really ugly. Try to 
> > derive sin(x)^cos(x) w.r.t. x to see what I mean :-).
> 
> I have such a system in Numexp-core (http://numexp.sf.net), but as
> Kenneth said, derivatives become very ugly.
> > 
> > Simplifying expressions is a much harder job. Of course you can do 
> > simple things like (x-x) -> 0 and (1*x) -> x but (x+y)-x is not that easy.
> 
> I am doing some of these simple simplifications. Started writing a
> better simplifier by patter matching in Perl. It gives some interesting
> results, but is not a decent way.

If you are interested in symbolic algebra, there are fully functional
free software packages available. I would argue that Maxima is the most
capable of them. (I might be biased by the fact that I lead the Maxima
Project.)

If you are really interested in learning how simplifications work in
computer algebra systems, you should probably try reading at least one
book on the subject. I would recommend starting with Paradigms of
Artificial Intelligence Programming by Peter Norvig. There are many
others.

--Jim