create a WhileLoop or ForLoop from a Maple procedure
procedure with a loop
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.
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:
ForLoopProcedure::=proc⁡p1,…,pmlocalv1,…,vn,x1,…,xp;# Initialization statementsx1≔f1(p);x2≔f2(p,x1);⋮xp≔fp(p,x1,…,xp−1);ForLoopend proc
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 lbi / upper bounds ubi must be linear in the loops' index variables v, parameters p and local variables x, 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:
variables : list of the loop's index variables, one per layer of nested for loops
arrays : list of indexable variables being read from or written to in the loop
parameters : list of the parameters passed to the procedure p that are not in arrays
initialization : list of equations representing the assignments that occur before the loop
layers : 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.
body : 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.
WhileLoops can be generated from procedures that have the following form:
WhileLoopProcedure::=proc⁡x1,…,xmlocalv1,…,vn,y1,…,yp;# Initialization statementsy1≔f1(x);y2≔f2(x,y1);⋮yp≔fp(x,y1,…,yp−1);ASSERT⁡pre­condition;whileguardconditiondoifbranchcondition1thenv1≔g1⁡v,x,y;⋯vn≔gn⁡v,x,y;elifbranchcondition2then⋯else⋯end if;end do;ASSERT⁡post­condition;returnh⁡x,v,y;end proc
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 v 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:
variables : list of the loop variables, i.e. variables updated in the loop.
parameters : list of the procedure's parameters.
initialization : list of initial values for the loop variables written in terms of the parameters.
precondition : conditional expression extracted from the ASSERT statements before the loop. These conditions are assumed to be true.
guard : conditional expression in the while clause of the do loop.
transitions : 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.
postcondition : 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 postcondition will be satisfied.
returnvalue : list of the procedure's return value(s). The procedure's return value are the operands of returnvalue.
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.
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]
Create the for loop data structure from the test procedure
loop1 ≔ CreateLoop⁡for_proc:
View the raw content of the data structure:
Convert the ForLoop back into a Maple procedure.
proca,b,nlocali,j;foritomin⁡10,n+2doforjfromiton+2doa[i,j] ≔ b[i+1]+a[i − 1,j − 1]end doend do;returnend proc
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:
r := 2 * r;
p := 1/2 * p:
ASSERT(q^2 <= a and a < q^2+err);
loop2 := CreateLoop(while_proc);
while_proc ≔ proca,errlocalr,q,p;r ≔ a − 1;q ≔ 1;p ≔ 1/2;ASSERT⁡a<=4and1<=aand0<errand0<p;whileerr<=2*p*rdoif0<=2*r − 2*q − pthenr ≔ 2*r − 2*q − p;q ≔ q+p;p ≔ 1/2*pelser ≔ 2*r;p ≔ 1/2*pend ifend do;ASSERT⁡q^2<=aanda<q^2+err;returnqend 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:
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.
while_proc_simultaneous ≔ GenerateProcedure⁡loop1
while_proc_simultaneous ≔ proca,blocali,j;i,j ≔ 1,1;whilea<b*jdoi,j ≔ i+1,a*i+1+bend do;returnjend proc
The CodeTools[ProgramAnalysis][CreateLoop] command was introduced in Maple 2016.
For more information on Maple 2016 changes, see Updates in Maple 2016.
Download Help Document