Functions and Lazy Evaluation in Prolog

There are several proposals for extending Prolog with functional capabilities. The basic idea is to enlarge the language with function definitions that are translated (or expanded) into Prolog predicates, analogously to what is done for Definite Clause Grammars (DCG's). It is easy to perform such a translation for a basic functional extension, but it requires an additional effort to incorporate more sophisticated functional capabilities such as higher order, lambda abstractions and lazy evaluation. In this paper we describe an extension that covers all these features. The main novelty is our treatment of laziness, as it is (optionally) associated to data type constructors instead of functions. We have found this approach very flexible, easy to use and efficient.