Independence in CLP languages

Studying independence of goals has proven very useful in the context of log ic programming. In particular, it has provided a formal basis for powerful automatic parallelization tools, since independence ensures that two goals may be evaluated in parallel while preserving correctness and efficiency. W e extend the concept of independence to constraint logic programs (CLP) and prove that it also ensures the correctness and efficiency of the parallel evaluation of independent goals. Independence for CLP languages is more com plex than for logic programming as search space preservation is necessary b ut no longer sufficient for ensuring correctness and efficiency Two additio nal issues arise. The first is that the cost of constraint solving may depe nd upon the order constraints are encountered. The second is the need to ha ndle dynamic scheduling. We clarify these issues by proposing various types of search independence and constraint solver independence, and show how th ey can be combined to allow different optimizations, from parallelism to in telligent backtracking. Sufficient conditions for independence which can be evaluated "a priori" at run-time are also proposed. Our study also yields new insights into independence in logic programming languages. In particula r, we show that search space preservation is not only a sufficient but also a necessary condition for ensuring correctness and efficiency of parallel execution.