Handling Mutable Information


Besides global variables, tables are another data structure that can be updated. They are motivated by the observation that in certain cases not all information required to construct a term is already available, and we need a mechanism to supply this later. As we will see, tables may also be used to represent cyclic structures.

In Gentle, one cannot modify the fields of a term, but one can supply an immutable key, that refers to a mutable record.

A table is an unbounded collection of records. Each record is identified by a unique key. A record is a list of one or more mutable fields.

A table declaration has the form

  • 'table' Name ( Fields )
where Fields is a comma-separated list of one or more field specifications. The identifier Name serves as a type name for the keys.

A field is specified in the form

  • FieldName : Type

To illustrate the use of tables, let us discuss the so-called basic-block-graph representation of programs. In this representation, the instructions of a program are grouped into blocks (only the last instruction of a block can be a jump; only the first instruction of a block can be the target of a jump).

Each block is characterized by a list of its instructions and a list of its successor blocks.

The basic-block graph can be described by a table:

   'table' BLOCK (Instructions: INSTRLIST, Successors: BLOCKLIST)
This introduces a table of records, where each record has a field Instructions (of type INSTRLIST) and a field Successors (of type BLOCKLIST). It also introduces a new type, BLOCK, the values of which are references to block records.

The type BLOCK can be used in the same way as any other type, e.g. as the type of the fields of a term. Hence we can define the type BLOCKLIST as usual:

   'type' BLOCKLIST
      list(BLOCK, BLOCKLIST)
A new record and its unique key are created by an allocation statement. It has the form
  • Var :: Name
This defines Var as a local variable of the key type Name, holding a unique key of a fresh record. The fields of this record are still undefined.

For example,

   B :: BLOCK
defines the variable B as a new key of a BLOCK record. This key can already be used as a value in terms, and it cannot be altered (hence terms still have the property of being constants). But the associated record can be modified by subsequent statements.

The fields of an entry can be modified and inspected in exactly the same way as a global variable, i.e. by update and query statements.

Instead of a simple variable name, a designator is used that specifies the key and the field:

  • Key ' FieldName
For example,

designates the Successors field of the record associated with the key given by the local variable B.

An update statement

   B'Successors <- nil
sets this field to nil.

A query statement

   B'Successors -> L
accesses the field and copies its value into L.

With the statements

   B'Successors -> OldList
   B'Successors <- list(NewBlock, OldList)
a new block can be inserted into the list of successors of B.

It is a checked run-time error to access a field that has not been defined.

In general, the basic blocks of a program form a graph that contains cycles. This can be expressed with tables, for example:

   'action' BuildLoop(-> BLOCK)

      'rule' BuildLoop(-> B1)

         B1 :: BLOCK
         B2 :: BLOCK

         B1'Instructions <- nil
         B2'Instructions <- nil

         B1'Successors <- list(B2, nil)
         B2'Successors <- list(B1, nil)
After an invocation

   BuildLoop(-> B)
B will refer to a block with one successor, the successor of which is B itself.