ACD Atlas Computing Division Prime Computer Systems

Jump To Main Content

Jump Over Banner

Home

ACDICFMulti User MinisPrime

Jump Over Left Menu

ROOTS

D A Duce, R W Witty

6 June, 1979

1 INTRODUCTION

ROOTS is an extended FORTRAN language which is translated into pure FORTRAN by a preprocessor. The language was designed for use in the context of a design methodology which allows a single, automated representational technique to be used throughout the design, construction and maintenance of hierarchically structured software (See R W Witty, The design and construction of hierarchically structured software, Pragmatic Programming and Sensible Software, Online 1978). Section 2 below contains an outline description of this methodology.

ROOTS can however be used outside this context as an extended FORTRAN providing enhanced control structures, but the authors suggest that the reader pays some attention to section 2 and the possible benefits of using the software tools to the full.

ROOTS also provides performance monitoring, control and data flow tracing facilities which are integrated into the representational technique described below. These facilities can be used with existing FORTRAN programs, though this does require some effort and the results are not as easy to display as are the results when used with a true ROOTS program.

2 THE DESIGN OF HIERARCHICALLY STRUCTURED SOFTWARE

2.1 Representation of hierarchically structured software

One technique for the creation of hierarchically structured software is the Step-Wise Refinement method (See N. Wirth, Program Development by Step-Wise Refinement, CACM Vol 7 No 5 Sept/Oct 1977) in which a specification is broken down or refined into a sequence of instructions. Each instruction may itself be further refined. Such software has three major structural features, sequence, parallelism and refinement. Dimensional Flowcharting is an automated graphical technique to represent these three features.

Figure 1 shows how in conventional Step-Wise Refinement there is no way of showing which instructions are derived from which specifications whereas in the Dimensional Flowchart of figure 2 the relationship is obvious. Refinement is denoted by a diagonal line connecting a specification to its refinement, ie to a sequence of instructions.

A sequence of instructions is represented as a vertically ordered list, which is executed from top to bottom. If a sequence is to be executed only once then it is called a single sequence and is indicated by the earthed symbol which is usually omitted for brevity. If a sequence is to be executed one or more times then it is called a Repeated Sequence and is indicated by the * symbol which cannot be omitted.

Conditional statements are represented by the C (conditional) symbol which, unless the specified condition is met, causes execution of the sequence to be terminated and the next (higher level) sequential instruction to be executed. The next sequential instruction is the one following the specification of the terminated sequence, see figure 3. Reaching an 'earthed' symbol causes termination of the sequence.

In general, any specification may be broken down into one or more sequences of instructions, with each sequence being executed in parallel (figure 4). A specification which is refined into executed in parallel sequences terminates if and when all its constituent sequences terminate.

Figures 2-4 show that hierarchically structured software can be represented by tree diagrams in which the three major structural features of such software are represented by lines in perpendicular directions (Figure 5). Dimensional flowchart drawings are 2-D projections of these 3-D tree structures.


SOLVE QUADRATIC EQUATION                          level 1 - specification

INPUT COEFFICIENTS                                level 2 - refinement of level 1
COMPUTE ROOTS BY FORMULA 
OUTPUT RESULTS


READ (A)                                          level 3 - refinement of 2 level 2 instructions
READ (B) 
READ (C) 
COMPUTE ROOTS BY FORMULA 
PRINT (A,B,C) 
PRINT (POSROOT,NEGROOT)
Figure 1: Step-wise refinement

SOLVE QUADRATIC EQUATION INPUT COEFFICIENTS COMPUTE ROOTS BY FORMULA OUTPUT RESULTS READ(A) READ(B) READ(C) PRINT (A,B,C) PRINT (POSTROOT,NEGROOT)

Figure 1: Step-wise refinement

Figures 6 shows how certain ROOTS constructs are represented as flowcharts. The direction labelled parallelism in figure 5 is used also to represent the selection of alternatives (see the IF and EPILOG examples).

2.2 Outline of design methodology

Suppose a new program is to be built from scratch. The initial design work is done with flowcharts hand drawn on the backs of envelopes. The step-wise refinement method of the initial design sketches causes a proliferation of small drawings which are combined into larger drawings as the work progresses and the design firms up. Refinement of the design drawing continues until a complete program is derived, ie when all the terminal nodes of the tree structure are compilable source code. At this stage the flowchart is coded up into ROOTS. This is done by tree-walking the flowchart, ie going through the flowchart in a particular order encoding each line and statement as it is visited. The technique is easily acquired by studying the example of the ROOTS source of a program and the corresponding flowchart given later in this paper.

The machine readable source code is then presented to the ROOTS preprocessor. The output from the preprocessor is an equivalent FORTRAN program and an encoded form of the program which may be fed into a second software tool (the DFC generating program) which generates a dimensional flowchart on one of a variety of output devices. Output devices currently available include Tektronix storage tubes and the Benson 1302 pen plotter.

The output from the preprocessor is thus an exact, but neater, replica of design as the flowchart should be exactly the same as the hand drawn version encoded.

Flowcharts have also been found to be a major aid to program testing as they help the programmer to appreciate the overall design when looking for bugs. As mentioned above and discussed in more detail below, program execution traces can be obtained in the same representation and program performance data can be displayed on the flowchart representing the static program structure.

