On narrowing strategies for partial non-strict functions

Abstract

We study completeness of narrowing strategies for a class of programs defining (possibly partial and non-strict) functions by means of equations, with a lazy semantics, so that infinite values are also admissible. We consider a syntactical restriction introduced by Echahed, under which he proved that any narrowing strategy is complete for specifications defining total functions with finite values. Unfortunately things are not so pretty for the larger class of programs that we consider. So we see that laziness of strategies is necessary in order to cope with non-strictness, fairness if we want to compute infinite values, and syntactically complete specifications (those including rules covering all possible patterns for each function) if we are also interested in the computation of partial values.