The global storage needs of a subcomputation

A defining characteristic of “functional” specifications is the absence of assignments: updates of tables and data structures are expressed by giving the relationship between the new and old values. An obvious implementation allocates separate space for new and old values and may consume a lot of storage. However, even when updates of attributes like symbol tables are expressed functionally, we would like to avoid making copies of the symbol table during attribute evaluation. In other words, if possible, the implementation should have a single global copy of the table that is updated using assignments. Since the value of the global copy changes during computation, the order of evaluation has to be chosen carefully. In this paper, we partition attributes into classes, the problem being to determine if there exists an evaluation order that allows each class to share a global storage area. The solution extends to handle symbol tables for block structured languages.

More precisely, consider a directed acyclic graph D in which vertices represent attribute values to be computed. Associated with each vertex is a label indicating the storage area to be shared by the vertex. Storage used during the evaluation of D is studied by playing a pebble game on D with the following steps: (1) pebble (i.e. place a pebble) on a source; (2) pebble a vertex if all its successors have pebbles (a pebble may be moved to the vertex from one of its successors); (3) pick up a pebble. Each vertex must be pebbled exactly once. The use of global storage is formalized by defining single pebblings, in which at most one of the vertices with a given label has a pebble at any time. The results also apply to a form of pebbling, called chain pebbling, that allows symbol tables for block structured languages to be studied.