.\" Copyright 1995,96 Thierry Bousch
.\" Licensed under the Gnu Public License, Version 2
.\"
.\" $Id: induce.1,v 2.2 1996/06/30 13:33:54 bousch Exp $
.\"
.TH INDUCE 1 "June 1996" "SAML"

.SH NAME
induce \- symbolic spreadsheet

.SH SYNOPSIS
.B induce
.RI [ options ]
.IR nodes ...

.SH DESCRIPTION
\fBinduce\fR is an interpreter for a purely declarative programming
language, without variables and loops. It consists of \fInodes\fR
related with \fIrules\fR. A \fInode\fR is an \fIidentifier\fR 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
\fIidentifier\fR (any sequence of letters, digits, and underscores, the
first character being a non-digit) before the brackets is called the
\fIrootname\fR, and the number of indices is the \fIarity\fR of the
node.
.PP
Each \fInode\fR has a value which is determined by user-supplied
\fIrules\fR; these rules are provided in a rules-file, which can be
preprocessed through \fBm4\fR(1), or on standard input. This file
contains semicolon-terminated instructions, which can be either:
.TP
.BI "precious \(lq" filename "\(rq " rootname ( arity ")\fR..."
Such a directive indicates that \fInodes\fR with this \fIrootname\fR and
this \fIarity\fR should be memoized across invocations of \fBinduce\fR.
The \fIfilename\fR is the name of the gdbm file where data should be
saved; if omitted, a default filename will be chosen. Multiple
.IB rootname ( arity )
pairs can appear in a single \fBprecious\fR directive, separated by commas.
.TP
.IB rootname [ indices "] = " expr " if " iexpr "\fR..."
This is a \fIrule\fR: 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 \fIiexpr\fRs
(index-expressions) depending on the \fIindices\fR 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.

.SS The left-hand Side
The left-hand side of a \fIrule\fR 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 \fIiexpr\fRs (index
expressions) depending on the previous indices. For instance, the rule
.nf

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

.fi
is equivalent to
.nf

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

.fi
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).

.SS Index-Expressions
An \fIiexpr\fR 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 \fIiexpr\fR can be any of:
.TP
.I index
A formal index, defined in the left-hand side of the rule.
.TP
.I integer
Any sequence of digits whose (non-negative) value doesn't exceed INT_MAX,
usually 2^31\-1.
.TP
.BI ( iexpr )
Returns the value of \fIiexpr\fR.
.TP
.I iexpr bop iexpr
Where \fIbop\fR can be any of `\fB+\fR' (addition), `\fB\-\fR'
(substraction), `\fB*\fR' or `\fB.\fR' (multiplication), `\fB/\fR'
(division), `\fB%\fR' (modulo). The division has a few features. It
never fails, but assumes that \fIa\fR/0==0 and \fIa\fR%0==\fIa\fR for
all \fIa\fR. If \fIb\fR is not zero, then \fIa\fR/\fIb\fR is truncated
(if necessary) to its floor; therefore, the remainder \fIa\fR%\fIb\fR
has the same sign as \fIb\fR.
.TP
.I uop iexpr
Where \fIuop\fR can be `\fB+\fR', `\fB\-\fR' or `\fB!\fR'. The
exclamation point is the negation operator: it returns one if
\fIiexpr\fR=0, and zero otherwise.
.TP
.I iexpr test iexpr
Where \fItest\fR can be any of `\fB=\fR' or `\fB==\fR' (equal),
`\fB!=\fR' (not equal), `\fB>\fR' (greater than), `\fB<\fR' (less than),
`\fB>=\fR' (greater or equal), `\fB<=\fR' (less or equal). Returns one
if the condition is true, zero otherwise.
.TP
.IB iexpr ^ integer
Raises the \fIiexpr\fR to the given exponent, with the convention that
anything^0 is 1.
.TP
.IB function ( iexpr ", " iexpr\fR... )
A \fIfunction\fR can be any identifier; the arguments are evaluated, and
are passed as command-line arguments to the external program called
`fn_\fIfunction\fR' (it must be in your path). The output of the program is
then read and parsed, and some value is returned.

.SS Expressions
Unlike an \fIiexpr\fR, an \fIexpr\fR represents an algebraic expression;
unless the \fB\-p\fR 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 \fIexpr\fR can be any of:
.TP
.I index
An index will be converted to a constant polynomial. In fact, this is only
syntactic sugar for `__value__[\fIindex\fR]'. There is one builtin rule in
\fBinduce\fR, 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.
.TP
.I big_integer
Any sequence of digits; it can be as big as you want, and it won't be
truncated.
.TP
.IB rootname [ iexpr ", " iexpr\fR... ]
The indices (if any) are evaluated, and the value of the corresponding
node is returned.
.TP
.I expr bop expr
The operation \fIbop\fR can be `\fB+\fR' (plus), `\fB\-\fR' (minus),
`\fB.\fR' or `\fB*\fR' (times), or `\fB/\fR' (divide).
.TP
.I uop expr
The unary operator \fIuop\fR can be `\fB+\fR', `\fB\-\fR' or `\fB!\fR'.
.TP
.IB expr ^ integer
Raises the \fIexpr\fR to the given exponent, with the convention
that anything^0 is 1.
.TP
.BI ( expr ", " subst ", " subst\fR... )
Applies a list of substitutions to \fIexpr\fR. Each substitution has the
form `\fIunary to expr\fR', where \fIunary\fR is any expression which
evaluates to a unary monomial, and \fIto\fR is either `\fB\->\fR' for a
simple substitution, or `\fB>>\fR' 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.
.TP
.IB expr : elit
Differentiates \fIexpr\fR with respect to \fIelit\fR, where \fIelit\fR is
any expression which evaluates to a literal.
.TP
.BI ~ elit ( expr , expr )
Returns the resultant of the two polynomials with respect to \fIelit\fR;
this can be used to eliminate a literal between two equations.
.TP
.IB function ( expr ", " expr\fR... )
A \fIfunction\fR can be any identifier; the arguments are evaluated, and
are passed as command-line arguments to the external program called
`fn_\fIfunction\fR' (it must be in your path). The output of the program is
then read and parsed, and some value is returned.

.SS 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.

.SH OPTIONS
The following options are recognized:
.TP
.BR \-D ", " \-\-define "\fI symbol\fR[" "=\fIvalue" ]
Defines a preprocessor symbol; this option will be passed to \fBm4\fR(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).
.TP
.BR \-e ", " \-\-enter "\fI 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
\fB\-f\fR option if present.
.TP
.BR \-f ", " \-\-file "\fI name"
Specifies where \fBinduce\fR should read its rules from; the \fIname\fR
can be `\fI\-\fR' to indicate standard input. This option will always be
overridden by the \fB\-e\fR option. If neither \fB\-f\fR nor \fB\-e\fR
appears, \fBinduce\fR will search the file-list indicated in the
environment variable \fBINDUCEFILES\fR. 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 \fBm4\fR(1) iff the last three characters of the
filename are `\fB.m4\fR'.
.TP
.BR \-m ", " \-\-memo "\fI name"
Specifies another default memo file. This option has precedence over the
\fBINDUCEMEMO\fR environment variable. The filename `\fI-\fR' 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
\fBinduce\fR is used as a filter, as it allows memoizing between
successive lines of input.
.TP
.BR \-n ", " \-\-nice "\fI adjust"
Adds \fIadjust\fR to the niceness of the process (symbolic calculations
can be very CPU-intensive).
.TP
.BR \-p ", " \-\-precision "\fI blocks"
The default behaviour of \fBinduce\fR
is to consider all expressions as polynomials with rational coefficients.
If this option is specified, with \fIblocks\fR
a power of two, \fBinduce\fR
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.
.TP
.B \-\-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.
.TP
.B \-\-dense
Select a representation of polynomials optimized for a dense set of
literals. This is the default when the environment variable \fBLITERALS\fR
is unset.
.TP
.BR \-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.
.TP
.BR \-v ", " \-\-verbose
Verbose mode. This is the default mode when stdout is a tty.
.TP
.B \-\-help
Displays a usage summary on standard output, and exits successfully.
.TP
.B \-\-version
Displays the version number on standard output, and exits successfully.
This manpage documents version 0.42 of \fBinduce\fR.
.PP
If there are remaining (i.e., non-option) arguments on the command line,
they will be interpreted as node names and evaluated. Otherwise,
\fBinduce\fR will read the node names from standard input. In both
cases, \fBinduce\fR will check that the names are syntactically correct.
If standard input is used, \fBinduce\fR will read it line after line;
each line should contain zero or more nodenames, separated with
whitespace, and \fBinduce\fR 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
\fBprecious\fR directive, perhaps combined with \fB\-m\-\fR if you don't
want memoizing across successive invocations of \fBinduce\fR.

.SH ENVIRONMENT
These environment variables are relevant to \fBinduce\fR:
.TP
.B HOME
The home directory is used for tilde expansion.
.TP
.B INDUCEFILES
A colon-separated list of filenames locating the rules-file. Can be
overridden with the \fB\-f\fR or \fB\-e\fR options. If undefined, a
default search path is used (see below).
.TP
.B INDUCEMEMO
The filename locating the default memo-file. Can be overridden with the
\fB\-m\fR option.
.TP
.B LITERALS
Select the most appropriate representation of polynomials; allowed
values are \fIsparse\fR and \fIdense\fR. If undefined, it defaults to
"dense". This variable can be overridden by the \fB\-\-sparse\fR and
\fB\-\-dense\fR command-line options; in this case, the new value will
be exported into the environment, so that subprocesses may take
advantage of it.
.TP
.B PATH
This variable is used to execute external functions.

.SH FILES
Note that tilde expansion is automatically performed on all pathnames
beginning with a tilde and slash. Here are the files relevant to \fBinduce\fR:
.TP
.I /usr/bin/m4
The \fBm4\fR(1) macro processor.
.TP
.I /some/path/to/fn_????
External functions. For each function \fIname\fR there must be an
executable called \fIfn_name\fR somewhere in your \fBPATH\fR. These
programs are supposed to read their arguments from the command line and
return their result on standard output.
.PP
.I Inducefile
.br
.I Inducefile.m4
.br
.I ~/.inducefile
.br
.I ~/.inducefile.m4
.RS
Default search path for the rules-file. Can be overridden with the
\fBINDUCEFILES\fR environment variable, or the \fB\-f\fR and \fB\-e\fR
options.
.RE
.TP
.I ~/.common-memo.gdbm
The default name of the memo database in \fBgdbm\fR(3) format. This is
where precious objects are saved when no file is specified.
Can be overridden with the \fBINDUCEMEMO\fR environment variable or the
\fB\-m\fR option.
.TP
.IR /tmp
Various temporary files are created in this directory (and automatically
removed, of course).

.SH "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.

.SH 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 \fBinduce\fR at a time.
This is really a restriction of \fBgdbm\fR(3). Perhaps there should be a
read-only access mode for memos.

.SH "SEE ALSO"
\fBgdbm\fR(3), \fBm4\fR(1), \fBsamuel\fR(1), \fBsaml\fR(3)

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