Applicative caching: Programmer control of object sharing and lifetime in. distributed implementations of applicative languages

ABSTRACT

The “referential transparency” of applicative language expressions demands that all occurrences of an expression in a given context yield the same value. In principle, that value therefore needs to be computed only once. However, in recursive programming, a context usually unfolds dynamically, precluding textual recognition of multiple occurrences, so that such occurrences are recomputed. To remedy the lack, in applicative languages, of an ability to store and retrieve a computed value under programmer control, “caching functionals” are proposed which allow the programmer to selectively avoid recomputation without overt use of assignment. The uses and implementation of such mechanisms are discussed, including reasons and techniques for purging the underlying cache. Our approach is an extension of the early notion of “memo function”, enabling improved space utilization and a “building-block” approach.

REFERENCES

• 1: Peter Buneman , Robert E. Frankel , Rishiyur Nikhil, An implementation technique for database query languages, ACM Transactions on Database Systems (TODS), v.7 n.2, p.164-186, June 1982 [doi>10.1145/319702.319711]
• 2: W.H. Burge. Recursive programming techniques. Addison-Wesley, 1975.
• 3: E.W. Dijkstra. Cooperating sequential processes. Academic Press, 1968,
• 4: R. Doany. Implementation of a network database using a function graph language. Master's thesis, University of Utah, Dept. of Computer Science, June, 1981.
• 5: Daniel P. Friedman , David S. Wise , Mitchell Wand, Recursive programming through table look-up, Proceedings of the third ACM symposium on Symbolic and algebraic computation, p.85-89, August 10-12, 1976, Yorktown Heights, New York, United States [doi>10.1145/800205.806326]
• 6: D.P. Friedman and D.S. Wise. CONS should not evaluate its arguments. Edinburgh University Press, 1976, pages 257-284.
• 7: D.P. Friedman and D.S. Wise. The impact of applicative programming on multiprocessing. IEEE Trans. on Computers C-27 (4):289-296, April, 1978.
• 8: M.L. Griss. Efficient expression evaluation in sparse minor expansion, using hashing and deferred evaluation. In Hawaii International Conference on System Sciences. IEEE, 1977.
• 9: Peter Henderson , James H. Morris, Jr., A lazy evaluator, Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, p.95-103, January 19-21, 1976, Atlanta, Georgia [doi>10.1145/800168.811543]
• 10: C.A.R. Hoare. Recursive data structures. International Journal of Computer and Information Sciences 4(2), 1975.
• 11: R.M. Keller, G. Lindstrom, and S. Patil. A loosely-coupled applicative multi-processing system. In AFIPS Conference. June, 1979.
• 12: R.M. Keller, B. Jayaraman, D. Rose, G. Lindstrom. FGL (Function Graph Language) Programmers' Guide. Technical Report AMPS Technical Memorandum No. 1, University of Utah, Computer Science Department, 1980.
• 13: Robert M. Keller , Gary Lindstrom, Applications of feedback in functional programming, Proceedings of the 1981 conference on Functional programming languages and computer architecture, p.123-130, October 18-22, 1981, Portsmouth, New Hampshire, United States [doi>10.1145/800223.806771]
• 14: R.M. Keller and W-C. J. Yen. A graphical approach to software development using function graphs. In Proc. Compcon 81, pages 156-161. IEEE, 1981.
• 15: P.J. Landin. The mechanical evaluation of expressions. Computer J. 6(4):308-320, January, 1964.
• 16: Gary Lindstrom. Efficiency in nondeterministic control through non-forgetful backtracking. Technical Report UUCS-77-114, University of Utah, October, 1977.
• 17: D. Michie. 'Memo' functions and machine learning. Nature 218:19-22, April, 1968.
• 18: James H. Morris , Eric Schmidt , Philip Wadler, Experience with an applicative string processing language, Proceedings of the 7th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.32-46, January 28-30, 1980, Las Vegas, Nevada [doi>10.1145/567446.567450]
• 19: C.P. Wadsworth. Semantics and pragmatics of the lambda-calculus. PhD thesis, University of Oxford, 1971.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Applicative (functional) languages