Rob Witty working on a ROOTS flow diagram

Rob Witty working on a ROOTS flow diagram
Large View

They are a help to the maintenance programmer as they facilitate the learning and understanding of a program's design by retaining the hierarchical design as an integral part of the program.

SOLVE MANY QUADRATIC EQUATIONS while not end of input file Next instruction after loop terminates INPUT COEFFICIENTS COMPUTE ROOTS BY FORMULA OUTPUT RESULTS

Figure 3

Batch operating system Startup Process workload Shutdown Input spooling Run user jobs Output spooling

Figure 4.

Parallelism Refinement Sequence

Figure 5.

3 ROOTS - A STRUCTURED FORTRAN LANGUAGE

The remainder of this paper describes the run-time monitoring facilities provided by the ROOTS preprocessor, which gives a flavour for the control structures provided in ROOTS and the appearance of ROOTS programs. The remaining sections describe the language in detail and the mechanics of running ROOTS programs and of flowchart generation.

4 RUN-TIME MONITORING

It is a weakness of many language implementations that they provide no facilities for debugging and performance measurement in programs. Discovering which sections of a program consume the most resources can be exceedingly laborious and hence is rarely undertaken.

The ROOTS translator aims to provide users with facilities to measure the CPU time and IO time taken by nominated statements in the program, to generate an execution trace of nominated sections of the program and to monitor control and data flow in the program. At the language level, this is achieved by inserting monitoring statements at the start of the program which define the type of monitoring required, and then tagging those statements in the program for which monitoring is desired.

It is a further weakness of most run-time monitoring systems that the results produced are in the form of a sequential line printer listing and relating the results to the program can be exceedingly tedious. The ROOTS monitoring system is closely linked to the DFC system and by feeding the output from the monitoring system along with the flowchart code generated by the ROOTS translator into the DFC program static performance data and snap-shots of data will be displayed on the flowchart.

The run-time execution trace generated by the monitor is also in the form of input data for the DFC program and this also is intended to be represented as a flowchart. There are several mechanisms provided to limit the volume of tracing output generated.

The facilities provided are best described by way of examples and for this the program below will be considered. The program converts binary representations of integers to character string representations of their decimal values by iterative and recursive algorithms. This is used to illustrate the point that the monitoring system is capable of handling recursion. Recursion is permitted as an option in the PRIME FORTRAN system.

LOOP LOOP BODY K=1,LENMAI .EXITIF(SIN(J).EQ.TERMINATOR).TOSITU(1) CONVERT JTH BIN TO DEC 2 WAYS, ONE PER COL CALL S2DI(BIN(J),PAGE,J,STLEFTCOL) CALL S2DR(BIN(J),PAGE,J,STRIGHTCOL) J=J+1 EPILOG .SITU(1) ASSUMPTION INPUT TERMINATOR FOUND OK LIMIT FAIL(EI,'TERMINATOR NOT FOUND & PAGE FULL')

Figure 6.
.PROG 
.MONITOR SNAPS,PERFORMANCE,HISTORY,CONTROL 
.TRACE 
    .T1: DEP(20,9),DET(3) ,RF(1) .ET 
    .T2: DEP(0,0),DET(10) .ET 
    .T3: DEP(4,4),DET(3) .ET 
.ENDTRACE 
.SNAP-SHOT 
    .SS1: DET(20),FORMAT(200),SIZE(80) .ESS 
    .SS2: DET(25),FORMAT(210),SIZE(80) .ESS 
    .SS3: DET(25),FORMAT(220),SIZE(80) .ESS 
.ENDSNAP 
.FILTERS 
.BF1: (MOD(IT(N) ,2) .EQ.0) .EBF 
.ENDFILTERS 
.ENDMONITOR 
.MASTER 
 .C DECLARATIONS 
    INTEGER IN,EX,NUM,J,K 
    INTEGER BIN(100) 
    INTEGER PAGE(30,100) 
    INTEGER ISTRNG(80) 
    .EC 
.T1: .BEGIN 
.C INITIALISE 
    .C I/O CHANNELS 
        IN = 1 
        EX = 1 
        .EC 
    .PARSEP 
    .C CLEAR OUTPUT PAGE BUFFER TO SPACES 
        .FOR J=1,30 .DO 
            .FOR K=1, 100 .DO 
                PAGE(J,K) = ' ' 
            .ENDFR 
        .ENDFR 
        .EC


    .EC 
.C READ INPUT DATA INTO ARRAY BIN 
    READ(IN,100)NUM,(BIN(J),J=1,NUM) 
    .C FORCE LAST DATUM TO BE 9999 TO ENSURE TERMINATION 
        BIN(NUM) = 9999 
        .EC
    .EC
.C CONVERT INPUT SET OF BIN NUMS TO DEC IN PAGE BUFFER 
    J = 1 
     .T1: .CYCLE K=l, 100 ,TILL (1) .DO 
     .SS2: NUM,(BIN(J1),J1=1,NUM)
