CodeTools[ProgramAnalysis] - Maple Programming Help

Online Help

All Products    Maple    MapleSim


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

CodeTools[ProgramAnalysis]

  

CreateLoop

  

create a WhileLoop or ForLoop from a Maple procedure

 

Calling Sequence

Parameters

Description

Examples

Compatibility

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:

  

ForLoopProcedure::=procp1,,pmlocalv1,,vn,x1,,xp;# Initialization statementsx1f1(p);x2f2(p,x1);xpfp(p,x1,,xp1);ForLoopend proc

  

ForLoop::=forvifromlbitoubiLoopBodyend do

  

LoopBody::=ForLoop|IfStatement|AssignmentStatements

  

IfStatement::=ifc1thenAssignmentStatementselifc2thenAssignmentStatementselseAssignmentStatementsend if

  

AssignmentStatements::=pjgjp,v,x+

• 

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.

While Loops

• 

WhileLoops can be generated from procedures that have the following form:

  

WhileLoopProcedure::=procx1,,xmlocalv1,,vn,y1,,yp;# Initialization statementsy1f1(x);y2f2(x,y1);ypfp(x,y1,,yp1);ASSERTpre­condition;whileguard­conditiondoifbranch­condition1thenv1g1v,x,y;vngnv,x,y;elifbranch­condition2thenelseend if;end do;ASSERTpost­condition;returnhx,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.

Examples

withCodeTools[ProgramAnalysis]:

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

loop1CreateLoopfor_proc:

• 

View the raw content of the data structure:

oploop1

RecordForLoop,body=,ai,j=bi+1+ai1,j1,layers=i,1,1,minn+2,10,j,i,1,n+2,initialization=,variables=i,j,parameters=n,arrays=a,b

(1)
• 

Convert the ForLoop back into a Maple procedure.

GenerateProcedureloop1

proca,b,nlocali,j;foritomin10,n+2doforjfromiton+2doa[i,j]b[i+1]+a[i1,j1]end doend do;returnend proc

(2)

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_procproca&comma;errlocalr&comma;q&comma;p&semi;ra1&semi;q1&semi;p1&sol;2&semi;ASSERTa<=4and1<=aand0<errand0<p&semi;whileerr<=2&ast;p&ast;rdoif0<=2&ast;r2&ast;qpthenr2&ast;r2&ast;qp&semi;qq&plus;p&semi;p1&sol;2&ast;pelser2&ast;r&semi;p1&sol;2&ast;pend ifend do&semi;ASSERTq&Hat;2<=aanda<q&Hat;2&plus;err&semi;returnqend proc

loop2RecordWhileLoop&comma;variables&equals;p&comma;q&comma;r&comma;parameters&equals;a&comma;err&comma;initialization&equals;12&comma;1&comma;a1&comma;transitions&equals;02r2qp&comma;12p&comma;q&plus;p&comma;2r2qp&comma;&comma;12p&comma;q&comma;2r&comma;guard&equals;err2pr&comma;precondition&equals;a4&comma;1a&comma;0<err&comma;0<p&comma;postcondition&equals;q2a&comma;a<q2&plus;err&comma;returnvalue&equals;q

(3)

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.

while_proc_simultaneousGenerateProcedureloop1

while_proc_simultaneousproca&comma;blocali&comma;j&semi;i&comma;j1&comma;1&semi;whilea<b&ast;jdoi&comma;ji&plus;1&comma;a&ast;i&plus;1&plus;bend do&semi;returnjend proc

(4)

Compatibility

• 

The CodeTools[ProgramAnalysis][CreateLoop] command was introduced in Maple 2016.

• 

For more information on Maple 2016 changes, see Updates in Maple 2016.

See Also

CodeTools[ProgramAnalysis]