induce(1) · carta

NAME

induce - symbolic spreadsheet

SYNOPSIS

induce [options] nodes...

DESCRIPTION

induce is an interpreter for a purely declarative programming language, without variables and loops. It consists of nodes related with rules. A node is an identifier followed by an arbitrary number of indices (maybe zero), where each index is a signed machine integer, usually 32-bit wide. The indices are written as a comma-separated list between brackets. If there are several such lists, they are catenated; for instance, `foo[-1,+04][][-0]' is a valid node, equivalent to `foo[-1,4,0]' (its canonic form). The identifier (any sequence of letters, digits, and underscores, the first character being a non-digit) before the brackets is called the rootname, and the number of indices is the arity of the node.

Each node has a value which is determined by user-supplied rules; these rules are provided in a rules-file, which can be preprocessed through m4(1), or on standard input. This file contains semicolon-terminated instructions, which can be either:

precious “filename” rootname(arity)...: Such a directive indicates that nodes with this rootname and this arity should be memoized across invocations of induce. The filename is the name of the gdbm file where data should be saved; if omitted, a default filename will be chosen. Multiple rootname(arity) pairs can appear in a single precious directive, separated by commas.

rootname[indices] = expr if iexpr...

This is a rule: it defines the left-hand side to be equal to the expression on the right, provided that some list of conditions is verified. The "if ..." part can be omitted if the rule is unconditionally true; if there are several conditions, they should be comma-separated. The conditions can be arbitrary iexprs (index-expressions) depending on the indices on the left-hand side.

If several valid rules define the same node, only the first one will be used. If there is none, the node is assumed to be a literal.

The left-hand Side

The left-hand side of a rule consists of a rootname, optionally followed by a comma-separated list of formal indices between brackets (or several of them). The indices can be either identifiers, or iexprs (index expressions) depending on the previous indices. For instance, the rule

    foo[i,i+1,5] = bar[4.i+3] if i>0;

is equivalent to

    foo[i,j,k] = bar[4.i+3] if j=i+1, k=5, i>0;

but is clearer to read, and doesn't clobber the namespace of the right-hand side with additional identifiers (any identifier appearing as a formal index on the left-hand side cannot appear as a rootname in the right-hand side).

Index-Expressions

An iexpr is an expression which can appear as an index. This includes small constants, and the formal indices of the left-hand side of the rule. They can also appear as conditions, in this case non-zero means true. All these expressions are computed with machine integers, so they can easily overflow. An iexpr can be any of:

index: A formal index, defined in the left-hand side of the rule.

integer: Any sequence of digits whose (non-negative) value doesn't exceed INT_MAX, usually 2^31-1.

(iexpr): Returns the value of iexpr.

iexpr bop iexpr: Where bop can be any of `+' (addition), `-' (substraction), `*' or `.' (multiplication), `/' (division), `%' (modulo). The division has a few features. It never fails, but assumes that a/0==0 and a%0==a for all a. If b is not zero, then a/b is truncated (if necessary) to its floor; therefore, the remainder a%b has the same sign as b.

uop iexpr: Where uop can be `+', `-' or `!'. The exclamation point is the negation operator: it returns one if iexpr=0, and zero otherwise.

iexpr test iexpr: Where test can be any of `=' or `==' (equal), `!=' (not equal), `>' (greater than), `<' (less than), `>=' (greater or equal), `<=' (less or equal). Returns one if the condition is true, zero otherwise.

iexpr^integer: Raises the iexpr to the given exponent, with the convention that anything^0 is 1.

function(iexpr, iexpr...): A function can be any identifier; the arguments are evaluated, and are passed as command-line arguments to the external program called `fn_function' (it must be in your path). The output of the program is then read and parsed, and some value is returned.

Expressions

Unlike an iexpr, an expr represents an algebraic expression; unless the -p option is given, it is a polynomial with rational coefficients. There is no modulo operator, nor tests, since the flow of control is entirely determined by the dependencies, and dependencies only depend on index-expressions. On the other hand, there are some polynomial-specific operations: substitution (simple or repeated), derivation and elimination. More precisely, an expr can be any of:

index: An index will be converted to a constant polynomial. In fact, this is only syntactic sugar for `__value__[index]'. There is one builtin rule in induce, which says that `__value__[i]' should return the value of its index. This builtin rule can be interesting for performance reasons, for instance __value__[i^2] is equivalent to i^2, but in the first case we square a machine integer instead of a multivariate polynomial. It's probably faster, but it will overflow for moderately big values of i.

big_integer: Any sequence of digits; it can be as big as you want, and it won't be truncated.

rootname[iexpr, iexpr...]: The indices (if any) are evaluated, and the value of the corresponding node is returned.

expr bop expr: The operation bop can be `+' (plus), `-' (minus), `.' or `*' (times), or `/' (divide).

uop expr: The unary operator uop can be `+', `-' or `!'.

expr^integer: Raises the expr to the given exponent, with the convention that anything^0 is 1.

(expr, subst, subst...): Applies a list of substitutions to expr. Each substitution has the form `unary to expr', where unary is any expression which evaluates to a unary monomial, and to is either `->' for a simple substitution, or `>>' for a repeated substitution (we apply it until we reach a fixed point); for instance `x^2.y -> (x-z)*2' is a valid substitution. The list of substitutions can be empty, in this case you simply get the value of the parenthesised expression.

expr:elit: Differentiates expr with respect to elit, where elit is any expression which evaluates to a literal.

~elit(expr,expr): Returns the resultant of the two polynomials with respect to elit; this can be used to eliminate a literal between two equations.

function(expr, expr...): A function can be any identifier; the arguments are evaluated, and are passed as command-line arguments to the external program called `fn_function' (it must be in your path). The output of the program is then read and parsed, and some value is returned.

