|
Abstract : |
We introduce novel, sound, complete, and locally optimal evaluation strategies for functional logic programming languages. Our strategies combine, in a non-trivial way, two landmark techniques in this area: the computation of uniers performed by needed narrowing in inductively sequential rewrite systems and the simultaneous reduction of a necessary set of redexes performed by rewriting in weakly orthogonal, constructor-based rewrite systems. First, we dene a sequential strategy similar in scope to other narrowing strategies used in modern lazy functional logic languages. Then, based on the sequential strategy, we dene a parallel narrowing strategy that has several noteworthy characteristics: it is the rst complete narrowing strategy which evaluates ground expressions in a fully deterministic, optimal way; it computes shortest derivations and minimal sets of solutions on inductively sequential rewrite systems; and when combined with term simplication, it subsumes and improves all recently developed optimizations of narrowing for overlapping rewrite rules. 1, |
