Efficient Translation of Lazy Functional Logic Programs into Prolog

Abstract. In this paper, we present a high-level implementation of lazy functional logic programs by transforming them into Prolog programs. The transformation is controlled by generalized definitional trees which specify the narrowing strategy to be implemented. Since we consider a sophisticated narrowing strategy, a direct mapping of functions into predicates is not possible. Therefore, we present new techniques to reduce the interpretational overhead of the generated Prolog code. This leads to a portable and efficient implementation of functional logic programs. 1 Introduction In recent years, a lot of proposals have been made to amalgamate functional and logic programming languages [15]. Functional logic languages with a sound and complete operational semantics are based on narrowing, a combination of the reduction principle of functional languages and the resolution principle of logic languages. Narrowing, originally introduced in automated theorem proving [26], is used to solve equations by finding appropriate values for variables occurring in arguments of functions. A narrowing step instantiates some variables in a goal and applies a reduction step to a redex of the instantiated goal. The instantiation of goal variables is usually computed by unifying a subterm of the goal with the left-hand side of some rule. Example 1. Consider the following rules defining the addition and comparison of natural numbers which are represented by terms built from 0 and s