Concurrent constraint logic programming: Difference between revisions

Revision as of 16:23, 30 June 2011

Latest revision as of 21:24, 20 August 2024

(23 intermediate revisions by 19 users not shown)

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]].

[[syntax (logic)|Syntactically]], concurrent constraintsconstraint 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,<ref>Frühwirth, Thom. "[https://www.sciencedirect.com/science/article/pii/S0743106698100055 Theory and practice of constraint handling rules]." [[The Journal of Logic Programming]] 37.1-3 (1998): 95-138.</ref> but are used for programming a constraint simplifier or solver rather than concurrent processes.

==Description==

Line 11:

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 andare equated.

The first semantical difference between regular and concurrent constraint logic programming is about the condition when more than one clause can be used for proving a goal. Non-concurrent logic programming tries all possible clauses when rewriting a goal: if the goal cannot be proved while replacing it with the body of a fresh variant of a clause, another clause is proved, if any. This is because the aim is to prove the goal: all possible ways to prove the goal are tried. On the other hand, concurrent constraint logic programming aims at programming parallel processes. In general concurrent programming, if a process makes a choice, this choice cannot be undone. The concurrent version of constraint logic programming implements processes by allowing them to take choices, but committing to them once they have been taken. Technically, if more than one clause can be used to rewrite a literal in the goal, the non-concurrent version tries in turn all clauses, while the concurrent version chooses a single arbitrary

clause: contrary to the non-concurrent version, the other clauses will never be tried. These two different ways for handling multiple choices are often called "don't know nondeterminism" and "don't care nondeterminism".

When rewriting a literal in the goal, the only considered clauses are those whose guard is entailed by the union of the constraint store and the equation of the literal with the clause head. The guards provide a way for telling which clauses are not to be considered at all. This is particularly important given the commitment to a single clause of concurrent constraint logic programming: once a clause has been chosen, this choice will be never reconsidered. Without guards, the interpreter could choose a "wrong" clause to rewrite a literal, while other "good" clauses exist. In non-concurrent programming, this is less important, as the interpreter always tries all possibilities. In concurrent programming, the interpreter commits to a single possibility without trying the other ones.

A second effect of the difference between the non-concurrent and the concurrent version is that concurrent constraint logic programming is specifically designed to allow processes to run without terminating. Non-terminating processes are common in general in concurrent processing; the concurrent version of constraint logic programming implements them by not using the condition of failure: if no clause is applicable for rewriting a goal, the process evaluating this goal stops instead of making the whole evaluation fail like in non-concurrent constraint logic programming. As a result, the process evaluating a goal may be stopped because no clause is available to proceed, but at the same time the other processes keep running.

Synchronization among processes that are solving different goals is achieved via the use of guards. If a goal cannot be rewritten because all clauses that could be used have a guard that is not entailed by the constraint store, the process solving this goal is blocked until the other processes add the constraints that are necessary to entail the guard of at least one of the applicable clauses. This synchronization is subject to [[Deadlock (computer science)|deadlock]]s: if all goals are blocked, no new constraints will be added and therefore no goal will ever be unblocked.

A third effect of the difference between concurrent and non-concurrent logic programming is in the way a goal is equated to the head of a fresh variant of a clause. Operationally, this is done by checking whether the variables in the head can be equated to terms in such a way the head is equal to the goal. This rule differs from the corresponding rule for constraint logic programming in that it only allows adding constraints in the form variable=term, where the variable is one of the head. This limitation can be seen as a form of directionality, in that the goal and the clause head are treated differently.

Line 30:

==History==

The study of concurrent constraint logic programming started at the end of the 1980s, when some of the principles of [[concurrent logic programming]] were integrated into constraint logic programming by [[Michael J. Maher]]. The theoretical properties of concurrent constraint logic programming were later studied by various authors, suchincluding asMartin Rinard and [[Vijay A. Saraswat]].<ref>{{Cite book |last=Saraswat |first=Vijay A. |url=http://dx.doi.org/10.7551/mitpress/2086.001.0001 |title=Concurrent Constraint Programming |date=1993 |publisher=The MIT Press |doi=10.7551/mitpress/2086.001.0001 |isbn=978-0-262-29097-5}}</ref>

==See also==

* [[Curry (programming language)|Curry]], a logic functional programming language, which allows programming concurrent systems [http://www.informatik.uni-kiel.de/~curry,/examples/#residuation].

* [[ToonTalk]]

* [[Janus (concurrent constraint programming language)|Janus]]

* [[Alice (programming language)|Alice]]

== References ==

{{reflist}}

==Bibliography==

*{{cite book

| first=Kim

| last=MarriotMarriott

| coauthorsauthor2=Peter J. Stuckey

| title=Programming with constraints: An introduction

| year=1998

| publisher=MIT Press

}} {{ISBN |0-262-13341-5}}

*{{cite book

| first=Thom

| last=Fr&uuml;hwirthFrühwirth

| coauthorsauthor2=Slim Abdennadher

| title=Essentials of constraint programming

| year=2003

| publisher=Springer

}} {{ISBN |3-540-67623-6}}

*{{cite journal

| first=Joxan

| last=Jaffar

| coauthorsauthor2=Michael J. Maher

| title=Constraint logic programming: a survey

| journal=Journal of logicLogic programmingProgramming

| volume=19/20

| pages=503–581

| year=1994

| doi=10.1016/0743-1066(94)90033-7

| doi-access=free

}}

[[Category:Constraint programming]]

[[Category:Constraint logic programming]]

[[Category:Programming paradigms]]

[[Category:Concurrent computing]]

[[Category:Constraint programming]]

[[Category:Logic programming]]

[[ja:並行制約プログラミング]]