article

Open access

Automatic transformation of series expressions into loops

Editor: Susan L. Graham Author:

Richard C. WatersAuthors Info & Claims

ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 13, Issue 1

Pages 52 - 98

https://doi.org/10.1145/114005.102806

Published: 01 January 1991 Publication History

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]

AHO, A, HOPC~tAFT, J, AND ULLMAN, J. The Design and Analysis of~omputer Algorithms. Addison-Wesley: Reading, IvlA, 1974.]]

[2]

AIKEN~ A., AND NICOLAU, A. Optimal loop parallelization. In Proceedings of the SIGPLAN '88 Conference on Programming Language Design and Implementation (Atlauta, CA, June 1988). ACM, New York, 1988, 308 317.]]

[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]

ALLEN, R., AND KENNEDY~ I4{ Automatic translation of Fortran programs to vector form. A~M Trans. Prog/'am. Lang. and Syst. 9, 4 (Oct. 1987), 491-542.]]

[5]

BACKUS, J. Can programraing be liberated from the Von Neuman style? A functional style and its algebra of programs. Commun. ACM 2L 8 (Ang. 1978), 613 641.]]

[6]

BARSTOW, D. Automatie progranmfing for streams. In Proceedings of the 9th International Joint Conference on Artificial Intelligence (Aug. 1985). 232 237.]]

[7]

BELLEGARDE, E. Rewriting systems on FP expressions that reduce the number of sequences they yield. In Proceedings AC~I Symposium on Lisp and Functional Programming (Aug. 1984). ACM, New York, 1984, 63 73.]]

[8]

BELLEGARDE, F. Convergent terre rewriting systems can be used for program transformation. In Proceedings Workshop on Programs as Data Objects. Springer-Verlag, New \%rk, 1985. 24 41.]]

[9]

BmD, R. An introduction to the theory of lists. In Logic of Programming and Calcuh of Discrete Design. M. Broy, Ed., NATO ASI series, Springer Verlag, New ~%rk, 1986, 5-42.]]

[10]

BISHOP, J The effect of data abstraction on loop programming techniques. /EEE Trans. Softw. Eng. 16, 4 (April 1990), 389-402.]]

[11]

BLOSS, A., HUDAK, P., AND YOUNG, J. Code optimizations for lazy evaluation. Lisp and Symbolic Comput. 1, 2 (Sept. 1988), 147 164.]]

[12]

BUDD, T. An APL Compiler. Springer-Verlag, New York, 1988.]]

[13]

BURKE, G., AND MOON, D Loop iteration macro. Massachusetts Institute of Technology Rep. LCS/TM-169, July 1980.]]

[14]

CAMERON~ R. Efficient high-level iteration with accumulators. ACM Trans. Program. Lang. and Syst. 11. 2 (Feb. 1989), 194-211.]]

[15]

ECKART, J. Iteration and abstract data types. ACM SIGPLAN Not. 22, 4 (April 1987), 103-110.]]

[16]

EMERY, J. Small-scale software components. ACM SIGSOFT Softw. Eng. Not. 4, 4 (Oct. 1979), 18 21.]]

[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]

GRISWOLD, R., AND GRISWOLD, M. The Icon Programming Language. Prentice-Hall, Englewood Cliffs, NJ, 1983.]]

[20]

GI~ISWOLD~ R., AND O~BAGY~ J. Seque: A programming language for manipulating sequences. ~omput. Lang. 13, 1 (.lan. 1988), 13 22.]]

[21]

GROSS, T., AND SUSSMAN, A. iMapping a single-assignment language onto the Warp systolic array. In Functional Programming Languages and Computer Architecture. G. Kahn, Ed., Springer-Verlag, New York, 1987, 347-363.]]

[22]

GUIBAS, L., AND WYATT, D. Compilation and delayed evaluation in APL. In Proceedings 1978 ACM Con~erence on the Principles of Programming Languages (Sept. 1978). ACM, New York, 1978.]]

[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]

IVERSON, K. Operators. A~M Trans. Program. Lang. and Syst. 1~ 2 (Oct. 1979), 161 176]]

[25]

JENSEN, K., AND WIRTH, N. Pascal User Manual and Report. Springer-Verlag, New York, 1985.]]

