— The Name in Software Engineering Automation

XTRAN Demonstration:  Restructure PL/I

The following example uses a rule set written in XTRAN's "meta-code" (rules language) that implements a set of code structuring algorithms to eliminate GOTO statements in PL/I by imposing IF, ELSE, and DO statements.  The algorithms use recursive statement and expression pattern matching and replacement capabilities provided by XTRAN's meta-code, involving "match" statement patterns and "replace" statement patterns.

In the patterns below, this indicates PL/I elements and <this> indicates meta (rules language) elements.  Also, the matching of each occurrence of <label> in each pattern is constrained by a condition:  The matching label must have only one GOTO to it.

 Structure with IF

To impose IFs, we use the following "match" and "replace" patterns.

The first IF "match" pattern has the form:

        IF <expr> THEN
            GOTO <label>;
        <stmts>
<label>:
        <stmt>

where <expr> matches any conditional expression, <label> matches any label, <stmts> match one or more statements containing no IF at the top level and no labels, and <stmt> matches any statement.  Note that the second occurrence of <label> must be the same symbol as the first occurrence in order for the pattern to match.

The second IF "match" pattern is the same as the first except that it allows IF statements at the top level of <stmts>.

The IF "replace" pattern has the form:

        IF ^<expr> THEN
            DO;
                <stmts>
                END;
<label>:
        <stmt>

where <expr>, <stmts>, <label>, and <stmt> are whatever matched them in the "match" patterns.

 Structure with IF/ELSE

To impose IF/ELSEs, we use the following "match" and "replace" patterns.

The IF/ELSE "match" pattern has the form:

        IF <expr> THEN
            DO;
                <stmts1>
                GOTO <label>;
                END;
        <stmts2>
<label>:
        <stmt>

The IF/ELSE "replace" pattern has the form:

        IF <expr> THEN
            DO;
                <stmts1>
                END;
        ELSE
            DO;
                <stmts2>
                END;
<label>:
        <stmt>

where <expr>, <stmts1>, <stmts2>, <label>, and <stmt> are whatever matched them in the "match" pattern.

 Structure with DO

To impose DOs, we use two pattern sets:  One for "up-counting" DOs and one for "down-counting" DOs.

The "up-counting" DO "match" pattern has the form:

        <index> = <init>;
<label>:
        <stmts>;
        <index> = <index> + <increm>;
        IF <index> < <limit> THEN
            GOTO <label>;

where <index> matches the index variable, <init> matches its initial value, <label> matches any label, <stmts> matches one or more statements with no labels, <increm> matches the index increment value, and <limit> matches the index limit value.  Note that the second occurrence of <label> must be the same symbol as the first occurrence in order for the pattern to match.  Also, since + is a commutative operator, XTRAN's pattern matching facility automatically tries for both <index> + <increm> and <increm> + <index>.

The "up-counting" DO "replace" pattern has the form:

        DO <index> = <init> TO <limit> [[BY <increm>]];
            <stmts>;
            END;

where <index>, <init>, <limit>, <increm>, and <stmts> are whatever matched them in the "match" pattern.  Note that BY <increm> is only added if <increm> is not 1.

The "down-counting" DO "match" pattern has the form:

        <index> = <init>;
<label>:
        <stmts>;
        <index> = <index> - <decrem>;
        IF <index> >= <limit> THEN
            GOTO <label>;

where <index> matches the index variable, <init> matches its initial value, <label> matches any label, <stmts> matches one or more statements with no labels, <decrem> matches the index decrement value, and <limit> matches the index limit value.  Note that the second occurrence of <label> must be the same symbol as the first occurrence in order for the pattern to match.

The "down-counting" DO "replace" pattern has the form:

        DO <index> = <init> TO <limit> [[BY -<decrem>]];
            <stmts>;
            END;

where <index>, <init>, <limit>, <decrem>, and <stmts> are whatever matched them in the "match" pattern.  Note that BY -<decrem> is only added if <decrem> is not 1.

 Strategy

For each "match" pattern, the meta-code repeatedly scans the code to be processed, using a facility built into XTRAN's rules language that visits each statement (recursively) once in each pass, looking for matches and replacing them with the corresponding "replace" patterns, until it can find no more matches to be replaced.  The meta-code also tells XTRAN to delete any label that has no references, at the end of each pass, so if the structuring deletes all references to a label, the label will disappear.  This has the effect that a successful match and replacement can trigger more structuring on the next pass.

The meta-code also:

• Preserves all comments on all affected statements, including deleted statements, and automatically annotates comments in cases where the meaning of a conditional expression is reversed by structuring, inserting (rvsd) if the condition is reversed and removing it if the same condition is reversed back to its original form by additional structuring.
  
  
• Automatically simplifies ^<expr> where possible; for example, ^(a < b) becomes a >= b.
  
  
• Cleans up any simple DO block that contains only one statement, by eliminating the DO/END around the statement.
  
  
• Reports, in the run log, the number of GOTOs eliminated by each algorithm.
  
  

