Strictness analysis

From Wikipedia, the free encyclopedia

You have new messages (last change).

In computer science, strictness analysis is 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 π is the projection which head-evaluates its list argument.

There was a large amount of research on strictness analysis in the 1980s.

Retrieved from "http://en.wikipedia.org../../../s/t/r/Strictness_analysis.html"