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.
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.
Philip Wadler,
