Skip to main content

Posted in Research Topics.

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)