A randomized implementation of multiple functional arrays

ABSTRACT

The array update problem in the implementation of a purely functional language is the following: once an array is updated, both the original array and the newly updated one must be preserved to maintain referential transparency. Previous approaches have mainly based on the detection or enforcement of single-threaded accesses to an aggregate, by means of compiler-time analyses or language restrictions. These approaches cannot deal with aggregates which are updated in a multi-threaded manner.Baker's shallow binding scheme can be used to implement multi-threaded functional arrays. His scheme, however, can be very expensive if there are repeated alternations between long binding paths. We design a scheme that fragments binding paths randomly. The randomization scheme is on-line, simple to implement, and its expected performance comparable to that of the optimal off-line solutions. All this is achieved without using compiler-time analyses, and without restricting the languages.The expected performance of the randomization scheme is analyzed in details, and some preliminary results are shown. Applications of the randomization technique to other functional aggregates, as well as its implications, are briefly outlined.

REFERENCES

• 1: A. Aasa , Sören Holmström , Christina Nilsson, An efficiency comparison of some representations of purely functional arrays, BIT, v.28 n.3, p.490-503, 1988
• 2: Arvind , Rishiyur S. Nikhil , Keshav K. Pingali, I-structures: data structures for parallel computing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.4, p.598-632, Oct. 1989 [doi>10.1145/69558.69562]
• 3: L. Augustsson , T. Johnsson, The Chalmers lazy ML-compiler, The Computer Journal, v.32 n.2, p.127-141, April 1989 [doi>10.1093/comjnl/32.2.127]
• 4: Lennaxt Augustsson and Thomas Johnsson. Lazy ML user's manual Version 0.999.J, July 1994. Draft, distributed with the Chalmers Lazy ML compiler.
• 5: Henry G. Baker, Jr., Shallow binding in Lisp 1.5, Communications of the ACM, v.21 n.7, p.565-569, July 1978 [doi>10.1145/359545.359566]
• 6: Henry G. Baker, Shallow binding makes functional arrays fast, ACM SIGPLAN Notices, v.26 n.8, p.145-147, Aug. 1991 [doi>10.1145/122598.122614]
• 7: Adrienne Bloss, Update analysis and the efficient implementation of functional aggregates, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.26-38, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99373]
• 8: Tyng-Ruey Chuang, Fully persistent arrays for efficient incremental updates and voluminous reads, Symposium proceedings on 4th European symposium on programming, p.110-129, January 1992, Rennes, France
• 9: Tyng-Ruey Chuang , Benjamin Goldberg, Real-time deques, multihead Turing machines, and purely functional programming, Proceedings of the conference on Functional programming languages and computer architecture, p.289-298, June 09-11, 1993, Copenhagen, Denmark [doi>10.1145/165180.165225]
• 10: James R. Driscoll , Neil Sarnak , Daniel D. Sleator , Robert E. Tarjan, Making data structures persistent, Journal of Computer and System Sciences, v.38 n.1, p.86-124, February 1989 [doi>10.1016/0022-0000(89)90034-2]
• 11: Robert Hood and Robert Melville. Real-time queue operations in pure Lisp. Information Processing Letters, 13(2):50- 53, 1981.
• 12: Paul Hudak , Adrienne Bloss, The aggregate update problem in functional programming systems, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.300-314, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318660]
• 13: Thomas Johnsson. Personal communication, October 1993.
• 14: Herbert Kuchen. Personal communication, September 1993.
• 15: Eugene W. Myers, Efficient applicative data types, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.66-75, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800517]
• 16: Martin Odersky, How to make destructive updates less destructive, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.25-36, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99590]
• 17: Simon L. Peyton Jones , Philip Wadler, Imperative functional programming, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.71-84, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158524]
• 18: Colin Runciman and David Wakeling. Heap profiling of lazy functional programs. Journal of Functional Programming, 3(2):217-245, April 1993.
• 19: Neil Ivor Sarnak, Persistent data structures, 1986
• 20: A. V. S. Sastry , William Clinger , Zena Ariola, Order-of-evaluation analysis for destructive updates in strict functional languages with flat aggregates, Proceedings of the conference on Functional programming languages and computer architecture, p.266-275, June 09-11, 1993, Copenhagen, Denmark [doi>10.1145/165180.165222]
• 21: David A. Schmidt, Detecting global variables in denotational specifications, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.2, p.299-310, April 1985 [doi>10.1145/3318.3323]
• 22: Berry Schoenmakers. Data Structures and Amortized Complexity in a Functional Setting. Phi) thesis, Deaprtment of Mathematics and Computing Science, Eindhoven University of Tectmology, September 1992.
• 23: Philip Wadler, Comprehending monads, Proceedings of the 1990 ACM conference on LISP and functional programming, p.61-78, June 27-29, 1990, Nice, France [doi>10.1145/91556.91592]

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.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Functional constructs

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Languages, Performance, Theory