210 FORMAT('MEASURE OF SET' ,I4,1X,'MEMBERS' ,100(Il0,1X)) 
            .EXITIF(BIN(J).EQ.9999).TOSITU(1) 
            .Tl: .C CONVERT JTH BIN TO DEC 2 WAYS,ONE PER COL 
                    .T1: .CALL (1) B2DI(BIN(J),PAGE,J,1) 
                .PARSEP 
                    .T1: .CALL (1) B2DR(BIN(J),PAGE,J,30/2+1)
                .EC
           J = J+1 
       .REPEAT 
           .SITU (1) 
               .ASSUMPTION INPUT 9999 FOUND 
                    .OK
           .LIMIT 
               .FAIL(EX,'9999 NOT FOUND & PAGE FULL')
       .ENDCY 
       .EC 
   .C OUTPUT CONTENTS OF PAGE BUFFER 
       WRITE(EX,110)(BIN(K),(PAGE(J,K),J=1,30),K=1,NUM) 
       .EC 
   .STOP
   .C I/O FORMATS 
100    FORMAT(I10)
110    FORMAT(Il0,2X,30 A1) 
       .EC 
   .ENDM 
   .LEVEL 1 
   .SUBROUTINE B2DR(BINARY,PAGE,LINE,START) 
   .C DECLARATIONS 
       .C PARAMETERS 
           INTEGER BINARY,PAGE(30,100),LINE,START 
           .EC  
       .C LOCALS 
           INTEGER NCP,BIN 
           .EC 
    .C FUNCTIONS 
        .IG NONE 
        .EC
    .EC 
  .BEGIN 
  .C OUTPUT SIGN & MAGNITUDE OF BINARY 
  .C OUTPUT SIGN OF BINARY 
      .IF(BINARY.LT.0).THEN 
          .CALL(3) PRINT('-' ,PAGE,LINE,START) 
      .ELSE 
          .CALL(3) PRINT('+' ,PAGE ,LINE ,START) 
      .ENDIF 
      .EC 
  .PARSEP
  .C OUTPUT MAGNITUDE IN DECIMAL CHARSFROM MOST SIG DIGIT TO LEAST
      BIN = IABS(BINARY) 
      NCP = START+l 
      .T1: .CALL (2) PB2DR(BIN,PAGE,LINE,NCP) 
      .EC
      .EC 
      .RETURN 
      .END 
      .SETSEP 
      .SUBROUTINE B2DI(BINARY,PAGE,LINE,START) 
      .C DECLARATIONS 
          .C PARAMETERS 
              INTEGER BINARY,PAGE(30,100),LINE,START 
              .EC 
      .C LOCALS 
              INTEGER NCP,BIN,I,REM 
              .EC 
      .C FUNCTIONS 
              INTEGER DIGITS 
              .EC
      .EC 
  .BEGIN 
  .C OUTPUT SIGN & MAGNITUDE OF BINARY 
  .C OUTPUT SIGN OF BINARY 
      .IF(BINARY.LT.0).THEN 
          .CALL(3) PRINT('-' ,PAGE,LINE,START) 
      .ELSE 
          .CALL(3) PRINT('+',PAGE,LINE,START) 
      .ENDIF 
      .EC 
  .PARSEP 
  .C OUTPUT MAGNITUDE IN DECIMAL CHARSFROM LEAST SIG DIGIT TO MOST
      BIN = IABS(BINARY) 
      NCP = START+DIGITS(BIN) 
      .CALL(2) PB2DI(BIN,PAGE,LINE,NCP) 
      .EC
  .EC 
  .RETURN 
  .END 
  .ENDLEV 
  .LEVEL 2 
  .SUBROUTINE PB2DR(BINARY,PAGE,LINE,NCP) 
  .C DECLARATIONS 
      .C PARAMETERS  
          INTEGER BINARY,PAGE(30,100),LINE,NCP 
          .EC 
      .C LOCALS 
          INTEGER LSTDIG,BIN,ISTRNG(80),CHR 
          .EC 
      .C FUNCTIONS 
          INTEGER CHAR 
          .EC
      .EC 
   .Tl: .BEGIN 
   .IF(BINARY.GE.10).THEN 
       BIN = BINARY/10 
       .Tl: .CALL (*) PB2DR(BIN,PAGE,LINE,NCP) 
   .ELSE
       .NULL 
   .ENDIF 
   .C DETATCH LEAST SIG DIGIT 
       LSTDIG = MOD(BINARY,10) 
       .EC .
   .C PRINT LEAST SIG DIGIT 
       CHR = CHAR(LSTDIG) 
       .SS1: CHR,LINE,NCP 
       .CALL(3) PRINT(CHR,PAGE,LINE,NCP) 
       NCP = NCP+1 
       .EC 
200 FORMAT ( 'CHARACTER', 1X,A1, 1X, 'LINE' ,I4, 1X, 'COLUMN' ,I4) 
   .RETURN 
   .END 
   .SETSEP 
   .SUBROUTINE PB2DI(BINARY,PAGE,LINE,NCP) 
   .C DECLARATIONS 
       .C PARAMETERS 
           INTEGER BINARY,PAGE(30,100),LINE,NCP 
           .EC 
       .C LOCALS 
           INTEGER LSTDIG,J,BIN,ISTRNG(80),CHR 
           .EC 
       .C FUNCTIONS 
           INTEGER CHAR 
           .EC
       .EC 
   .BEGIN BIN = BINARY 
   .T2: .CYCLE J = 1 ,30 . TILL ( 1) . DO 
       .C DETATCH JTH LEAST SIG DIGIT 
           LSTDIG = MOD(BIN,10) 
           BIN = BIN/10 
           .EC 
       .T3: .C PRINT JTH LEAST SIG DIGIT 
           CHR = CHAR(LSTDIG) 
           .SS1: CHR,LINE,NCP 
           .T2: .CALL(3) PRINT(CHR,PAGE,LINE,NCP) 
           NCP = NCP-l 
           .EC 
       .EXITIF(BIN.EQ.0).TOSITU(l) 
   .REPEAT 
       .SITU (1) 
           .OK 
       .LIMIT 
           .FAIL(1,'PB2DI LOOP GUARD ERROR')
   .ENDCY 
