Polymorphic strictness analysis using frontiers

ABSTRACT

This paper shows how to implement sensible polymorphic strictness analysis using the Frontiers algorithm. A central notion is to only ever analyse each function once, at its simplest polymorphic instance. Subsequent non-base uses of functions are dealt with by generalising their simplest instance analyses. This generalisation is done using an algorithm developed by Baraki, based on embedding-closure pairs. Compared with an alternative approach of expanding the program out into a collection of monomorphic instances, this technique is hundreds of times faster for realistic programs. There are some approximations involved, but these do not seem to have a detrimental effect on the overall result. The overall effect of this technology is to considerably expand the range of programs for which the Frontiers algorithm gives useful results reasonably quickly.

REFERENCES

• Abr85: Samson Abramsky, Strictness analysis and polymorphic invariance, on Programs as data objects, p.1-23, April 1986, Copenhagen, Denmark
• AJ91: Samson Abramsky , Thomas P. Jensen, A relational approach to strictness analysis for higher-order polymorphic functions, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.49-54, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99593]
• Bar91: Gebreselassie Baraki, A note on abstract interpretation of polymorphic functions, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.367-378, June 1991, Cambridge, Massachusetts, United States
• BHA85: G. L. Burn , C. L. Hankin , S. Abramsky, The theory of strictness analysis for higher order functions, on Programs as data objects, p.42-62, April 1986, Copenhagen, Denmark
• Bur87: G.L. Burn. Abstract Interpretation and the Parallel Evaluation of Functional Languages. PhD thesis, Imperial College, University of London, March 1987.
• CP85: Chris Clack , Simon L. Peyton Jones, Strictness analysis—a practical approach, Proc. of a conference on Functional programming languages and computer architecture, p.35-49, January 1985, Nancy, France
• HH91: Sebastian Hunt and Chris Hankin. Fixed points and frontiers: a new perspective. Journal of Functional Programming, 1(1):91- 120, January 1991.
• HH92: Chris Hankin , Sebastian Hunt, Approximate Fixed Points in Abstract Interpretation, Proceedings of the 4th European Symposium on Programming, p.219-232, February 26-28, 1992
• Hun91: Sebastian Hunt. Abstract Interpretation o} Functional Languages: From Theory to Practice. PhD thesis, imperial College, University of London, 1991.
• HWe90: P. Hudak and P. Wadler (editors). Report on the programming language Haskell, a non-strict purely functional language (Version 1.0). Technical Report YALEU/DCS/RR777, Yale University, Department of Computer Science, April 1990.
• KHL91: Ryszard Kubiak , John Hughes , John Launchbury, Implementing Projection-based Strictness Analysis, Proceedings of the 1991 Glasgow Workshop on Functional Programming, p.207-224, August 12-14, 1991
• Mil78: R. Mflner. A theory of type polymorphism in programming. Journal of Computer and System Science, 17(3):348-375, 1978.
• PL92: Simon L. Peyton Jones , David R. Lester, Implementing functional languages, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• Sew91: Julian Seward. Towards a strictness analyser for haskell: Putting theory into practice. Master's thesis, University of Manchester, Department of Computer Science, 1991. Available as University of Manchester Technical Report UMCS-92-2-2.
• Wad87: P.L. Wadler. Strictness analysis on non-fiat domains (by abstract interpretation over finite domains). In S. Abramsky and C.L. Hankjn, 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.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Procedures, functions, and subroutines

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Functional constructs

General Terms:
Algorithms, Languages, Performance, Verification