The aggregate update problem in functional programming systems

ABSTRACT

We discuss the problem of efficiently implementing aggregates (contiguous data structures) such as arrays in functional programming systems. Simple changes to an aggregate conceptually involve making a new copy of the aggregate differing only in the changed component, but such copying can be expensive. We present both static and dynamic techniques for avoiding this copying, and argue that they allow one to program functionally using aggregates, without loss of efficiency over conventional programs.1

REFERENCES

• 1: Alfred V. Aho , Jeffrey D. Ullman, Principles of Compiler Design (Addison-Wesley series in computer science and information processing), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1977
• 2: John Backus, Can programming be liberated from the von Neumann style?: a functional style and its algebra of programs, Communications of the ACM, v.21 n.8, p.613-641, Aug. 1978 [doi>10.1145/359576.359579]
• 3: 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]
• 4: 4. Fisher, J. A. Very Long Word Architectures. 253, Yale University, Dec., 1982.
• 5: 5. Hudak, P. ALFL Reference Manual and Programmers Guide. Technical Report YALEU/DCS/TR-322, Yale University, July, 1984.
• 6: 6. Hudak, P. and Young, J. A Set-theoretic Characterization of Function Strictness. draft form, 1984.
• 7: Paul Hudak , David Kranz, A combinator-based compiler for a functional language, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.122-132, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800523]
• 8: 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]
• 9: 9. Kahn, K. "Implementation of Arrays". PROLOG Digest 2, 4 (Jan. 1984).
• 10: 10. Keller, R. M. FEL programmer's guide. AMPS TR 7, University of Utah, March, 1982.
• 11: 11. Lamport, L. "Sometime" is sometimes "not never" Research Report CSL-86 #49, SRI International, Jan., 1979.
• 12: Zohar Manna, Introduction to Mathematical Theory of Computation, McGraw-Hill, Inc., New York, NY, 1974
• 13: 13. McCarthy, J. A basis of the mathematical theory of computation. In Pogramming Systems and Languages, McGraw-Hill, New York, 1967, pp. 455-480.
• 14: James R. McGraw, The VAL Language: Description and Analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.1, p.44-82, Jan. 1982 [doi>10.1145/357153.357157]
• 15: Robin Milner, A proposal for standard ML, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.184-197, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802035]
• 16: Prateek Mishra , Robert M. Keller, Static inference of properties of applicative programs, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.235-244, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800535]
• 17: Alan Mycroft, The Theory and Practice of Transforming Call-by-need into Call-by-value, Proceedings of the Fourth 'Colloque International sur la Programmation' on International Symposium on Programming, p.269-281, April 22-24, 1980
• 18: 18. Pippenger, N. Pebbling. Proc. 5th IBM Sym. on Math. Foundations of Comp. Sci., IBM, May, 1980, pp. 1-19.
• 19: Jean-Claude Raoult , Ravi Sethi, The global storage needs of a subcomputation, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.148-157, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800526]
• 20: 20. Schwarz, J. Verifying the safe use of destructive operations in applicative programs. Program Transformations - Proc. of the 3rd Int'l Sym. on Programming, Dunod Informatique, 1978, pp. 395-411.
• 21: 21. Turner, D. A. SASL language manual. University of St. Andrews, 1976.
• 22: J. Weizenbaum, Symmetric list processor, Communications of the ACM, v.6 n.9, p.524-536, Sept. 1963 [doi>10.1145/367593.367617]

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Data types and structures

  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

General Terms:
Design, Languages, Performance, Theory, Verification