200 FORMAT ('CHARACTER' , 1X, A1 , 1X, 'LINE' ,I4, 1X, 'COLUMN' , I4) 
   .RETURN 
   .END 
   .ENDLEV 
   .LEVEL 3 
   .SUBROUTINE PRINT(CHCODE,PAGE,LINE,WIDPOS)
   .C DECLARATIONS 
       .C PARAMETERS 
           INTEGER CHCODE,PAGE(30,100),LINE,WIDPOS 
           .EC
       .EC 
       .T2: .BEGIN 
       .T2: PAGECWIDPOS,LINE) = CHCODE 
       .RETURN 
       .END 
       .SETSEP 
       .INTEGER FUNCTION CHAR(INT) 
       .C DECLARATIONS 
           .C PARAMETERS 
               INTEGER INT 
               .EC
           .EC 
       .BEGIN 
       .IF(INT.EQ.O) .THEN 
           CHAR = '0' 
       .ELIFC(INT.EQ.1) .THEN 
           CHAR = '1' 
       .ELIF(INT.EQ.2) .THEN 
           CHAR = '2' 
       .ELIFC(INT.EQ.3).THEN 
           CHAR = '3' 
       .ELIF(INT.EQ.4) .THEN 
           CHAR = '4' 
       .ELIF(INT.EQ.5) .THEN 
           CHAR = '5' 
       .ELIFCINT.EQ.6) .THEN 
           CHAR = '6' 
       .ELIFCINT.EQ.7) .THEN 
           CHAR = '7' 
       .ELIFCINT.EQ.8) .THEN 
           CHAR = '8' 
       .ELIFCINT.EQ.9) .THEN 
           CHAR = '9' 
       .ELSE 
           .FAIL(1,'FUNC CHAR PARAM NOT DIGIT') 
       .ENDIF 
       .RETURN 
       .END 
       .SETSEP 
       .INTEGER FUNCTION DIGITS(POSINT) 
       .C DECLARATIONS 
           .C PARAMETERS 
               INTEGER POSINT 
               .EC 
           .C FUNCTIONS 
               INTEGER DIGTSR 
               .EC
           .EC 
       .BEGIN
       .IF(POSINT.GE.10).THEN 
           DIGITS = 1+DIGTSR(POSINT/10) 
       .ELSE 
           DIGITS = 1
       .ENDIF 
       .RETURN 
       .END 
       .ENDLEV 
       .LEVEL 4 
       .INTEGER FUNCTION DIGTSR(INT) 
       INTEGER INT,DIGITS 
       .BEGIN 
       DIGTSR = DIGITS(INT) 
       .RETURN 
       .END 
       .ENDLEV 
       .ENDP

The type of run-time monitoring required is requested by the inclusion of a .MONITOR section at the head of the program as shown below.

.MONITOR PERFORMANCE, HISTORY, CONTROL, SNAPS 
.TRACE 
 .T1: DEP(20, 7) ,DET(3) ,RF(1) .ET 
 .T2 : DEP(0 ,0) ,DET (10) ,RF (1) .ET 
.ENDTRACE 
.SNAP-SHOT 
 .SS1: DET(20) ,FORMAT(200) ,SIZE(80) .ESS 
 .SS2: DET(25) ,FORMAT(210),SIZE(80) .ESS 
.ENDSNAP 
.FILTERS 
  .BF1: (MOD(IT(N) ,2) .EQ.0) .EBF 
.ENDFILTERS 
.ENDMONITOR

The monitoring categories required are specified by the keywords following .MONITOR. The statement above represents all available monitoring categories. TRACE - ENDTRACE, SNAP-SHOT - ENDSNAP and FILTERS - ENDFILTERS are optional sections which control the details of monitoring.

4.1 Tracing

The most general form of trace statement possible is indicated above. The number following .T is the tracing level being defined. When statements in the program are tagged for monitoring, the tag includes a tracing level, which indexes a set of tracing parameters defined in .TRACE.

Tracing parameters are set as follows:

Detail level
DET(<number>)
Pruning data
DEP(<number>,<number>)
Repetition filter
RF(<number>)

The association of a level of detail with each statement tagged for tracing provides a mechanism whereby the user may select at run-time a subset of these statements to be actually traced. The user specifies at run-time a level of detail, and only those statements with

detail ≤  run-time detail

will appear in the tracing output.

The specification of a repetition filter is a method for selecting the iterations of a loop to be traced. The filter to be associated with a particular tracing level is defined by an index into the set of filters (specified in the .FILTERS section). Thus in the example above, the filter

(MOD(IT(N),2).EQ.0)

