|
Calling Sequence
|
|
CreateLoop(p)
|
|
Parameters
|
|
p
|
-
|
procedure with a loop
|
|
|
|
|
Description
|
|
•
|
This command processes the procedure p and returns either a ForLoop or a WhileLoop data structure, depending on p's form. Both for loops and while loops are represented in Maple using do statements. In this package, a for loop is understood to be a loop that iterates over some index variable(s), reading from and updating the entries of an indexable variable, i.e. an Array, Matrix, Vector or table. A while loop is a loop that recursively updates its loop variable(s) until its guard condition (while clause) is no longer satisfied.
|
|
For Loops
|
|
•
|
The procedures that can be converted to ForLoops have a particular structure. They consist of initialization statements, followed by a (possibly nested) for loop. More precisely, they can be defined as follows, where means "defined as", means "or", and means one or more of the enclosed:
|
•
|
In addition, the loop must have the following properties:
|
–
|
The assignments in the loop body must assign to indexable variables
|
–
|
The indices of the loop's arrays must be polynomials with rational coefficients
|
–
|
The loops' lower bounds / upper bounds must be linear in the loops' index variables , parameters and local variables , or the max/min of a sequence of such expressions, respectively. Optionally, the lower/upper bounds may have the ceil/floor function applied, respectively.
|
•
|
This command processes such procedures and returns a ForLoop data structure. This data structure is a Record with the following fields:
|
–
|
: list of the loop's index variables, one per layer of nested for loops
|
–
|
: list of indexable variables being read from or written to in the loop
|
–
|
: list of the parameters passed to the procedure p that are not in
|
–
|
: list of equations representing the assignments that occur before the loop
|
–
|
: listlist, one for each layer of for loop in p. Each inner list consists of four elements: the loop variable name, the lower bound, the step size and the upper bound.
|
–
|
: listlist, one entry for each if branch in the loop's body. The inner lists have two elements: the conditional expression for the branch of the if statement and a list of equations representing the branch's statement sequence.
|
|
|
While Loops
|
|
•
|
WhileLoops can be generated from procedures that have the following form:
|
•
|
In addition, the procedure must satisfy the following:
|
–
|
The WhileLoop cannot have any statements between the ASSERT statement for the pre-conditions and the do statement of the loop, or between the loop statement and the ASSERT statement for the post-conditions
|
–
|
The pre-conditions, post-conditions, branch conditions, and assignments to the loop variables must be polynomials with rational coefficients
|
•
|
A WhileLoop with only assignments inside the loop is equivalent to a loop with an if statement that only has an else clause.
|
•
|
The returned WhileLoop data structure has the following fields:
|
–
|
: list of the loop variables, i.e. variables updated in the loop.
|
–
|
: list of the procedure's parameters.
|
–
|
: list of initial values for the loop variables written in terms of the .
|
–
|
: conditional expression extracted from the ASSERT statements before the loop. These conditions are assumed to be true.
|
–
|
: conditional expression in the while clause of the do loop.
|
–
|
: listlist, one entry for each if branch in the loop's body. The inner lists have two elements: the conditional expression for the branch of the if statement and a list of values representing that branch's loop variable assignments. These are the updated values that the loop variables will receive on the next iteration. The loop variables may have been updated with sequential assignments in the original loop, but here they have been converted to one simultaneous assignment that is equivalent to a multiple assignment in Maple.
|
–
|
: conditional expression extracted from the ASSERT statements after the loop that may or may not hold after the loop's completion. The VerifyLoop is used to determine whether or not the will be satisfied.
|
–
|
: list of the procedure's return value(s). The procedure's return value are the operands of .
|
•
|
The conditional expressions in the WhileLoop data structure represent boolean by using a list of elements to signify their disjunction and a set of elements to indicate their union.
|
|
|
|
Examples
|
|
|
For Loop Example
|
|
•
|
We now set up a test procedure including a perfectly nested for loop.
|
>
|
for_proc := 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:
|
•
|
Create the for loop data structure from the test procedure
|
•
|
View the raw content of the data structure:
|
•
|
Convert the ForLoop back into a Maple procedure.
|
|
|
While Loop Example
|
|
•
|
Create a basic While Loop with pre- and post-conditions:
|
>
|
while_proc := proc (a, err)
local r, q, p;
r := a - 1;
q := 1;
p := 1/2;
ASSERT(a <= 4 and 1 <= a and 0 < err and p > 0);
while err <= 2 * p * r do
if 0 <= 2 * r - 2 * q - p then
r := 2 * r - 2 * q - p;
q := q + p;
p := 1/2 * p:
else
r := 2 * r;
p := 1/2 * p:
end if:
end do;
ASSERT(q^2 <= a and a < q^2+err);
return q:
end proc;
loop2 := CreateLoop(while_proc);
|
|
|
While Loops and Assignments
|
|
•
|
This WhileLoop uses sequential assignments:
|
>
|
while_proc_sequential := proc(a, b)
local i, j:
i := 1:
j := 1:
while a < b*j do
i := i + 1:
j := a*i + b:
end do:
return j:
end proc:
loop1 := CreateLoop(while_proc_sequential):
|
•
|
When converting back into a procedure using GenerateProcedure, however, the sequential assignments are converted into equivalent simultaneous assignments. While the bodies of the loops in while_proc_sequential and while_proc_simultaneous are different, they are equivalent.
|
|
|
|
Compatibility
|
|
•
|
The CodeTools[ProgramAnalysis][CreateLoop] command was introduced in Maple 2016.
|
|
|
|