All this software, source and object is placed in the public domain. INTRODUCTION ------------ This package allows you to manipulate expressions. Currently, it's two main functions are evaluation and differentiation. I may add other operations at a later date ... It also does some basic simplifications (based on pattern matching), to make the result of a differentiation more presentable. DISCUSSION ---------- a) Basic concepts The basic object is a "value", an expression stored in the form of a binary tree. It is composed of numeric constants (eg 1, 2.4e5 ..., plus pi and e), "variables", functions (for a list of those recognized, see appendix A), and the operators +, -, *, /, ^ (exponentiation). The expressions are case insensitive (everything is converted to lower case). A "variable" is any sequence of characters starting with a letter, and followed by letters or numbers (providing it isn't the name of a function or constant). A "quick variable" is a variable that can take on numerical values. They are faster and easier to set up. A "context" is a list of variables with "values" associated with them. Note that the same variable may be defined several times, the most 'recent' version is used. The "current context" is the one searched when any routine needs the value of a variable (eg when evaluating). b) Initialising & cleanup Before using any of these routines, you must call init_expr(). This will return TRUE if it succeeds, FALSE otherwise (this normally indicates that there isn't enough memory, check eval_error. When you have finished, call cleanup_expr() (even if init_expr() failed). These routines are quite slow (around 1/2 sec for init), avoid calling them more than once ... (that is, don't repeat the init/cleanup pair). c) Variables Before using any of the routines (except compile, decompile, differentiate and free_expr), you must define a context. To do so, declare a variable of type "context", and call init_context() and set_context(), as in : context our_context; ... if (init_expr()) { init_context(&our_context); set_context(&our_context); /* whatever you're doing */ } cleanup_expr(); You can of course use several contexts (for example, have one per function in a graphing program), calling set_context to switch between them. There are 2 ways to refer to variables: either directly by name, or through the type "variable". The second implements a cache that will make subsequent references to that variable much faster (the cache is invalidated every time you change context, create or free a variable). If you use the "variable" structure, set up the name field, and set key to 0. The actual routines available are int create_var(variable *v) create v void free_var(variable *v) delete the first instance of v int set_var(variable *v, value val) set v to "value" val, create if doesn't exist. value get_var(variable *v) return the value of v, NULL if doesn't exist. As pointed out earlier, you can have multiple copies of the same variable in existence, the latest one created is the one referred to. Therefore create_var (and set_var) can only fail because of lack of memory. The same routines exist, suffixed by _name, if you wish to refer to variables by name (the parameter is then a char *). If you need to use numeric variables, there is a quick way of doing so: use the _quick routines. These use the same format as above, except that you *must* create the variable before use, and you pass "double's" instead of "value's" (the routines are: create_quick, free_quick, set_quick, get_quick). Finally, there is a group of functions to generate and use "variable lists": this is an Exec list, with the node names being the names of variables. The function init_var_list (actually, a macro) initialises the var_list. You can then call make_var_list(expression, list) to build the list of variables present in "expression". This will return NULL if it fails. create_vars() will create the variables in a list, free_vars() will free them and free_var_list will delete the list itself. If you want to something more sophisticated, you must scan the list yourself (in the usual fashion). d) Expression creation The routine compile() takes a string and creates a "value" from it. For the recognized syntax, see Appendix a). If the routine fails, it returns NULL, and eval_error contains the error (see Appendix C for a detailed explanation). decompile(expr, buffer, maxlen) takes an expression and creates a string in the 'standard' mathematical format. free_expr() frees the memory used by an expression. e) Expression evaluation The basic routine is eval(expression, flags). It returns a "value", NULL if there's an error (see eval_error). This is a new expression, you must free_expr() it when you are finished. The flags are as follows (you can combine them, as in gasp = eval(glorf, PAT | REC); ) PAT: do some simple simplifications, eg 0*X -> 0. For a complete list, see Appendix D. NICE: By default, any operation involving constants in the source expression is replaced by its value in the destination. With this flag, this is only done if the result is an integer (thus 2*3 becomes 6, but 2/3 stays as is). VAR: Replace variables by their values (taken from the current context). If they haven't one, simply leave the variable name as is. REC: Replace variables by their evaluated values. As an example of the difference between VAR & REC, consider the expression 2*A with A = B*C, B = 4, C = 3 With VAR, this will give 2*B*C, with REC, 24. Recursive calls (that is evaluating "A", when A = B and B = A, or more complex loops) will result in an error. NORED: Don't do any constant folding (replacing operations on numeric arguments by their values). If you want a numeric value as a result, call quick_eval. This is equivalent to eval(expression, REC), but will return a double, or set eval_error if this isn't possible (eg if a variable has no value). f) Expression manipulation All you can yet do is differentiate an expression. The call is res = differentiate(expression, name) and it will differentiate expression with respect to "name". "res" will be NULL if this fails, and eval_error will contain the error. EXTRA INFORMATION ----------------- A detailed description of the routines, types, etc can be found in the doc directory. USE --- To actually use these routines, it is best to make an object library out of them (see Appendix E, compilation). You will want to copy the include file eval.h to some convenient place. This provides the definition of all the externally visible data structures, variables and functions. An example is provided in the example directory. APPENDICES ---------- APPENDIX A: Expression syntax The following is an informal description of the syntax of expressions, the actual priorities of the operators are the usual arithmetic ones (with unary minus higher than power), they all group left to right. | indicates alternatives, [] optional parts. expression := expression '+' expression | expression '-' expression | expression '*' expression | expression '/' expression | expression '^' expression | '+' expression | '-' expression | '(' expression ')' | number | function '(' expression ')' | variable number := mantissa [exponent] mantissa := integer [ '.' integer ] exponent := 'E' [sign] integer sign := '+' | '-' function := variable := You will notice (?) that numbers do not allow a leading sign, negative numbers are actually entered as an expression of the form -expression. After constant folding, this may not be the case any more .,, APPENDIX B: Recognized functions: name description ---- ----------- sin sine cos cosine tan tangent asin Arc sine acos Arc cosine atan Arc tangent sinh hyperbolic sine cosh hyperbolic cosine tanh hyperbolic tangent asinh inverse hyperbolic sine acosh inverse hyperbolic cosine atanh inverse hyperbolic tangent exp e^x exp10 10^x abs absolute value - not differentiable log base e logarithm log10 base 10 logarithm sqrt square root sqr x^2 gamma gamma function - not differentiable APPENDIX C: Errors - SYNTAX : the syntax of an expression was incorrect - OUT_OF_MEM : no memory for requested operation - UNMATCHED : parenthesises are not matched - WANT_LEFT : left parenthesis expected (after a function) - NOT_DIFFERENTIABLE : guess. - RECURSIVE : you have asked for a recursive evaluation ... - NOTNUM : the result isn't a number (quick_eval) APPENDIX D: Simplifications This table contains the list of simplifications done, the first column is the expressions recognized, the second what they are replaced by. Any variable can take the place of any expression however complex. This table is taken directly from the source ... expression replaced by ---------------------------------- x+(-y) x-y -x+y y-x x-(-y) x+y -(-x) x sqr(x^y) x^(y*2) 0+x x x+0 x x-0 x 0-x -x x-x 0 x*0 0 0*x 0 1*x x x*1 x -1*x -x x*-1 -x x/1 x -x/-y x/y 1^x 1 x^0 1 x^1 x x^2 sqr(x) x^-1 1/x sin(-x) -sin(x) cos(-x) cos(x) tan(atan(x)) x tan(-x) -tan(x) sin(x)/cos(x) tan(x) abs(abs(x)) abs(x) abs(-x) abs(x) 10^x exp10(x) log(exp(x)) x log10(exp10(x)) x log10(exp(x)) x*log10(e) log(exp10(x)) x*log(10) sinh(asinh(x)) x asinh(sinh(x)) x 0/x 0 Debatable simplification x/sqr(x) 1/x " " More could easily be added, but more complex (and useful) simplifications such as replacing x+3*x+x with 5*x are another problem entirely ... APPENDIX E: Compilation These routines were written with Lattice C V4.01, and use a certain number of lattice-specific routines. The easiest way to use them is to make an object library (called eval.lib of course), I have provided a DMake makefile for this (a last minute addition, as I got DMake this morning :-)). It is quite easy to do manually. The source is in the src directory, eval.h is at the 'root' level.