is associated with tracing level 1. Statements are only traced when the value of the associated filter is .TRUE. (and some other conditions are satisfied). Associated with each loop in the program is an iteration counter, assigned the value zero before the loop is entered and incremented by one at the start of each iteration of the loop. The function IT(N) is a function of type INTEGER*4 provided by the monitor which returns the current value of the iteration counter. Thus the repetition filter above will cause all odd numbered iterations not to be traced.

Note that any routine in which IT(N) is invoked must include a declaration:

INTEGER*4 IT

this is NOT included automatically by the translator. Failure to include such a declaration will lead to spurious results (the filter will always return the value 0).

The pruning data specified by DEP allow the user to control the depth to which the trace is allowed to grow and how much of the trace is to be retained as levels of refinement are terminated.

The motivation behind this is that if the execution of a refinement terminates unexpectedly (for example a .FAIL statement is executed or the condition specified in a .ASSERTION statement yields the value .FALSE.) one can have a very detailed execution trace to work from. If the execution is successful, one is not in general interested in the detail of the execution so this can be discarded from the trace.

Consider the section of code:

.T3:  .C PRINT JTH LEAST SIG DIGIT 
.T2:  CALL PRINT(CHAR(LSTDIG),PAGE,LINE,NCP)
      .EC
..........
.SUBROUTINE PRINT(CHCODE,PAGE,LINE,WIDPOS) 
.T2: .BEGIN 
.T2: PAGE(WIDPOS,LINE) = CHCODE 
     .RETURN 
     .END

Execution of this code will produce a trace. Depths of refinement are indicated at the head of each refinement in the text <number>=RD. Suppose the statement

.C PRINT JTH LEAST SIG DIGIT

is tagged with the tag .T3 where tracing level 3 is defined by:

.T3: DEP(2,1) ,DET(3) .ET

The first parameter specified in DEP (DOWN) is the number of refinements of the current refinement which are to be traced. This value is used to calculate a new value of the maximum depth of refinement to be traced (MDRT), which is given by:

MDRT = MAX (MDRT,MDRT + DOWN)

Thus in this example, since the value of DOWN associated with tracing level 2 is zero, the statements CALL PRINT and BEGIN PRINT would be traced, but the refinements of BEGIN PRINT would not.

The second parameter specified in DEP (UP) is the number of refinements of the current refinement to be saved. This value is used when a refinement terminates to decide whether the refinement should be saved in the tracing buffer or discarded. The maximum depth of refinement to be saved (MDRS) is calculated as for MDRT, ie:

MDRS = MAXCMDRS,MDRS + UP)

Thus in this example, if MDRS has the value 7 when the statement PRINT JTH LEAST SIG DIGIT is obeyed, the new value calculated will be 8. Thus on termination of all refinements with depths greater than 8, any statements traced will be discarded.

4.2 Snap-shots

The SNAP-SHOT section specifies how current data values are to be recorded in the tracing buffers and the circular snap-shot buffers. The parameter, specified by DET is the level of detail which controls whether anything will be recorded in the buffer. FORMAT specifies the label of a FORMAT statement which will be used as a template for writing the data values into the tracing buffer. SIZE specifies how many characters of the string produced by writing the values into a buffer according to FORMAT are to be saved. Snap-shots are invoked by a program statement of the form:

.SS<number>: <name list>

for example:

.SS1: I,J,K

<number> is an index into the set of snap-shot definitions in .SNAP-SHOT. Thus with the snap-shot definitions given earlier, 80 characters of the string produced by writing the values of I, J, K, into a buffer according to FORMAT statement 200 will be recorded in the tracing buffer if the detail level specified at run-time is greater than 20. Statement 200 might be:

200 FORMAT('VALUES OF I, J, K' ,2X,3(I6,2X))

Every routine producing snap-shots should include the declaration of an array:

  INTEGER ISTRNG(<n>)

where the dimension <n> is large enough to hold the number of characters specified by the SIZE parameter of the .SS statement defining the snap-shot. Thus for a maximum SIZE of 80 characters, the array should be dimensioned at 40, as 2 characters are stored per word.

The run-time monitor will produce an output file containing snap-shot information in the format:

STATEMENT NUMBER           1 
ENTRY     ITERATION AND SNAP-SHOT
   -2     (           1) MEASURE OF SET 3 MEMBERS -123 5436 9999 
   -1     (           2) MEASURE OF SET 3 MEMBERS -123 5436 9999 
   0      (           3) MEASURE OF SET 3 MEMBERS -123 5436 9999 

STATEMENT NUMBER           2 
ENTRY     ITERATION AND SNAP-SHOT 
   -6     (           1) CHARACTER 1 LINE 1 COLUMN 17 
   -5     (           1) CHARACTER 2 LINE 1 COLUMN 18 
   -4     (           1) CHARACTER 3 LINE 1 COLUMN 19 
   -3     (           2) CHARACTER 5 LINE 2 COLUMN 17 
   -2     (           2) CHARACTER 4 LINE 2 COLUMN 18 
   -1     (           2) CHARACTER 3 LINE 2 COLUMN 19 
    0     (           2) CHARACTER 6 LINE 2 COLUMN 20 
