Time Equations for Lazy Functional (Logic) Languages

Elvira Albert, Josep Silva, and Germán Vidal

2003 Joint Conf. on Declarative Programming (AGP'03), Reggio Calabria (Italy), pp. 13-24, 2003.

There are very few approaches to measure the execution costs of lazy functional (logic) programs. The use of a lazy execution mechanism implies that the complexity of an evaluation depends on its context, i.e., the evaluation of the same expression may have different costs depending on the degree of evaluation required by the different contexts where it appears. In this paper, we present a novel approach to complexity analysis of functional (logic) programs. We focus on the construction of equations which compute the time-complexity of expressions. In contrast to previous approaches, it is simple, precise (i.e., it computes exact costs rather than upper/lower bounds), and fully automatic.

Available: PS PDF BibTeX-Entry

Germán Vidal