---
name: "induce"
section: "1"
platform: "linux"
package: "saml"
version: "970418-9"
release: "Debian 3.0 (Woody)"
platforms: ["linux"]
url: "https://new.carta.tech/induce"
---

# induce(1)

symbolic spreadsheet

## 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)](/m4/1.md), 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 *iexpr*s (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 *iexpr*s (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)](/m4/1.md) 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)](/m4/1.md) 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)](/m4/1.md) 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)](/gdbm/3.md) 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)](/gdbm/3.md). Perhaps there should be a read-only access mode for memos.

## SEE ALSO

[**gdbm**(3)](/gdbm/3.md), [**m4**(1)](/m4/1.md), [**samuel**(1)](/samuel/1.md), [**saml**(3)](/saml/3.md)

## AUTHOR

Thierry Bousch (bousch@topo.math.u-psud.fr)