Inductively computable constructs in very high level languages

ABSTRACT

In this paper we study the profitability of applying the "reduction in strength" technique to programs in set-theoretic languages, focusing on the high level constructs involving set-formers. We define recursively two classes of expressions we shall call inductively computable set-formers and inductively computable predicates which can be evaluated with an order of magnitude improvement of the asymptotic running time as compared to the straightforward evaluation. The quantity developed for this comparison can be used to derive further results when additional information is known. For programs written in very high level languages, which often consist mostly of "nested" iterative constructs, this technique amounts to altering the "algorithm" used to compute the program by replacing it with an asymptotically faster algorithm.

REFERENCES

• 1: {A1} F. E. Allen, "Program Optimization," in Annual Review in Automatic Programming, Vol. 5, Pergamon, 1969, pp. 239-307.
• 2: {AC} F. E. Allen and J. Cocke, "A Catalogue of Optimizing transformations," in Design and Optimization of Compilers (R. Rustin, ed.), Prentice Hall, 1972, pp. 1-30.
• 3: {ACK} F. E. Allen, J. Cocke and K. Kennedy, "Reduction of Operator Strength," TR 476-093-6, Dept. of Math. Sciences, Rice Univ., Houston, Aug., 1974.
• 4: Alfred V. Aho , Jeffrey D. Ullman, Theory of Parsing, Translation and Compiling, Prentice Hall Professional Technical Reference, 1973
• 5: {CK} J. Cocke and K. Kennedy, "An Algorithm for Reduction of Operator Strength," TR 476-093-2, Dept. of Math. Sciences, Rice Univ., Houston, March, 1974.
• 6: John Cocke, Programming languages and their compilers: Preliminary notes, Courant Institute of Mathematical Sciences, New York University, 1969
• 7: {E1} J. Earley, "Relational Level Data Structures in Programming Languages," Technical Report, Computer Science Department, University of California at Berkerly (1973).
• 8: Jay Earley, High level operations in automatic programming, Proceedings of the ACM SIGPLAN symposium on Very high level languages, p.34-42, March 28-29, 1974, Santa Monica, California, United States
• 9: Jerome A. Feldman , James R. Low , Daniel C. Swinehart , Russell H. Taylor, Recent developments in SAIL, an algol-based language for artificial intelligence., Stanford University, Stanford, CA, 1972
• 10: Amelia Fong , John Kam , Jeffrey Ullman, Application of lattice algebra to loop optimization, Proceedings of the 2nd ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.1-9, January 20-22, 1975, Palo Alto, California [doi>10.1145/512976.512977]
• 11: Amelia C. Fong , Jeffrey D. Ullman, Induction variables in very high level languages, Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, p.104-112, January 19-21, 1976, Atlanta, Georgia [doi>10.1145/800168.811544]
• 12: {M} J. B. Morris, "A comparison of MADCAP and SETL," Los Alamos Scientic Lab., University of California, Los Alamos, New Mexico (1973).
• 13: Bob Paige , J. T. Schwartz, Expression continuity and the formal differentiation of algorithms, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.58-71, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512957]
• 14: {S1} J. T. Schwartz, "On Earley's Method of 'Iterator Inversion'," SETL Newsletter, No. 138, Courant Institute, 1974.
• 15: {S2} J. T. Schwartz, On Programming, Vols. I and II, Courant Institute, 1971 and 1973.