STATEMENT NUMBER          3 
ENTRY     ITERATION AND SNAP-SHOT 
   -6     (           1) CHARACTER 3 LINE 1 COLUMN 4 
   -5     (           2) CHARACTER 2 LINE 1 COLUMN 3 
   -4     (           3) CHARACTER 1 LINE 1 COLUMN 2 
   -3     (           1) CHARACTER 6 LINE 2 COLUMN 5 
   -2     (           2) CHARACTER 3 LINE 2 COLUMN 4 
   -1     (           3) CHARACTER 4 LINE 2 COLUMN 3 
    0     (           4) CHARACTER 5 LINE 2 COLUMN 2

ENTRY records the position of the snap-shot in the circular snap-shot buffers (least recent first). The value of the current iteration counter is recorded with each entry which is of value in tying up snap-shots and program execution.

If HISTORY tracing is invoked, snap-shots will also appear in the history trace file and will be displayed in context if a flowchart is drawn of this data.

4.3 Tracing Modes

The tracing mechanism operates in one of two modes, either dumping information to the tracing file as it is generated (history buffer) or by maintaining a circular buffer of information and dumping the buffer when the monitor is terminated. The latter mode is useful during later stages of debugging as it produces significantly less output than the history buffer, typically giving an execution trace of the last 100 statements executed. Tracing mode is selected at run-time.

Tracing mode can also be changed dynamically at execution time by including statements

.HISTORICAL TRACE 
.CIRCULAR TRACE

in the ROOTS source code. Execution of these statements switches the trace mode to history buffer or circular buffer respectively.

4.4 Control Tracing

If CONTROL monitoring is requested, the file produced by the monitoring package will contain information of the form

CIRCULAR CONTROL BUFFER
  EXEC. ORDER   STMT. NO.  ITERATION 
          -98           3          1 
          -97           4          1 
          -96           5          1 
          -95           6          1 
          -94          24          1 
          -93          25          1 
          -92          15          1 
          -91          16          1 
          -90          17          1 
          -89          18          1 
          -88          19          1 
          -87          24          1 
          -86          25          1 
          -85          20          1 
          -84          17          2 
          -83          18          2 
          -82          19          2 
          -81          24          2
.......
          -11          14          2 
          -10          13          2 
           -9          24          2 
           -8          25          2 
           -7          24          2 
           -6          25          2 
           -5          24          2 
           -4          25          2 
           -3          24          2 
           -2          25          2 
           -1           9          1 
            0          10          1 

The monitoring package stores the statement numbers and associated iteration counter of the last 100 statements executed by the program. Statement numbers can be ascertained from the flowchart of the program. Numbers used to identify performance, control and snap-shot data are given in parentheses after each tagged statement, for example:

CONVERT JTH BIN TO DEC 2 WAYS, ONE PER COL 
(PF NO 3 CL NO 3)

The performance (PF NO) identifier of this statement is 3, the control statement number (CL NO) is also 3.

4.5 Performance Measurement

If PERFORMANCE monitoring is requested, the file produced by the monitoring package will contain information of the form:

PERFORMANCE MONITOR

STMNO  CPU-TIME  IO-TIME  FREQUENCY MAX.REC.DEP CURR.REC.DEP
    1       855        1          1           1            0
    2       799        1          1           1            0
    3       793        1          1           1            0
    4       780        1          2           1            0
    5       409        0          2           1            0
    6       407        0          2           1            0
    7       363        1          2           1            0
    8       360        1          2           1            0
    9         3        0          1           1            0
   10         0        0          1           1            0
   11         0        0          0           0            0
   12       332        1          2           1            0
   13       326        1          7           4            0
   14       189        1          5           3            0
   15       359        0          2           1            0
   16       347        0          2           1            0
   17       322        0          7           1            0
   18       199        0          7           1            0
   19        43        0          7           1            0
   20         3        0          7           1            0
   21         6        0          2           1            0
   22         0        0          2           1            0
   23         0        0          0           0            0
   24        58        0         18           1            0
   25        10        0         18           1            0

Statement numbers can be related to statements as discussed above. PRIME routines CTIM$A and DTIM$A are used to measure the CPU times and IO times used by statements. CPU times and IO times are recorded in units of 1/100th of a second.

As far as possible resources used by subroutine calls to the monitor are subtracted from the CPU-TIME figures reported, but some proportion of the monitor overheads will be used, because some instructions must be executed before CPU time monitoring can be turned off. Thus the figures reported should be treated with some caution and fine grain effects should be ignored.

Monitor overhead is measured by the monitor and is printed out at the end of the program run.

The column headed FREQUENCY records the execution frequencies of the statements monitored. MAX.REC.DEP reports the maximum depth of recursion of the statement and CURR.REC.DEP records the depth of recursion of the statement when monitoring terminated.

In general performance monitoring information will be displayed as a flowchart of the program under consideration, in preference to direct examination of the file produced by the monitor.

5 GENERAL LAYOUT FEATURES OF ROOTS PROGRAMS

All reserved words in ROOTS are preceded by the symbol .. ROOTS source text must start in or after column 7 and must not go beyond column 72 of the line. FORTRAN source may be intermingled with ROOTS constructs as desired, but only 'pure' FORTRAN source may be continued to a second or subsequent line.

If the FORTRAN code generated by a ROOTS statement exceeds 72 characters, it will be automatically continued to the next line. This should cause no problems.

