Formulc

A byte-compiler for mathematical functions

Version 2.22

by Harald Helfgott

Copying

The following short explanation of the Library General Public License is essentially the same as that in the TeXinfo 2.16 distribution.

Formulc is free; this means that everyone is free to use it and free to redistribute it on a free basis. Formulc is not in the public domain; it is copyrighted and there are restrictions on its distribution, but these restrictions are designed to permit everything that a good cooperating citizen would want to do. What is not allowed is to try to prevent others from further sharing any version of these programs that they might get from you.

Specifically, I want to make sure that you have the right to give away copies of Formulc, that you receive source code or else can get it if you want it, that you can change Formulc or use pieces of it in new free programs, and that you know you can do these things.

To make sure that everyone has such rights, I have to forbid you to deprive anyone else of these rights. For example, if you distribute copies of Formulc, you must give the recipients all the rights that you have. You must make sure that they, too, receive or can get the source code. And you must tell them their rights.

Also, for my own protection, I must make certain that everyone finds out that there is no warranty for the programs that relate to Formulc. If these programs are modified by someone else and passed on, I want their recipients to know that what they have is not what I distributed, so that any problems introduced by others will not reflect on my reputation.

The precise conditions of the license for Formulc are found in the GNU Library General Public License accompanying it. Linking Formulc to non-free programs is allowed.

Overview

It is very frustrating that there is nothing in the standard C and C++ libraries for evaluating mathematical functions at running time. Crafting a small interpreter on one's own is not very difficult, but a standard set of routines would save much time to many people. There are already a few freely available C programs that parse mathematical expressions. Unfortunately, all such programs I have seen are too slow for numerically intensive work.

Formulc is a byte-compiler for mathematical functions. In other words, given a string representing a function, Formulc translates it into a postfix representation designed to minimize execution time. The Formulc routines use this representation instead of the original string whenever the function has to be evaluated at any point. Formulc's byte-compiler design makes for a far greater speed than that of a simple interpreter.

Filter

Compilation
```
make formulc
```

Usage

