Spiral (Imperial College London) · 1991 · 34 citations · 1 references
Open access
ComputingComputer EngineeringComputer ScienceParallel AlgorithmsParallel ComputingProgramming LanguagesConcurrent ProgrammingData ParallelismLogic ProgrammingParallel Computing SystemsParallel Programming ModelsLogic Parallel ProgrammingParallel Logic ProgrammingParallel Programming
8.3.3.2.The Choice-point Stack 186 8.3.3.3.The Trail 187 8.3.3.4.The Deadlock List 188 8.3.3.5.The Trailing Mechanism 189 8.3.3.5.1.Trailing a Process Structure 190 8.3.3.5.2.Trailing a Variable 191 8.3.3.5.3.Trailing a Hanger 192 8.3.3.6.Collecting Suspended Processes in the Deadlock Phase 8.3.3.7.The Pandora Deadlock Handler 8.3.3.8.Scheduling 8.3.3.9.Failure and Backtracking 8.3.Summary 9. Conclusions 200 9.1.Summary 9.2.Related Research 9.3.Future Research R eferencesL o g i c p r o g r a m m i n g has emerged as another form of declarative language, based on first order predicate logic.This formalism was originally devised for the purpose of studying human reasoning, therefore logic programming languages are declared to be particularly human oriented.In Chapter 2, and-parallelism is classified into several types.The most interesting one is referred to as s t r e a m a n d -p a r a l l e l i s m : the concurrent evaluation of goals in a conjunction which share variables, with the values of the shared variables communicated incrementally among the goals.The special significance of stream and-parallelism is that it provides a useful programming paradigm, namely that of parallel communicating processes.The problem in implementing stream and-parallelism is that concurrently executing goals may generate conflicting bindings to shared variables.One of the goals must then be forced to undo its bindings and generate alternative ones.Other goals that are sharing these variables must also backtrack to their state of computation before the conflicting bindings were made.This behaviour does not seem to coexist well with the idea of stream and-parallelism, where shared variable bindings act as "messages" between processes.This is why a new family of logic programming languages, called c o m m i t t e d -c h o i c e l o g i c p r o g r a m m i n g l a n g u a g e s , has been developed.These languages are based on committed-choice non-determinism instead of don't-know non-determinism.The use of committed-choice nondeterminism, together with a suspension mechanism that delays binding a goal variable until after commitment, ensures that all variable bindings are committed bindings: that is, they will not be undone.Members of this family are the Relational Language (Clark and Gregory, 1981), Parlog (Clark and Gregory, 1986), Concurrent Prolog (CP) (Shapiro, 1983), and Guarded Horn Clauses (GHC) (Ueda, 1985).Committed-choice non-determinism makes the committed-choice languages less suitable than Prolog for applications which require searching through multiple solutions, but it has had the substantial benefit of allowing very simple and efficient implementations of stream and-parallelism (Crammond, 1988;Foster, 1988).Another major contribution of these languages has been to make logic programming applicable to a wide range of new applications: those which can naturally be expressed as systems of concurrent, communicating processes.Examples of these applications are systems programming (Foster, 1988), discrete event simulation (Broda and Gregory, 1984), and specification, verification and simulation of In 1988, David Warren proposed the b a s i c A n d o r r a m o d e l (Yang, 1988;Yang, 1989): a new execution model which transparently extracts stream and-parallelism from Prolog programs.In this model, execution alternates between two phases: the and-parallel phase and the non-deterministic phase.During the a n d -p a r a l l e l p h a s e , all deterministic goals are evaluated concurrently.A goal is d e t e r m i n i s t i c if it has at most one clause that is unifiable with it.This is checked by simple run-time tests, intended to be deduced by a compile-time analysis.When no deterministic goals remain, a n o n -d e t e r m i n i s t i c p h a s e is started in which a choice point is created for the leftmost goal.For each search branch, a new and-parallel phase is begun, running all deterministic goals until they are exhausted.The basic Andorra model executes search programs in a coroutining manner which can significantly reduce the search space in many cases, resulting in a more intelligent problem-solving behaviour than either a sequential evaluation, as in Prolog, or a fully eager parallel evaluation as in C P [i, I, &,;].An additional bonus of this novel form of "lazy non-determinism" is to make an implementation of an integrated system combining stream and-parallelism and A t e r m is either a logical variable, a constant, or a structured term, f(Ti, ..., Tm), which represents a function whose name is f, its arity is m, and its arguments T i , ..., Tm are terms.A l i s t is a structured term that is oftenly used in logic programming.For convenience, a special syntax is used for lists.A list with head X and tail Xs is written as [XlXs] while the empty list is denoted by '[]'.A l o g i c a l v a r i a b l e is an unquoted alphanumeric identifier beginning with either an upper-case letter or an underscore.For example, X, _x, Y 1 2, Y_ 1 2 are all variables.A logical variable is initially an u n b o u n d v a r i a b l e that is i n s t a n t i a t e d when bound to a non-variable term T. Once instantiated, a logical variable cannot be bound to a different term, i.e. it is a single assignment variable.A term which contains no unbound variables is known as a g r o u n d te r m . F i f t h G e n e
1