home *** CD-ROM | disk | FTP | other *** search
/ The Fred Fish Collection 1.5 / ffcollection-1-5-1992-11.iso / ff_disks / 100-199 / ff192.lzh / Eval / doc / eval.doc < prev    next >
Text File  |  1989-03-14  |  11KB  |  335 lines
  1. All this software, source and object is placed in the public domain.
  2.  
  3.  
  4. INTRODUCTION
  5. ------------
  6.  
  7. This package allows you to manipulate expressions. Currently, it's two main
  8. functions are evaluation and differentiation. I may add other operations at
  9. a later date ... It also does some basic simplifications (based on pattern
  10. matching), to make the result of a differentiation more presentable.
  11.  
  12.  
  13. DISCUSSION
  14. ----------
  15.  
  16. a) Basic concepts
  17.  
  18.    The basic object is a "value", an expression stored in the form of a binary
  19.    tree. It is composed of numeric constants (eg 1, 2.4e5 ..., plus pi and
  20.    e), "variables", functions (for a list of those recognized, see appendix
  21.    A), and the operators +, -, *, /, ^ (exponentiation). The expressions
  22.    are case insensitive (everything is converted to lower case).
  23.  
  24.    A "variable" is any sequence of characters starting with a letter, and
  25.    followed by letters or numbers (providing it isn't the name of a
  26.    function or constant).
  27.  
  28.    A "quick variable" is a variable that can take on numerical values. They
  29.    are faster and easier to set up.
  30.  
  31.    A "context" is a list of variables with "values" associated with them.
  32.    Note that the same variable may be defined several times, the most
  33.    'recent' version is used.
  34.  
  35.    The "current context" is the one searched when any routine needs the
  36.    value of a variable (eg when evaluating).
  37.  
  38.  
  39. b) Initialising & cleanup
  40.  
  41.    Before using any of these routines, you must call init_expr(). This will
  42.    return TRUE if it succeeds, FALSE otherwise (this normally indicates
  43.    that there isn't enough memory, check eval_error.
  44.  
  45.    When you have finished, call cleanup_expr() (even if init_expr()
  46.    failed).
  47.  
  48.    These routines are quite slow (around 1/2 sec for init), avoid calling
  49.    them more than once ... (that is, don't repeat the init/cleanup pair).
  50.  
  51. c) Variables
  52.  
  53.    Before using any of the routines (except compile, decompile,
  54.    differentiate and free_expr), you must define a context. To do so,
  55.    declare a variable of type "context", and call init_context() and
  56.    set_context(), as in :
  57.  
  58.     context our_context;
  59.  
  60.     ...
  61.  
  62.     if (init_expr()) {
  63.     init_context(&our_context);
  64.     set_context(&our_context);
  65.  
  66.     /* whatever you're doing */
  67.     }
  68.     cleanup_expr();
  69.  
  70.    You can of course use several contexts (for example, have one per
  71.    function in a graphing program), calling set_context to switch between
  72.    them.
  73.  
  74.    There are 2 ways to refer to variables: either directly by name, or
  75.    through the type "variable". The second implements a cache that will
  76.    make subsequent references to that variable much faster (the cache is
  77.    invalidated every time you change context, create or free a variable).
  78.    If you use the "variable" structure, set up the name field, and set key
  79.    to 0. The actual routines available are
  80.  
  81.     int create_var(variable *v)     create v
  82.     void free_var(variable *v)      delete the first instance of v
  83.     int set_var(variable *v, value val)
  84.                     set v to "value" val, create if
  85.                     doesn't exist.
  86.     value get_var(variable *v)      return the value of v, NULL if
  87.                     doesn't exist.
  88.  
  89.    As pointed out earlier, you can have multiple copies of the same
  90.    variable in existence, the latest one created is the one referred to.
  91.    Therefore create_var (and set_var) can only fail because of lack of
  92.    memory. The same routines exist, suffixed by _name, if you wish to
  93.    refer to variables by name (the parameter is then a char *).
  94.  
  95.    If you need to use numeric variables, there is a quick way of doing so:
  96.    use the _quick routines. These use the same format as above, except that
  97.    you *must* create the variable before use, and you pass "double's"
  98.    instead of "value's" (the routines are: create_quick, free_quick,
  99.    set_quick, get_quick).
  100.  
  101.  
  102.    Finally, there is a group of functions to generate and use "variable
  103.    lists": this is an Exec list, with the node names being the names of
  104.    variables. The function init_var_list (actually, a macro) initialises
  105.    the var_list. You can then call make_var_list(expression, list) to build
  106.    the list of variables present in "expression". This will return NULL if
  107.    it fails. create_vars() will create the variables in a list, free_vars()
  108.    will free them and free_var_list will delete the list itself. If you
  109.    want to something more sophisticated, you must scan the list yourself
  110.    (in the usual fashion).
  111.  
  112. d) Expression creation
  113.  
  114.    The routine compile() takes a string and creates a "value" from it. For
  115.    the recognized syntax, see Appendix a). If the routine fails, it returns
  116.    NULL, and eval_error contains the error (see Appendix C for a detailed
  117.    explanation).
  118.  
  119.    decompile(expr, buffer, maxlen) takes an expression and creates a string
  120.    in the 'standard' mathematical format.
  121.  
  122.    free_expr() frees the memory used by an expression.
  123.  
  124. e) Expression evaluation
  125.  
  126.    The basic routine is eval(expression, flags). It returns a "value", NULL
  127.    if there's an error (see eval_error). This is a new expression, you must
  128.    free_expr() it when you are finished. The flags are as follows (you can
  129.    combine them, as in gasp = eval(glorf, PAT | REC); )
  130.  
  131.     PAT: do some simple simplifications, eg 0*X -> 0. For a complete list,
  132.     see Appendix D.
  133.  
  134.     NICE: By default, any operation involving constants in the source
  135.     expression is replaced by its value in the destination. With this flag,
  136.     this is only done if the result is an integer (thus 2*3 becomes 6, but
  137.     2/3 stays as is).
  138.  
  139.     VAR: Replace variables by their values (taken from the current
  140.     context). If they haven't one, simply leave the variable name as is.
  141.  
  142.     REC: Replace variables by their evaluated values. As an example of the
  143.     difference between VAR & REC, consider the expression
  144.  
  145.     2*A
  146.  
  147.     with A = B*C, B = 4, C = 3
  148.  
  149.     With VAR, this will give 2*B*C, with REC, 24. Recursive calls (that is
  150.     evaluating "A", when A = B and B = A, or more complex loops) will
  151.     result in an error.
  152.  
  153.     NORED: Don't do any constant folding (replacing operations on numeric
  154.     arguments by their values).
  155.  
  156.  
  157.    If you want a numeric value as a result, call quick_eval. This is
  158.    equivalent to eval(expression, REC), but will return a double, or set
  159.    eval_error if this isn't possible (eg if a variable has no value).
  160.  
  161. f) Expression manipulation
  162.  
  163.    All you can yet do is differentiate an expression. The call is
  164.  
  165.     res = differentiate(expression, name)
  166.  
  167.    and it will differentiate expression with respect to "name". "res" will
  168.    be NULL if this fails, and eval_error will contain the error.
  169.  
  170.  
  171. EXTRA INFORMATION
  172. -----------------
  173.  
  174.    A detailed description of the routines, types, etc can be found in the
  175.    doc directory.
  176.  
  177.  
  178. USE
  179. ---
  180.  
  181.    To actually use these routines, it is best to make an object library out
  182.    of them (see Appendix E, compilation). You will want to copy the include
  183.    file eval.h to some convenient place. This provides the definition of
  184.    all the externally visible data structures, variables and functions.
  185.  
  186.    An example is provided in the example directory.
  187.  
  188.  
  189. APPENDICES
  190. ----------
  191.  
  192. APPENDIX A: Expression syntax
  193.  
  194.     The following is an informal description of the syntax of expressions,
  195.     the actual priorities of the operators are the usual arithmetic ones
  196.     (with unary minus higher than power), they all group left to right.
  197.     | indicates alternatives, [] optional parts.
  198.  
  199. expression := expression '+' expression |
  200.           expression '-' expression |
  201.           expression '*' expression |
  202.           expression '/' expression |
  203.           expression '^' expression |
  204.           '+' expression |
  205.           '-' expression |
  206.           '(' expression ')' |
  207.           number |
  208.           function '(' expression ')' |
  209.           variable
  210.  
  211. number := mantissa [exponent]
  212.  
  213. mantissa := integer [ '.' integer ]
  214.  
  215. exponent := 'E' [sign] integer
  216.  
  217. sign := '+' | '-'
  218.  
  219. function := <see Appendix B>
  220.  
  221. variable := <any name>
  222.  
  223.  
  224.     You will notice (?) that numbers do not allow a leading sign, negative
  225.     numbers are actually entered as an expression of the form -expression.
  226.     After constant folding, this may not be the case any more .,,
  227.  
  228.  
  229. APPENDIX B: Recognized functions:
  230.  
  231. name        description
  232. ----        -----------
  233. sin        sine
  234. cos        cosine
  235. tan        tangent
  236. asin        Arc sine
  237. acos        Arc cosine
  238. atan        Arc tangent
  239. sinh        hyperbolic sine
  240. cosh        hyperbolic cosine
  241. tanh        hyperbolic tangent
  242. asinh        inverse hyperbolic sine
  243. acosh        inverse hyperbolic cosine
  244. atanh        inverse hyperbolic tangent
  245. exp        e^x
  246. exp10        10^x
  247. abs        absolute value - not differentiable
  248. log        base e logarithm
  249. log10        base 10 logarithm
  250. sqrt        square root
  251. sqr        x^2
  252. gamma        gamma function - not differentiable
  253.  
  254.  
  255. APPENDIX C: Errors
  256.  
  257.     - SYNTAX : the syntax of an expression was incorrect
  258.  
  259.     - OUT_OF_MEM : no memory for requested operation
  260.  
  261.     - UNMATCHED : parenthesises are not matched
  262.  
  263.     - WANT_LEFT : left parenthesis expected (after a function)
  264.  
  265.     - NOT_DIFFERENTIABLE : guess.
  266.  
  267.     - RECURSIVE : you have asked for a recursive evaluation ...
  268.  
  269.     - NOTNUM : the result isn't a number (quick_eval)
  270.  
  271.  
  272. APPENDIX D: Simplifications
  273.  
  274.     This table contains the list of simplifications done, the first column
  275.     is the expressions recognized, the second what they are replaced by.
  276.     Any variable can take the place of any expression however complex. This
  277.     table is taken directly from the source ...
  278.  
  279.      expression      replaced by
  280.      ----------------------------------
  281.      x+(-y)              x-y
  282.      -x+y         y-x
  283.      x-(-y)              x+y
  284.      -(-x)               x
  285.      sqr(x^y)            x^(y*2)
  286.      0+x         x
  287.      x+0         x
  288.      x-0         x
  289.      0-x         -x
  290.      x-x         0
  291.      x*0         0
  292.      0*x         0
  293.      1*x         x
  294.      x*1         x
  295.      -1*x         -x
  296.      x*-1         -x
  297.      x/1         x
  298.      -x/-y         x/y
  299.      1^x         1
  300.      x^0         1
  301.      x^1         x
  302.      x^2         sqr(x)
  303.      x^-1         1/x
  304.      sin(-x)             -sin(x)
  305.      cos(-x)             cos(x)
  306.      tan(atan(x))        x
  307.      tan(-x)             -tan(x)
  308.      sin(x)/cos(x)       tan(x)
  309.      abs(abs(x))         abs(x)
  310.      abs(-x)             abs(x)
  311.      10^x         exp10(x)
  312.      log(exp(x))         x
  313.      log10(exp10(x))     x
  314.      log10(exp(x))       x*log10(e)
  315.      log(exp10(x))       x*log(10)
  316.      sinh(asinh(x))      x
  317.      asinh(sinh(x))      x
  318.      0/x         0        Debatable simplification
  319.      x/sqr(x)            1/x               "           "
  320.  
  321.     More could easily be added, but more complex (and useful) simplifications
  322.     such as replacing x+3*x+x with 5*x are another problem entirely ...
  323.  
  324. APPENDIX E: Compilation
  325.  
  326.     These routines were written with Lattice C V4.01, and use a certain
  327.     number of lattice-specific routines. The easiest way to use them is
  328.     to make an object library (called eval.lib of course), I have provided
  329.     a DMake makefile for this (a last minute addition, as I got DMake this
  330.     morning :-)). It is quite easy to do manually.
  331.  
  332.     The source is in the src directory, eval.h is at the 'root' level.
  333.  
  334.  
  335.