Pandora : non-deterministic parallel logic programming
Reem Bahgat · Spiral (Imperial College London) · 1991
I co n sid er m y s e lf a p riv ileg ed student.I had tw o rem arkable supervisors: K eith Clark and S tev e G regory.I am grateful to both o f them .K eith Clark w ith his v isio n and vast k n o w led ge, as w e ll as his continuous ch allen ge to the results, w as a m ajor d rivin g force to a ch ie v e the contributions o f the th esis.W ork in g and brainstorm ing w ith S tev e G regory w as a m otivatin g and profitable exp erien ce.I h op e that our partnership as w ell as our friendship w ill last for years to com e. M y first m eetin g w ith D a v id Warren and R ong Y an g in 1 9 8 7 had a great in flu en ce on m y w ork.W e d iscu sse d the advantages and d isad van tages o f the " ex clu siv e relation" in P -P rolog, b ased on w h ich the b a sic A ndorra m o d el w a s later on d evelop ed .I am a lso grateful to S e if H aridi and D a v id W arren for in vitin g m e to several P E P M A w ork sh op s in S w e d e n and B risto l w h ich g a v e m e the opp ortu nity to d iscu ss the w ork w ith m em bers o f their groups.I had lo n g d iscu ssion s w ith Jim C ram m ond con cern in g the d esign o f the Pandora abstract machine; thank you Jim.I m u st a lso thank a num ber o f p eo p le w h o read earlier drafts o f the th esis and supplied extrem ely inform ative com m ents.T h ey are (in alphabetical order): K eith Clark, A n d rew D a v iso n , S te v e G regory, B o b K em p, and E van T ick.S p ecia l thanks to A ndrew D a v iso n for his tim e and patience in reading ev en the final draft o f the th esis.I b e lie v e that the D ep artm en t o f C om puting at Im perial C o lle g e and the lo g ic p rogram m in g group in the departm ent w ere the right ch o ice.It w as a gro w in g exp erien ce to spend the last four years at this place.M y research has b een supported by a scholarship from U n iv ersity o f L o n d on as w e ll as an O .R .S. award, to w h o m I am m ost grateful.L ast but n ot least, I w ou ld like to express m y gratitude first to m y parents and then to m y friends w h o tolerated m y ups and d ow n s in the last four years.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 193 8.3.3.7.The Pandora Deadlock Handler 193 8.3.3.8.Scheduling 195 8.3.3.9.Failure and Backtracking 196 8.3.Summary 197 9. Conclusions 200 9.1.Summary 200 9.2.Related Research 202 9.3.Future Research 203 R eferences 205In 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 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 .