XTRAN Example — Restructure PL/I

Scenario — you're the software development manager in a PL/I shop, and you realize that some of the PL/I code for which you're responsible is poorly structured, compromising the code's readability and maintainability.

XTRAN to the rescue!

The following example uses rules written in XTRAN's rules language ("meta-code") that implement 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 rules language, involving "match" statement patterns and "replace" statement patterns.

The rules comprise 515 code lines of XTRAN's rules language. They are not very specific to PL/I; they can easily be adapted to work for any 3GL language. In fact, we also have versions for COBOL and C/C++/C#/Java .

How can such powerful and generalized code quality improvement be achieved in only 515 lines of rules? Because there is so much capability already available as part of XTRAN's rules language. The rules used for this example take advantage of the following functionality provided by that rules language:

Statement and expression pattern matching and replacement
Text manipulation
Text formatting
Access to XTRAN's Internal Representation (XIR)
XIR's language-independent properties
Navigation in XIR
Creating new meta-functions written in meta-code, which we call user meta-functions

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.

Process Flowchart

Here is a flowchart for this process, in which the elements are color coded:

BLUE for XTRAN versions (runnable programs)
ORANGE for XTRAN rules (text files)
RED for code

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 with XTRAN rules:

        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