Andorra and AKL

Appeared in Volume 6/4, November 1993

borbor@divsun.unige.ch
Boris Borcic
21st June 1993

Searching for the string "AKL" or "Andorra" fails on any of the FAQ-lists. Would someone provide a pointer ?

sverker@sics.se
Sverker Janson
22nd June 1993

The Basic Andorra Model is a way to execute definite clause programs that allows dependent and-parallelism to be exploited transparently. It also supports nice programming techniques for search programs. The idea is to first reduce all goals that match at most one clause. When no such goal exists, any goal (e.g., the left-most) may be chosen. The BAM was proposed by David H. D. Warren, and his group at Bristol has developed an AND-OR parallel implementation called Andorra-I, which also supports full Prolog. See:

Seif Haridi and Per Brand. Andorra Prolog, an integration of Prolog and committed choice languages. In Proc. of the FGCS 1988. ICOT, Tokyo, 1988.

Vitor Santos Costa, David H. D. Warren, and Rong Yang. < Two papers on the Andorra-I engine and preprocessor >. In Proc. of the 8th ICLP. MIT Press, 1991.

Steve Gregory and Rong Yang. Parallel Constraint Solving in Andorra-I. In Proc. of FGCS'92. ICOT, Tokyo, 1992.

AKL (Andorra Kernel Language) is a concurrent constraint programming language that supports both Prolog-style programming and committed choice programming. Its control of don't know nondeterminism is based on the Andorra model, which has been generalised to also deal with nondeterminism encapsulated in guards and aggregates (such as bagof) in a concurrent setting. See:

Sverker Janson and Seif Haridi. Programming Paradigms of the Andorra Kernel Language. In Proc. of ILPS'91. MIT Press, 1991.

Torkel Franzen. Logical Aspects of the Andorra Kernel Language, SICS Research Report R91:12, Swedish Institute of Computer Science, 1991.

Torkel Franzen, Seif Haridi, and Sverker Janson. An Overview of the Andorra Kernel Language. In LNAI (LNCS) 596, Springer-Verlag, 1992.

Sverker Janson, Johan Montelius, and Seif Haridi. Ports for Objects in Concurrent Logic Programs. In Research Directions in Concurrent Object-Oriented Programming. MIT Press, 1993 (forthcoming).

The above papers on AKL are available by anonymous FTP from: ftp://sics.se/pub/ccp/papers
An (as yet non-released) prototype implementation of AKL is available for research purposes (contact sverker@sics.se).

bmtong@cs.cuhk.hk
Bo-Ming Tong
22nd June 1993

Aggregates (e.g. bagof)?

Suppose I collect all the solutions to a predicate with something like findall/3. In Prolog, the execution order is highly predictable, but in a concurrent language such as AKL, one may wish to send/receive messages to the predicate used in findall/3. In the other words, we cannot create a nondeterminate choice point just because a sub-system deadlocks. But, rather, we should create the choice point only if a system-wide deadlock is encountered. However, this will violate the original intention of findall/3.

Would somebody explain how this is handled ? Or have I missed something ?

sverker@sics.se
Sverker Janson
23rd June 1993

AKL handles this using two concepts: stability of "sub-systems" and quietness of solutions in aggregates.

The purpose of stability is to control nondeterminism in this kind of situation. Intuitively, a "sub-system" of an AKL configuration is stable if nothing except introducing nondeterminism remains to be done there, and further computation outside it cannot affect it by adding constraints to its environment. Nondeterminism may be introduced inside a stable "sub-system". (By affecting is meant causing failure or the entailment of constraints in the "sub-system".)

Solutions collected by aggregates have to be quiet in the sense that they do not restrict variables external to the aggregate.

Given suitable restrictions on where nondeterminism is introduced (and, of course, if indeterminism is avoided), computations will be confluent, i.e., highly predictable.

As a very simple example I give the following AKL program:

member(X, [X|_]).
member(X, [_|Y]) :- member(X, Y).

?- bagof(X, member(X, L), Y), L = [1,2,3].

Other examples can be found in:

Sverker Janson and Seif Haridi. Programming Paradigms of the Andorra Kernel Language. In Proc. of ILPS'91. MIT Press, 1991.