The rules are not specific to PL/I; they can easily be adapted for any language.

 PL/I Code Before Structuring

        DCL (i, j) FIXED BIN (31);              /*DCL (i, j) FIXED BIN (31);*/
/*
 * The following should structure to nested IFs and an ELSE:
 */
lbl0:   IF i = 0 | i = 1 THEN                   /*lbl0: IF i = 0  | i = 1 THEN*/
            GOTO lbl2;                          /*GOTO lbl2;*/
        i = 1;                                  /*i = 1;*/
        IF i > 1 THEN                           /*IF i > 1 THEN*/
            GOTO lbl1;                          /*GOTO lbl1;*/
        i = 2;                                  /*i = 2;*/
lbl1:   i = 3;                                  /*lbl1: i = 3;*/
        GOTO lbl3;                              /*GOTO lbl3;*/
lbl2:   i = 4;                                  /*lbl2: i = 4;*/
lbl3:   i = 5;                                  /*lbl3: i = 5;*/
/*
 * The following should structure to an up-counting DO with "i" as the index:
 */
lbl4:   i = 1;                                  /*lbl4: i = 1;*/
lbl5:   j = i + 1;                              /*lbl5: j = i + 1;*/
        j = i + 2;                              /*j = i + 2;*/
        i = i + 3;                              /*i = i + 3;*/
        IF i < 10 THEN                          /*IF i < 10 THEN*/
            GOTO lbl5;                          /*GOTO lbl5;*/
        j = i + 3;                              /*j = i + 3;*/
/*
 * The following should structure to a down-counting DO with "i" as the index:
 */
lbl6:   i = 10;                                 /*lbl6: i = 10;*/
lbl7:   j = i + 1;                              /*lbl7: j = i + 1;*/
        j = i + 2;                              /*j = i + 2;*/
        i = i - 2;                              /*i = i - 2;*/
        IF i >= 1 THEN                          /*IF i >= 1 THEN*/
            GOTO lbl7;                          /*GOTO lbl7;*/
        j = i + 3;                              /*j = i + 3;*/
/*
 * The reference in the following GOTO will prevent XTRAN from deleting lbl0:
 */
        GOTO lbl0;                              /*GOTO lbl0;*/

 PL/I Code After Structuring by XTRAN

        DECLARE (i, j) FIXED BINARY (31);       /*DCL (i, j) FIXED BIN (31);*/
/*
 * The following should structure to nested IFs and an ELSE:
 */
lbl0:   IF i ^= 0 & i ^= 1 THEN                 /*(rvsd) lbl0: IF i = 0  | i = 1 THEN*/
            DO;                                 /*GOTO lbl2;*/
                i = 1;                          /*i = 1;*/
                IF i <= 1 THEN                  /*(rvsd) IF i > 1 THEN*/
                    i = 2;                      /*i = 2;*/
                                                /*GOTO lbl1;*/
                i = 3;                          /*lbl1: i = 3;*/
                END;
        ELSE                                    /*GOTO lbl3;*/
            i = 4;                              /*lbl2: i = 4;*/
        i = 5;                                  /*lbl3: i = 5;*/
/*
 * The following should structure to an up-counting DO with "i" as the index:
 */
        DO i = 1 TO 10 BY 3;                    /*lbl4: i = 1;*/
            j = i + 1;                          /*lbl5: j = i + 1;*/
            j = i + 2;                          /*j = i + 2;*/
            END;                                /*i = i + 3;*/
                                                /*IF i < 10 THEN*/
                                                /*GOTO lbl5;*/
        j = i + 3;                              /*j = i + 3;*/
/*
 * The following should structure to a down-counting DO with "i" as the index:
 */
        DO i = 10 TO 1 BY -2;                   /*lbl6: i = 10;*/
            j = i + 1;                          /*lbl7: j = i + 1;*/
            j = i + 2;                          /*j = i + 2;*/
            END;                                /*i = i - 2;*/
                                                /*IF i >= 1 THEN*/
                                                /*GOTO lbl7;*/
        j = i + 3;                              /*j = i + 3;*/
/*
 * The reference in the following GOTO will prevent XTRAN from deleting lbl0:
 */
        GOTO lbl0;                              /*GOTO lbl0;*/

 Notation in XTRAN run log

Structuring rules eliminated 5 of 6 GOTOs (83%):
      2 by structuring IFs
      1 by inserting ELSEs
      2 by inserting DOs

COPYRIGHT 2012; reproduction prohibited without permission.  Revised 2009-09-11

XTRAN is a trademark of Pennington Systems Incorporated.