Applicative style programming, program transformation, and list operators

ABSTRACT

An important feature of the applicative style is the use of operators that package common patterns of computation. For example, the list operator map applies a function to every element of a list. Practical use of this style has been hampered by the fact that it can be very inefficient to execute. One remedy for this situation is to use source-to-source program transformation to convert applicative style programs to more efficient equivalents. This paper examines how list operators can be used to guide the transformation process. It describes a small set of list operators that possess a “complete” set of transformation rules, allowing transformations to be performed very efficiently. Whereas most previous transformation methods resemble proofs, this transformation method resembles algebraic manipulation.

REFERENCES

• 1: Abrams, P. An APL machine. SLAC Technical Report 114, Stanford Univ., Feb 1970.
• 2: John Backus, Can programming be liberated from the von Neumann style?: a functional style and its algebra of programs, Communications of the ACM, v.21 n.8, p.613-641, Aug. 1978 [doi>10.1145/359576.359579]
• 3: Burge, W. H. Recursive Programming Techniques. Addison-Wesley, Reading, Mass., 1975.
• 4: Burge, W. H. An optimizing technique for high level programming languages. IBM Watson Research Center, RC 5834 (#25271), Feb 1976.
• 5: Burstall, R. M., McQueen, D. B., and Sanella, D. T. Hope: An experimental applicative language. Univ. of Edinburgh, Dept. of Computer Science, 1980.
• 6: 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]
• 7: A. Chiarini, On FP languages combining forms, ACM SIGPLAN Notices, v.15 n.9, p.25-27, September 1980 [doi>10.1145/947706.947709]
• 8: Darlington, J., and Burstall, R. M. A system which automatically improves programs. Acta Informatica 6, 1 (1976).
• 9: 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
• 10: Feather, M. S. A system for developing programs by transformation. Ph.D. Thesis, Univ. of Edinburgh, 1979.
• 11: Friedman, D. P., and Wise, D. S. Cons should not evaluate its arguments. In Automata, Languages, and Programming, ed. Michaelson and Milner, Edinburgh Univ. Press, 1976, pp. 257-284.
• 12: Leo J. Guibas , Douglas K. Wyatt, Compilation and delayed evaluation in APL, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.1-8, January 23-25, 1978, Tucson, Arizona [doi>10.1145/512760.512761]
• 13: 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]
• 14: Huet, G., and Lang, B. Proving and applying program transformations expressed with second-order patterns. Acta Informatica 11 (1978), pp. 31-55.
• 15: Kenneth E. Iverson, Operators, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.2, p.161-176, Oct. 1979 [doi>10.1145/357073.357074]
• 16: Kenneth E. Iverson, Notation as a tool of thought, Communications of the ACM, v.23 n.8, p.444-465, Aug. 1980 [doi>10.1145/358896.358899]
• 17: P. J. Landin, Correspondence between ALGOL 60 and Church's Lambda-notation: part I, Communications of the ACM, v.8 n.2, p.89-101, Feb. 1965 [doi>10.1145/363744.363749]
• 18: 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]
• 19: Manna, Z., and Waldinger, R. Knowledge and reasoning in program synthesis. Artificial Intelligence 6 (1975), p. 175.
• 20: Manna, Z., and Waldinger, R. Synthesis: Dreams &equil; > Programs. IEEE Trans. Software Engineering SE-5, 4 (July 1979).
• 21: Miller, T. C. Tentative compilation: a design for an APL compiler. Univ. of California, San Diego, Technical Report 78-CS-013, May 1978.
• 22: James H. Morris , Eric Schmidt , Philip Wadler, Experience with an applicative string processing language, Proceedings of the 7th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.32-46, January 28-30, 1980, Las Vegas, Nevada [doi>10.1145/567446.567450]
• 23: Thomas J. Myers, Infinite structures in programming languages, 1980
• 24: 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]
• 25: William L. Scherlis, Program improvement by internal specialization, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.41-49, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567536]
• 26: Sharir, M. Some observations concerning formal differentiation of set-theoretic expressions. New York Univ., Dept. of Computer Science, Courant Inst. Mathematical Sciences, Tech. Rep. 16, Oct. 1979.
• 27: Guy Lewis Steele, Jr., Debunking the “expensive procedure call” myth or, procedure call implementations considered harmful or, LAMBDA: The Ultimate GOTO, Proceedings of the 1977 annual conference, p.153-162, January 1977 [doi>10.1145/800179.810196]
• 28: David Sheridan Wile, A generative, nested-sequential basis for general purpose programming languages., 1974
• 29: Wile, D. S. Generator expressions. Internal memo, USC-ISI, 1979.

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.1 Applicative (Functional) Programming

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Lists, stacks, and queues

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming
          Subjects: Program transformation

General Terms:
Design, Languages, Verification