Re: [boost] [GSoC] Some new ideas for this year's GSoC

Subject: Re: [boost] [GSoC] Some new ideas for this year's GSoC
From: Stefan (mstefanro_at_[hidden])
Date: 2010-04-06 17:06:08

Topher Cooper wrote:
> Actually the difficulty is "easy".  The basic precedence parser  could be whipped out in an hour or so.  Another day or a bit more to do the interfacing, define the expression data structures, and do the constant folding.
> 
> Operators also need associativity, or, more expressively, two precedences -- a left and a right precedence.
> 
> You don't really need to specify "allowed variables" any more than you need to specify allowed literals -- if the parser sees a variable it can use it.
> 
> Personally I would include templates rather than just an operator string and then depend on the arity to determine the type.  Then you can handle ternary and postfix operators.
> 
> Topher
> 
> On Apr 6, 2010, at 8:01 AM, Stefan wrote:
> 
>> * A parser capable of evaluating mathematical expressions which contains operands,operators,function calls,variable names and constant names (also considering priority of operators):
>> 1. a list of valid operators described by: a) number of operands (unary/binary/ternary?); b) allowed operand types; c) the precedence (priority of the operator)
>> 2. a list of existent functions described by: a) function name; b) number of parameters; c) type of each parameter and return type; d) a callback (maybe just automatically deduce type based on the callback's type if possible)
>> 3. a list of constants
>> 4. a list of allowed variable names and types
>>
>> Here's a pseudo-C++ code sample on how it should look like:
>> namespace m = boost::math_expressions_parser;
>> m::parser p;
>> p.add_operators()
>> ('+', 1, ret<int32_t>(_1+_2)) // binary +, precedence 1
>> ('*', 2, ret<int32_t>(_1*_2)) // binary -, precedence 2
>> ('+', 3, ret<int32_t>(_1)) // unary +, precedence 3
>> ('-', 3, ret<int32_t>(-_1)); // unary - (also a funny face), precedence 3
>> p.add_functions()
>> ("sin", ret<int32_t>(sin(_1)));
>> p.add_constants()
>> ("PI", 3);
>> p.add_allowed_variables()
>> (allowed_var<int32_t>("x"));
>>
>> m::expression E("1 + 3*sin(PI*x)", p); // evaluates mathematical expression E against parser p
>> if (!E.valid()) { /* ... */ }
>> else {
>> std::cout << E.evaluate( ("x", 3) ); // evaluate this expression by letting x=3
>> E.let() ("x",4);
>> std::cout << E.evaluate();
>> }
>> //Maybe an optimization so only the parts that depend on the changed variable will be recalculated every time?. E.g.: for expression f(x)+y, f(x) is recomputed only when x is changed. This may cause problems for functions that do not always yield the same results for the same input. Maybe make this optimization optional, only if the user marks the function/operator as "volatile" or something
>> Difficulty: hard-very hard
> 
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
> 
Yes, I apologize. The "hard-very hard" wasn't meant to be there (I only 
wanted to use very-easy and easy on the difficulty tags initially). This 
is quite trivial to implement and all the other ideas are. I agree that 
these alone aren't sufficient for a proposal as they would be all 
finished in a relatively small amount of time, but I was thinking of 
implementing some of these in addition to one of the boost's ideas.
Also, you have good points on associativity and preferring the use of 
templates, appreciated.

Stefan