Expression continuity and the formal differentiation of algorithms

ABSTRACT

This paper explores the technique of 'strength reduction' or 'formal differentation' in a set theoretic context, as recently introduced by Earley. We give pragmatic rules for the recognition and treatment of reasonably general cases in which the optimization is applicable, and consider some of the problems which arise in actually attempting to install this optimization as part of a compiling system.

REFERENCES

• 1: {A1} Allen, Frances F., Cocke, John, and Kennedy, Ken, "Reduction of Operator Strength," Rice University Tech. Rep. 476-093-6, August 1974.
• 2: {B1} Balzer, Robert, Goldman, Neil, and Wile, David, "On the Transformational Implementation Approach to Programming," UCS/Information Sciences Institute, Marina del Rey, Calif., April 1975.
• 3: {B2} Burstall, R. M., and Darlington, J., "A Transformation System for Developing Recursive Programs," D.A.I. Research Report No. 19, University of Edinburgh, March 1976.
• 4: {C1} Cocke, John and Kennedy, Ken, "An Algorithm for Reduction of Operator Strength," Rice University Technical Report 476-093-2.
• 5: John Cocke, Programming languages and their compilers: Preliminary notes, Courant Institute of Mathematical Sciences, New York University, 1969
• 6: {E1} Earley, Jay, "High Level Iterators and a Method for Automatically Designing Data Structure Representation," Dept. of Elec. Engr. & Computer Sciences, and the Electronic Research Lab., Univ. of California, Berkeley, Calif., February 1974.
• 7: {E2} Earley, Jay, "High Level Operations in Automatic Programming," Dept. of Elec. Engr. & Comp. Sciences and the Electronics Research Lab., University of California, Berkeley, Calif., October 1973.
• 8: 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]
• 9: {K1} Kennedy, Ken, "Reduction in Strength Using Hashed Temporaries," SETL Newsletter No. 102, March 12, 1973.
• 10: {K2} Kennedy, Ken, "Linear Function Test Replacement," SETL Newsletter No. 107, May 20, 1973.
• 11: {K3} Kennedy, Ken, "Global Dead Computation Elimination," SETL Newsletter No. 111, August 7, 1973.
• 12: {K4} Kennedy, Ken, "An Algorithm to Compute Compacted Use Definition Chains," SETL Newsletter No. 112, August 14, 1973.
• 13: {K5} Kennedy, Ken, "Variable Subsumption with Constant Folding," SETL Newsletter No. 123, February 1, 1974.
• 14: {L1} Liu, S-C., "An Experiment with Peephole Optimization in SETL," to appear in the, Proceedings of the September 1976 Moscow Conference on Very High Level Languages.
• 15: {S1} Schonberg, Ed, "The VERS2 Language of J. Earley Considerd in Relation to SETL," SETL Newsletter No. 124, January 30, 1974.
• 16: {Sch1} Schwartz, J. T., On Programming: An Interim Report on the SETL Project. Installments I, II, Courant Institute of Mathematical Sciences, New York University, New York, 1974.
• 17: {Sch2} Schwartz, J. T., "General Comments on High Level Dictions, and Specific Suggestions Concerning 'Converge' Iterators and Some Related Dictions," SETL Newsletter No. 133B, January 29, 1975.
• 18: {Sch3} Schwartz, J. T., "Introductory Lecture at the June 28 'Informal Optimization Symposium'," SETL Newsletter No. 135, July 1, 1974.
• 19: {Sch4} Schwartz, J. T., "Structureless Programming, or the Notion of 'Rubble', and the Reduction of Programs to Rubble," SETL Newsletter No. 135A, July 12, 1974.
• 20: {Sch5} Schwartz, J. T., "A Framework for Certain Kinds of High Level Optimization," SETL Newsletter No. 136, July 16, 1974.
• 21: {Sch6} Schwartz, J. T. and Paige, R., "On Jay Earley's 'Method of Iterator Inversion'," SETL Newsletter No. 138, April 19, 1976.
• 22: {St1} Standish, Thomas, "An Example of Program Improvement using Source-to-Source Transformations," Dept. of Information and Computer Science, University of California at Irvine, Irvine, Calif., February 11, 1976.
• 23: {St2} Standish, Thomas, et al., "The Irvine Program Transformation Catalogue," Dept. of Information and Computer Science, University of California at Irvine, Calif., January 7, 1976.