formulc [-xtal] [-d"x"] "function(s)" "arguments" ["c-format"|@# ...] [file]

Example

formulc -xtal "x+1/4, y-1/4, z+1/4" .xyz @1 " %8.5f" xtal.inp

General behavior The input is read line by line and separated into fields. The fields are delimited by white-spaces (space, tab, vertical-tab, or form-feed). Each input line which causes an error is simply echoed. No other error diagnostics are given.
Command line arguments
- -xtal "Crystallographic mode": Normalize results of evaluations, i.e., compute results modulo 1, so that all output values are in the interval "[0...1[". Feature: Input values have to be in the interval "[-2...2]". If one of the input values is out of range, the input line will just be echoed.
- -d"x" With -xtal, the function-delimiter defaults to ",". Otherwise there is no delimiter defined.
- "function(s)" One or more algebraic functions. Functions are separated by the character defined with -d.
- "arguments" Variable name definitions and mappings. Legal variables names are "a"-"z". All variable names are mapped to lower case, i.e., "A" = "a". The first character maps the first field in the input line to the corresponding variable, the next character to the next variable, and so on. Any character but "a"-"z" (and "A"-"Z") is a signal that the input field at that position is to be ignored. Thus, ".xyz" means: Ignore the first field of all input lines, take the value for "x" from the first, for "y" from the second, and for "z" from the third field, respectively.
- ["c-format"|@# ...] Any sequence of legal C output format strings for the "double" results of the functions, and "@#" input-field-echo commands. The first c-format in the list will be used to print the result of the first function, the second for the second function, and so on. If there are more functions than c-formats, the last c-format is used to print all of the remaining results. @ echoes the whole input line. @n echoes the n'th input field. n is a positive integer. @n-m echoes input fields n through m. @-m echoes the input fields up to and including m. Whitespaces preceding the first input field are preserved. @n- echoes the input fields starting with field n up to the end of the line.
- file Input file name. If no input file is specified, the input is read from stdin. The STAND_ALONE front-end for Formulc was written by Ralf W. Grosse-Kunstleve (rwgk@laplace.csb.yale.edu).

Routines

Type

make formulc

to obtain the object file formulc.o (as well as the stand-alone Formulc).

If you do not want to use the random number generator provided with Formulc, compile formumr.o with

make formumr.o

You should then link formumr.o with your random number generator and with your own program.

Evaluation
```
formu translate(char *source, char *args, int *length, int *error);
```
Examples:
```
formu f,g;
int leng;
int error;

f = translate("x^2 + sin(3*x) + 0.1", "x", &leng, &error);

f = translate("1E+5 * x/x \n", "x", &leng, &error);

gets(gsource);
g=translate(gsource, "xyz", &length, &error);
    /* g is a function of x, y and z */
```
This function transforms a mathematical function in the usual representation (char *source) into a data structure containing the function in precompiled form (the return value, of type formu). The arguments of source (x,y,z,etc.) are in string arg[]. They must be lowercase letters. If any error occurs, translate will return empty code (see fnot_empty()), *length will have the value 0, and *error will be the index of the character in source[] that caused the error. (The user is strongly recommended to detect errors through *error instead of *length. *length is returned only for the sake of compatibility with older versions, and might be removed in the future.) The result string is dynamically allocated. The user can deallocate the space by calling destrf(). The syntax of source is as follows (in Extended Backus-Naur Form):
```
source = expression "\0"
expression = [-] summand {("+" | "-") summand}
summand = factor {("*" | "/") factor}
   /*Please, don't forget "*" ! */
factor = base {"^" base}
base = "(" expression ")" | function "(" expression ")" |
        function "(" expression "," expression ")" |
function "(" expression "," expression "," expression ")" |
                 number | parameter
function = a string in the function table
parameter = a lower-case letter mentioned by arg[]
number = any nonnegative number  /* the sign is considered in
                                    the definition of expression */
                        /* please write 3.5E-3, not 3.5e-3 */
```
This description of the syntax mimics the algorithm in translate(). Please notice that -3+5*6 and 3+5*(-6) are allowed, but 3+5*-6 and 3+-5*6 are not. Also notice that functions without parameters (such as pi()) must still be followed by parentheses. White space is ignored. Precedence:
```
parentheses, function
power
unary minus
* /
+ -
```
If all operands are constants, translate() executes fval() to evaluate the expression at "compile time". (The inbuilt random-number generator is tagged so as not to be called at compile time. Other functions can also be thus tagged.) The standard functions are:
```
exp()
ln()
sin()
cos()
tan()
asin()
acos()
atan()
atan2()
abs()
pi() (without parameters inside the parentheses)
sqrt()
rnd()
```
One can add new functions by using fnew(). The names of the new functions must obey the same rules as names of C functions: the first character of a name must be a letter, and following characters can be either letters or numbers.
```
double fval(formu function, char *args, ...);
```
Example:
```
function=translate("x^2+sin(cos(x))","x", &leng, &error);
result=fval(f,"x",3.0);  /* 3.0, not 3 */
/* returns 3^2+sin(cos(3)) */

g=translate("n*m","nm", &leng, &error);
for(p=0; p<100; p++)
 for(q=0; q<1000; q++)
  a[p][q]=fval(g,"nm",(double) p,(double) q);
/* the arguments must always be double */
```
fval() calculates the value of formu function when the parameters listed in char *args have the given values. If fval attempts any invalid arithmetical operations (division by zero, extracting a square root of a negative number), errno is EDOM (domain error) or ERANGE (range error) and/or the result is Infinity or Not-A-Number, depending on the platform.
```
double f_x_val(formu function, double x);
```
Example:
```
result=f_x_val(f,3); /* calculates f(3) if f is a function of x */
```
A shorthand version of fval() for functions on x. It is about as fast as fval().
```
double fval_at(formu function);
void make_var(char var, double value);
```
This is the interface for the evaluation of functions whose number of parameters is determined at run-time. Example:
```
make_var('x',2);
make_var('y',0.2);
make_var('z',-2);
result=fval_at(f);
/* evaluates f(x,y,z) at point x=2, y=0.2, z=-2 */
```
Management of the Function Library
```
int fnew(char *name, Func f, int n_pars, int varying);
```
Examples:
```
fnew("sinh",(Func) sinh,1,0);  /* sinh has been declared as
                                  double sinh(double); */
fnew("logb",(Func) logb,2,0);  /* logb has been declared as
                                  double logb(double, double); */
fnew("rnd", (Func) rnd, 0,1);  /* varying = 1 because the result
                                  of rnd is not determined
                                  by its parameters. */
```
fnew() adds a user-defined C function with double parameters to the library of Formulc. The C function can have from 0 to 3 parameters. fnew() returns 0 if the library is full (255 functions) or if some other error occurs. Otherwise, it returns 1. Do not call any function 'E'.
```
int read_table(int i, char *name, int *n_of_pars, int *varying);
```
Example:
```
i=0;
while(read_table(i++, name, &n_pars, &varying)
    printf("%s %d",name,n_pars);
```
read_table() copies the name, the number of parameters and the non-determinism bit of function #i onto name[], *n_of_pars and *varying. If function #i does not exist, read_table() returns 0. Otherwise, it returns a positive number.
```
int where_table(char *name);
```
Example:
```
if(where_table("sinh") == -1)
 printf("Hyperbolic sine not defined.");
```
If there is a mathematical function called name[], where_table() returns its index in the table of functions. Otherwise where_table() returns -1. Use fnew to register functions which are not in Formulc's standard library.
```
int fdel(char *name);
```
Example:
```
if(where_table("sinh" != -1)
 fdel("sinh");
```
If there is a mathematical function called name[], fdel() deletes it. If fdel() is successful, it returns a non-negative number. Otherwise, it returns -1.
Random-Number Generation The standard library of Formulc includes double rnd(void). Any program that generates random numbers through Formulc must call
```
void rnd_init(void);
```
first. By default, Formulc uses the random-number generator r250() (written by W. L. Maier, S. Kirkpatrick and E. Stoll). If you want to use another RNG, you must define functions according to the declarations
```
double rnd(void);
void rnd_init(void);
```
Furthermore, you must compile formulc with
```
make myrnd
```
as stated at the beginning of this section.
Miscellaneous
```
void destrf(formu f);
```
frees memory occupied by f.
```
void make_empty(formu f);
```
makes f an empty function. Note that this function should not to be used as a destructor, as it does not deallocate any memory. You should use destrf() for this purpose.
```
int fnot_empty(formu f);
```
returns 1 if f is not an empty function; returns 0 otherwise.
```
const char *fget_error(void);
```
Every routine in Formulc gives an error message if it fails and erases the previous error message from memory if it succeeds. fget_error() renders an error string if the last routine failed; otherwise, it returns NULL. The only routine that does not alter the error message is fget_error() itself. Usually, error messages are self-explanatory. If you ever see an error message that begins with I1, I2 or I3, please send tell me (hhelf@cs.brandeis.edu). You should never see such a thing.

History

On May 1993, a mathematics professor in Lima, Peru asked me whether I could write a fast formula interpreter. His program needed to compute functions entered by the user hundreds of thousands of times. I decided, therefore, to write a two-stage interpreter. A two-stage interpreter is at a middle point between a compiler and an interpreter: it is system-independent and easily linkable, just like a good interpreter, but the speed of the code it produces is close to the speed of compiled code.

The first version of Formulc to be distributed through the INTERNET was v2.1. Formulc v2.1 could not run in some computers, and lacked a UNIX-filter front end. Thanks to the feedback of several users, I was able to eliminate these two defects.

The main difference between Formulc 2.2 and Formulc 2.22 is that the newer version can be distributed freely under the GNU Library General Public License. No changes have been made to the UNIX front-end or to the behaviour of the C routines.

I have been considering changing both the Formulc front-end and the declarations of the Formulc routines so as to make them more SCHEME-like. In particular, I would like to make the names of the variables be declared only at byte-compilation time, so as to These changes would allow me to make both the code and the interface more elegant. On the other hand, they would obligue all those who have used Formulc until now to change their code. There would be no increase or decrease in efficiency. Please send me e-mail with your opinion, if you have one. My address as of February 1998 is:

Harald Helfgott
MB 1807 Brandeis University
Waltham, MA 02254-9110
U.S.A.
hhelf@cs.brandeis.edu

Acknowledgements

I thank all users who have proposed, or actually implemented, improvements to Formulc. I am especially grateful to Ralf Groesse-Kunstleve (rwgk@laplace.csb.yale.edu) for having written the command-line front end.