Strictness analysis

Philip Wadler

Strictness analysis aids time analysis

Philip Wadler. 15'th ACM Symposium on Principles of Programming Languages, San Diego, California, January 1988.

Analysing time complexity of functional programs in a lazy language is problematic, because the time required to evaluate a function depends on how much of the result is ``needed'' in the computation. Recent results in strictness analysis provide a formalisation of this notion of ``need'', and thus can be adapted to analyse time complexity.

Available in: dvi, ps, dvi.gz, ps.gz.

Projections for strictness analysis

Philip Wadler and R.J.M. Hughes. 3'rd International Conference on Functional Programming Languages and Computer Architecture, Portland, Oregon, September 1987.

Contexts have been proposed as a means of performing strictness analysis on non-flat domains. Roughly speaking, a context describes how much a sub-expression will be evaluated by the surrounding program. This paper shows how contexts can be represented using the notion of projection from domain theory. This is clearer than the previous explanation of contexts in terms of continuations. In addition, this paper describes finite domains of contexts over the non-flat list domain. This means that recursive context equations can be solved using standard fixpoint techniques, instead of the algebraic manipulation previously used.

Available in: dvi, ps, dvi.gz, ps.gz.

Strictness analysis on non-flat domains (by abstract interpretation over finite domains)

Philip Wadler. Chapter in Samson Abramsky and Chris Hankin, editors, Abstract Interpretation, Ellis Horwood, 1987.

Available in: dvi, ps, dvi.gz, ps.gz.

Philip Wadler,