The global storage needs of a subcomputation

ABSTRACT

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.

REFERENCES

• 1: A.V. Aho and J. D. Ullman, "Optimization of straight line programs," SIAM J. Computing1(1), pp. 1-19 (March 1972).
• 2: T.P. Baker, Personal communication, November 1983.
• 3: P.A. Bernstein, D. W. Shipman, and W. S. Wong, "Formal aspects of serializability in database concurrency control," IEEE Trans. Software EngineeringSE-5(3), pp. 203-216 (May 1979).
• 4: Gregor V. Bochmann, Semantic evaluation from left to right, Communications of the ACM, v.19 n.2, p.55-62, Feb. 1976 [doi>10.1145/359997.359999]
• 5: Jan Borowiec, Pragmatics in a complier production system, Symposium on Methods of Algorithmic Language Implementation, p.314-340, September 10-13, 1975
• 6: C.A. Brown and P. W. Purdom, Jr, Specifying one-pass bottom-up compilers, Computer Science Dept., Indiana Univ., Bloomington IN (July 1981).
• 7: Rina Cohen , Eli Harry, Automatic generation of near-optimal linear-time translators for non-circular attribute grammars, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.121-134, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567764]
• 8: Patrick Cousot , Radhia Cousot, Systematic design of program analysis frameworks, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.269-282, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567778]
• 9: Rodney Farrow, LINGUIST-86: Yet another translator writing system based on attribute grammars, ACM SIGPLAN Notices, v.17 n.6, p.160-171, June 1982
• 10: Harald Ganzinger, On Storage Optimization for Automatically Generated Compilers, Proceedings of the 4th GI-Conference on Theoretical Computer Science, p.132-141, March 26-28, 1979
• 11: Harald Ganzinger , Robert Giegerich , Ulrich Möncke , Reinhard Wilhelm, A truly generative semantics-directed compiler generator, ACM SIGPLAN Notices, v.17 n.6, p.172-184, June 1982
• 12: Harald Ganzinger , Knut Ripken , Reinhard Wilhelm, MUG1 - an incremental compiler-compiler, Proceedings of the annual conference, p.415-418, October 20-22, 1976, Houston, Texas, United States [doi>10.1145/800191.805629]
• 13: Mehdi Jazayeri , Diane Pozefsky, Space-Efficient Storage Management in an Attribute Grammar Evaluator, ACM Transactions on Programming Languages and Systems (TOPLAS), v.3 n.4, p.388-404, Oct. 1981 [doi>10.1145/357146.357148]
• 14: Neil D. Jones , Steven S. Muchnick, A flexible approach to interprocedural data flow analysis and programs with recursive data structures, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.66-74, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582161]
• 15: Ken Kennedy , Scott K. Warren, Automatic generation of efficient evaluators for attribute grammars, Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, p.32-49, January 19-21, 1976, Atlanta, Georgia [doi>10.1145/800168.811538]
• 16: Ken Kennedy , Jayashree Ramanathan, A Deterministic Attribute Grammar Evaluator Based on Dynamic Scheduling, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.1, p.142-160, July 1979 [doi>10.1145/357062.357072]
• 17: D. E. Knuth, "Semantics of context-free languages," Mathematical Systems Theory2(2), pp. 127-145 (1968). Errata 5(1), pp. 95-96 (1971).
• 18: K. Koskimies and K.-J. Räihä, "Modelling of space-efficient one-pass translation using attribute grammars," Software - Practice and Experience13, pp. 119-129 (1983).
• 19: J. Lewi , M. Huybrechts , Vlaminck K. De , J. Huens, A Programming Methodology in Compiler Construction, Elsevier Science Inc., New York, NY, 1979
• 20: P.M. Lewis II, D. J. Rosenkrantz, and R. E. Stearns, "Attributed translations," J. Computer and System Sciences9, pp. 279-307 (1974).
• 21: Bernard Lorho, Semantic attributes processing in the system DELTA, Symposium on Methods of Algorithmic Language Implementation, p.21-40, September 10-13, 1975
• 22: Ole Lehrmann Madsen, On defining semantics by means of extended attribute grammars, Semantics-Directed Compiler Generation, Proceedings of a Workshop, p.259-299, January 14-18, 1980
• 23: T. Marill, "Computational chains and the simplification of computer programs," IRE Trans. Electronic ComputersEC-11(2), pp. 173-180 (April 1962).
• 24: Christos H. Papadimitriou, The serializability of concurrent database updates, Journal of the ACM (JACM), v.26 n.4, p.631-653, Oct. 1979 [doi>10.1145/322154.322158]
• 25: N. Pippenger, "Pebbling," Proc. Fifth IBM Symp. on Math. Foundations of Computer Science, pp. 1-19 (May 1980).
• 26: K.-J. Räihä, "On attribute grammars and their use in a compiler writing system," Report A-1977-4, Dept. of Computer Science, University of Helsinki (August 1977).
• 27: K.-J. Räihä, "A space management technique for multi-pass attribute evaluators," Report A-1981-4, Dept. of Computer Science, University of Helsinki (November 1981).
• 28: Mikko Saarinen, On Constructing Efficient Evaluators for Attribute Grammars, Proceedings of the Fifth Colloquium on Automata, Languages and Programming, p.382-397, July 17-21, 1978
• 29: D. Schmidt, "Detecting global variables in denotational specifications," manuscript, Computer Science Dept., Edinburgh Univ. (May 1983).
• 30: J. Schwarz, "Verifying the safe use of destructive updates in applicative programs," pp. 395-411 in Program Transformations, 3rd Intl. Symposium on Programming, ed. B. Robinet, Dunod, Paris (1978).
• 31: R. Sethi, "Complete register allocation problems," SIAM J. Computing4(3), pp. 226-248 (September 1975).
• 32: R. Sethi, "A model of concurrent database transactions," 22nd Annual Symposium on Foundations of Computer Science, Nashville TN, pp. 175-184 (October 1981).
• 33: R. Sethi, "Pebble games for studying storage sharing," Theoretical Computer Science19(1), pp. 69-84 (July 1982).
• 34: R.E. Stearns, P. M. Lewis II, and D. J. Rosenkrantz, "Concurrency control for database systems," pp. 19-32 in 17th Annual Symposium on Foundations of Computer Science, Houston Texas (October 1976).

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

General Terms:
Management, Theory