Applicative caching

ABSTRACT

The “referential transparency” principle of applicative language expressions stipulates that a single value exists for all occurrences of an expression in a given context (where a context is a set of bindings of variables to values). In principle, each such value therefore need to be computed only once. However, in applicative language systems supporting recursive programming or tasking notions, the bindings are not all precomputed and explicit. As a result, textual recognition of all multipleoccurrences is precluded, with the unfortunate consequence that such occurrences are recomputed. We elaborate upon the early notion of “memo function” for solving this problem. We suggest syntactic and semantic constructs providing programmer control for avoiding recomputation, which is incorporated into a “building-block” approach.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: R. S. Bird, Tabulation Techniques for Recursive Programs, ACM Computing Surveys (CSUR), v.12 n.4, p.403-417, Dec. 1980 [doi>10.1145/356827.356831]
• 3: BROWN, G. A new concept in programming. In Management and the Computer of the Future, M. Greenberger, Ed., Wiley, New York, 1962.
• 4: R. M. Burstall , John Darlington, A Transformation System for Developing Recursive Programs, Journal of the ACM (JACM), v.24 n.1, p.44-67, Jan. 1977 [doi>10.1145/321992.321996]
• 5: Norman H. Cohen, Characterization and elimination of redundancy in recursive programs, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.143-157, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567766]
• 6: DIJKSTRA, E. W. Cooperating sequential processes. In Programming Languages, Academic Press, New York, 1968.
• 7: Edward Fredkin, Trie memory, Communications of the ACM, v.3 n.9, p.490-499, September 1960 [doi>10.1145/367390.367400]
• 8: 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]
• 9: FRIEDMAN, D. P., AND WISE, D. S. CONS should not evaluate its arguments. In Automata, Languages, and Programming, Edinburgh University Press, 1976, 257-284.
• 10: FRIEDMAN, D. P., AND WISE, D.S. The impact of applicative programming on multiprocessing. IEEE Trans. Comput. C-27, 4 (Apr. 1978), 289-296.
• 11: GRISS, M.L. Efficient expression evaluation in sparse minor expansion, using hashing and deferred evaluation. In Hawaii International Conference on System Sciences, IEEE, New York, 1977.
• 12: 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]
• 13: HILDEN, J. Elimination of recursive calls using a small table of "randomly" selected function values. BIT 16, I (1976), 60-73.
• 14: HOARE, C. A.R. Recursive data structures. Int. J. Comput. Inf. Sc~ 4, 2 (1975).
• 15: KELLER, R.M. Denotational models for parallel programs with indeterminate operators. In Formal Description of Programming Concepts, E. J. Neuhold, Ed., North-Holland, Amsterdam, 1978, 337-366.
• 16: KELLER, R. M., LINDSTROM, C., AND PATIL, S. A loosely-coupled applicative multiprocessing system. In AFIPS Conference (June, 1979), 613-622.
• 17: KELLER, R. M., AND LINDSTROM, G. Hierarchical analysis of a distributed evaluator. In Proceedings International Conference on Parallel Processing, (Aug. 1980), IEEE, New York, 299-310.
• 18: Robert M. Keller , M. Ronan Sleep, Applicative caching: Programmer control of object sharing and lifetime in. distributed implementations of applicative languages, Proceedings of the 1981 conference on Functional programming languages and computer architecture, p.131-140, October 18-22, 1981, Portsmouth, New Hampshire, United States [doi>10.1145/800223.806772]
• 19: KELLER, R.M. FEL (Function Equation Language) programmer's guide. AMPS Tech. Memo. 7, Dept. of Computer Science, Univ. of Utah, 1982.
• 20: KELLER, R. M., AND LINDSTROM, C. Approaching distributed database implementations through functional programming concepts. In Proceedings 5th International Conference on Distributed Computing Systems. (Denver, Colo., May 1985), IEEE, New York, 192-200.
• 21: LANDIN, P. J. The mechanical evaluation of expressions. Computer J. 6, 4 (Jan. 1964), 308-320.
• 22: P. J. Landin, The next 700 programming languages, Communications of the ACM, v.9 n.3, p.157-166, March 1966 [doi>10.1145/365230.365257]
• 23: LINDSTROM, G. Efficiency in nondeterministic control through nonforgetful backtracking. Tech. Rep. UUCS-77-114, Univ. of Utah, Oct. 1977.
• 24: Zohar Manna, Introduction to Mathematical Theory of Computation, McGraw-Hill, Inc., New York, NY, 1974
• 25: John McCarthy, LISP 1.5 Programmer's Manual, The MIT Press, 1962
• 26: MICHIE, D. 'Memo' functions and machine learning. Nature 218, (Apr. 1968), 19-22.
• 27: 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
• 28: H. Gordon Rice, Recursion and iteration, Communications of the ACM, v.8 n.2, p.114-115, Feb. 1965 [doi>10.1145/363744.363781]
• 29: D. A. Turner, The semantic elegance of applicative languages, Proceedings of the 1981 conference on Functional programming languages and computer architecture, p.85-92, October 18-22, 1981, Portsmouth, New Hampshire, United States [doi>10.1145/800223.806766]
• 30: WADSWORTH, C.P. Semantics and pragmatics of the lambda-calculus. Ph.D. thesis, Univ. of Oxford, 1971.

INDEX TERMS

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

  E. Data

General Terms:
Design, Experimentation, Languages, Measurement, Performance