ROOTS reserved words may not contain embedded spaces. Thus:

.I F(.TRUE.).T H E N

is illegal.

The ROOTS preprocessor generates labels in the range 20000 to 29999. Variable names KT<n> where <n> is in the range 0001 to 9999 are generated by the preprocessor in the translation of the .CYCLE statement and hence should not be used in the source fed to the preprocessor.

6 NOTATION

We introduce the notation

<be>
to mean any valid FORTRAN boolean expression,and:
<ls>
to be any sequence of FORTRAN or ROOTS statements.
<text>
is any sequence of characters such as would appear in a FORTRAN comment statement,
<lines of text>
is any number of lines of <text>.

7 SELECTION STATEMENTS

7.1 .IF-.THEN-.ELIF-.ELSE

The syntax is:

.IF(<be>).THEN
   <ls>
.ELIF(<be>).THEN  
   <ls>
.ELIF(<be>).THEN  
   <ls>
.ELSE
   <ls>
.ENDIF

The .ELSE clause is mandatory. The statement may contain any number (including zero) of .ELIF clauses. The code generated is:

      IF(.NOT.(<be>))GOTO 20000
      <ls>
      GOTO 20001
2000  IF(.NOT.(<be>))GOTO 20002
      <ls>
      GOTO 20001
2002  IF(.NOT.(<be>))GOTO 20003
      <ls>
      GOTO 20001
2003  CONTINUE
      <ls>
2001 CONTINUE

Further syntatic restrictions are:

  1. .THEN must appear at the end of a line
  2. .IF-.THEN must appear on one line, continuation lines are not allowed.
  3. .ELSE and .ENDIF must appear alone on separate lines.

The conditionals are evaluated seriallv until one is TRUE, the <ls> is obeyed and control passes to the end of the statement.

7.2 .SWITCH

In the syntax below <int> is an INTEGER variable, and <nc> is the number of cases in the statement. The syntax ais:

.SWITCH(<int>,<nc>)
.CASE(1)
  <ls>
.CASE(2)
  <ls>
.CASE(3)
  <ls>
.OUT-OF-RANGE
  <ls>
.ENDSW

The code generated, when number of cases is 3, is:

      IF(<int>.LT.1 .OR. <int>.GT.<nc>)GOTO 20004
      GOTO(20001,20002,20003),<int>
20001 CONTINUE
      <ls>
      GOTO 20005
20002 CONTINUE
      <ls>
      GOTO 20005
20003 CONTINUE
      <ls>
      GOTO 20005
20004 CONTINUE
      <ls>
      GOTO 20005
20005 CONTINUE

The .OUT-OF-RANGE statement is mandatory.

8 ITERATION STATEMENTS

8.1 LOOPS

The language contains three loop statements, .FOR-.ENDFR is a simple iteration statement akin to the FORTRAN DO statement. .CYCLE is a general Zahn loop construct, .WHILE will be familiar from ALGOL.

8.1.1 .WHILE-.ENDWH

The syntax and code generated are:

.WHILE (<be>).DO
<ls>
.ENDWH

20000 IF (.NOT.(<be>))GOTO 20001 
      <ls> 
      GOTO 20000 
20001 CONTINUE

Note that .WHlLE (<be>) and .ENDWH must occupy single lines.

8.1.2 .FOR-.ENDFR

The syntax and code generated are:

.FOR I = N1,N2,N3 .DO
<ls>
.ENDFR

      DO 20000 I = N1,N2,N3
      <ls>
20000 CONTINUE
      <ls>

8.1.3 .CYCLE-.ENDCY

All reserved words with the exception of .UNTIL in this statement are mandatory. In line with the syntax of .IF and .SWITCH statements, .LIMIT must be the last clause of the epilog before .ENDCY.

The .UNTIL construct has been introduced to provide a mechanism for representing the statements of which .EXITIF is a refinement. For example:

.UNTIL(End of file).IE 
.UNTIL(Top bit set).IE 
.EXITIF(REPLY.LT.O).TOSITU(2)

In the description below, <ns> is the number of distinct exits from the loop, ie. the number of .SITU clauses to follow.

The syntax is as follows followed by the code generated for <ns>=2:

.CYCLE I=N1,N2,N3 .TILL(<ns>).DO
   <ls>
.UNTIL (<text>).IE
.EXITIF(<be>).TOSITU(1)
   <ls>
.EXITIF(<be>).TOSITU(2)
   <ls> 
.REPEAT
.SITU(1)
   <ls>  
.SITU(2)
   <ls> 
.LIMIT
   <ls>
   .ENDCY
   
      DO 20000 I = N1,N2,N3
      <ls>
      ASSIGN 20003 TO KT0001
      IF(<be>) GOTO 20002
      <ls>    
      ASSIGN 20004 TO KT0001
      IF(<be>) GOTO 20002
      <ls> 
20000 CONTINUE
      ASSIGN 20005 TO KT0001
20002 CONTINUE
      GOTO KT0001
20003 CONTINUE
      <ls>
      GOTO 20001
20004 CONTINUE  
      <ls>
      GOTO 20001
20005 CONTINUE
      <ls>
20001 CONTINUE

9 REFINEMENT STATEMENTS

9.1 Refinement

A refinement is introduced by either of the statements:

.C <text>

.N
<lines of text> 
.EN

