Transformations of FP program schemes

ABSTRACT

The perceived inefficiency in execution functional programming languages has been an obstacle to their widespread acceptance. Consequently, algorithms are often coded for efficient execution at the expense of clarity. This compromises the functional style, which is the prime advantage of such languages. We argue that high-level program transformations can relieve the programmer from concern for efficiency in many instances. We present several transformations applicable to FP program schemes, and show how these may be proven using fixpoint induction. We also show how specific subalgebras may be exploited to develop more specialised transformations, and suggest that this may be the most fruitful direction for further efforts to take. Comparison with earlier work on transformations reveals that the use of variables in LISP-like languages has often interfered with the identification of superficially dissimilar programs as instances of a common scheme. A variable-free notation such as FP has proven easier to work with.

REFERENCES

• 1: 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]
• 2: R. S. Bird, Tabulation Techniques for Recursive Programs, ACM Computing Surveys (CSUR), v.12 n.4, p.403-417, Dec. 1980 [doi>10.1145/356827.356831]
• 3: 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]
• 4: Norman H. Cohen, Characterization and elimination of redundancy in recursive programs, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.143-157, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567766]
• 5: Darlington, J. and Burstall, R.M., "A System which Automatically Improves Programs", Acta Informatica 6 (1976), 41-60
• 6: Dennis, J.B., "Data Flow Supercomputers", Computer 13:11 (Nov. 1980), 48-56
• 7: Friedman, D.P. and Wise, D.S., "CONS Should Not Evaluate its Arguments", in Automata, Languages and Programming, S. Michaelson and R. Milner, Eds., Edinburgh Univ. Press, Edinburgh, 1976, 257-284
• 8: Grismer, T.M., "Solving Common Programming Problems With an Applicative Language", Tech. Rept. #109, Indiana Univ. Computer Sci. Dept., 1981
• 9: 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]
• 10: Keller, R.M., Lindstrom, G. and Patil, S., "A Loosely-coupled, Applicative Multi-processing System", Proc. NCC 48 (1979), AFIPS Press, 861-870
• 11: Mago, G., "A Network of Microprocessors to Execute Reduction Languages" (two parts), Int. J. Computer and Info. Sci. 8:5,6 (1979)
• 12: Zohar Manna, Introduction to Mathematical Theory of Computation, McGraw-Hill, Inc., New York, NY, 1974
• 13: Zohar Manna , Richard Waldinger, A Deductive Approach to Program Synthesis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.1, p.90-121, Jan. 1980 [doi>10.1145/357084.357090]
• 14: Michie, D., "Memo Functions: A Language Feature with Rote Learning Properties", DMIP Memo MIP-R-29, Edinburgh, 1967

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Applicative (functional) languages

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Program and recursion schemes

General Terms:
Algorithms, Languages, Verification