Efficient interpretation of synchronizable series expressions

ABSTRACT

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 algorithms expressed as loops. Unfortunately, many programmers hesitate to use series expressions because they are typically implemented very inefficiently-the prime source of inefficiency being the creation of intermediate series objects.A restricted class of series expressions, obviously synchronizable series expressions, is defined which can be evaluated very efficiently because they do not require the creation of any intermediate series objects. A Common Lisp macro package has been implemented which supports obviously synchronizable series expressions. Using this macro package, programmers can obtain the advantages of expressing computations as series expressions without incurring any runtime overhead. Obviously synchronizable series expressions could be straightforwardly supported in any programming language.

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: [2] F. Allen and J. Cocke, "A Catalogue of Optimizing Transformations", in Design and Optimization of Compilers, R. Rustin (ed.), Prentice-Hall, 1971.
• 3: 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]
• 4: 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]
• 5: Francoise Bellegarde, Convergent term rewriting systems can be used for program transformation, on Programs as data objects, p.24-41, April 1986, Copenhagen, Denmark
• 6: [6] T. Budd, An APL Compiler, Univ. of Arizona, TR 81-17, Oct. 1981.
• 7: Timothy A. Budd, An APL Compiler for a Vector Processor, ACM Transactions on Programming Languages and Systems (TOPLAS), v.6 n.3, p.297-313, July 1984 [doi>10.1145/579.357248]
• 8: [8] D. Barstow, "Automatic Programming for Streams", Proc. of the 9th Int. Joint Conf on Artificial Intelligence, Aug. 1985.
• 9: [9] G. Burke and D. Moon, Loop Iteration Macro, MIT/LCS/TM-169, July 1980.
• 10: [10] D. Friedman and D. Wise, CONS Should Not Evaluate Its Arguments, Indiana Tech. Rep. 44, Nov. 1975.
• 11: [11] A. Goldberg and R. Paige, Stream Processing, Rutgers report LCSR-TR-46, Aug. 1983.
• 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: [13] G. Kahn and D. MacQueen, "Coroutines and Networks of Parallel Processes", Proc. 1977 IFIP congress, North-Holland, 1977.
• 14: B Liskov , E Moss , A Snyder , R Atkinson , J C. Schaffert , T Bloom , R Scheifler, CLU reference manual, Springer-Verlag New York, Inc., New York, NY, 1984
• 15: Raymond P. Polivka , Sandra Pakin, APL: The Language and Its Usage, Prentice Hall Professional Technical Reference, 1975
• 16: 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]
• 17: [17] G. Ruth, S. Alter, and W. Martin, A Very High Level Language for Business Data Processing, MIT/LCS/TR-254, 1981.
• 18: Guy L. Steele, Jr., Common LISP: the language, Digital Press, Newton, MA, 1984
• 19: 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]
• 20: 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]
• 21: Philip. Wadler, Listlessness is better than laziness II: composing listless functions, on Programs as data objects, p.282-305, April 1986, Copenhagen, Denmark
• 22: [22] R. Waters, "A Method for Analyzing Loop Programs", IEEE Trans. on Software Engineering, 5(3), May 1979.
• 23: [23] R. Waters, LetS: an Expressional Loop Notation, MIT/AIM-680, Oct. 1982.
• 24: 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]
• 25: Richard C. Waters, The Programmer's Apprentice: A Session with KBEmacs, IEEE Transactions on Software Engineering, v.11 n.11, p.1296-1320, November 1985 [doi>10.1109/TSE.1985.231880]
• 26: [26] R. Waters, OSS: Efficient Compilation of Synchronizable Series Expressions, MIT/AI/TR-959, June 1987.
• 27: [27] D. Wile, Generator Expressions, USC Information Sciences Institute Technical Report ISI/RR-83-116, 1983.
• 28: Wm. A. Wulf , Ralph L. London , Mary Shaw, An introduction to the construction and verification of Alphard programs, Proceedings of the 2nd international conference on Software engineering, p.390, October 13-15, 1976, San Francisco, California, United States
• 29: [29] Military Standard Ada Programming Language, ANSI/MIL-STD-1815A-1983, U.S. Government Printing Office, February 1983.
• 30: [30] Lisp Machine Documentation, Symbolics, Cambridge MA, 1986.

INDEX TERMS

Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Interpreters

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.1 Expressions and Their Representation
          Subjects: Simplification of expressions

General Terms:
Algorithms, Languages