Parallel Evaluation Strategies for Functional Logic Languages
Sergio Antoy, Rachid Echahed, Michael D. Hanus · The MIT Press eBooks · 1997
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 unifiers 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 define a sequential strategy similar in scope to other narrowing strategies used in modern lazy functional logic languages. Then, based on the sequential strategy, we define a parallel narrowing strategy---the first ever to be proposed---that joins in a seamless way the operational behavior of functional and logic computations for the largest class of programs used in functional logic languages. Our parallel strategy has several noteworthy characteristics: it is the first complete narrowing strategy which evaluates ground expressions in...