Copy elimination in functional languages

ABSTRACT

Copy elimination is an important optimization for compiling functional languages. Copies arise because these languages lack the concepts of state and variable; hence updating an object involves a copy in a naive implementation. Copies are also possible if proper targeting has not been carried out inside functions and across function calls. Targeting is the proper selection of a storage area for evaluating an expression. By abstracting a collection of functions by a target operator, we compute targets of function bodies that can then be used to define an optimized interpreter to eliminate copies due to updates and copies across function calls. The language we consider is typed lambda calculus with higher-order functions and special constructs for array operations. Our approach can eliminate copies in divide and conquer problems like quicksort and bitonic sort that previous approaches could not handle. We also present some results of implementing a compiler for a single assignment language called SAL on some small but tough programs. Our results indicate that it is possible to approach a performance comparable to imperative languages like Pascal.

REFERENCES

• 1: Alfred V. Aho , Jeffrey D. Ullman, Principles of Compiler Design (Addison-Wesley series in computer science and information processing), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1977
• 2: A. Neirynck , A. J. Demers, Computation of aliases and support sets, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.274-283, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41650]
• 3: Adrienne Bloss , Paul Hudak, Path Semantics, Proceedings of the 3rd Workshop on Mathematical Foundations of Programming Language Semantics, p.476-489, April 08-10, 1987
• 4: 3.1%. Ellis. A Compiler for VLIW Architectures. PhD thesis, Yale University, December 1984.
• 5: William E. Weihl, Interprocedural data flow analysis in the presence of pointers, procedure variables, and label variables, Proceedings of the 7th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.83-94, January 28-30, 1980, Las Vegas, Nevada [doi>10.1145/567446.567455]
• 6: K. Gopinath, Copy elimination in single assignment languages, Stanford University, Stanford, CA, 1988
• 7: Paul Hudak, A semantic model of reference counting and its abstraction (detailed summary), Proceedings of the 1986 ACM conference on LISP and functional programming, p.351-363, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319876]
• 8: Paul Hudak , Adrienne Bloss, The aggregate update problem in functional programming systems, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.300-314, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318660]
• 9: Paul Hudak , Jonathan Young, Higher-order strictness analysis in untyped lambda calculus, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.97-109, January 01, 1986, St. Petersburg Beach, Florida [doi>10.1145/512644.512653]
• 10: Alan Mycroft. A bstracl interpretation and Oplimisin9 lransformations for applicative programs. PhD thesis, Edinburgh University, 1981.
• 11: Anne Denise Neirynck, Static analysis of aliases and side effects in higher-order languages, Cornell University, Ithaca, NY, 1988
• 12: P.Cousot and R.Cousot. Abstract interpretation. In A CM Symposium on Principles of Programming Languages, ACM, Jan 1977.
• 13: R.J.M.Hughes. Graph Reduction with Super-combinators. Technical Report, Oxford University PRG Technical Monograph PRG-28, 1982.
• 14: d.R.Celoni S.J. and J.L.Hennessy. SAL: A Single. Assignment Language for Parallel Algorithms. Technical Report, Computer Systems Laboratory, Stanford University, July 1981.
• 15: Z.G.Mou and P.Hudak. An algebraic model for divideand-conquer and its parallelism. Journal of Supercompuling, 2(3), 1988.
• 16: Zohar Manna, Introduction to Mathematical Theory of Computation, McGraw-Hill, Inc., New York, NY, 1974

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

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

General Terms:
Algorithms, Languages