Strictness Analysis

Strictness Analysis (SA) determines during compilation whether functions definitely evaluate their arguments, and is essential for PFP systems that retain normal-order termination properties. However, SA time complexity is exponential. Though worst-case behaviour may be exponential, is it possible to find the fixed point efficiently for the common, well-behaved functions? The following two papers show how a simple lattice representation of finite height, with a monotonicity rule and a synergistic search algorithm, leads to a new combinatorially-implosive technique based on tracking "frontiers" in the lattice:

  • "Finding fixpoints in abstract interpretation" (Peyton Jones and Clack,in Abstract Interpretation of Declarative Languages eds. S.Abramsky and C. Hankin, Chapter 11, pp 246-265, ISBN 0-7458-0109-9, 1987)
  • "Strictness analysis - a practical approach" (Clack and Peyton Jones, LNCS 201:35-49, ISSN 0302-9743, 1985)

Christopher D. Clack
Department of Computer Science
UCL
Gower Street
London
WC1E 6BT

 clack@cs.ucl.ac.uk