Concurrent constraint logic programming: Difference between revisions

Revision as of 14:55, 31 May 2008

Revision as of 19:32, 11 November 2008

Line 1:

'''Concurrent constraint logic programming''' is a version of [[constraint logic programming]] aimed primarily at programming [[concurrent process]]es rather than (or in addition to) solving [[constraint satisfaction problem]]s. Goals in constraint logic programming are evaluated concurrently; a concurrent process is therefore programmed as the evaluation of a goal by the [[Interpreter (computing)|interpreter]].

Syntactically, concurrent constraints logic programs are similar to non-concurrent programs, the only exception being that clauses include ''[[Guard (computing)|guards'']], which are constraints that may block the applicability of the clause under some conditions. Semantically, concurrent constraint logic programming differs from its non-concurrent versions because a goal evaluation is intended to realize a concurrent process rather than finding a solution to a problem. Most notably, this difference affects how the interpreter behaves when more than one clause is applicable: non-concurrent constraint logic programming [[Recursion|recursively]] tries all clauses; concurrent constraint logic programming chooses only one. This is the most evident effect of an intended ''directionality'' of the interpreter, which never revise a choice it has previously taken. Other effects of this are the semantical possibility of having a goal that cannot be proved while the whole evaluation does not fail, and a particular way for equating a goal and a clause head.

[[Constraint handling rules]] can be seen as a form of concurrent constraint logic programming, but are used for programming a constraint simplifier or solver rather than concurrent processes.

Line 9:

In constraint logic programming, the goals in the current goal are evaluated sequentially, usually proceeding in a [[LIFO]] order in which newer goals are evaluated first. The concurrent version of logic programming allows for evaluating goals in [[Parallel computing|parallel]]: every goal is evaluated by a process, and processes run concurrently. These processes interact via the constraint store: a process can add a constraint to the constraint store while another one checks whether a constraint is entailed by the store.

Adding a constraint to the store is done like in regular constraint logic programming. Checking entailment of a constraint is done via ''[[Guard (computing)|guards'']] to clauses. Guards require a syntactic extension: a clause of concurrent constraint logic programming is written as <code>H :- G | B</code> where <code>G</code> is a constraint called the guard of the clause. Roughly speaking, a fresh variant of this clause can be used to replace a literal in the goal only if the guard is entailed by the constraint store after the equation of the literal and the clause head is added to it. The precise definition of this rule is more complicated, and is given below.

The main difference between non-concurrent and concurrent constraint logic programming is that the first is aimed at search, while the second is aimed at implementing concurrent processes. This difference affects whether choices can be undone, whether processes are allowed not to terminate, and how goals and clause heads and equated.