Curry [12] is a multi-paradigm language aiming to amalgamate several important declarative programming paradigms. It combines in a seamless way features from functional programming (nested expressions, lazy evaluation, higher-order functions), logic programming (logical variables, partial data structures, built-in search), and concurrent programming (concurrent evaluation of constraints with synchronization on logical variables). Moreover, Curry provides additional features in comparison to the pure languages (compared to functional programming: search, computing with partial information; compared to logic programming: more efficient evaluation due to the deterministic evaluation of functions). It also amalgamates the most important operational principles developed in the area of integrated functional logic languages: ``residuation'' and ``narrowing'' ([8], see [7] for a survey on functional logic programming).
A Curry program specifies the semantics of expressions, where goals, which occur in logic programming, are particular constraint expressions. Executing a Curry program means simplifying an expression until a value (or solution) is computed. To distinguish between values and reducible expressions, Curry has a strict distinction between (data) constructors and operations or defined functions on these data. Hence, a Curry program consists of a set of type and function declarations. The type declarations define the computational domains (constructors) and the function declarations the operations on these domains. Curry combines various features known in declarative programming, like higher-order functions, constraints and the possibility to use constraint solvers for various domains, encapsulated search [11], a Hindley/Milner-like polymorphic type system [3], monadic I/O [24] and features for communication and distributed programming [14]. A detailed description of these features can be found in [12]. In the following we will only outline those which are necessary to understand the ideas of our analysis.