Strictness analysis

Strictness analysis refers to any algorithm used to prove that a function in a non-strict functional programming language is actually strict in one or more of its arguments. This information is useful to compilers because strict functions can be safely compiled to use a more efficient calling convention.

Approaches to strictness analysis include

• Abstract interpretation, which approximates each function in the program by a function from divergence properties of the arguments to divergence properties of the results. As pioneered by Alan Mycroft, this used a two-point domain, with 0 denoting the set $\{\bot \}$ considered as a subset of the argument or return type, and 1 denoting all values in the type.

• Demand analysis, which models each function by a function from value demands on the result to value demands on the arguments. A function is strict in an argument if a demand for its result leads to a demand for that argument.

• Projection-based strictness analysis, introduced by Philip Wadler and R.J.M. Hughes, which uses strictness projections to model more subtle forms of strictness, such as head-strictness in a list argument. A function $f$ is considered head-strict if $f=f\circ \pi$, where $\pi$ is the projection which head-evaluates its list argument.

There was a large amount of research on strictness analysis in the 1980s, but interest in the subject seems to have largely died out.