Many of the algorithms in this book manipulate representations of functions. We extend the standard definition of function on sets to include functions on variables. A factor is a representation of a function. An array is an explicit representation of a function that can have its individual components modified.

If $S$ is a set, we write $f(S)$ to be a function, with domain $S$. Thus, if $c\in S$, then $f(c)$ is a value in the range of $f$. $f[S]$ is like $f(S)$, but individual components can be updated. This notation is based on that of Python, C and Java (but C and Java only allow $S$ to be the set of integers $\{0,\mathrm{\dots },n-1\}$ for arrays of size $n$). Thus $f[c]$ is a value in the range of $f$. If $f[c]$ is assigned a new value, it will return that new value.

This notation can be extended to (algebraic) variables. If $X$ is an algebraic variable with domain $D$, then $f(X)$ is a function that given a value $x\in D$, returns a value in the range of $f$. This value is often written as $f(X=x)$ or simply as $f(x)$. Similarly, $f[X]$ is an array indexed by $X$, that is, it is a function of $X$ whose components can be modified.

This notation can also be extended to set of variables. $f(X_1,X_2,\mathrm{\dots },X_n)$ is a function such that given a value $v_1$ for $X_1$, a value $v_2$ for $X_2$, …, and a value $v_n$ for $X_n$ returns a value in the range of $f$. Note that it is the name of the variable that is important, not the position. This factor applied to the specific values is written as $f(X_1=v_1,X_2=v_2,\mathrm{\dots },X_n=v_n)$. The set of variables, $X_1,X_2,\mathrm{\dots },X_n$ is called the scope of $f$. The array $f[X_1,X_2,\mathrm{\dots },X_n]$ is a function on $X_1,X_2,\mathrm{\dots },X_n$ where the values can be updated.

Assigning just some of the variables gives a function on the remaining variables. Thus, for example, if $f$ is a function with scope $X_1,X_2,\mathrm{\dots },X_n$, then $f(X_1=v_1)$ is a function of $X_2,\mathrm{\dots },X_n$, such that

Factors can be added, multiplied or composed with any other operation level on the elements. If $f_1$ and $f_2$ are factors, then $f_1+f_2$ is a factor with scope the union of the scopes of $f_1$ and $f_2$, defined pointwise:

where we assume that $f_1$ and $f_2$ ignore variables not in their scope. Multiplication and other binary operators work similarly.

Other operations on factors are defined in the book.