Induction variables in very high level languages

ABSTRACT

We explore the notion of an induction variable in the context of a set-theoretic programming langugage. An appropriate definition, we believe, involves both the necessity that changes in the variable around a loop be easily computable and that they be small. We attempt to justify these requirements and show why they are independent assumptions. Next the question of what operators on sets play the role of +, − and * for arithmetic languages is explored, and several theorems allowing us recursively to detect induction variables in a loop are given. It is shown that most of the usual set operations do fit nicely into the theory and help form induction variables. The reason most variables fail to be induction variables concerns the structure of control flow, more than it does the operators applied.

REFERENCES

• 1: F. E. Allen, "Program Optimization," in Annual Review in Automatic Programming, Vol. 5, Pergamon, 1969, pp. 239-307.
• 2: 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: John Cocke, Programming languages and their compilers: Preliminary notes, Courant Institute of Mathematical Sciences, New York University, 1969
• 4: Alfred V. Aho , Jeffrey D. Ullman, Theory of Parsing, Translation and Compiling, Prentice Hall Professional Technical Reference, 1973
• 5: 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.
• 6: 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.
• 7: 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]
• 8: J. Earley, "High Level Iterators and a Method of Automatically Designing Data Structure representation," ERL-M416, Computer Science Division, Univ. of Cal-if., Berkeley, Feb., 1974.
• 9: J. T. Schwartz, "On Earley's Method of Iterator Inversion," SETL Newsletter, No. 138, Courant Institute, 1974.
• 10: J. T. Schwartz, On Programming, Vols. I and II, Courant Institute, 1971 and 1973.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Very high-level languages

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Recursive function theory; Set theory
      F.4.2 Grammars and Other Rewriting Systems
          Subjects: Parsing

General Terms:
Algorithms, Design, Languages, Performance, Theory