A relationship between abstract interpretation and projection analysis

ABSTRACT

Abstract interpretation and projection analysis are two techniques for finding out information about lazy functional programs. Two typical uses of these techniques are speeding up sequential implementations, and the introduction of parallelism into parallel implementations. Our main result is the proof of a relationship between a certain class of projections and a certain class of abstract interpretations. One of the claims of projection analysis is that it can find out information about head-strictness, whilst abstract interpretation cannot. We show that there are at least two intuitive notions of head-strictness, and that one of them can be determined using abstract interpretation.

REFERENCES

• 1: Geoffrey L. Burn, Evaluation transformers—a model for the parallel evolution of functional languages, Proc. of a conference on Functional programming languages and computer architecture, p.446-470, October 1987, Portland, Oregon, United States
• 2: G.L. Burn. Abstract Interpretation and the Parallel Evaluation of Functional Languages. PhD thesis, Imperial College, University of London, March 1987.
• 3: G.L. Burn. Using projection analysis in executing lazy functional programs. Draft Manuscript, July 1989.
• 4: G.L. Burn, C.L. Hankin, and S. Abramsky. Strictness analysis of higher-order functions. Science of Computer Programming, 7:249-278, November 1986.
• 5: P. Dybjer, Inverse image analysis, 14th International Colloquium on Automata, languages and programming, p.21-30, July 1987, Karlsruhe, Germany
• 6: 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]
• 7: Dieter Maurer, Strictness computation using special &lgr;-expressions, on Programs as data objects, p.136-155, April 1986, Copenhagen, Denmark
• 8: A. Mycroft. Abstract Interpretation and Optiraising Transformations for Applicative Programs. PhD thesis, University of Edinburgh, Department of Computer Science, December 1981. Also published as CST- 15-81.
• 9: Philip Wadler , R. J. M. Hughes, Projections for strictness analysis, Proc. of a conference on Functional programming languages and computer architecture, p.385-407, October 1987, Portland, Oregon, United States
• 10: P.L. Wadler. Strictness analysis on non-fiat domains (by abstract interpretation over finite domains). In S. Abramsky and C.L. H ankin, editors, Abstract Interpretation of Declarative Languages, chapter 12, pages 266-275. Ellis Horwood Ltd., Chichester, West Sussex, England, 1987.

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency
  F.3 LOGICS AND MEANINGS OF PROGRAMS

General Terms:
Languages, Theory, Verification