Automatic transformation of series expressions into loops

ABSTRACT

The benefits of programming in a functional style are well known. In particular, algorithms that are expressed as compositions of functions operating on sequences/vectors/streams of data elements are easier to understand and modify than equivalent algorithms expressed as loops. Unfortunately, this kind of expression is not used anywhere near as often as it could be, for at least three reasons: (1) most programmers are less familiar with this kind of expression than with loops; (2) most programming languages provide poor support for this kind of expression; and (3) when support is provided, it is seldom effcient. In any programming language, the second and third problems can be largely solved by introducing a data type called series, a comprehensive set of procedures operating on series, and a preprocessor (or compiler extension) that automatically converts most series expressions into efficient loops. A set of restrictions specifies which series expressions can be optimized. If programmers stay within the limits imposed, they are guaranteed of high efficiency at all times. A common Lisp macro package supporting series has been in use for some time. A prototype demonnstrates that series can be straightforwardly supported in Pascal.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: A. Aiken , A. Nicolau, Optimal loop parallelization, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.308-317, June 20-24, 1988, Atlanta, Georgia, United States
• 3: ALLEN, F., AND COCKE, J. A catalogue of optimizing transformations. In Design and Optimization of Compilers. R. Rustin, Ed.~ Prentice Hall, New York. 1971.
• 4: Randy Allen , Ken Kennedy, Automatic translation of FORTRAN programs to vector form, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.4, p.491-542, Oct. 1987 [doi>10.1145/29873.29875]
• 5: 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]
• 6: BARSTOW, D. Automatie progranmfing for streams. In Proceedings of the 9th International Joint Conference on Artificial Intelligence (Aug. 1985). 232 237.
• 7: Francoise Bellegarde, Rewriting systems on FP expressions that reduce the number of sequences they yield, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.63-73, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802022]
• 8: Francoise Bellegarde, Convergent term rewriting systems can be used for program transformation, on Programs as data objects, p.24-41, April 1986, Copenhagen, Denmark
• 9: R. S. Bird, An introduction to the theory of lists, Proceedings of the NATO Advanced Study Institute on Logic of programming and calculi of discrete design, p.5-42, June 1987, Marktoberdorf, Germany
• 10: Judy M. Bishop, The Effect of Data Abstraction on Loop Programming Techniques, IEEE Transactions on Software Engineering, v.16 n.4, p.389-402, April 1990 [doi>10.1109/32.54291]
• 11: BLOSS, A., HUDAK, P., AND YOUNG, J. Code optimizations for lazy evaluation. Lisp and Symbolic Comput. 1, 2 (Sept. 1988), 147 164.
• 12: Timothy Budd, An APL compiler, Springer-Verlag New York, Inc., New York, NY, 1988
• 13: BURKE, G., AND MOON, D Loop iteration macro. Massachusetts Institute of Technology Rep. LCS/TM-169, July 1980.
• 14: Robert D. Cameron, Efficient high-level iteration with accumulators, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.2, p.194-211, April 1989 [doi>10.1145/63264.63401]
• 15: J D Eckart, Iteration and abstract data types, ACM SIGPLAN Notices, v.22 n.4, p.103-110, April 1987 [doi>10.1145/24714.24727]
• 16: James E. Emery, Small-scale software components, ACM SIGSOFT Software Engineering Notes, v.4 n.4, p.18-21, October 1979 [doi>10.1145/1005907.1005910]
• 17: FRIEDMAN, D., AND WISE, D. CONS should not evaluate its arguments. University of Indmna Computer Science Department Rep. 44, Nov. 1975.
• 18: GOLDBERG, A., AND PAIGE, R. Stream processing. Rutgers University Laboratory for Computer Systems Research Rep. LCSR-TR-46, Aug. 1983.
• 19: Ralph E. Griswold , Madge T. Griswold, ICON Programmng Language, Prentice Hall Professional Technical Reference, 1983
• 20: Ralph E. Griswold , Janalee O'Bagy, Seque: a programming language for manipulating sequences, Computer Languages, v.13 n.1, p.13-22, Jan., 1988 [doi>10.1016/0096-0551(88)90003-3]
• 21: Thomas Gross , Alan Sussman, Mapping a single-assignment language onto the Warp systolic array, Proc. of a conference on Functional programming languages and computer architecture, p.347-363, October 1987, Portland, Oregon, United States
• 22: 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]
• 23: HARTMANIS, J., LEWIS, P.~ AND STEARNS, R. Classification of computations by rime and mernory requirements. In Proceedings IFIP Congress 65. Spartan Books~ Washington DC, 1965, 31 35.
• 24: 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]
• 25: K Jensen , N Wirth , A B Mickel , J F Miner, Pascal user manual and report; 3rd ed., Springer-Verlag New York, Inc., New York, NY, 1985
• 26: KAHN, CJ., AND MACQUEEN, D. Corontines and networks of parallel processes. In Proceedings 1977 IFIP Congress. North-Holland, Amsterdam, 1977.
• 27: M. Lam, Software pipelining: an effective scheduling technique for VLIW machines, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.318-328, June 20-24, 1988, Atlanta, Georgia, United States
• 28: LISKOV, B., et. al (?,LU Re~orence Manual. Springer-Verlag. New York, 1981.
• 29: ORWANT, J. Support of obviously syn~hronizablp serres expressions in Pascal. Massachusetts Institute of Technology Rep. AI/WP-312, Sept. 1988.
• 30: PERDUE, C , AND xvVATERS, R. Generators and gatherers. In Common Lisp: the language, 2nd Ed. G Steele Jr., Ed., Digital Press, Burhngton, MA, 1990, 956-959
• 31: Keshav Pingali , Arvind, Efficient demand-driven evaluation. Part 1, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.2, p.311-333, April 1985 [doi>10.1145/3318.3480]
• 32: Raymond P. Polivka , Sandra Pakin, APL: The Language and Its Usage, Prentice Hall Professional Technical Reference, 1975
• 33: N. S. Prywes , Amir and S. Shastry, Use of a Nonprocedural Specification Language and Associated Program Generator in Software Development, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.2, p.196-217, Oct. 1979 [doi>10.1145/357073.357076]
• 34: R,ICH, C., AND WATERS, R. The Prograrnmer's Apprentice. Addison-Wesley, Reading MA, 1990.
• 35: RUTH, CI , ALTER, S , AND MARTIN, W. A very high level language for business data pro- ~essing. Massachusetts Institute of Technology Rep LCS/TR-254, 1981.
• 36: J. T. Schwartz , R. B. Dewar , E. Schonberg , E. Dubinsky, Programming with sets; an introduction to SETL, Springer-Verlag New York, Inc., New York, NY, 1986
• 37: Guy L. Steele, Jr., Common LISP: the language, Digital Press, Newton, MA, 1984
• 38: TEITELMAN, W Interlisp Reference Manual. Xerox PARC, 1978.
• 39: Philip Wadler, Applicative style programming, program transformation, and list operators, Proceedings of the 1981 conference on Functional programming languages and computer architecture, p.25-32, October 18-22, 1981, Portsmouth, New Hampshire, United States [doi>10.1145/800223.806759]
• 40: Philip Wadler, Listlessness is better than laziness: Lazy evaluation and garbage collection at compile-time, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.45-52, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802020]
• 41: Philip. Wadler, Listlessness is better than laziness II: composing listless functions, on Programs as data objects, p.282-305, April 1986, Copenhagen, Denmark
• 42: \~ATEaS, R A method for analyzing loop programs. IEEE Trans Softw. Eng. 5, 3 (Mav 1979), 237-247.
• 43: WATERS, R. LetS. An expressional loop notation Massachusetts Instltute of Technology Rep AIM-680a, Oct. 1982.
• 44: Richard C. Waters, Expressional loops, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.1-10, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800511]
• 45: R. C. Waters, Efficient interpretation of synchronizable series expressions, Papers of the Symposium on Interpreters and interpretive techniques, p.74-85, June 24-26, 1987, St. Paul, Minnesota, United States
• 46: WATERS, R Using obviously synchronizable series expressions instead of loops. In Proeeedings 1988 hiternational CoIlference on Computer Languages (Miami, FL, Oct. 1988). IEEE Computer Society Press, New York, 1988, 338-346.
• 47: Richard C. Waters, Optimization of Series Expressions: Part I: User''s Manual for the Series Macro Package, Massachusetts Institute of Technology, Cambridge, MA, 1989
• 48: Guy L. Steele, Jr., Common LISP: the language (2nd ed.), Digital Press, Newton, MA, 1990
• 49: WmE, D. Generator expressions. USC Information Sciences Inst~tute P~ep. ISI/RR-83-116, 1983
• 50: XvVULF, ~V., LONLDON, P~ , AND ~HAVV, M An introduction to the construction and venfication of Alphard programs. IEEE Trans. Softw. Eng. 2, 4 (Dec. 1976), 253 265.
• 51: Military Standard Ada Programmmg Language. ANSI/MIL-STD-1815A-1983, U.S. Government Printing Office, Feb. 1983.

INDEX TERMS

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

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Data types and structures; Control structures

General Terms:
Algorithms, Design, Languages

Keywords:
sequences, series, streams, vectors