ML/I


Underlying data structures and functions




January 1977, October 2018



Stephen Fickas


R.D. Eager

Copyright © 1977, 2018 Stephen Fickas, R.D. Eager

Permission is granted to copy and/or modify this document for private use only. Machine readable versions must not be placed on public web sites or FTP sites, or otherwise made generally accessible in an electronic form. Instead, please provide a link to the original document on the official ML/I web site.


[ < ] [ > ]   [Contents] [Index] [ ? ]

ML/I — Underlying data structures and functions

Copyright © 1977, 2018 Stephen Fickas, R.D. Eager

Permission is granted to copy and/or modify this document for private use only. Machine readable versions must not be placed on public web sites or FTP sites, or otherwise made generally accessible in an electronic form. Instead, please provide a link to the original document on the official ML/I web site.

Preface

This document was originally written by Stephen Fickas. It has been rewritten in Texinfo, so that it can be published in both printed and machine readable form; this has necessitated some re-wording and re-ordering of the text. Some minor corrections and clarifications have also been made. The rewrite was carried out by Bob Eager.

The changes have been fairly minor, mainly to fit the document within the Texinfo conventions. Appendix C was added, documenting the subroutines and code sections in the L source. A contents list and index were also added. Reference is also made to ML/I character variables, which are not present in the L version, but are available in the C implementation.


