Friday, October 2, 2009

Evaluating math expressions in F#

This time we will try to write math expressions evaluator in F#. At first - why we need that ? Well, math expressions evaluator is useful in computer algebra systems - for evaluating some equations. Also such evaluator may be useful for financial institutions where also some kind of formula computation/evaluation is needed and etc. It`s a pitty that such eval function is not implemented in F# language. Possible reasons is that F# is compiled language... Anyway we will try to write such universal eval function which accepts arbitrary math expression and returns result to the user. So what are possible ways of implementing such function in F# ?

- by writing so called domain-specific language - math expressions compiler. This is achieved by using some tools such as fsyacc and fslex. Defining custom tokens and etc.

- by using .NET System.CodeDom.Compiler libraries. This is achieved by generating class definition "on the fly" and with the help of CodeDom - compiling this class in memory.

- another different approach - is try to write F# script which recursively analyzes math expression and evaluates it piece by piece until it finds the answer. This solution does not use tools mentioned above.

So the last approach will be discussed here. Main algorithm of evaluating math expressions is displayed below:

F# code which implements this idea is placed here.
There are also some eval() function tests implemented in this code. So that after executing this script you will get output something like:


It is possible to generalize eval() function algorithm in about 90~ lines of F# code without using CodeDom model or fsyacc/fslex tools. This makes solution pretty much "homogeneous" which can be useful in some situations. Also this eval() implementation takes as input arbitrary math expression. As for the bad side - solution is very slow (can be hundreds of times slower than plain F# function call), because of joining/spliting lists constantly. So if you need fast implementation of eval - you should optimize/rewrite this code if possible or take a look in other above mentioned solutions. But in systems where speed issues are not critical - this solution may be OK.

Have fun with F# and eval !!

No comments:

Post a Comment

Comment will be posted after comment moderation.
Thank you for your appreciation.