Needed Narrowing in Prolog

We describe the implementation of needed narrowing deployed in a compiler of a functional-logic language and present a few related concepts and results. Our implementation is obtained by translating rewrite rules into Prolog source code and optionally applying a set of optimizations to this code. We benchmark the effectiveness of each individual optimization. We show that our implementation is more efficient than all other previously proposed similar implementations. We measure both execution times, as is customarily done, and memory allocation that turns out to be a significant factor. We solve equations using a semi-strict equality relation that generalizes classic strict equality with sometimes a smaller search space. We give a new, more declarative and accessible formulation of a definitional tree, a crucial concept of our approach, and we present a simple algorithm to build definitional trees. We briefly explore a notion of simplification that is applicable to and sometimes benefi..