[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

1 Introduction

These notes are a by-product of my efforts in providing in-line documentation to the L version of ML/I. The following sections are arranged in the most conducive way for understanding the documented L code. The notes are general in nature, and for specifics the in-line documentation should be consulted.


[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

1.1 Reference material

Some of the following material can be found on the ML/I website, at http://www.ml1.org.uk.

Three manuals/notes/listings should be obtained before attempting hand simulations of the documented L code:

  1. ML/I User’s Manual, Fourth Edition (or later), P.J. Brown, University of Kent at Canterbury.
  2. Implementing Software Using The L Language, P.J. Brown, University of Kent at Canterbury.
  3. The actual documented L code itself, P.J. Brown, University of Kent at Canterbury.

If only the LOWL or undocumented L version of ML/I are available, then also obtain How ML/I Works, P. J. Brown, 1973. For readers that are more interested in an L mapping, the following material will be useful:

  1. ANSI FORTRAN listing of ML/I, Steve Fickas, Code 5200 Naval Electronics Lab, San Diego, CA 92152.
  2. ML/I Mapping Notes - FORTRAN, Steve Fickas, Code 5200 Naval Electronics Lab, San Diego, CA 92152.
  3. The PL/I L-Map, P. J. Brown, University of Kent at Canterbury.

The above material is available to anyone who agrees that it will not be used in any type of commercial venture.


[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

1.2 Strategy

There is no belying the fact that the L code presents a complex system to be fully understood only after a number of simulated cases are tried. I have found the following procedure (not algorithm, for it does not necessarily halt) to be a good one in understanding the L code (• signifies newline):

  1. After reading The Construction, sketch out a matched skip construction, using, say < as a primary name and > as a secondary and closing delimiter.
  2. Call SIMULATE(X<ABC>Y)
  3. Call SIMULATE(X<A<BC>>Y)
  4. Using different M, D and T options, repeat steps 1, 2 and 3 until the skip is fully understood.
  5. Sketch out the construction resulting from MCDEF X AS Y
  6. Call SIMULATE(A X B)
  7. Sketch out the construction obtained from MCGO in MACNAMES in the L data section.
  8. Call SIMULATE(MCGO L1)
  9. Sketch out the construction obtained from MCDEF in MACNAMES in the L data section.
  10. Call SIMULATE(MCDEF X Y AS %A1.)
  11. Sketch out the construction obtained from MCINS in MACNAMES in the L data section.
  12. Call SIMULATE(X Q Y Z)
  13. At this point, most of the major concepts of the L code should be understood. Still, there are many points still to be covered. I leave it to the reader to work out cases of nodes, nested calls, global vs. local definitions and error routines.

The subroutine SIMULATE is defined as:

SUBROUTINE SIMULATE (INSOURCE)
Starting at MBEGIN, hand-simulate
the L code, obtaining source input
from the passed parameter INSOURCE.
END SIMULATE

[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

2 Low Level Data Structures

The easiest way to understand the L implementation of ML/I is first to understand the underlying data structures. There are three basic data areas in ML/I:

  1. a large contiguous portion of memory used for stacks.
  2. a contiguous portion of memory used for a hash table.
  3. memory allocated to various pointer, number, switch and character variables. Note that the L version does not have character variables.

The size of each area is at the individual implementer’s discretion. Each will be described below in more detail.


[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

2.1 The stacks

See also FSTACK and BSTACK.

ML/I makes use of two stacks called FSTACK (forwards stack) and BSTACK (backwards stack). Given a contiguous section of memory between M and N (M<N), FSTACK will grow towards N and have its bottom at M. Likewise, BSTACK will grow towards M and have its bottom at N. Currently, if they meet in the middle, ML/I is aborted.


[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

2.2 The hash table

See [2], section 6.2.3.

The hash table is made up of a number of pointers (LHV being the number), four additional pointers and, finally, a switch variable. There is also an additional bottom neighbour pointer.

  1. The first LHV pointers.
    It is up to each implementer to define a routine called MDFIND, which takes the current atom being scanned and produces a number K where 0 < K < LHV, the value of LHV also being up to the implementer. It is hoped that MDFIND will efficiently scatter K within this range. As various macros, inserts, etc. are defined, they will be added to the appropriate chain headed by one of these pointers.
  2. The four additional pointers
    These pointers serve a complex purpose and will probably not be fully understood until moving through the code. Briefly, they are used in conjunction with routine CKVALY, to turn off any local definitions when a MCNODEF is called, any local skips when a MCNOSKIP is called, etc. (see [1], section 5.2.5). The initial value for all four is any number greater than a possible pointer value.
  3. The global warning switch
    Used in conjunction with a call on MCWARNG. Initially 7, denoting no warning active, changed to 6 when MCWARNG is called.
  4. Bottom Neighbour
    Although not strictly part of the hash table, a pointer is added to the end of the hash table every time one is stacked (i.e. each time a new level is entered). This pointer points to the start of the previously stacked hash table (or NULLPT for the earliest version), and in this way the stacked hash tables are chained together.

    Note
    Although it was initially stated that only one hash table exists, there now seems to be a proliferation of hash tables. Actually, storage need be allocated for only one hash table; in processing, ML/I will stack and unstack various copies of this original on BSTACK.


[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

2.3 Variables

See [2], section 3.1.

Each variable type can use an implementer defined number of bits, words or bytes, depending on the mapping of the OF function.


[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

3 Miscellaneous Data Types


[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

3.1 Pointers

There are two types of pointers used in ML/I; relative and absolute. Relative pointers (actually, numbers) are used only within the stacks and are defined relative to their location. For example, if a block of 10 pointers are stacked on FSTACK, and we wish the last pointer to point relatively to the first, we would set it to -9.

Absolute pointers correspond with the usual notion of a pointer, their value being the address of some memory location.

                        +-----+
                        |  R  | flags a relative pointer
                        +-----+ 
                        |  A  | flags an absolute pointer
                        +-----+

[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

3.2 Arrays of numbers

Most blocks of numbers (i.e. permanent variables, system variables, etc.) have the following format:

                        +-----+
                        |  .  |
                        +-----+
                        |  .  |
                        |  .  | values
                        |  .  |
                        +-----+
                        |  .  |
                        +-----+
pointer to block -----> |  N  | number of above values
                        +-----+

where the values are stored in reverse order. For example, P0 would be the cell above N and PN-1 would be the top cell.


[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

3.3 Arrays of characters

If character variables are implemented, they are stored as a fixed number of character cells preceded by the actual number of cells used. The fixed number is determined by the second argument to the first call of MCCVAR, and is stored in CVSIZE. The variables are stored in the following format:

                        +-----+
                        |  .  | etc.
                        +-----+
                        |  .  | value2
                        +-----+
                        |  .  | value1
                        +-----+
pointer to block -----> |  N  | number of values
                        +-----+

where the values are stored in reverse order. Each value looks like this:

                        +-----+
                        |  .  |
                        |  .  |
                        |  .  | M cells, determined by MCCVAR
                        |  .  | 
                        |  .  |
                        +-----+
                        |  M  | actual length of value
                        +-----+

[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

3.4 LIDs

A LID is a number N followed by N characters. One or more LIDs can occur in sequence. If there is more than one, they are separated by either a WITHMK or a WTHSMK. As an example, XX WITH ; would be represented as 

                        +-------+
                        |   2   |
                        +-------+
                        |   X   |
                        +-------+
                        |   X   |
                        +-------+
                        |WITHMK |
                        +-------+
                        |   1   |
                        +-------+
                        |   ;   |
                        +-------+

Following are the definitions for various keywords:

  1. SPACE
                            +-------+
                            |   1   |
                            +-------+
                            |       | character for space
                            +-------+
    
  2. SPACES
                            +-------+
                            |   1   |
                            +-------+
                            |       | character for space
                            +-------+
                            |SPCSMK |
                            +-------+
    
  3. SPACES WITH, SPACES WITHS, SPACE WITHS
                            +-------+
                            |   1   |
                            +-------+
                            |       | character for space
                            +-------+
                            |WTHSMK |
                            +-------+
    
  4. WITH SPACES, WITHS SPACE
                            +-------+
                            |WTHSMK |
                            +-------+
                            |SPCSMK |
                            +-------+
    
  5. WITHS SPACES
                            +-------+
                            |WTHSMK |
                            +-------+
                            |   1   |
                            +-------+
                            |       | character for space
                            +-------+
                            |SPCSMK |
                            +-------+
    

[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

3.5 The ERBLOC

There is a contiguous block of storage required for the error block (ERBLOC), which is used by the error routines. This can be reserved on the top of FSTACK, or else in variable storage.


[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

4 The Construction

Perhaps the quintessential structure of ML/I is the construction. Each time a MCDEF(G), MCWARN(G), MCINS(G) or MCSKIP(G) is processed by ML/I, a new construction is built. Constructions exist also for each ML/I operation macro (e.g. MCDEF), but not necessarily on the stack. All local and global constructions reside entirely on one of the two stacks. A construction or structure representation is as shown in the following sections.


[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

4.1 Primary construction

         +-----+
         |  .  |
         |  .  | Replacement text (see type 1 below)
         |  .  |
         +-----+
         |  A  | Hash chain to next construction
         +-----+
         |  R  | OR-LINK to alternative name of same construction
         +-----+
         |  .  | One or more LIDs representing the name of the
         |  .  | primary construction (more than one in the
         |  .  | case of WITH)
         +-----+
         |  R  | NEXT-LINK to next delimiter
         +-----+
         |     | Construction type (0 through 4)
         +-----+
         |  .  |
         |  .  | Information block (depends on type)
         |  .  |
         +-----+

The items above are, in more detail:

  1. Hash chain
    This is used to form a list which originates in the hash table. Each primary construction on the list has been mapped into the same K and thus belongs to an equivalence class defined by MDFIND.
  2. OR-LINK
    Normally ENDCHN, else used to link together alternative names (i.e. primary constructions) for this construction. Before studying the following example, it will probably be necessary to review [1], section 5.1.3.

    An example macro definition, and its corresponding representation, is:

    MCDEF N1 OPT A N1 OR B ALL C AS D
          +-----+
          |  D  |
          +-----+
    +---> |     | --> Hash chain A
    |     +-----+                  +-----+
    |     |     | ---------------> |     | --> Hash chain B
    |     +-----+                  +-----+
    |     |  1  |                  | 00  | OR-LINK
    |     +-----+                  +-----+
    |     |  A  |                  |  1  |
    |     +-----+                  +-----+
    +---- | -4  | NEXT-LINK        |  B  |
          +-----+                  +-----+
          |  1  |                  |     | --> Secondary delimiter for C
          +-----+                  +-----+
          | -6  | <-- Info block   |  1  |
          +-----+                  +-----+
          | -8  |                  |     |
          +-----+                  |     | <-- Info block
          |  3  |                  |     |
          +-----+                  +-----+
    

    ML/I will then recognise as a macro call:

        B ..... C
      A B ..... C
    A A B ..... C
    

    etc.

  3. NEXT-LINK
    Points at the next delimiter to be matched.

    This is normally a secondary delimiter, but in some cases may be another primary construction (see (b) above).

  4. Construction type
    0 for STOP-MARKER
    1 for MACRO
    2 for WARNING-MARKER
    3 for INSERT
    4 for SKIP
    

[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

4.2 Information blocks

  1. Type = 0 STOP-MARKER
    No information block
  2. Type = 1 MACRO
    There are two types of macros; user defined substitution macros, and ML/I defined operation macros. They can be differentiated by the first element of their information block; if this is < 0 or 2, this is a substitution macro; if it is 0 or 1, this is an operation macro. Other values are unused and undefined.

    A substitution macro information block looks like this:

          +-----+
          |  2  | optional STRMK
          +-----+
          |  R  | --> negative offset to end + 1
          +-----+
          |  R  | --> negative offset to start
          +-----+
          |     | number of temporary variables
          +-----+
    

    If the optional STRMK is present, then this is a straight scan macro (see [1], section 2.9).

    The two negative offsets refer to the replacement text in the primary construction.

    As an example, after ML/I had fully processed

    MCDEF X AS Y
    

    the following construction would appear on the hash chain associated with X:

          +-----+
          |  Y  | replacement text
          +-----+
          |     | --> hash chain X
          +-----+
          | 00  | OR-LINK
          +-----+
          |  1  |
          +-----+
          |  X  |
          +-----+
          | 00  | NEXT-LINK
          +-----+
          |  1  |
          +-----+
          | -6  | Info block
          +-----+
          | -8  |
          +-----+
          |  3  |
          +-----+
    

    An operation macro information block looks like this:

          +-----+
          |  .  | LOCMK (1) for local macros, else OPMK (2)
          +-----+
          |  .  | Operation type (0-15)
          +-----+
    
  3. Type = 2 WARNING-MARKER

    No information block
  4. Type = 3 INSERT
          +-----+
          |  .  | PINSMK (2) or UINSMK (3)
          +-----+
    

    PINSMK for protected insert, UINSMK for unprotected insert (see [1], section 2.6.8).

  5. Type = 4 SKIP
          +-----+
          |  .  | flags (only least significant three bits used)
          +-----+
    

    Bit 0 = 1 if matched skip (M option) (least significant bit)
    Bit 1 = 1 if text copy (T option)
    Bit 2 = 1 if delimiter copy (D option)


[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

4.3 Secondary delimiters

      +-----+
      |  R  | OR-LINK
      +-----+
      |  .  |
      |  .  | LID(s)
      |  .  |
      +-----+
      |  R  | NEXT-LINK
      +-----+

As can be seen, secondary delimiters have a similar but abbreviated format to the primary construction. They are used to hold delimiters which follow the primary name. As an example,

MCDEF MAIN1 SECDl SECD2 AS ...

would result in

                              +-----+
      (MAIN1)   +-----------> | 00  |
      +-----+   |             +-----+
      |  .  |   |             |  5  |
      |  .  |   |             +-----+
      |  .  |   |             |  S  |
      +-----+   |             +-----+
      |     |---+ NEXT-LINK   |  E  |
      +-----+                 +-----+
      |  .  |                 |  C  |
      |  .  |                 +-----+
      |  .  |                 |  D  |
      +-----+                 +-----+
                              |  1  |
                              +-----+       +-----+
                              |     | ----> | 00  |
                              +-----+       +-----+
                                            |  5  |
                                            +-----+
                                            |  S  |
                                            +-----+
                                            |  E  |
                                            +-----+
                                            |  C  |
                                            +-----+
                                            |  D  |
                                            +-----+
                                            |  2  |
                                            +-----+
                                            | 00  |
                                            +-----+

The OR-LINK is used to chain together delimiters found in an option block. As an example:

MCDEF X OPT A OR B ALL C AS ...

would result in:

 primary construction         +-----+
      for X                   | 00  |
         |                    +-----+
         V                    |  1  |
      +-----+                 +-----+
      |  .  |                 |  B  |
      +-----+                 +-----+
      |  1  |              +- |  .  |
      +-----+              |  +-----+
      |  A  |              |
      +-----+              V
      |  .  | --> secondary delimiter for C
      +-----+

The NEXT-LINK can be:

  1. a pointer to the next delimiter required;
  2. ENDCHN, signifying this is the last delimiter, or
  3. EXCLMK, signifying this is the last delimiter, and in addition that this is an exclusive delimiter (see [1], section 3.5).

[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

5 FSTACK

The top pointer of FSTACK is FFPT, which points at the first available cell (contrast with LFPT). After finishing the initialisation code at MBEGIN, FSTACK will be as follows:

      +-----+
      |  .  |
      |  .  | <-- predefined global macros (possibly empty)
      |  .  |
      +-----+
      |  .  | <-- permanent variables
      |  .  |
      |  .  | <-- P1
      +-----+
      |     | <-- number of permanent variables
      +-----+
      |  .  |
      |  .  | <-- FSTACK free space
      |  .  |
      +-----+

All global constructions are retained on the bottom of FSTACK. Since the ML/I macros defined in the MACNAMES section are global, they may be placed here. When the user calls upon ML/I macros such as MCDEFG or MCSKIPG, they are defining additional global constructs which must be included on FSTACK. This is accomplished by inserting the new global construction in between the current global constructions and the top of the permanent variables (see MKROOM routine), moving everything down to make room.

If character variables are implemented, a single value of zero is stacked on FSTACK immediately after the number of permanent variables; this signifies the number of character variables (initially none), and CVARPT is set to point to this.


[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

6 BSTACK

The top pointer of BSTACK is LFPT, which points at the last used cell. After finishing the initialisation code at MBEGIN, BSTACK looks as follows:

           +-----+
           |  .  |
           |  .  | <-- BSTACK free space
           |  .  |
           +-----+
  LFPT --> |  .  |
           |  .  | <-- copy of hash table
           |  .  |
           +-----+
 ENDPT --> | 00  | <-- hash table link
           +-----+

All local constructions are eventually placed on BSTACK. Note that this means a hash chain pointer to a global definition will always be less than LFPT. This fact is used in differentiating between the two.


[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

7 Recognition

Once the basic data structures of ML/I are understood, it is left to study the various ways ML/I manipulates these structures to produce the desired results. There are two basic actions which ML/I performs:

  1. construction evaluation, which involves building new constructions, setting macro time variables, etc. and
  2. recognising previously defined constructions.

Since the second is a prerequisite to the first, it may be desirable to understand this section before moving on to the next, which deals with the evaluation of a recognised construction. Ignoring the STOP-MARKER, there are four types of construction:

  1. MACRO
  2. WARNING-MARKER
  3. INSERT
  4. SKIP

All are evaluated in similar fashion, but the MACRO construction has been chosen to follow as an example, mainly because it is the most difficult of the four. Let us assume that the user has typed in:

MCDEF A B C AS D

[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

7.1 Recognising the primary name

The section of code at BSNAME is responsible for searching the primary constructions, looking for a match on the current atom. In our example, the current atom is MCDEF, and a match will be found with the primary construction set up in the MACNAMES section. Following is a diagram of the MCDEF construction set up in the MACNAMES and DELS sections. The $ sign is used to represent a newline. Readers may wish to review these two sections for their own verification.

 +-----+
 |     | --> Hash chain for MCDEF
 +-----+
 | 00  | No alternative names
 +-----+
 |  5  |
 +-----+
 |  M  |
 +-----+
 |  C  |
 +-----+
 |  D  |
 +-----+
 |  E  |
 +-----+
 |  F  |
 +-----+         +-----+         +-----+
 |     | ------> |     | ---+--> |     | ------> DSSAS ...
 +-----+         +-----+    |    +-----+
 |  1  |         |  4  |    |    |  2  |
 +-----+         +-----+    |    +-----+
 |  1  |         |  V  |    |    |  A  |
 +-----+         +-----+    |    +-----+
 |  4  |         |  A  |    |    |  S  |
 +-----+         +-----+    |    +-----+         +-----+
                 |  R  |    |    |     | ------> | 00  |
                 +-----+    |    +-----+         +-----+
                 |  S  |    |                    |  1  |
                 +-----+    |                    +-----+
                 |     | -->+                    |  $  |
                 +-----+                         +-----+
                                                 | 00  |
                                                 +-----+

The TEBEST routine will decipher this as a MACRO type construction, and set the variable BESTPL so as to jump at BSSWIT accordingly (i.e. to CALLO).


[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

7.2 Delimiter recognition

After the primary name has been matched, ML/I attempts to find each of the secondary delimiters defined by the NEXT-LINK chain. In our example, ML/I will continue reading in characters (i.e. the first argument A B C) until either a VARS, AS, or SSAS is matched. When the AS of our example is read, CMPARE will match it and TEBEST, after determining that it is a secondary delimiter, will set BESTPL so as to jump to DELLO at BSSWIT.

ML/I will determine that AS is not the last or closing delimiter, and so continue reading characters (i.e. the second argument D) until the next delimiter (newline) is matched, again shifting control to DELLO. ML/I notes that this is the last delimiter, so searching is halted. One by-product of the above actions is an argument vector, which is constructed on BSTACK.

Below is the status of the two stacks at this point; once again, the $ sign is used to represent a newline.

         +-----+
         |     | other FSTACK info
         +-----+
  1 ---> |  M  |
         +-----+
         |  C  |
         +-----+
         |  D  |
         +-----+              +-----+
         |  E  |    LFPT ---> |     | ---> FFPT
         +-----+              +-----+
         |  F  |              |  A  | ---> 5
         +-----+              +-----+
  2 ---> |     |              |  A  | ---> 4
         +-----+              +-----+
         |  A  |              |  A  | ---> 3
         +-----+              +-----+
         |     |              |  A  | ---> 2
         +-----+              +-----+
         |  B  |              |  A  | ---> 1
         +-----+              +-----+
         |     |  DBUGPT ---> |  .  |
         +-----+              |  .  | Stacked SDB
         |  C  |              |  .  |
         +-----+              +-----+
         |     |              |  .  |
         +-----+              |  .  | other BSTACK info
  3 ---> |  A  |              |  .  |
         +-----+              +-----+
         |  S  |
         +-----+
  4 ---> |     |
         +-----+
         |  D  |
         +-----+
  5 ---> |  $  |
         +-----+
FFPT --> |     |
         +-----+

[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

7.3 Nested constructions

If, while searching for the delimiters by the procedure described above, a nested construction call is found, then note the following actions:

  1. Nested macro call
    In our example, suppose that MCDEF A C AS Z had been previously typed. While searching for the AS in our current example, ML/I would have discovered the nested call on A. The action of ML/I in this case would then be:
    1. suspend the current search for AS,
    2. process the macro A in the same fashion described earlier in this section, i.e. find all delimiters, and
    3. resume looking for AS.

    Note that at this stage A B C is not replaced by Z, but is merely scanned over so that the search for AS can be resumed.

  2. Nested skip call
    Similar to above in that the current search is suspended until a closing skip delimiter is found, whereupon the suspended search is resumed.
  3. Nested insert call
    In a similar way to the previous two, while the current search is suspended, the insert delimiters will be matched, after which the suspended search is resumed.

It should be clear from the above description why it is not allowed to use macros in place of delimiters in the hope that they will be evaluated and reduced to the desired delimiter. As an example, suppose we are given the following definitions:

MCDEF Q AS B
MCDEF A B AS . . .

then we might expect the call

A ... Q

to be correctly matched. We know that it will not, for even though Q will be recognised as a macro, it will not be evaluated (i.e. replaced by B), and so ML/I will vainly search for the closing delimiter B.

The next section will describe the actions of ML/I after construction evaluation.


[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

8 Construction Evaluation

This section deals with the actions taken by ML/I once a construction has been recognised. When an example is called for, we will carry on with the example started in Recognition, i.e. MCDEF A B C AS D.


[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

8.1 Evaluating arguments – the STKARG routine

In Recognition, ML/I skipped over any nested constructions found while searching for delimiters. Before evaluation can proceed on MCDEF, each argument must be evaluated to catch any nested calls. The STKARG routine is used by ML/I for this purpose, evaluating a specific argument. When STKARG is called, ARGN0 contains the argument number to be evaluated. STKARG then finds where the argument starts and ends in FSTACK, and jumps back to the construction recognition loop to scan the argument. Basically, we are back to Recognition, trying to recognise a primary construction. We can see then that STKARG is a recursive routine, for if any constructions are recognised in an argument, they in turn will eventually lead to another call on STKARG, potentially ad infinitum.

The following diagram shows the call MCDEF A B C AS D before link-up.

     +-----+
     |  .  |
     |  .  | original source text
     |  .  |
     +-----+
     |  D  | evaluated form of argument 2
     +-----+
     |  A  |
     |     |
     |  B  | evaluated form of argument 1
     |     | (no longer needed)
     |  C  |
     +-----+
     | 00  | Hash chain for A
     +-----+
     | 00  | OR-LINK
     +-----+
     |  1  |
     +-----+
+--- |  A  |
|    +-----+
|    |  5  | NEXT-LINK
|    +-----+
|    |  1  |
|    +-----+
|    | -6  | <-- Info block
|    +-----+
|    | -8  |
|    +-----+
|    |  3  |
|    +-----+
+--> | 00  | OR-LINK for secondary delimiter B
     +-----+
     |  1  |
     +-----+
     |  B  |
     +-----+
+--- |  1  | NEXT-LINK
|    +-----+
+--> | 00  | OR-LINK for secondary delimiter C
     +-----+
     |  1  |
     +-----+
     |  C  |
     +-----+
     | 00  |
     +-----+
     |  .  |
     |  .  | FSTACK free space
     |  .  |
     +-----+

When control does return from STKARG (LINK-BACK) for the final time, we are guaranteed that all nested calls have been evaluated, and FSTACK will be as follows:

           +-----+
           |  .  |
           |  .  | globals, permanent variables,
           |  .  | etc.
           |  .  |
           +-----+
           |  .  |
           |  .  | original source text
           |  .  | (e.g. MCDEF A B C AS D)
           |  .  |
           +-----+
           |  .  |
           |  .  | possible other information
   SPT --> |  .  |
           +-----+
           |  .  | evaluated argument N
           |  .  |
           |  .  |
           +-----+
STOPPT --> |  .  |
           |  .  | free space
           |  .  |
           +-----+

[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

8.2 Building a construction

Depending on the construction type (i.e. MCSET, MCDEF, user macro, etc.), prescribed actions are carried out on the evaluated arguments. To show what these actions are in the MCDEF case, we will carry on with the example started in Recognition. After finding the closing delimiter, ML/I will transfer control to DEF, the MCDEF handler. There are two arguments to worry about: the replacement text D and the structure representation A B C. The strategy ML/I will use is:

  1. evaluate the replacement text and place on FSTACK
  2. evaluate the structure representation and place on FSTACK
  3. build a construction as defined in The Construction on FSTACK using results from a. and b.

The result can be seen in Evaluating arguments – STKARG. If arguments 1 or 2 had contained any nested calls, their evaluated forms would have reflected the results of these calls. In our example, since no nested calls were involved, the call to STKARG was almost nothing more than a straight copy from the original source text to the evaluated form, (almost, because leading and trailing spaces are deleted).

In arriving at the diagram in Evaluating arguments – STKARG, we have glossed over a large amount of ML/I processing in the EVTREE section, and in the GETDEL routine. These sections of code deal with the sticky details of parsing a structure, and will need to be worked through by hand to appreciate their function.


[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

8.3 Link-up

The final step of ML/I is to link the newly built construction into the appropriate hash chain, in our case MDFIND(A). Preliminary to this link-up, ML/I will move the construction up adjacent to the replacement text, overwriting evaluated argument 1 which is no longer needed. Since our construction is a local one (MCDEF instead of MCDEFG), it will be moved to the top of BSTACK. Next, the correct hash chain will be found and ML/I will insert the new construction at the head of the chain. BSTACK will be as follows:

     +-----+
     |  D  |
     +-----+
+--> |     | ---> previous head of chain
|    +-----+
|    |  .  |
|    |  .  | rest of construction
|    |  .  |
|    +-----+
|    |  .  |
|    |  .  | other BSTACK info
|    |  .  |
|    +-----+
|    |  .  |
|    |  .  | most current hash table
|    |  .  |
|    +-----+
+--- |     | entry for MDFIND(A)
     +-----+
     |  .  |
     |  .  |
     |  .  |
     +-----+
     |  .  |
     |  .  | rest of BSTACK
     |  .  |
     +-----+

This concludes ML/I processing of MCDEF A B C AS D.


[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

References

  1. Brown, P.J. and Eager, R.D., ML/I User’s Manual, Sixth Edition.
  2. Brown, P.J. and Eager, R.D., Implementing software using the L language.

[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

Appendix A Description of uses of variables

The following summarises the uses of important variables in the MI-logic of ML/I. Note that line numbers may vary slightly, depending on the exact version of the L code available.

VariableDeclaredMeaning
in line
ALLPT61head of chain of nextlinks to be attached to delimiter following ALL
ARGCT13in SDB
ARGLEN49length of value of current argument
ARGNO24in SDB
ARGPT19in SDB
BESLIN123best-so-far value of LINECT
BESPT96best-so-far value of SPT
BESTPL120switch value used in basic scan routine
BFNDPT87best-so-far value of FNDPT
BINDIC111best-so-far value of INDIC
BINFPT89best-so-far value of INFOPT
CALTYP124first number in information block
CHANPT94used in CHAIN FROM operation
CHLINK116used in CHAIN FROM operation
CINFPT103points at information block in primary construction
CLLFPT101points to top entry after scanning information is stacked
CONSW150for syntax checking (see EVTREE and GETDEL)
COPDSW131for skips. Reflects setting of delimiter option.
COPTSW130for skips. Reflects setting of text option.
CVARPT72points at character variables
CVNUM74number of character variables
DBUGPT20in SDB
DBUGSW25in SDB
DELCT145count of delimiters
DELPT104head of chain of delimiters being searched for
ENDPT71points at end of BSTACK
ERIAPT95points at value of operation macro argument
ETEMPT84points at error block (temporary storage for EDB)
EXIDPT140temporary storage for IDPT
EXITSW151for syntax checking (see EVTREE)
FFPT90points to first free location on FSTACK
FLAGPT158points at flag
FNDPT86points at LID when a name is found
GHSHPT845points at global hash table
GLBWSW705value 6 if there is a global warning; value 7 otherwise
HASHPT30in SDB
HTABPT97points at current hash table
IDLEN119length of current identifier
IDPT98points at current identifier
INDIC115contents of nextlink
INFFPT34in SDB
INFOPT88points beyond currently matched LID
INSW132to set DBUGSW, and as implied parameter to SETPTS
INVOCT113count of macro calls
KEYSW149for syntax checking (see EVTREE and GETDEL)
KNPT83temporary storage
LABPT33in SDB
LEVEL112level of macros and inserts
LFPT73points at top of BSTACK (last used location)
LINECT23in SDB
LINKPT48link for STKARG
LNODPT139points at topmost node entry on BSTACK
MASKSW129mask used to indicate which types of construction are recognised
MCHLIN22in SDB
MEVAL122miscellaneous. Used for numerical values calculated at macro time
MHSHPT46value of HASHPT when macro was called
MTCHPT31in SDB
MTYPE175type of items to be printed
NARGPT102points at argument vector + 1
NDEFPT143destination of newly defined construction
NEGVAL162indicates if result is to be negative
NESTLV109nesting level of calls and skips during scanning
NNODPT138points at current node entry on BSTACK
NODEPT137head of chain of links to be attached to next delimiter
NODESW148for syntax checking (EVTREE and GETDEL)
NTYPSW53type of construction being defined
OFFSET121offset in hash table
OHSW37in SDB
OLDSPT142previous value of SPT
OLIDPT157temporary storage for IDPT
OLLFPT141previous value of LFPT
OP1160LHS operand
OPLEV110level of operation macros and inserts
OPSW164“operation expected” switch (see GETEXP)
OPTHPT663head of orlink chain
OPTLEV146level of OPT-ALL brackets
OPTPT62last entry on orlink chain
OPTYP50type, e.g. global, local, insert. Also other uses
PARNM117formal parameter of type number
PARPT91formal parameter of type pointer
PARSW128formal parameter of type switch
PRSTPT172start of current hash table (see PRCTXT)
PRTAPT173counts down hash table (see PRCTXT)
PRTBPT174follows down hash chains (see PRCTXT)
PVARPT72points at permanent variables
PVNUM74number of permanent variables
SKIPLV108level of skip nesting
SKLIN36in SDB
SKVAL35in SDB
SPT21in SDB
SQNUM51safe variable, miscellaneous uses
SQPT47safe variable, miscellaneous uses
SQSW52safe variable, miscellaneous uses
STAKPT18in SDB
STFFPT100points at start of global macros
STOPPT32in SDB
SUM161running total
TEMAPT93temporary pointer
TEMP114temporary number
TEMPSW127temporary switch
TEMAPT92temporary pointer
TEMPT92temporary pointer
TIDPT99temporary storage for IDPT
TLINCT125temporary storage for LINECT
TOPSPT45points at latest OPDB on BSTACK
TSPT100temporary storage for SPT
TVARPT29in SDB
TYPE118type of construction name
VARPT156points at vector of variables
VARSW165“variable expected” switch (see GETEXP)
WNIDPT106temporary storage for IDPT
WNSPT105temporary storage for SPT
WSW166written argument or delimiter

[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

Appendix B Uses of variables in SDB

This Appendix describes the uses of the variables declared in the Scanning Description Block (SDB), and their values in each of the main scanning states.

If this table looks messy in HTML, try making the window smaller.


Name of variable
1.
Scanning
source text
2.
Scanning
replacement text
3.
Scanning
argument
or delimiter
4.
Evaluating
operation
macro or first insert
ARGCTcounts number of arguments when nested construction is scannednot used
STAKPTNULLPTpoints at latest SDB on stack ..............................
ARGPTNULLPTpoints at argument vectorcontaining text valuecalling value
DBUGPTnot usedpoints at orlink preceding macro namepoints at argument vector in which argument or delimiter is includedpoints at argument vector
MCHLINset to current value of LINECT when a nested construction is encounterednot used
LINECTline count of current text ........................................not used
ARGNOnot usednot usednumber of argument or delimiternumber of argument currently being processed
DBUGSW012 for operation macro argument
4 for substitution macro argument
6 for delimiter
5
HASHPTpoints at local hash tableU insert: calling value
P insert: containing text value
calling value
TVARPTNULLPTpoints at temporary variablescontaining text valuecalling value
MTCHPTwhen a nested construction is encountered, this is set to point at the orlink of this constructionused as workspace
SPTpoints at last scanned character ..............................used in scanning values of arguments
STOPPTNULLPTpoints one beyond last character of current textpoints one beyond end of latest argument
LABPTNULLPThead of chain of labels ..........not used
INFFPTpoints at start of source text on FSTACKnot usedfor operation macro argument: 4;
otherwise undefined
value of FFPT when operation macro was called
SKVALif not scanning call or insert, then number of designated label for forward MCGO, zero if none in progress. If scanning call or insert, then (-1 - (above value))not used
OHSWtrue if a new hash table has been stacked for this level; false otherwisenot used
SKLINif in forward MCGO, then line number in which MCGO occurrednot used

[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

Appendix C List of subroutines and code sections in L

The following lists all of the sections, subroutines and other important areas of code in the L source.

NameSectionTypeDeclared
in line
ADVNCEMAINSUBSSubroutine383
BUMPFFMAINSUBSSubroutine395
CHATOMMAINSUBSSubroutine406
CHEKIDMAINSUBSSubroutine418
CKVALYMAINSUBSSubroutine430
CMPAREMAINSUBSSubroutine442
CORECTMAINSUBSSubroutine460
DECALVMAINSUBSSubroutine471
DECLFMAINSUBSSubroutine484
DEFSUBSSection1448
ENCALLMAINSUBSSubroutine495
ENVPRSection2116
ER1TSTMAINSUBSSubroutine511
ERMTSTERRSubroutine1773
ERRSection1712
ERSICERRSubroutine1743
ERSNWERRSubroutine1759
ERTESTDEFSUBSSubroutine1450
GARGCHMAINSUBSSubroutine523
GETDELDEFSUBSSubroutine1460
GETEXPMAINSUBSSubroutine535
GMEADDMAINSUBSSubroutine584
GSATOMMAINSUBSSubroutine610
GSRATMDEFSUBSSubroutine1610
GTATOMMAINSUBSSubroutine626
INVALSSection8
JOINCHDEFSUBSSubroutine1622
KEYSRCDEFSUBSSubroutine1639
LUDELMAINSUBSSubroutine652
LULAYKMAINSUBSSubroutine665
MAINSection26
MAINSUBSSection380
MCALTERMACOPMACSCode for1024
MCDEFMACOPMACSCode for1238
MCGOMACOPMACSCode for1056
MCINSMACOPMACSCode for1260
MCLENGMACOPMACSCode for1135
MCNO---OPMACSCode for1216
MCNOTEMACOPMACSCode for1148
MCPVARMACOPMACSCode for1161
MCSETMACOPMACSCode for1175
MCSKIPMACOPMACSCode for1277
MCSUBMACOPMACSCode for1191
MCWARNMACOPMACSCode for1230
MKROOMMAINSUBSSubroutine688
OPEXITMAINSUBSSubroutine726
OPMACSSection1022
PLNODEDEFSUBSSubroutine1652
PRARGMAINSUBSSubroutine737
PRCTXTERRSubroutine1834
PRENVENVPRSubroutine2118
PRERRERRSubroutine1913
PRIDERRSubroutine1923
PRLIDERRSubroutine1965
PRLINOERRSubroutine1982
PRMISSERRSubroutine1993
PRNAMEERRSubroutine2027
PRNFNDERRSubroutine2041
PRNUMERRSubroutine2053
PRSCANMAINSUBSSubroutine761
PRTABLENVPRSubroutine2137
PRTYPEERRSubroutine2065
PRVIZERRSubroutine2086
RESSPMAINSUBSSubroutine774
SBSTPLMAINSUBSSubroutine796
SETPTSMAINSUBSSubroutine808
SETYPEERRSubroutine2100
SKLABMAINSUBSSubroutine821
SMSKSWMAINSUBSSubroutine837
SNODCHDEFSUBSSubroutine1682
SUBCHKMAINSUBSSubroutine847
TEBESTMAINSUBSSubroutine884
TESDELMAINSUBSSubroutine867
TESPACDEFSUBSSubroutine1697
TEWITHMAINSUBSSubroutine948
UNOPDBMAINSUBSSubroutine959
UNSDBMAINSUBSSubroutine974

[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

Index

Jump to:   A   B   C   D   E   F   G   H   I   L   M   N   O   P   R   S   T   U   W  
Index Entry  Section

A
absolute pointers 3.1 Pointers
argument evaluation 8.1 Evaluating arguments – the STKARG routine
arrays of characters 3.3 Arrays of characters
arrays of numbers 3.2 Arrays of numbers

B
block, information 4.2 Information blocks
bottom neighbour 2.2 The hash table
BSNAME 7.1 Recognising the primary name
BSTACK 2.1 The stacks
BSTACK 6 BSTACK
building a construction 8.2 Building a construction

C
characters, arrays of 3.3 Arrays of characters
construction 4 The Construction
construction evaluation 8 Construction Evaluation
construction, building 8.2 Building a construction
construction, global 5 FSTACK
construction, nested 7.3 Nested constructions
construction, primary 4.1 Primary construction

D
data elements 2 Low Level Data Structures
data structures 2 Low Level Data Structures
delimiter copy (skip) 4.2 Information blocks
delimiter recognition 7.2 Delimiter recognition
delimiter, exclusive 4.3 Secondary delimiters
delimiter, secondary 4.3 Secondary delimiters

E
ENDCHN 4.1 Primary construction
ENDCHN 4.3 Secondary delimiters
ERBLOC 3.5 The ERBLOC
error block 3.5 The ERBLOC
evaluation, argument 8.1 Evaluating arguments – the STKARG routine
evaluation, construction 8 Construction Evaluation
EXCLMK 4.3 Secondary delimiters
exclusive delimiter 4.3 Secondary delimiters

F
FFPT 5 FSTACK
FORTRAN 1.1 Reference material
FSTACK 2.1 The stacks
FSTACK 5 FSTACK

G
global construction 5 FSTACK
global warning switch 2.2 The hash table

H
hash chain 4.1 Primary construction
hash table 2.2 The hash table

I
information block 4.2 Information blocks
INSERT 4.2 Information blocks
introduction 1 Introduction

L
LFPT 6 BSTACK
LHV 2.2 The hash table
LID 3.4 LIDs
link-up 8.3 Link-up
low level data structures 2 Low Level Data Structures

M
MACRO 4.2 Information blocks
matched skip 4.2 Information blocks
MDFIND 2.2 The hash table
MKROOM 5 FSTACK

N
neighbour, bottom 2.2 The hash table
nested construction 7.3 Nested constructions
NEXT-LINK 4.1 Primary construction
numbers, arrays of 3.2 Arrays of numbers

O
OR-LINK 4.1 Primary construction

P
PINSMK 4.2 Information blocks
PL/I 1.1 Reference material
pointers 3.1 Pointers
primary construction 4.1 Primary construction
primary name recognition 7.1 Recognising the primary name

R
recognition 7 Recognition
recognition, delimiter 7.2 Delimiter recognition
recognition, primary name 7.1 Recognising the primary name
reference material 1.1 Reference material
relative pointers 3.1 Pointers

S
secondary delimiter 4.3 Secondary delimiters
SIMULATE 1.2 Strategy
SKIP 4.2 Information blocks
SPACE 3.4 LIDs
SPACE WITHS 3.4 LIDs
SPACES 3.4 LIDs
SPACES WITH 3.4 LIDs
SPACES WITHS 3.4 LIDs
SPCSMK 3.4 LIDs
SPCSMK 3.4 LIDs
stacks 2.1 The stacks
STKARG 8.1 Evaluating arguments – the STKARG routine
STOP-MARKER 4.2 Information blocks
straight scan macro 4.2 Information blocks
strategy 1.2 Strategy
STRMK 4.2 Information blocks
structures, data 2 Low Level Data Structures
switch, global warning 2.2 The hash table

T
table, hash 2.2 The hash table
text copy (skip) 4.2 Information blocks

U
UINSMK 4.2 Information blocks

W
warning, global switch 2.2 The hash table
WARNING-MARKER 4.2 Information blocks
WITH SPACES 3.4 LIDs
WITHMK 3.4 LIDs
WITHS SPACE 3.4 LIDs
WITHS SPACES 3.4 LIDs
WTHSMK 3.4 LIDs
WTHSMK 3.4 LIDs

Jump to:   A   B   C   D   E   F   G   H   I   L   M   N   O   P   R   S   T   U   W  

[Top] [Contents] [Index] [ ? ]

Table of Contents


[Top] [Contents] [Index] [ ? ]

About This Document

This document was generated on October 1, 2018 using texi2html 5.0.

The buttons in the navigation panels have the following meaning:

Button Name Go to From 1.2.3 go to
[ << ] FastBack Beginning of this chapter or previous chapter 1
[ < ] Back Previous section in reading order 1.2.2
[ Up ] Up Up section 1.2
[ > ] Forward Next section in reading order 1.2.4
[ >> ] FastForward Next chapter 2
[Top] Top Cover (top) of document  
[Contents] Contents Table of contents  
[Index] Index Index  
[ ? ] About About (help)  

where the Example assumes that the current position is at Subsubsection One-Two-Three of a document of the following structure:


This document was generated on October 1, 2018 using texi2html 5.0.