[26]

KAHN, CJ., AND MACQUEEN, D. Corontines and networks of parallel processes. In Proceedings 1977 IFIP Congress. North-Holland, Amsterdam, 1977.]]

[27]

LAM, M. Software pipehning: An effective scheduling technique for VLIW machines. In Proceedings SIGPLAN '88 ~onference on Programming Language Design and Implementation (Atlanta, GA, June 1988). ACM, New York, 1988, 318 328.]]

[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]

PINGALI, Ix., AND AR,VIND Efficient demand-drlven evaluation, part 1. AC3/i Trans Prograrn. Lang and Syst a 2 (ApriI 1985), 311 333.]]

[32]

{POLWKA, R., AND PAKIN, S. APL. The Language and Its Usag'e. Prentice-Hali, Englewood Cliffs, N J, 1975.]]

[33]

PRYWES, N., PNUEm, A., AND SHASTRY, S Use of a non-procedural specification language and associated program generator in software development. ACM Trans Program Lang' and,_qyst. 1, 2 (Oct. 1979), 196-217.]]

[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]

SCHWARTZ, J et. al. Programming ~Tith Sers. An Introduction To SETL Springer-Verlag, New York, 1986.]]

[37]

STEELE, G JP, Common Lisp: The Language. Digital Press, Maynard, MA, 1984.]]

[38]

TEITELMAN, W Interlisp Reference Manual. Xerox PARC, 1978.]]

[39]

WADLER, P. Applicative languages, program transformation, and hst operators. In Proceedings A~i~I ~onference on Functlonal Pro,g'ramrnmu Languages and Computer Architecture (Oct. 1981). ACM, New ~%rk, 1981, 25 32]]

[40]

W'ADLEi% P Listlessness ls better than laziness; Lazy evaluatlon and garbage collection at compfie-time. In Proceedings ACM Symp. on Lisp and Functional Programmmg (Aug. 1984). A~',M, New York, 1984, 45 52.]]

[41]

X~^DLER, P Listlessness is better than laziness II: Composing listless fimctions. In Proceedings worka'hop on Programs as Data Objerts. Springer-Verlag, New York, 1985.]]

[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]

WATERS, R. Expressional loops. In Proceedings 1984 ACM Conference on the Prineiples of Programming Languages (Jan. 1984). ACM, New York, 1984, I 10]]

[45]

WATERS, R Efficmnt interpretation of synchronizable series expressions. In Proceedings AC3/I SIGPLAN '87 OEvmposium on {nterpreters and Interpretive Techmques. ACM SIGPLAN Not. 22, 7 (July 1987), 74-~85.]]

[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]

WATERS, R,. Optimization of series expressions: part I: A user's manua} for the series macro pa~kage. Massachusetts Instxtute of Te~hnology Rep. AIM-1082, Dec 1989]]

[48]

W~,TERS R Series. In C'ommon Lisp: The Language, 2nd Ed. G. Steele Jr., Ed., Dxgital Press, Burlingtom MA, 1990, 9:23 955.]]

[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.]]

Cited By

Møller AVeileborg O(2020)Eliminating abstraction overhead of Java stream pipelines using ahead-of-time program optimizationProceedings of the ACM on Programming Languages10.1145/34282364:OOPSLA(1-29)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428236
Kiselyov OBiboudis APalladinos NSmaragdakis Y(2017)Stream fusion, to completenessACM SIGPLAN Notices10.1145/3093333.300988052:1(285-299)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1145/3093333.3009880
Kiselyov OBiboudis APalladinos NSmaragdakis YCastagna GGordon A(2017)Stream fusion, to completenessProceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages10.1145/3009837.3009880(285-299)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1145/3009837.3009880
Show More Cited By

Index Terms

Automatic transformation of series expressions into loops
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
    2. General programming languages
      1. Language features
        Control structures
        Data types and structures
      2. Language types
        Functional languages

Recommendations

Efficient interpretation of synchronizable series expressions
SIGPLAN '87: Papers of the Symposium on Interpreters and interpretive techniques

The benefits of programming in a functional style are well known. For example, algorithms which are expressed as compositions of functions operating on series/vectors/streams of data elements are much easier to understand and modify than equivalent ...
Efficient interpretation of synchronizable series expressions