and is terminated by the statement

.EC

For example:

.C ADVANCE OUTPUT BUFFER POINTER 
   OBUFPR = OBUFPR + 1
.EC

Parallel sequences may be represented by the syntax:

.C         or .N  .....  .EN
    <ls>
    .PARSEP
    <ls>
.EC

ny number of .PARSEP ... <ls> are allowed.

9.2 .OK and .NULL

These statements have been found to be extremely useful in the language DRIL. The code generated by both will be CONTINUE.

9.3 .FAIL

The syntax of this statement and code generated are:

.FAIL(<channel number>,'<message>')

      WRITE(<channel number>,<label>)
<label> FORMAT('(<message>') 
      IF( .TRUE. )STOP

The last line is necessarily contorted to get round the problem of no path to statement in the PRIME FORTRAN compiler.

10 SUEPROGRAM STATEMENTS

ROOTS recognises the statements

      .BLOCK DATA 
      .SUEROUTINE 
      .FUNCTION 
      .INTEGER FUNCTION 
      .INTEGER*4 FUNCTION 
      .REAL FUNCTION 
      .DOUBLE PRECISION FUNCTION 
      .LOGICAL FUNCTION 
      .COMPLEX FUNCTION 
      .RETURN 
      .STOP 
      .END

Note that single spaces must appear in these statements where shown above. The code generated by .STOP is:

      IF(.TRUE.)STOP

To facilitate program monitoring ROOTS recognises statements of the form:

      .CALL .....

Two forms of the statement are allowed:

      .CALL <name>(<argument list>)

ie the addition of a period (.) to the front of a FORTRAN CALL statement. The second form allows the insertion of the routine level after CALL:

      .CALL(<level>)<name>(<argument list>)

Recursive calls are denoted by the symbol * in place of <level>.

The notion of subroutine level comes from a consideration of call graphs, a routine at level n can be called by routines at all levels m#x2264;n and may call routines at all levels k≥n.

There is a need to delimit the MASTER segment (in 1900 terminology) of a program and hence we introduce:

.MASTER 
.ENDM

It is also useful to know where the code of a routine begins and hence we introduce

.BEGIN

The statements

.PROG <text string> 
.ENDP

delimit the entire source.

To facilitate the representation of the level concept in flowcharts, the statements:

.LEVEL <number> 
.SETSEP 
.ENDLEV

are introduced. The structure of a ROOTS program is then represented by the syntax:

.PROG 
.MASTER
  ...
.ENDM 
.LEVEL 1 
.SUBROUTINE
  ...
.END 
.SETSEP 
.SUBROUTINE
  ...
.END 
.SETSEP 
.SUBROUTINE
  ...
.END 
.ENDLEV 
.LEVEL 2
.ENDLEV 
.ENDP

11 INPUT DIRECTION STATEMENTS

11.1 .ADD

It is a frequent source of annoyance that many software tools do not have an equivalent of the $INSERT Facility of the PRIME FORTRAN compiler. ROOTS has such a facility which will increase the utility of tools such as PFORT for investigation of the intermediate FORTRAN code generated by ROOTS. The construct is:

.ADD <filename>

adds the text in <filename> and generates a flowchart of the entire source text, unless preceded by an edit tag. .ADD can be nested to a finite depth.

12 MONITOR STATEMENTS

12.1 .MONITOR

Monitoring w levels are defined by statements enclosed by the reserved words:

.MONITOR 
.ENDMONITOR

Trace, filter and snap-shot levels are defined within this section:

.MONITOR 
.TRACE 
   .T1: DEP(20,7),DET(3),RF(1) .ET 
   .T2: DEP(0,0),DET(10),RF(1) .ET
.ENDTRACE 
.SNAP-SHOT 
   .SS1: DET(20),FORMAT(200) ,SIZE(80) .ESS
   .SS2: DET(25),FORMAT(210) ,SIZE(80) .ESS
.ENDSNAP 
.FILTERS 
   .SF1: (MOD(IT(N),2).EQ.O) .EBF
.ENDFILTERS 
.ENDMONITOR

Statements to be monitored are tagged as follows:

.T <level>: <statement>

where <level> indexes a tracing level defined in the .TRACE section of the MONITOR statement.

Snap shots are produced by the statement:

.SS<index>: <list of variables>

and <index> refers to a snap shot set up in the SNAP-SHOT section of the MONITOR statement.

To invoke monitoring, the .MONITOR statement must be followed by keywords (in any order) indicating the monitoring categories required. The most general form is:

.MONITOR PERFORMANCE,HISTORY,CONTROL,SNAPS

12.2 ASSUMPTION

The syntax of this statement is:

.ASSUMPTION <number>: (<text>)

the code generated is as for a comment statement.

12.3 .ASSERTION

The syntax of this statement is:

.ASSERTION <number>: (<be>)

If the statement is not tagged by a monitoring tag (e.g. .T1:) the code generated is as for a comment statement.

If the statement is tagged, for example:

.T1: .ASSERTION 1: (N.GT.M)

then the code generated is:

      IF(<be>) GOTO 20000 
      STOP <number> 
20000 CONTINUE

The original paper followed these sections by a description of the editing facilities and this was followed by a set of quite complex examples which unfortunately are impossible to read on the version of the paper that survived.