Precedence of Operators

Operators have the same precedence in index-expressions and normal (algebraic) expressions, and are evaluated from left to right. The operators of highest precedence are the caret (power) and colon (derivation). They are followed by the three unary operators (plus, minus, negate). After them come the binary multiplication, division, and modulo. Then, come the binary addition and substraction. And finally, the test operators.

OPTIONS

The following options are recognized:

-D, --define symbol[=value]: Defines a preprocessor symbol; this option will be passed to m4(1) without modification. This option can be repeated, in order to define several symbols. It won't have any effect if the rules file is not preprocessed (as determined by the file extension, see below).

-e, --enter text: This option allows you to enter the rules on the command line, instead of putting them into a file. This option can be repeated. It will override the -f option if present.

-f, --file name: Specifies where induce should read its rules from; the name can be `-' to indicate standard input. This option will always be overridden by the -e option. If neither -f nor -e appears, induce will search the file-list indicated in the environment variable INDUCEFILES. If this variable doesn't exist, a default search list will be used (see below). Once the file is found (it is a fatal error if none can be found), it will be preprocessed through m4(1) iff the last three characters of the filename are `.m4'.

-m, --memo name: Specifies another default memo file. This option has precedence over the INDUCEMEMO environment variable. The filename `-' has special significance: it means that the memo is temporary and should be removed from the filesystem as soon as possible. It can be useful when induce is used as a filter, as it allows memoizing between successive lines of input.

-n, --nice adjust: Adds adjust to the niceness of the process (symbolic calculations can be very CPU-intensive).

-p, --precision blocks: The default behaviour of induce is to consider all expressions as polynomials with rational coefficients. If this option is specified, with blocks a power of two, induce will consider all expressions as real numbers, whose precision in 16-bit blocks is the given number. In particular, literals are no longer allowed (at least in the current version) and will cause type errors. Sorry, but it's rather clumsy to handle polynomials with real coefficients.

--sparse: Select a representation of polynomials optimized for a sparse set of literals. In some cases it can be a win, but usually it's slower and more memory-consuming than the dense representation.

--dense: Select a representation of polynomials optimized for a dense set of literals. This is the default when the environment variable LITERALS is unset.

-q, --quiet: Quiet mode; only errors are reported to stderr, normal informative messages are discarded. This is the default mode when stdout isn't a tty.

-v, --verbose: Verbose mode. This is the default mode when stdout is a tty.

--help: Displays a usage summary on standard output, and exits successfully.

--version: Displays the version number on standard output, and exits successfully. This manpage documents version 0.42 of induce.

If there are remaining (i.e., non-option) arguments on the command line, they will be interpreted as node names and evaluated. Otherwise, induce will read the node names from standard input. In both cases, induce will check that the names are syntactically correct. If standard input is used, induce will read it line after line; each line should contain zero or more nodenames, separated with whitespace, and induce will return their values on one line, separated with tabs (at least in "quiet" mode). After a line has been fully evaluated, all the nodes are erased from memory, and the next line is processed. Thus, if you want memoizing across lines, you'll have to say it explicitly with the precious directive, perhaps combined with -m- if you don't want memoizing across successive invocations of induce.

ENVIRONMENT

These environment variables are relevant to induce:

HOME: The home directory is used for tilde expansion.

INDUCEFILES: A colon-separated list of filenames locating the rules-file. Can be overridden with the -f or -e options. If undefined, a default search path is used (see below).

INDUCEMEMO: The filename locating the default memo-file. Can be overridden with the -m option.

LITERALS: Select the most appropriate representation of polynomials; allowed values are sparse and dense. If undefined, it defaults to "dense". This variable can be overridden by the --sparse and --dense command-line options; in this case, the new value will be exported into the environment, so that subprocesses may take advantage of it.

PATH: This variable is used to execute external functions.

FILES

Note that tilde expansion is automatically performed on all pathnames beginning with a tilde and slash. Here are the files relevant to induce:

/usr/bin/m4: The m4(1) macro processor.

/some/path/to/fn_????: External functions. For each function name there must be an executable called fn_name somewhere in your PATH. These programs are supposed to read their arguments from the command line and return their result on standard output.

Inducefile
Inducefile.m4
~/.inducefile
~/.inducefile.m4

Default search path for the rules-file. Can be overridden with the INDUCEFILES environment variable, or the -f and -e options.

~/.common-memo.gdbm: The default name of the memo database in gdbm(3) format. This is where precious objects are saved when no file is specified. Can be overridden with the INDUCEMEMO environment variable or the -m option.

/tmp: Various temporary files are created in this directory (and automatically removed, of course).

EXIT CODE

Non-zero if an error is detected. Detected errors include: invalid options on the command line, invalid variable names, syntax errors in the "rules" file, cyclic dependencies, and overflowing of statically-allocated arrays. Run-time errors (like division by zero) are not reported.

BUGS

There are lots of static arrays in this program, and there are at least two places (for now) where the overflow is not tested. Let's hope that the limits are high enough. For example, the lexer will choke on tokens (numbers or identifiers) longer than 1023 bytes.

Memoizing is disabled on floating-point numbers. Maybe we could call this a feature?

It is not yet possible to handle other data types than reals and polynomials with rational coefficients (it's on the to-do list, though).

A memo file can be opened by at most one instance of induce at a time. This is really a restriction of gdbm(3). Perhaps there should be a read-only access mode for memos.

AUTHOR

Thierry Bousch ([email protected])