The benefits of programming in a functional style are well known. For example, algorithms which are expressed as compositions of functions operating on series/vectors/streams of data elements are much easier to understand and modify than equivalent ...
Genome-wide co-expression based prediction of differential expressions

Motivation: Microarrays have been widely used for medical studies to detect novel disease-related genes. They enable us to study differential gene expressions at a genomic level. They also provide us with informative genome-wide co-expressions. Although ...

Reviews

Reviewer: Donald Cohen

A series is a possibly unbounded sequence of values. Compositions of functions that operate on series are generally briefer and more easily understood than alternative expressions of the same computation, for example, the sum of the squares of the differences of the corresponding elements of two series. Programming with series feels a lot like using APL, except that the series need not be computed before their use, and in fact may be infinite, and the intermediate series results need never be stored and the computation is therefore extremely efficient. This paper provides some relatively easy to understand conditions under which such expressions can be compiled into extremely efficient loops and describes the Common Lisp implementation. All of the above also appears in the Common Lisp manual [1]. (It is only fair to point out that this paper was submitted long before that manual came out.) Waters also describes a prototype implementation for Pascal, describes how the efficient loop is assembled from the series expression, discusses related work, and attempts to compare series with the facilities available in other languages.

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Programming Languages and Systems

ACM Transactions on Programming Languages and Systems Volume 13, Issue 1

Jan. 1991

178 pages

ISSN:0164-0925

EISSN:1558-4593

DOI:10.1145/114005

Editor:
Susan L. Graham
Univ. of California at Berkeley, Berkeley

Issue’s Table of Contents

Copyright © 1991 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 1991

Published in TOPLAS Volume 13, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

35
Total Citations
View Citations
858
Total Downloads

Downloads (Last 12 months)85
Downloads (Last 6 weeks)10

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Møller AVeileborg O(2020)Eliminating abstraction overhead of Java stream pipelines using ahead-of-time program optimizationProceedings of the ACM on Programming Languages10.1145/34282364:OOPSLA(1-29)Online publication date: 13-Nov-2020
Kiselyov OBiboudis APalladinos NSmaragdakis Y(2017)Stream fusion, to completenessACM SIGPLAN Notices10.1145/3093333.300988052:1(285-299)Online publication date: 1-Jan-2017
Kiselyov OBiboudis APalladinos NSmaragdakis YCastagna GGordon A(2017)Stream fusion, to completenessProceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages10.1145/3009837.3009880(285-299)Online publication date: 1-Jan-2017
Castagna GGordon A(2017)Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming LanguagesundefinedOnline publication date: 1-Jan-2017
Farmer AHoener zu Siederdissen CGill AChin WHage J(2014)The HERMIT in the streamProceedings of the ACM SIGPLAN 2014 Workshop on Partial Evaluation and Program Manipulation10.1145/2543728.2543736(97-108)Online publication date: 11-Jan-2014
Lippmeier BChakravarty MKeller GRobinson A(2013)Data flow fusion with series expressions in HaskellACM SIGPLAN Notices10.1145/2578854.250378248:12(93-104)Online publication date: 23-Sep-2013
Würthinger TWimmer CWöß AStadler LDuboscq GHumer CRichards GSimon DWolczko MHosking AEugster PHirschfeld R(2013)One VM to rule them allProceedings of the 2013 ACM international symposium on New ideas, new paradigms, and reflections on programming & software10.1145/2509578.2509581(187-204)Online publication date: 29-Oct-2013
Lippmeier BChakravarty MKeller GRobinson AShan C(2013)Data flow fusion with series expressions in HaskellProceedings of the 2013 ACM SIGPLAN symposium on Haskell10.1145/2503778.2503782(93-104)Online publication date: 23-Sep-2013
Chin W(2008)Safe fusion of functional expressions II: Further improvementsJournal of Functional Programming10.1017/S09567968000011794:04(515-555)Online publication date: 7-Nov-2008
Morel L(2007)Array Iterators in Lustre: From a Language Extension to Its Exploitation in ValidationEURASIP Journal on Embedded Systems10.1186/1687-3963-2007-0591302007:1(059130)Online publication date: 2007
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents