CodeTools[ProgramAnalysis] - Maple Programming Help

Home : Support : Online Help : Programming : CodeTools : Program Analysis : CodeTools/ProgramAnalysis/IterationSpace

CodeTools[ProgramAnalysis]

 IterationSpace
 relations on the index variables of a ForLoop

 Calling Sequence IterationSpace(loop)

Parameters

 loop - The ForLoop to be analyzed

Description

 • This command computes the iteration space of the ForLoop loop, which is the set of values for the indices into the arrays over all iterations of loop.  This set is represented as the integer solutions to a list of non-strict inequalities.  The relations are written in terms of the loop's index variables and parameters.
 • The returned system of inequalities has not been simplified and may represent an empty set for trivial loops.

Examples

 > $\mathrm{with}\left(\mathrm{CodeTools}\left[\mathrm{ProgramAnalysis}\right]\right):$

Example usage

Find the possible values of $\left(i,j\right)$ used by the given nested loop, as encoded by a list of inequalities:

 > p1 := proc(a, b, n)     local i, j;     for i from 1 to min(n + 2, 10) do         for j from i to n + 2 do             a[i, j] := b[i + 1] + a[i - 1, j - 1]         end do     end do end proc: loop1 := CreateLoop(p1): iteration_space1 := IterationSpace(loop1);
 ${\mathrm{iteration_space1}}{≔}\left[{1}{\le }{i}{,}{i}{\le }{10}{,}{i}{\le }{n}{+}{2}{,}{i}{\le }{j}{,}{j}{\le }{n}{+}{2}\right]$ (1)

Specifying a value for the parameter $n$, the integer solutions to the given list of inequalities can be computed:

 > $\mathrm{iteration_space1_2}≔\mathrm{subs}\left(n=2,\mathrm{iteration_space1}\right):$$\mathrm{isolve}\left(\mathrm{convert}\left(\mathrm{iteration_space1_2},\mathrm{set}\right)\right)$
 $\left\{{i}{=}{1}{,}{j}{=}{1}\right\}{,}\left\{{i}{=}{1}{,}{j}{=}{2}\right\}{,}\left\{{i}{=}{1}{,}{j}{=}{3}\right\}{,}\left\{{i}{=}{1}{,}{j}{=}{4}\right\}{,}\left\{{i}{=}{2}{,}{j}{=}{2}\right\}{,}\left\{{i}{=}{2}{,}{j}{=}{3}\right\}{,}\left\{{i}{=}{2}{,}{j}{=}{4}\right\}{,}\left\{{i}{=}{3}{,}{j}{=}{3}\right\}{,}\left\{{i}{=}{3}{,}{j}{=}{4}\right\}{,}\left\{{i}{=}{4}{,}{j}{=}{4}\right\}$ (2)

These solutions correspond to the values of the loop variables for which the loop's statements will be executed.  Note that the order of solutions returned by isolve will not necessarily match the order of the loop's execution.

Trivial Loop with an Empty Iteration Space

The body of the following loop will never be executed:

 > p2 := proc(a)     local i;     for i from 2 to 1 do         a[i] := a[i - 1]:     end do end proc: loop2 := CreateLoop(p2): iteration_space2 := IterationSpace(loop2);
 ${\mathrm{iteration_space2}}{≔}\left[{2}{\le }{i}{,}{i}{\le }{1}\right]$ (3)

Its iteration space is a list of infeasible inequalities, i.e. there are no solutions for $i$:

 > $\mathrm{simplex}\left[\mathrm{feasible}\right]\left(\mathrm{iteration_space2}\right)$
 ${\mathrm{false}}$ (4)

Compatibility

 • The CodeTools[ProgramAnalysis][IterationSpace] command was introduced in Maple 2016.
 • For more information on Maple 2016 changes, see Updates in Maple 2016.