A compositional analysis of evaluation-order and its application

ABSTRACT

We present a compositional definition of the order of evaluation of variables in a lazy first-order functional language. Unlike other published work, our analysis applies to all evaluation strategies which may use strictness information to change the normal (lazy) order of evaluation. At the same time it can be adapted to pure lazy evaluation yielding a sharper analysis in this case. It can also be adapted to take advantage of any information about the order in which primitive functions evaluate their arguments. The time complexity of the method is that of strictness analysis. We also present a compositional definition of the set of variables which denote locations where the result of an expression might be stored. This analysis yields a simple solution to the aliasing problem. Using these two analyses we develop a new algorithm for the destructive update problem.

REFERENCES

• Blo86: Adrienne Bloss , Paul Hudak, Variations on strictness analysis, Proceedings of the 1986 ACM conference on LISP and functional programming, p.132-142, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319857]
• Blo87: Bloss A., Hudak P. Path Semantics, Mathe,natical Foundations of Programming Language Semantics, LNCS 298, 476-489, Springer-Verlag, 1987.
• Blo89a: Adrienne Gael Bloss, Path analysis and the optimization of nonstrict functional languages, 1989
• Blo89b: Adrienne Bloss, Update analysis and the efficient implementation of functional aggregates, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.26-38, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99373]
• Gop89: K. Gopinath , J. L. Hennessy, Copy elimination in functional languages, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.303-314, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75304]
• Hud85: 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]
• Hud87: Hudak P. A semantic model of reference counting and its abstraction, S. Abramsky and C. Hankin, editors, Abstract Interpretation of Declarative Languages, Ellis Horwood Ltd., 1987.
• Hug87: Hughes J. Analysing strictness by abstract interpretation of continuations, S. Abramsky and C. Hankin, editors, Abstract Interpretation of Declarative Languages, Ellis I-Iorwood Ltd., 1987.
• Myc81: Mycroft A. Abstract interpretation and optiraising transformations .for applicative programs, PhD thesis, University of Edinburgh, 1981.
• Sch86: Schmidt D.A. Denotational Semantics, Allyn and Bacon, 1986.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Control structures

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

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Functional constructs
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

General Terms:
Algorithms, Languages, Verification