/ GENTLE PRIMER
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
A field is specified in the form
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) nilA new record and its unique key are created by an allocation statement. It has the form
B :: BLOCKdefines 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:
B'Successorsdesignates the Successors field of the record associated with the key given by the local variable B.
An update statement
B'Successors <- nilsets this field to nil.
A query statement
B'Successors -> Laccesses 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.