Effective Strictness Analysis with HORN Constraints

We introduce a constraint-based framework for strictness analysis applicable to ML style languages supporting higher-order functions, let-style polymorphism and algebraic data types. The analysis produces strictness types for expressions in a program. A strictness type is defined using Boolean constraints. Perhaps surprisingly, the Boolean constraints that arise during analysis are in HORN, which makes the operations on them amenable to efficient implementation. We have implemented the approach within a highly optimising Haskell compiler (GHC) and give a comparison with the current strictness analyser of GHC.