Extended unification algorithms for the integration of functional programming into logic programming

AbstractExtended unification algorithms are considered for the integration of a functional language into a logic programming language. The extended language is a particular case of logic programming language with equality. A comprehensive survey is given which is structured following the procedural semantics taken for the functional language. This survey includes past works based on evaluation and derivation (as procedural semantics of the functional language) and new algorithms based on surderivation. These algorithms are compared especially regarding their completeness. Also, we discuss issues arising in practice when different surderivation strategies are used, as these influence directly efficiency and especially termination. This leads us to propose an algorithm based on lazy surderivation which compares favorably with the others and endows logic programming with two advanced features of functional programming: automatic coroutining and handling of infinite data structures without extra control