Parallel Evaluation Strategies for Functional Logic Languages

1 Introduction The interest in integrating functional and logic programming has grown over the last decade, since the languages resulting from this integration are expected to have advantages of both paradigms. Most proposals with a sound and complete operational semantics for the integration of functional and logic programming languages (see [10] for a recent survey) are based on narrowing. Narrowing solves equations by computing unifiers with respect to an equational theory. Informally, narrowing unifies a term with the left-hand side of a rewrite rule and fires the rule on the instantiated term. Example 1 Consider the following rewrite rules defining the addition for natural numbers, which are represented by terms built with 0 and s