A powerful strategy for deriving efficient programs by transformation

ABSTRACT

We present a method for deriving efficient iterative programs by transformation from recursive equation specifications. It consists of two phases: i) the transformation of general recursive programs into linear recursive ones, and ii) the transformation of linear recursive programs into iterative ones. In the first phase we apply the “tupling strategy” studied in [BUD77, Pet77], and implicitly used by other authors in the area of program transformation. That strategy enables us to introduce linear recursive functions, instead of the general recursive ones occurring in program specifications. In the second phase we apply known methods for transforming linear recursion into iteration (avoiding the use of stacks) [WaS73], and equivalence results between recursive schemas and flowchart schemas. Through various examples we show how the breaking of the transformation process into the above mentioned phases allows the derivation of efficient iterative algorithms. Those examples include challenges by Prof. E. Dijkstra and other authors. Through our method we were also able to improve some recent results for eliminating redundant calls in recursive programs [Coh83].

REFERENCES

• 1: Atkinson, M.D.:"The Cyclic Towers of Hanoi" Info. Proc. Lett. Vol.13(3) (Dec 1981) pag.118-119
• 2: Friedrich Ludwig Bauer , H. Woessner, Algorithmic Language and Program Development, Springer-Verlag New York, Inc., Secaucus, NJ, 1982
• 3: 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]
• 4: Buneman, P. and Levy, L.:"The Towers of Hanoi Problem" Info. Proc. Lett. 10 (1980) pag.243-244
• 5: 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]
• 6: Norman H. Cohen, Eliminating Redundant Recursive Calls., ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.3, p.265-299, July 1983 [doi>10.1145/2166.2167]
• 7: Darlington, J.:"A Synthesis of Several Sorting Algorithms" Acta Informatica 11 (1978) pag.1-30.
• 8: Darlington, J. and Burstall, R.M.:"A System Which Automatically Improves Programs" Acta Informatica 6 (1976) pag.41-60
• 9: Edsger Wybe Dijkstra, Selected Writings on Computing: A Personal Perspective, Springer-Verlag New York, Inc., Secaucus, NJ, 1982
• 10: Hayes, P.J.:"A Note on the Towers of Hanoi Problem" Computer Journal 20 (1977) pag.282-285
• 11: Kott, L.: "About Transformation System: A Theoretical Study" 3ème Colloque Intern. sur la Programmation. Paris (1978) Dunod. pag.232-247
• 12: Paterson, M.S. and Hewitt, C.E.:"Comparative Schematology" Proj. MAC Conf. On Concurrent Systems and Parallel Computation Woods Hole, (Mass. Jun 2-5 1970) pag.119-127.
• 13: Pettorossi, A.: "Transformation of Programs and Use of 'Tupling Strategy'" Infomatica 77 Conf. Bled Jugoslavia (1977) pag.1-6
• 14: Pettorossi, A.: "Methodologies for Transformations and Memoing in Applicative Languages" Ph.D. Computer Science Dept. Edinburgh (Forthcoming)
• 15: Pettorossi, A. and Burstall, R.M.:"Deriving Very Efficient Algorithms for Evaluating Linear Recurrence Relations Using The Program Transformation Technique" Acta Informatica 18 (1982) pag.181-206.
• 16: 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]
• 17: "Space Filling Curves, or How to Waste Time on a Plotter" Softw. Pract. and Exper. Vol.1 no.4 (1971) pag.403-410
• 18: Walker, S.A. and Strong, H.R.:"Characterizations of Flowchartable Recursions" JCSS Vol.7 no.4 (Aug.1973) pag.404-447
• 19: Walsh, T.R.:"Iteration strikes back at the Cyclic Towers of Hanoi" Info. Proc. Lett. 16(1983) pag.91-93
• 20: Wegbreit, B.:"Goal-directed Program Transformation" IEEE Trans. Software Engin. SE-2 (1976) pag.69-79
• 21: Niklaus Wirth, Program development by stepwise refinement, Communications of the ACM, v.14 n.4, p.221-227, April 1971 [doi>10.1145/362575.362577]
• 22: Niklaus Wirth, Algorithms + Data Structures = Programs, Prentice Hall PTR, Upper Saddle River, NJ, 1978

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.3 Language Constructs and Features
          Subjects: Recursion

General Terms:
Languages