"Fossies" - the Fresh Open Source Software Archive

Member "gmp-6.2.1/demos/expr/README" (14 Nov 2020, 19269 Bytes) of package /linux/misc/gmp-6.2.1.tar.xz:


As a special service "Fossies" has tried to format the requested text file into HTML format (style: standard) with prefixed line numbers. Alternatively you can here view or download the uninterpreted source code file.

    1 Copyright 2001, 2004 Free Software Foundation, Inc.
    2 
    3 This file is part of the GNU MP Library.
    4 
    5 The GNU MP Library is free software; you can redistribute it and/or modify
    6 it under the terms of either:
    7 
    8   * the GNU Lesser General Public License as published by the Free
    9     Software Foundation; either version 3 of the License, or (at your
   10     option) any later version.
   11 
   12 or
   13 
   14   * the GNU General Public License as published by the Free Software
   15     Foundation; either version 2 of the License, or (at your option) any
   16     later version.
   17 
   18 or both in parallel, as here.
   19 
   20 The GNU MP Library is distributed in the hope that it will be useful, but
   21 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
   22 or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
   23 for more details.
   24 
   25 You should have received copies of the GNU General Public License and the
   26 GNU Lesser General Public License along with the GNU MP Library.  If not,
   27 see https://www.gnu.org/licenses/.
   28 
   29 
   30 
   31 
   32 
   33 
   34                     GMP EXPRESSION EVALUATION
   35                     -------------------------
   36 
   37 
   38 
   39 THIS CODE IS PRELIMINARY AND MAY BE SUBJECT TO INCOMPATIBLE CHANGES IN
   40 FUTURE VERSIONS OF GMP.
   41 
   42 
   43 
   44 The files in this directory implement a simple scheme of string based
   45 expression parsing and evaluation, supporting mpz, mpq and mpf.
   46 
   47 This will be slower than direct GMP library calls, but may be convenient in
   48 various circumstances, such as while prototyping, or for letting a user
   49 enter values in symbolic form.  "2**5723-7" for example is a lot easier to
   50 enter or maintain than the equivalent written out in decimal.
   51 
   52 
   53 
   54 BUILDING
   55 
   56 Nothing in this directory is a normal part of libgmp, and nothing is built
   57 or installed, but various Makefile rules are available to compile
   58 everything.
   59 
   60 All the functions are available through a little library (there's no shared
   61 library since upward binary compatibility is not guaranteed).
   62 
   63 	make libexpr.a
   64 
   65 In a program, prototypes are available using
   66 
   67 	#include "expr.h"
   68 
   69 run-expr.c is a sample program doing evaluations from the command line.
   70 
   71 	make run-expr
   72 	./run-expr '1+2*3'
   73 
   74 t-expr.c is self-test program, it prints nothing if successful.
   75 
   76 	make t-expr
   77 	./t-expr
   78 
   79 The expr*.c sources don't depend on gmp-impl.h and can be compiled with just
   80 a standard installed GMP.  This isn't true of t-expr though, since it uses
   81 some of the internal tests/libtests.la.
   82 
   83 
   84 
   85 SIMPLE USAGE
   86 
   87 int mpz_expr (mpz_t res, int base, const char *e, ...);
   88 int mpq_expr (mpq_t res, int base, const char *e, ...);
   89 int mpf_expr (mpf_t res, int base, const char *e, ...);
   90 
   91 These functions evaluate simple arithmetic expressions.  For example,
   92 
   93 	mpz_expr (result, 0, "123+456", NULL);
   94 
   95 Numbers are parsed by mpz_expr and mpq_expr the same as mpz_set_str with the
   96 given base.  mpf_expr follows mpf_set_str, but supporting an "0x" prefix for
   97 hex when base==0.
   98 
   99 	mpz_expr (result, 0, "0xAAAA * 0x5555", NULL);
  100 
  101 White space, as indicated by <ctype.h> isspace(), is ignored except for the
  102 purpose of separating tokens.
  103 
  104 Variables can be included in expressions by putting them in the stdarg list
  105 after the string.  "a", "b", "c" etc in the expression string designate
  106 those values.  For example,
  107 
  108         mpq_t  foo, bar;
  109         ...
  110 	mpq_expr (q, 10, "2/3 + 1/a + b/2", foo, bar, NULL);
  111 
  112 Here "a" will be the value from foo and "b" from bar.  Up to 26 variables
  113 can be included this way.  The NULL must be present to indicate the end of
  114 the list.
  115 
  116 Variables can also be written "$a", "$b" etc.  This is necessary when using
  117 bases greater than 10 since plain "a", "b" etc will otherwise be interpreted
  118 as numbers.  For example,
  119 
  120         mpf_t  quux;
  121         mpf_expr (f, 16, "F00F@-6 * $a", quux, NULL);
  122 
  123 All the standard C operators are available, with the usual precedences, plus
  124 "**" for exponentiation at the highest precedence (and right associative).
  125 
  126         Operators      Precedence
  127          **              220
  128          ~ ! - (unary)   210
  129          * / %           200
  130          + -             190
  131          << >>           180
  132          <= < >= >       170
  133          == !=           160
  134          &               150
  135          ^               140
  136          |               130
  137          &&              120
  138          ||              110
  139          ? :             100/101
  140 
  141 Currently only mpz_expr has the bitwise ~ % & ^ and | operators.  The
  142 precedence numbers are of interest in the advanced usage described below.
  143 
  144 Various functions are available too.  For example,
  145 
  146         mpz_expr (res, 10, "gcd(123,456,789) * abs(a)", var, NULL);
  147 
  148 The following is the full set of functions,
  149 
  150         mpz_expr
  151             abs bin clrbit cmp cmpabs congruent_p divisible_p even_p fib fac
  152             gcd hamdist invert jacobi kronecker lcm lucnum max min nextprime
  153             odd_p perfect_power_p perfect_square_p popcount powm
  154             probab_prime_p root scan0 scan1 setbit sgn sqrt
  155 
  156         mpq_expr
  157             abs, cmp, den, max, min, num, sgn
  158 
  159         mpf_expr
  160             abs, ceil, cmp, eq, floor, integer_p, max, min, reldiff, sgn,
  161             sqrt, trunc
  162 
  163 All these are the same as the GMP library functions, except that min and max
  164 don't exist in the library.  Note also that min, max, gcd and lcm take any
  165 number of arguments, not just two.
  166 
  167 mpf_expr does all calculations to the precision of the destination variable.
  168 
  169 
  170 Expression parsing can succeed or fail.  The return value indicates this,
  171 and will be one of the following
  172 
  173 	MPEXPR_RESULT_OK
  174 	MPEXPR_RESULT_BAD_VARIABLE
  175 	MPEXPR_RESULT_BAD_TABLE
  176 	MPEXPR_RESULT_PARSE_ERROR
  177 	MPEXPR_RESULT_NOT_UI
  178 
  179 BAD_VARIABLE is when a variable is referenced that hasn't been provided.
  180 For example if "c" is used when only two parameters have been passed.
  181 BAD_TABLE is applicable to the advanced usage described below.
  182 
  183 PARSE_ERROR is a general syntax error, returned for any mal-formed input
  184 string.
  185 
  186 NOT_UI is returned when an attempt is made to use an operand that's bigger
  187 than an "unsigned long" with a function that's restricted to that range.
  188 For example "fib" is mpz_fib_ui and only accepts an "unsigned long".
  189 
  190 
  191 
  192 
  193 ADVANCED USAGE
  194 
  195 int mpz_expr_a (const struct mpexpr_operator_t *table,
  196                 mpz_ptr res, int base, const char *e, size_t elen,
  197                 mpz_srcptr var[26])
  198 int mpq_expr_a (const struct mpexpr_operator_t *table,
  199                 mpq_ptr res, int base, const char *e, size_t elen,
  200                 mpq_srcptr var[26])
  201 int mpf_expr_a (const struct mpexpr_operator_t *table,
  202                 mpf_ptr res, int base, unsigned long prec,
  203                 const char *e, size_t elen,
  204                 mpf_srcptr var[26])
  205 
  206 These functions are an advanced interface to expression parsing.
  207 
  208 The string is taken as pointer and length.  This makes it possible to parse
  209 an expression in the middle of somewhere without copying and null
  210 terminating it.
  211 
  212 Variables are an array of 26 pointers to the appropriate operands, or NULL
  213 for variables that are not available.  Any combination of variables can be
  214 given, for example just "x" and "y" (var[23] and var[24]) could be set.
  215 
  216 Operators and functions are specified with a table.  This makes it possible
  217 to provide additional operators or functions, or to completely change the
  218 syntax.  The standard tables used by the simple functions above are
  219 available as
  220 
  221 	const struct mpexpr_operator_t * const mpz_expr_standard_table;
  222 	const struct mpexpr_operator_t * const mpq_expr_standard_table;
  223 	const struct mpexpr_operator_t * const mpf_expr_standard_table;
  224 
  225 struct mpexpr_operator_t is the following
  226 
  227 	struct mpexpr_operator_t {
  228 	  const char    *name;
  229 	  mpexpr_fun_t  fun;
  230 	  int           type;
  231 	  int           precedence;
  232 	};
  233 
  234         typedef void (*mpexpr_fun_t) (void);
  235 
  236 As an example, the standard mpz_expr table entry for multiplication is as
  237 follows.  See the source code for the full set of standard entries.
  238 
  239 	{ "*", (mpexpr_fun_t) mpz_mul, MPEXPR_TYPE_BINARY, 200 },
  240 
  241 "name" is the string to parse, "fun" is the function to call for it, "type"
  242 indicates what parameters the function takes (among other things), and
  243 "precedence" sets its operator precedence.
  244 
  245 A NULL for "name" indicates the end of the table, so for example an mpf
  246 table with nothing but addition could be
  247 
  248         struct mpexpr_operator_t  table[] = {
  249           { "+", (mpexpr_fun_t) mpf_add, MPEXPR_TYPE_BINARY, 190 },
  250           { NULL }
  251         };
  252 
  253 A special type MPEXPR_TYPE_NEW_TABLE makes it possible to chain from one
  254 table to another.  For example the following would add a "mod" operator to
  255 the standard mpz table,
  256 
  257         struct mpexpr_operator_t  table[] = {
  258         { "mod", (mpexpr_fun_t) mpz_fdiv_r, MPEXPR_TYPE_BINARY, 125 },
  259         { (const char *) mpz_expr_standard_table, NULL, MPEXPR_TYPE_NEW_TABLE }
  260         };
  261 
  262 Notice the low precedence on "mod", so that for instance "45+26 mod 7"
  263 parses as "(45+26)mod7".
  264 
  265 
  266 Functions are designated by a precedence of 0.  They always occur as
  267 "foo(expr)" and so have no need for a precedence level.  mpq_abs in the
  268 standard mpq table is
  269 
  270 	{ "abs", (mpexpr_fun_t) mpq_abs, MPEXPR_TYPE_UNARY },
  271 
  272 Functions expecting no arguments as in "foo()" can be given with
  273 MPEXPR_TYPE_0ARY, or actual constants to be parsed as just "foo" are
  274 MPEXPR_TYPE_CONSTANT.  For example if a "void mpf_const_pi(mpf_t f)"
  275 function existed (which it doesn't) it could be,
  276 
  277 	{ "pi", (mpexpr_fun_t) mpf_const_pi, MPEXPR_TYPE_CONSTANT },
  278 
  279 
  280 Parsing of operator names is done by seeking the table entry with the
  281 longest matching name.  So for instance operators "<" and "<=" exist, and
  282 when presented with "x <= y" the parser matches "<=" because it's longer.
  283 
  284 Parsing of function names, on the other hand, is done by requiring a whole
  285 alphanumeric word to match.  For example presented with "fib2zz(5)" the
  286 parser will attempt to find a function called "fib2zz".  A function "fib"
  287 wouldn't be used because it doesn't match the whole word.
  288 
  289 The flag MPEXPR_TYPE_WHOLEWORD can be ORed into an operator type to override
  290 the default parsing style.  Similarly MPEXPR_TYPE_OPERATOR into a function.
  291 
  292 
  293 Binary operators are left associative by default, meaning they're evaluated
  294 from left to right, so for example "1+2+3" is treated as "(1+2)+3".
  295 MPEXPR_TYPE_RIGHTASSOC can be ORed into the operator type to work from right
  296 to left as in "1+(2+3)".  This is generally what's wanted for
  297 exponentiation, and for example the standard mpz table has
  298 
  299         { "**", (mpexpr_fun_t) mpz_pow_ui,
  300           MPEXPR_TYPE_BINARY_UI | MPEXPR_TYPE_RIGHTASSOC, 220 }
  301 
  302 Unary operators are postfix by default.  For example a factorial to be used
  303 as "123!" might be
  304 
  305 	{ "!", (mpexpr_fun_t) mpz_fac_ui, MPEXPR_TYPE_UNARY_UI, 215 }
  306 
  307 MPEXPR_TYPE_PREFIX can be ORed into the type to get a prefix operator.  For
  308 instance negation (unary minus) in the standard mpf table is
  309 
  310 	{ "-", (mpexpr_fun_t) mpf_neg,
  311           MPEXPR_TYPE_UNARY | MPEXPR_TYPE_PREFIX, 210 },
  312 
  313 
  314 The same operator can exist as a prefix unary and a binary, or as a prefix
  315 and postfix unary, simply by putting two entries in the table.  While
  316 parsing the context determines which style is sought.  But note that the
  317 same operator can't be both a postfix unary and a binary, since the parser
  318 doesn't try to look ahead to decide which ought to be used.
  319 
  320 When there's two entries for an operator, both prefix or both postfix (or
  321 binary), then the first in the table will be used.  This makes it possible
  322 to override an entry in a standard table, for example to change the function
  323 it calls, or perhaps its precedence level.  The following would change mpz
  324 division from tdiv to cdiv,
  325 
  326         struct mpexpr_operator_t  table[] = {
  327           { "/", (mpexpr_fun_t) mpz_cdiv_q, MPEXPR_TYPE_BINARY, 200 },
  328           { "%", (mpexpr_fun_t) mpz_cdiv_r, MPEXPR_TYPE_BINARY, 200 },
  329           { (char *) mpz_expr_standard_table, NULL, MPEXPR_TYPE_NEW_TABLE }
  330         };
  331 
  332 
  333 The type field indicates what parameters the given function expects.  The
  334 following styles of functions are supported.  mpz_t is shown, but of course
  335 this is mpq_t for mpq_expr_a, mpf_t for mpf_expr_a, etc.
  336 
  337     MPEXPR_TYPE_CONSTANT     void func (mpz_t result);
  338 
  339     MPEXPR_TYPE_0ARY         void func (mpz_t result);
  340     MPEXPR_TYPE_I_0ARY       int func (void);
  341 
  342     MPEXPR_TYPE_UNARY        void func (mpz_t result, mpz_t op);
  343     MPEXPR_TYPE_UNARY_UI     void func (mpz_t result, unsigned long op);
  344     MPEXPR_TYPE_I_UNARY      int func (mpz_t op);
  345     MPEXPR_TYPE_I_UNARY_UI   int func (unsigned long op);
  346 
  347     MPEXPR_TYPE_BINARY       void func (mpz_t result, mpz_t op1, mpz_t op2);
  348     MPEXPR_TYPE_BINARY_UI    void func (mpz_t result,
  349                                         mpz_t op1, unsigned long op2);
  350     MPEXPR_TYPE_I_BINARY     int func (mpz_t op1, mpz_t op2);
  351     MPEXPR_TYPE_I_BINARY_UI  int func (mpz_t op1, unsigned long op2);
  352 
  353     MPEXPR_TYPE_TERNARY      void func (mpz_t result,
  354                                         mpz_t op1, mpz_t op2, mpz_t op3);
  355     MPEXPR_TYPE_TERNARY_UI   void func (mpz_t result, mpz_t op1, mpz_t op2,
  356                                         unsigned long op3);
  357     MPEXPR_TYPE_I_TERNARY    int func (mpz_t op1, mpz_t op2, mpz_t op3);
  358     MPEXPR_TYPE_I_TERNARY_UI int func (mpz_t op1, mpz_t op2,
  359                                        unsigned long op3);
  360 
  361 Notice the pattern of "UI" for the last parameter as an unsigned long, or
  362 "I" for the result as an "int" return value.
  363 
  364 It's important that the declared type for an operator or function matches
  365 the function pointer given.  Any mismatch will have unpredictable results.
  366 
  367 For binary functions, a further type attribute is MPEXPR_TYPE_PAIRWISE which
  368 indicates that any number of arguments should be accepted, and evaluated by
  369 applying the given binary function to them pairwise.  This is used by gcd,
  370 lcm, min and max.  For example the standard mpz gcd is
  371 
  372 	{ "gcd", (mpexpr_fun_t) mpz_gcd,
  373 	  MPEXPR_TYPE_BINARY | MPEXPR_TYPE_PAIRWISE },
  374 
  375 Some special types exist for comparison operators (or functions).
  376 MPEXPR_TYPE_CMP_LT through MPEXPR_TYPE_CMP_GE expect an MPEXPR_TYPE_I_BINARY
  377 function, returning positive, negative or zero like mpz_cmp and similar.
  378 For example the standard mpf "!=" operator is
  379 
  380 	{ "!=", (mpexpr_fun_t) mpf_cmp, MPEXPR_TYPE_CMP_NE, 160 },
  381 
  382 But there's no obligation to use these types, for instance the standard mpq
  383 table just uses a plain MPEXPR_TYPE_I_BINARY and mpq_equal for "==".
  384 
  385 Further special types MPEXPR_TYPE_MIN and MPEXPR_TYPE_MAX exist to implement
  386 the min and max functions, and they take a function like mpf_cmp similarly.
  387 The standard mpf max function is
  388 
  389 	{ "max",  (mpexpr_fun_t) mpf_cmp,
  390           MPEXPR_TYPE_MAX | MPEXPR_TYPE_PAIRWISE },
  391 
  392 These can be used as operators too, for instance the following would be the
  393 >? operator which is a feature of GNU C++,
  394 
  395 	{ ">?", (mpexpr_fun_t) mpf_cmp, MPEXPR_TYPE_MAX, 175 },
  396 
  397 Other special types are used to define "(" ")" parentheses, "," function
  398 argument separator, "!" through "||" logical booleans, ternary "?"  ":", and
  399 the "$" which introduces variables.  See the sources for how they should be
  400 used.
  401 
  402 
  403 User definable operator tables will have various uses.  For example,
  404 
  405   - a subset of the C operators, to be rid of infrequently used things
  406   - a more mathematical syntax like "." for multiply, "^" for powering,
  407     and "!" for factorial
  408   - a boolean evaluator with "^" for AND, "v" for OR
  409   - variables introduced with "%" instead of "$"
  410   - brackets as "[" and "]" instead of "(" and ")"
  411 
  412 The only fixed parts of the parsing are the treatment of numbers, whitespace
  413 and the two styles of operator/function name recognition.
  414 
  415 As a final example, the following would be a complete mpz table implementing
  416 some operators with a more mathematical syntax.  Notice there's no need to
  417 preserve the standard precedence values, anything can be used so long as
  418 they're in the desired relation to each other.  There's also no need to have
  419 entries in precedence order, but it's convenient to do so to show what comes
  420 where.
  421 
  422         static const struct mpexpr_operator_t  table[] = {
  423 	  { "^",   (mpexpr_fun_t) mpz_pow_ui,
  424             MPEXPR_TYPE_BINARY_UI | MPEXPR_TYPE_RIGHTASSOC,           9 },
  425 
  426           { "!",   (mpexpr_fun_t) mpz_fac_ui, MPEXPR_TYPE_UNARY_UI,   8 },
  427           { "-",   (mpexpr_fun_t) mpz_neg,
  428             MPEXPR_TYPE_UNARY | MPEXPR_TYPE_PREFIX,                   7 },
  429 
  430           { "*",   (mpexpr_fun_t) mpz_mul,    MPEXPR_TYPE_BINARY,     6 },
  431           { "/",   (mpexpr_fun_t) mpz_fdiv_q, MPEXPR_TYPE_BINARY,     6 },
  432 
  433           { "+",   (mpexpr_fun_t) mpz_add,    MPEXPR_TYPE_BINARY,     5 },
  434           { "-",   (mpexpr_fun_t) mpz_sub,    MPEXPR_TYPE_BINARY,     5 },
  435 
  436           { "mod", (mpexpr_fun_t) mpz_mod,    MPEXPR_TYPE_BINARY,     6 },
  437 
  438           { ")",   NULL,                      MPEXPR_TYPE_CLOSEPAREN, 4 },
  439           { "(",   NULL,                      MPEXPR_TYPE_OPENPAREN,  3 },
  440           { ",",   NULL,                      MPEXPR_TYPE_ARGSEP,     2 },
  441 
  442           { "$",   NULL,                      MPEXPR_TYPE_VARIABLE,   1 },
  443           { NULL }
  444         };
  445 
  446 
  447 
  448 
  449 INTERNALS
  450 
  451 Operator precedence is implemented using a control and data stack, there's
  452 no C recursion.  When an expression like 1+2*3 is read the "+" is held on
  453 the control stack and 1 on the data stack until "*" has been parsed and
  454 applied to 2 and 3.  This happens any time a higher precedence operator
  455 follows a lower one, or when a right-associative operator like "**" is
  456 repeated.
  457 
  458 Parentheses are handled by making "(" a special prefix unary with a low
  459 precedence so a whole following expression is read.  The special operator
  460 ")" knows to discard the pending "(".  Function arguments are handled
  461 similarly, with the function pretending to be a low precedence prefix unary
  462 operator, and with "," allowed within functions.  The same special ")"
  463 operator recognises a pending function and will invoke it appropriately.
  464 
  465 The ternary "? :" operator is also handled using precedences.  ":" is one
  466 level higher than "?", so when a valid a?b:c is parsed the ":" finds a "?"
  467 on the control stack.  It's a parse error for ":" to find anything else.
  468 
  469 
  470 
  471 FUTURE
  472 
  473 The ternary "?:" operator evaluates the "false" side of its pair, which is
  474 wasteful, though it ought to be harmless.  It'd be better if it could
  475 evaluate only the "true" side.  Similarly for the logical booleans "&&" and
  476 "||" if they know their result already.
  477 
  478 Functions like MPEXPR_TYPE_BINARY could return a status indicating operand
  479 out of range or whatever, to get an error back through mpz_expr etc.  That
  480 would want to be just an option, since plain mpz_add etc have no such
  481 return.
  482 
  483 Could have assignments like "a = b*c" modifying the input variables.
  484 Assignment could be an operator attribute, making it expect an lvalue.
  485 There would want to be a standard table without assignments available
  486 though, so user input could be safely parsed.
  487 
  488 The closing parenthesis table entry could specify the type of open paren it
  489 expects, so that "(" and ")" could match and "[" and "]" match but not a
  490 mixture of the two.  Currently "[" and "]" can be added, but there's no
  491 error on writing a mixed expression like "2*(3+4]".  Maybe also there could
  492 be a way to say that functions can only be written with one or the other
  493 style of parens.
  494 
  495 
  496 
  497 ----------------
  498 Local variables:
  499 mode: text
  500 fill-column: 76
  501 End: