Straight-line Programs
A straight-line program (SLP) is a representation of a computation
involving the operations : + , - , * , - and ^.
An SLP is a directed acyclic graph in which the interior nodes
represent these arithmetic computations and the leaf nodes
represent variables or numbers over which the computations are
carried out. Each internal node has out-degree 2, i.e. points to
two children which represent the operands of the operator
represented by the node.
Evaluation of SLP's : A basic operation for an SLP is evaluating it at (random) values of the input variables. This operation is used, for example, when interpolating an SLP. To do this efficiently, an SLP node has to store the value during a given evaluation. To determine if the value stored in the SLP node is current, we need a flag (an int value) which will indicate when the last evaluation was done; this flag will be compared with a global variable Slp::Eval_level and if the flag is found to be not equal to it, the node will be re-evaluated and its flag updated to the value of Slp::Eval_level. Otherwise, the value of the node will be current.