Andorra-I

The Basic Andorra model has been implemented in the form of a prototype parallel Prolog system called Andorra-I. Andorra-I supports the full Prolog language and, in addition, is able to support programs which use implicit coroutining in the style of committed-choice languages. The Andorra-I system runs both on sequential machines and on shared-memory multiprocessors, in particular the Sequent Symmetry. On multiprocessor machines it provides completely transparent exploitation of both dependent and-parallelism and or-parallelism. In its exploitation of or-parallelism, it follows closely the or-parallel Prolog system, Aurora. In its exploitation of dependendent and-parallelism, it follows closely the parallel Parlog system, JAM.

The Basic Andorra model is an execution model for logic programs. The initial motivation of the model was the transparent exploitation of dependent and-parallelism and or-parallelism in logic programs, but the model can also be seen as providing an elegant combination of Prolog and flat committed choice languages.

The Basic Andorra model uses the idea developed by Prof. D H D Warren that goals which do not have to guess what clause to try (determinate goals) should be executed before other goals, and that these goals can be executed in parallel. In more detail

• Goals can be executed early, and in parallel (giving dependent and-parallelism), as soon as they are determinate. A goal is determinate if one can determine a unique clause to match the goal. In Andorra-I, only head unification and certain builtin goals in the body are used in detecting determinacy.
• When no goal is determinate, a goal is selected and a choicepoint is created for that goal as in Prolog. Normally the leftmost goal will be selected, as in Prolog. Choicepoints may be explored in parallel (giving or-parallelism), following the SRI model for example.

Tony's home page. Aurora. The Bristol scheduler.