Recursive programming through table look-up

ABSTRACT

The maintenance of arbitrarily large tables of previously computed values for functions on integer domains becomes practical when those tables are built using constructor functions which suspend evaluation of their arguments. Two styles of programming with such tables are presented. The first results from replacing recursive invocations within standard recursive function definitions with a reference into a table which is predefined to be all the possible results of the function. The second, more sophisticated, style requires that the table be defined strictly through a generation scheme. In either case the table may be available to the user as a data structure exclusive of the function definition with entries still being manifested only when they are actually used.

REFERENCES

• 1: G. Berry. Bottom-up computation of recursive programs. Revue Francaise d'Informatique et de Recherche Operationaelle 10, 3 (March, 1976), 47-82.
• 2: W.H. Burge. Recursive Programming Techniques, Addison-Wesley, Reading, MA (1975).
• 3: D.P. Friedman and D.S. Wise. Cons should not evaluate its arguments. Third International Colloquium on Automata, Languages and Programming, Edinburgh University Press (July, 1976).
• 4: 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]
• 5: C.A.R. Hoare. Recursive data structures. International Journal of Computer and Information Sciences 2, (June, 1975), 105-132.
• 6: John McCarthy, Recursive functions of symbolic expressions and their computation by machine, Part I, Communications of the ACM, v.3 n.4, p.184-195, April 1960 [doi>10.1145/367177.367199]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Recursive function theory

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.1 Expressions and Their Representation

General Terms:
Algorithms, Theory

Keywords:
Dynamic owns, Generation, Infinite lists, LISP, Streams, Suspended evaluation