Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

The design of a distributed interpreter for concurrent Prolog Tam, Chun Man 1984

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-UBC_1984_A6_7 T34.pdf [ 2.41MB ]
Metadata
JSON: 831-1.0051857.json
JSON-LD: 831-1.0051857-ld.json
RDF/XML (Pretty): 831-1.0051857-rdf.xml
RDF/JSON: 831-1.0051857-rdf.json
Turtle: 831-1.0051857-turtle.txt
N-Triples: 831-1.0051857-rdf-ntriples.txt
Original Record: 831-1.0051857-source.json
Full Text
831-1.0051857-fulltext.txt
Citation
831-1.0051857.ris

Full Text

T h e D e s i g n o f a D i s t r i b u t e d I n t e r p r e t e r f o r C o n c u r r e n t P r o l o g b y C H U N M A N T A M B . S c , T h e U n i v e r s i t y o f B r i t i s h C o l u m b i a , 1981 A T H E S I S S U B M I T T E D IN P A R T I A L F U L F I L L M E N T O F T H E R E Q U I R E M E N T S FOR T H E D E G R E E O F M A S T E R O F S C I E N C E in T H E F A C U L T Y O F G R A D U A T E S T U D I E S D e p a r t m e n t o f C o m p u t e r S c i e n c e We a c c e p t t h i s t h e s i s as c o n f o r m i n g t o t h e r e q u i r e d s t a n d a r d T H E U N I V E R S I T Y O F B R I T I S H C O L U M B I A S e p t e m b e r , 1984 © C h u n Man T a r n , 1984 In presenting t h i s thesis i n p a r t i a l f u l f i l m e n t of the requirements for an advanced degree at the University of B r i t i s h Columbia, I agree that the Library s h a l l make i t f r e e l y a v a i l a b l e for reference and study. I further agree that permission for extensive copying of t h i s thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. I t i s understood that copying or publication of t h i s thesis for f i n a n c i a l gain s h a l l not be allowed without my written permission. Department of COMPUTER SCIENCE The University of B r i t i s h Columbia 1956 Main Mall Vancouver, Canada V6T 1Y3 Date VOX. i,l<)&f DE-6 (3/81) ABSTRACT Prolog i s a programming language based on predicate l o g i c . Its successor, Concurrent Prolog, was designed to meet the needs of a multiprocessing environment to the extent that i t may be desirable as a succinct language for wri t ing operating systems. Here, we demonstrate the f e a s i b i l i t y of implementing a distr ibuted interpreter for Concurrent Prolog using t r a d i t i o n a l programming tools under a multiprocess structuring methodology. We w i l l discuss the considerations that must be made in a d i s t r ibuted environment and how the constructs of the language may be implemented. In p a r t i c u l a r , several subtle p i t f a l l s associated with the implementation of read-only variables and the propagation of new bindings w i l l be i l l u s t r a t e d . In addi t ion , a modification to Shapiro's treatment of read-only variables i s proposed in an attempt to "clean up" the semantics of the language. (The discussion w i l l centre around a pr imit ive version of an interpreter for the language written in Zed (a language s imi lar to C) on an Unix- l ike operating system, Verex. Although a br ie f introduction of Prolog and Concurrent Prolog w i l l be given, i t is assumed that the reader i s f ami l iar with the paper A Subset  of Concurrent Prolog and Its Interpreter by E.Y. Shapiro [Shapiro83] .) Abstract C O N T E N T S 1.0 I n t r o d u c t i o n . . . . 1 1.1 Motivation for Logic Programming 2 2 . 0 S e q u e n t i a l P r o l o g 5 2.1 Procedural Semantics of Prolog 6 2.2 Declarative Semantics of Prolog 8 2.3 Associated Problems with Prolog 10 3 . 0 I n t r o d u c i n g . . . C o n c u r r e n t P r o l o g ! 13 3.1 Guards, Clean Up These Cuts! 15 3.2 Read-Only Variables * 17 3.3 Perpetual Processes 22 4 . 0 O v e r v i e w o f T a r g e t M a c h i n e / E n v i r o n m e n t 23 5 . 0 D e s i g n o f t h e I n t e r p r e t e r 27 5.1 Representation of Axioms 27 5.1.1 Compacted Representation of Axioms 28 5.1.2 Structure-Sharing 30 5.2 Uni f i ca t ion Under Our Representation 32 5.3 Div i s ion of Workload Between Processes 35 5.3.1 Goal Process (Or-Node) 35 5.3.2 Clause Process (And-node) 36 Contents i i i 5.4 Dealing with Successes/Coping with Failures 39 5.5 Mutual Exclusion Considerations • • 46 5.6 Read-Only Variables 49 5.7 Supporting Dynamic Databases 50 6.0 Evaluation and Conclusions 52 6.1.1 Possible Optimizations 55 6.1.2 Summary 56 7.0 References 59 Contents i v L I S T O F I L L U S T R A T I O N S Figure 1. Sample Prolog Code - Append ( l i s t l , l i s t 2 , resul t ) 5 Figure 2. Comparison of (P->Q) with (-P or Q) 7 Figure 3. Sample And-Or Solution Tree 7 Figure 4. Concurrent Prolog Equivalents of A Conventional Language . 14 Figure 5. Sample Axiom for Concurrent Prolog 16 Figure 6. Example of the Commit Operator 17 Figure 7. Verex Communication Primit ives 24 Figure 8. A Lisp CONS-cell 28 Figure 9. Compacted/Contiguous Representation of Axioms 29 Figure 10. Structure Sharing: Skeleton and Variables of An Axiom . . . 31 Figure 11. Reference Loops - Unifying Two Unbound Variables * 33 Figure 12. Process Tree from An And-Or Tree 36 Figure 13. Deadlock: Broadcast by Parent Clause-Process 41 Figure 14. Deadlock: Broadcast by Reporting Process 42 Figure 15. Creating a Broadcast Server 43 Figure 16. Mutual Exclusion Problems of "Cross-Layer" Reference Loops 47 Figure 17. Publ ic iz ing References . 48 Figure 18. BNF description of Syntax Accepted by Current Interpreter . 53 Figure 19. Performance Measurement on a Bounded-Wait Merge 54 L i s t of I l l u s t r a t i o n s v A C K N O W L E D G E M E N T S I would l i k e to thank the many professors that I have had the pleasure of meeting during my years at the University of B r i t i s h Columbia especial ly those who have introduced me to the f i e ld s of logic programming and operating systems. In par t i cu la r , I would l i k e to thank my supervisor, Dr. H. Abramson, and A. Kusalik for the i r guidance and helpful comments in the researching th i s thes is . Acknowledgements vi 1.0 INTRODUCTION There are currently three major classes of programming languages. These are: 1. Procedural (von Neumann) Languages 2. Functional Languages 3. Logic Programming Procedural languages such as Pascal , A l g o l , Fortran, Cobol, and PL/I have "s ide-effects" as t h e i r underlying theme. • A variable i s assigned a value. • A variable may be bound to zero or more values. • A program i s a descript ion of a sequence of actions or procedures to be performed (hence the name "procedural") . Functional languages (the most predominate being LISP) are based on Church's Lambda-Calculus. They are ( i d e a l l y ) characterized by: • No side-effecting • Values return via functions only (rather than side-effects on "g loba l " variables) • Exactly one value i s returned by a function • Programs resemble the d e f i n i t i o n of desired computations. Logic programming languages are pr imari ly based on predicate-calculus . Major character i s t ics of logic programming include: Introduction 1 No side-effecting Programs resemble clauses/axioms of f i r s t -o rder logic and are simply statements of facts . The computation of a program can be considered as invoking a mechanical theorem prover to assert the desired goal. "Results" of a computation are obtained by ins tant ia t ing the unbound terms of a log ica l re la t ion (predicate) . 1.1 M O T I V A T I O N F O R L O G I C P R O G R A M M I N G The major advantages of logic programming languages over the other two classes can be seen by comparing the above l i s t of a t t r ibutes : • Programs written in both functional and logic languages resemble the d e f i n i t i o n of the problem rather than the algorithm from a procedural language. I n t u i t i v e l y , i t appears easier to state the d e f i n i t i o n of a problem than to devise the algorithm to solve i t . • Since logic programs are simply l i s t s of facts , they can be v e r i f i e d more ea s i ly . One need simply examine each statement, independent of a l l other  statements, and decide whether i t i s a correct representation of the domain. For a procedural language, we must also understand a l l the inter-dependencies between each statement. Introduction 2 • A variable in a procedural or functional language may be assigned zero or more times. I t i s the re spons ib i l i ty of the programmer to i n i t i a l i z e any variable before using i t in a computation and to assure that variables are not assigned inadvertently. In a logic program, a variable may be bound at most once. Hence, we need not worry about some errant portion of code inva l ida t ing a legitimate value. Furthermore, an axiom s t i l l holds even i f one of the variable i s u n i n i t i a l i z e d ; the resul t of the computation would then be expressed as a re lat ionship to the variable (eg. father(x) , y+1) rather than concrete values such as John or 3. • For those who have noted that the differences stated so far between a functional language and a logic language are only minor ones, i t i s suggested that logic programming i s , in fact , more powerful. Since a logic program "returns" values v ia arguments of a predicate, a "procedure" may return a set of values whereas a function, by i t s d e f i n i t i o n , may return exactly one value. Also , since logic languages are simply statements, there may be s imi lar statements (each defining a speci f ic case of the problem); i f more than one statement can resul t in the success of the goal ( i e . mult iple so lut ions) , then the choice o f . statements i s random. A goal invoked several times may resul t in several indeterminate resul t s . As the desire for v e r i f i a b l e programs increases and the cost of computing power decreases, logic programming i s gaining much interes t . Prolog (PROgramming in LOGic) [Kowalski74] [Warren77] i s a programming language which i s considered to f a l l into th i s category. This thesis examines the f e a s i b i l i t y of applying Prolog in a multiprocessing environment by implementing a d i s t r ibuted Introduction 3 interpreter for a variant of the language, Concurrent Prolog, introduced by Shapiro [Shapiro83]. In the next chapter, an overview of Sequential Prolog i s presented, including a discussion of i t s bad points along with the good. Chapter Threeintroduces the features of Shapiro's Concurrent Prolog. The target system, Verex, i s described in Chapter Four followed by Chapter Five which discusses the problems and design decisions of the implementation. An evaluation of the interpreter i s presented with performance measurements in the concluding chapter. Introduction 4 2.0 SEQUENTIAL PROLOG A program in Prolog [Kowalski74] [Warren77] [Nilsson80] i s a set of "statements" of the form1 P <- Ql & Q2 & . . . & Qn. and can be viewed in two ways: 1. as an implicat ion rule where Ql, Q2, . . . , Qn are the antecedents and P i s the consequent, 2. as a procedure declaration with P as the head of the procedure and Ql, Q2, . . . , Qn as the body. Append ( * l i s t l , n i l , * l i s t l ) . Append ( *head l . * t a i11 , * l i s t 2 , *head l . * sub l i s t ) <- Append ( * t a i l l , * l i s t 2 , * s u b l i s t ) . Figure 1. Sample Prolog Code - Append ( l i s t l , l i s t 2 , resul t ) . In the above example, only the d e f i n i t i o n of append i s given: 1. When the second l i s t i s empty, the result i s simply the f i r s t l i s t . We w i l l use the syntax from Prolog/MTS [Goebel80] and augment i t where necessary. (The i n f i x operator " . " i s the constructor predicate which can be thought of as a concatenation symbol.) Sequential Prolog 5 2. Otherwise, the new l i s t i s simply the head (or f i r s t element) of the f i r s t l i s t followed by the l i s t formed by the concatenation of the t a i l (or remainder) of the f i r s t l i s t with the second l i s t . There were no statements ins truct ing the interpreter how to construct a new l i s t . The d e f i n i t i o n of the problem i_s i t s e l f the program. 2.1 PROCEDURAL SEMANTICS OF PROLOG From the programmer's point of view, there are two major differences between Prolog and a procedural language: 1. There may be multiple "procedure declarat ions" with the same name. When a procedure P i s to be executed, a two-way pattern matching scheme ca l l ed uni f ica t ion i s f i r s t used to pick which procedure i s to be invoked. Then, execution proceeds recursively with each "statement" in the body of the chosen declarat ion. (The system i s said to have resolved [Robinson65] from the head of the clause to the system consist ing of the terms in the body of the clause.) If one of these statements causes program f a i l u r e , the system backtracks to the nearest decision point and a new choice i s t r i e d . 2. A formal argument of a procedure may ei ther be an input parameter or an output parameter even though there i s no spec i f ic indicator (such as the reserved word VAR in Pascal to designate a "va lue-resul t " parameter). The choice need not be made in advance. Instead, the choice i s determined at Sequential Prolog 6 procedure invocation, allowing some programs to be ran "backwards". For example, the procedure ADD (x ,y , z ) may be ran as ADD ( 1, 2, z ) to y i e l d a value of 3 for z • ADD ( x, 3, 5 ) to y i e l d a value of 2 for x • ADD ( 1, y , 1 ) to y i e l d a value of 0 for y . This two-way capabi l i ty i s a powerful one in that i t turns uni-purpose procedures into multi-purpose ones. 1 1 P h P Q 1 P->Q 1 1 1 i -P or Q | 1 T | F T I 1 1 T | " T ' | 1 T | F F 1 F | F | i F | T T 1 T | T | 1 F | T F 1 T | T ' | j Figure i 2. Compari son of (P->Q) with (-P or Q) | i Sequential Prolog 7 2.2 DECLARATIVE SEMANTICS OF PROLOG Wearing our logic ians ' caps, the Prolog interpreter i s a theorem prover working on a a subset of f i r s t -order logic known as Horn Clauses. These are clauses with exactly one negation. (Recall that P -> Q i s equivalent to (-P or Q) as in Figure 2 on page 7) . Each clause or implicat ion rule i s a statement about what i s true about the domain at hand rather than a descript ion of how to compute the so lut ion . A " so lu t ion" i s obtained by specifying a clause (possibly with unknowns) as the goal and asking Prolog to f ind an instance of the unknowns for which the goal can be asserted. Prolog must backchain from the goal using the "reverse" of Modus Ponens ( impl ica t ion) . In order to assert the goal Q, in P -> Q, one must assert P, recurs ively . I f P can be asserted then Q must have a truth value of TRUE otherwise TRUE -> FALSE y ie ld ing FALSE w i l l inval idate the d e f i n i t i o n of P -> Q as an axiom. On the other hand, i f P cannot be asserted, we cannot comment on the truth value of Q 2; FALSE -> TRUE and FALSE -> FALSE both y i e l d TRUE. Thus, computation amounts to searching an And-Or Solution Tree (Figure 3 on page 7) for a path from the root to one of i t s leaves. Or-nodes indicate where more than one possible axiom (dis junct) may contribute to the so lut ion . And-nodes of the tree " t i e " together the conjuncts of an axiom. (For each [Reiter79] suggests the use of the Closed World Assumption to treat the f a i lu re to f ind a solution as negation and, thereby, assigning the truth value of FALSE to Q. Sequential Prolog 8 conjuct, a sub-path must be found spanning the height of the subtree rooted at the And-node.) The tree i s obtained by the following sequence: 1. Take the goal as the root (an Or-Node) 2. Find a l l axioms in the database whose heads are potent ia l ly uni f iable with the goal and create an And-Node for each, " t y i n g " them to the root. 3. For each of these axioms, treat each term in i t s body as a new subgoal and recursively create subtrees for them. If an axiom does not have have a body, i t i s known as a base or ground axiom and forms a leaf of the tree. (The tree i s , of course, an i m p l i c i t one; that i s i t i s never generated but i s i m p l i c i t in the execution of the interpreter with conjunctions implied by sequential solution of brother-goals and dis junctions implied by backtracking.) Sequential Prolog 9 2.3 ASSOCIATED PROBLEMS WITH PROLOG So far , I have claimed Prolog to be a " log ic programming language". In r e a l i t y , i t i s only a good approximation. In order to have true logic programming we need true para l le l i sm in trying a l l choices (dis juncts) and in solving a l l conjuncts. Prolog i s merely a sequential simulation of th i s process. It accomplishes dis junction by backtracking (where necessary) and conjunction by sequentially resolving each conjunct. Whenever a dis junct proves unsuccessful, any bindings made by that path i s undone • and an a l ternat ive path i s t r i e d . (As in f i r s t order l o g i c , a dis junction f a i l s when a l l of i t s dis juncts f a i l . ) After solving one conjunct, the next subgoal in the conjunction i s attempted. (A conjunction f a i l s when any of i t s conjuncts f a i l s . ) This sequential simulation can either be i n e f f i c i e n t using breadth-f irs t * searching or susceptible to non-termination (even when the goal i s provable!) i f depth-f i r s t searching repeatedly picks an errant path as i t s f i r s t choice. The strategy employed by Prolog i s that of depth-f i r s t search supplemented by some control constructs to eliminate some of the dupl icat ion of ef fort between axioms. These constructs are the "cut" operator, a speci f ic order of execution and the introduction of side-effects by allowing creation / destruction of axioms: Order of Execution Prolog has chosen to define a spec i f ic order of execution: the database i s searched in order of axiom entry and conjuncts are solved from l e f t to r i g h t . The speci f ic search order allows knowledge gained from one axiom to Sequential Prolog 10 " f low" to another in the database. Consider two axioms P <- Q & R and P <- -Q & R, in that order. I f Q causes f a i l u r e , the second axiom w i l l s t i l l necessarily solve -Q. By re ly ing on the order of search, the second axiom may be rewritten as P <- R to avoid the duplicat ion of e f for t . A x i o m C r e a t i o n a n d D e s t r u c t i o n Axiom creation and destruction in Prolog i s analogous in power to the inclus ion of EVAL as a program-callable function in Lisp . In an interpret ive system, they allow using user-generated data interchangeably with program source code. In Prolog, however, a major use of these constructs i s to maintain state information - using axioms as a form of s t a t i c variables and defeating the advantage of the single-binding log ica l var iable . T h e " C u t " O p e r a t o r The "cut" ("/") operator allows the program to d irect the execution of Prolog. Since the Prolog interpreter usually has an " I f I can solve the problem, don't worry about how I go about computing i t " a t t i tude , a major objection to the language i s that i t lacks the control which i s essential in explo i t ing the knowledge b u i l t into the programs. Thus, the cut i s used to give more control back to the programmer and to d i rec t the interpreter away from i r re levant choices. Sequential Prolog 11 On encountering a " cu t " , a l l backtracking information i s discarded. A l l choices made at the time w i l l never be undone. The interpreter commits i t s e l f to the current search path. T r a d i t i o n a l l y , the "NOT" predicate has been implemented using the "cut" and re l i e s on the ordering of axioms as: Not ( *x ) <- *x & / & FAIL. Not ( *x ). I f x can be asserted, then the interpreter commits to the choice of the f i r s t "Not" axiom and subsequently causes f a i l u r e . Otherwise, the second i s chosen and the "Not" succeeds. We have discussed the common usages of each of the three control constructs but not only are they beyond the scope of f i r s t -o rder l o g i c , the i r use s i g n i f i c a n t l y reduces the v e r i f i a b i1 i t y of the software. They force the programmer to correct ly sequence axioms and to understand the relat ionships between one axiom and another. Worst of a l l , the intent of a "cut" i s often obscure and eliminates the "two-way" aspect of procedures. In addit ion, these constructs rely on assumptions which v i r t u a l l y eliminate the p o s s i b i l i t y of porting the same program to a d i s t r ibuted system. Sequential Prolog 12 3 . 0 I N T R O D U C I N G . . . C O N C U R R E N T P R O L O G ! To address some of the c r i t i c i sms of Sequential Prolog, Shapiro, in his paper A Subset of Concurrent Prolog and Its Interpreter, introduces a variant of Prolog which i s endowed with the elegance of multi-process structuring and raises the p o s s i b i l i t y of using a logic-programming language for the development of operating systems. Below, we b r i e f l y examine the properties of Concurrent Prolog and how i t qua l i f i e s for i t s intended role of a systems programming language. Shapiro l i s t s four essential elements for a concurrent programming language: concurrency, communication, synchronization, and indeterminacy. Concurrent Prolog supports these as fol lows: C o n c u r r e n c y By simultaneously solving the terms of a conjunction. Each term in the body of an axiom can be regarded as a program/procedure invocation. By executing each program with a separate (poss ibly , v i r t u a l ) processor, each becomes a Concurrent Prolog process. C o m m u n i c a t i o n Via the uni f i ca t ion of shared var iables . When a term with an unbound var iable , say P(x) , i s unif ied with a term having a constant as the corresponding argument, say P(3), information i s being communicated from the l a t t e r process to the former. S y n c h r o n i z a t i o n Is accomplished by the introduction of Read-Qnly variables . A process having a read-only variable must block i t s e l f unt i l Introducing.. .Concurrent Prolog! 13 the variable has been instantiated by some other process. (We w i l l discuss read-only variables further in a following sect ion.) Indeterminacy By simultaneously exploring a l l paths which may provide a solution to the goal. Assuming random a l loca t ion of processing power (due to di f ferent speeds of actual processors, random processor a l l o c a t i o n , e tc . ) and multiple solutions to a goal , the actual solution returned i s a function of time. Procedure Procedure Ca l l Binding Mechanism Process System Process State Communication Process Synchronization Ax i om Solving a Goal Uni f ica t ion Unit Goal Conjunction of Goals Value of Arguments Uni f ica t ion of Shared Variables Read-Only Variables Figure 4. Concurrent Prolog Equivalents of A Conventional Language Introducing.. .Concurrent Prolog! 14 3.1 GUARDS, CLEAN UP THESE CUTS! We have already mentioned that one of the biggest c r i t i c i s m s of Sequential Prolog i s the use of the cut symbol ( " / " ) . Its range and asymmetry often lead to obscure programs. Shapiro recognizing that the control aspect of the cut must be included in a concurrent language, to help synchronize processes, decided to provide a cleaner version ca l led the commit operator ( " | " ) . An example on the use of the commit operator i s given in Figure 6 on page 17. The commit operator i s patterned much after the guarded-if of [Di jkstra76] . I t s p l i t s the body of an axiom into two parts: the guard and the main body (Figure 5 on page 16). In t ry ing a par t i cu lar axiom as an a l ternat ive , the interpreter must solve i t s guard before solving the body and once the guard of one of the dis juncts i s solved, a l l brother-disjuncts are abandoned. The reason that the commit i s a cleaner operator than the cut i s due to i t s symmetry. The asymmetry appears in two forms: 1. In Prolog, choices of a d i s junct ion are t r i e d sequentially (usually from l e f t to r ight in the current subtree). When the cut operator i s encountered, Prolog commits to the current path. A l l branches on one side of th i s path have already f a i l e d and the cut " k i l l s " the remaining branches on the other side. Introducing.. .Concurrent Prolog! 15 I H <- Gl & G2 & . . . & Gm | Bl & B2 & . . . & Bn. | Here H i s the head of the clause, G l , G2, Gm are the guards of the clause, and B l , B2, Bn are the terms in the body of the clause. When no guards are required, the axiom may be written as H <- Bl & B2 & . . . & Bn. Figure 5. Sample Axiom for Concurrent Prolog | i In Concurrent Prolog, a l l guards are executed in para l l e l and the commit operator e f fec t ive ly " k i l l s " the branches on both sides of the current path. 2. A cut has an effect only when i t i s executed. If two alternatives exis t with only one containing a cut, the second a l ternat ive i s , in ef fect , a default . I t i s th i s default assumption that renders the program useless in a concurrent system. Because of the differences in ( v i r t u a l ) processor speeds, the default may be mistakenly chosen even i f the f i r s t a l ternat ive would have succeeded. The commit operator, however, forces every a l ternat ive to be guarded by some (possibly empty) clause. The success of a goal w i l l always necessitate the el imination i t s brother a l ternat ives . Introducing.. .Concurrent Prolog! 16 Database 1. a (*x) <- b l (*x) | c ( *x ) . 2. a (*x) <- b2 (*x) | c ( *x ) . 3. b l (*x) <- d (*x) | f a i l . 4. b2 (*x) <- d (*x) | true. 5. d ( 1). 6. c ( 1). Top-Level Goal <- a ( *x) . Figure 6. Example of the Commit Operator In solving the top-level goal in Concurrent Prolog, resolution may proceed with axioms A l and A2 in p a r a l l e l . The guard in A l must be reduced using axiom A3 while the guard in A2 must use axiom A4. Suppose A3 solves d (*x) with d (1) before A4 can solve i t s guard. A3 commits but the scope of committment i s local and the choice between A l and A2 i s NOT affected. Thus when A3 f a i l s and causes the f a i l u r e of A l , the interpreter i s free to solve the system using A2. As an analogy, "A cut i s to a commit as an i f- then-else i s to a guarded-if". Di j sks t ra argues that every a l ternat ive should be associated with a guard instead of having a default philosophy of the i f - then-e l se . He points out that the lack of symmetry of the i f- then-else may lead to errant choices in concurrent system. Here, Shapiro uses the same arguments for the use of the commit operator over the cut. 3.2 READ-ONLY VARIABLES The second extension to Sequential Prolog i s the introduction of read-only var iables . A variable designated as read-only i s the synchronization mechanism Introducing.. .Concurrent Prolog! 17 between two processes. Read-only variables c l a s s i fy processes into writers and readers. A process t ry ing to unify an unbound variable in another process with a value can be thought of as a wri ter process while the l a t t e r process as the reader. The read-only annotation ("?") indicates that the current process cannot write to the var iable . The reader process must wait u n t i l the variable has been instantiated by some other process before proceeding further with the uni f i cat i on. Formally, i f X? i s a read-only variable and Y i s any variable then Shapiro defines the un i f i ca t ion of X? with Y as fol lows: 1. I f X? has been ins tant ia ted 3 and Y has been instantiated then uni f i ca t ion proceeds as usual with the bindings of X and Y. 2. I f X? has been instantiated and Y unbound then Y becomes instantiated with the binding of X. 3. I f X? i s unbound and Y has been instantiated then uni f ica t ion f a i l s u n t i l X? becomes instantiated by some other process sharing X without the read-only annotation. In the context of read-only var iables , we only require that the predicate name or pr inc ipa l functor be determined for a variable to be considered instant ia ted . This was a design decision in Concurrent Prolog to allow for p a r t i a l l y determined messages. When two variables are uninstantiated but are bound to each other, they are said to reference each other. Introducing.. .Concurrent Prolog! 18 4. I f X? i s unbound and Y i s unbound then uni f i ca t ion succeeds with X and Y referencing 1* each other. Moreover, Y inher i t s the read-only property from X?. Two points need to be considered with th i s d e f i n i t i o n . F i r s t , the d e f i n i t i o n makes the success or f a i lure of un i f i ca t ion time-dependent. Uni f icat ion may f a i l at a given time due to read-only variables but may succeed at a l a ter time. In actual pract ice , a process may unify the two terms repeatedly or eliminate the busy-wait by implementing the t h i r d case in a manner such that the process owning Y must block or suspend u n t i l X? has been instant ia ted . Second, the d e f i n i t i o n of the last case (X? unbound with Y unbound) i s a somewhat controversial one. I t states that after unifying a term such as P (x?) with the head of P ( *y ) <- G ( *y ) . . . | . . . the variable y inher i t s the read-only property and the interpreter i s allowed to continue to reduce the remainder of the axiom. Several questions concerning th i s scheme need to be addressed: • I f the primary intent of read-only variables i s to synchronize processes by suspending a process unt i l a l l of i t s read-only variables are ins tant ia ted , i s i t desirable to allow uni f i ca t ion with an unbound variable to succeed and continue? • Applying Shapiro's de f in i t ion recurs ive ly , i f the variable y la ter becomes bound to some other unbound var iable , the l a t t e r variable should also Introducing.. .Concurrent Prolog! 19 inher i t the read-only property. Is i t desirable to propagate the read-only property throughout the solution tree? Shapiro suggests the use of read-only variables in the head of axioms causing these variables to be s t r i c t l y output variables . (Such axioms are eliminated from further consideration i f the corresponding argument in the goal i s a l i t e r a l . ) That i s , an axiom of the form P ( x?, *y ) <- . . . may only be invoked by a goal of the form <- P ( * x , *y ) . or <- P ( * x , l i t e r a l ) . BUT not of the form <- P ( l i t e r a l , *y ) . At the top-level th i s strategy may be acceptable but elsewhere in the tree, a read-only variable in the head of a clause may cause the read-only property to propagate (possibly several levels ) up the tree , not only down i t . The upward propagation may cause a process which was previously unblocked to become suspended. For example, i f in P ( *x ) <- Q ( *x ) & R ( *x ) . Q ( *y ) <- S ( *y ). S ( z? ) <- . . . R ( 1 ). <- P ( *x ). Q (*x) i s solved pr ior to R (*x) being solved, then the process t ry ing to unify R (*x) with R (1) w i l l suspend due to the variables y and x Introducing.. .Concurrent Prolog! 20 inher i t ing the read-only property from z. Is th i s form of "dynamic suspension" desirable? It i s l i k e l y that the answers to a l l of the above questions are a l l "NO". • I t i s much simpler to implement a uni f i ca t ion algorithm that suspends when attempting to unify an unbound read-only variable with another unbound var iab le ; there i s no need to propagate the read-only property up or down the tree . • The concept of suspending the process u n t i l the ins tant ia t ion of the read-only variable i s a more natural d e f i n i t i o n . • I t i s not c lear what forms of problems require the additional properties specif ied by Shapiro. • More important, one of the major virtues of logic programming i s that one statement or axiom may be inspected independently of the other axioms in the database. One should be able to determine whether the uni f i ca t ion of a term containing an unbound read-only variable with the head of a given axiom w i l l result in suspension without having to " trace" the outcome of the axiom. Hence, the remainder of th i s paper shall replace the las t part of Shapiro's d e f i n i t i o n with • I f X? i s unbound and Y i s unbound then uni f i ca t ion suspends u n t i l X? becomes instant iated. Introducing.. .Concurrent Prolog! 21 3.3 PERPETUAL PROCESSES In Sequential Prolog, a primary use of axiom creation and deletion was to save state information. In a concurrent language, th i s scheme is no longer necessary; a process that stays activated throughout the l i f e of the program never "forgets" i t s own state. (The operating system would, at leas t , restore the state when i t reactives the process.) In Concurrent Prolog, a perpetual process i s simply an axiom that resolves to i t s e l f with possibly di f ferent arguments. eg. P ( x.y ) <- P ( y ). Any local variables would then be the state of the process. The resolution of the or ig ina l axiom can be considered to be a state t r a n s i t i o n . (In our example, a state t r ans i t i on takes place in which the state changes, say, from x to y . ) With such a simple, wel 1 -understood construct, Concurrent Prolog can thus be extended to capture the elegance of an object-oriented language and the d e f i n i t i v e power of state t r ans i t ion diagrams. Introducing.. .Concurrent Prolog! 22 4.0 OVERVIEW OF TARGET MACHINE/ENVIRONMENT It has been suggested that Concurrent Prolog can be used as a multi-processing systems programming language. In order for th i s idea to become r e a l i t y , the interpreter w i l l necessarily require and provide the same multi-tasking c a p a b i l i t i e s found in conventional operating systems. Because of th i s systems-language/operating systems d u a l i t y , i t may be advisable to construct the interpreter using the same design p r inc ip l e s ! One school of thought [Cheriton79.1,81] advocates the use of multi-process s t ructur ing : "Multi-process structuring i s the use of several processes to structure programs. The term process i s used to mean an ent i ty that executes actions sequentially and de te rmin i s t i c a l ly . A process can l o g i c a l l y execute concurrently with other processes . . . . " The Verex operating system [Cheriton79.2], a descendent of Thoth [Cheriton79.1], i s based on th i s design p r i n c i p l e . I t provides inexpensive or 1ight-weight processes: • low overhead process creation / destruct ion, • low overhead process switching, and • inexpensive interprocess communication. Overview of Target Machine/Environment 23 Send ( i d , message ) | Sends the message to the process ident i f i ed by j id and blocks unt i l the destination process j acknowledges with a reply j id = Receive ( message ) j Blocks unt i l a message i s received from any process | and returns the sender's id and the contents of the j message buffer | id = Receive ( message, spec i f i c_ id ) j S imilar to the above except the invoking process j i s blocked u n t i l a message i s received from the | specif ied id j Reply ( message, id ) | Acknowledges the sender ident i f i ed by id with | the contents of the invoker's message buffer (the | invoker does NOT become blocked) j Forward ( message, from_id, to_id ) j Forwards the message received from from_id j to the process t o _ i d . To the process * j t o _ i d , i t would be as i f from_id had j sent the message d i r e c t l y (Note that the invoking j process may have a l t e r the message before forwarding i t . ) j Figure 7. Verex Communication Primit ives j i Furthermore, Verex provides process communication via blocking messages (see Figure 7 on page 24). Processes communicate with f ixed-length messages; the sender of the message i s blocked u n t i l the receiving process acknowledges the message with a reply. Cheriton argues that th i s i s a more natural and more powerful form of interprocess communication: • Other than for synchronization purposes, processes often have a requirement to communicate data. On non-message-based systems, one must Overview of Target Machine/Environment " 24 f i r s t use semaphores, etc . to synchronize the readers and writers of the message buffers and then perform the actual transfer of data, making communications awkward. I t i s more natural to associate a message with the synchronization mechanism. • The Verex communication scheme can, in fact , be used to simulate semaphores. Hence, i t i s as powerful as a semaphore-based scheme. • Blocking-Sends are a natural part of the Remote Procedure Cal l or Server concept. A conventional program wishing a subtask to be performed invokes a procedure; a Verex process wishing the help of a server simply sends a message and i s unblocked when the server has f u l f i l l e d the request with a reply. • Since the sender i s automatically blocked, there can be at most one outstanding message per process. 5 The operating system need not concern i t s e l f with the problems of dynamically a l loca t ing new message buffers. By explo i t ing low-overhead processes, i t has been demonstrated that Cheriton's concepts are both feasible and a t t r a c t i v e : • [Cheriton79.1] designed and implemented the portable multi-user operating systems Thoth and Verex. • [Lockhart79] furthered the work of Cheriton, by designing a v e r i f i a b l e system kernel . 5 Concurrency i s accomplished via multiple processes rather than multiple messages. Overview of Target Machine/Environment 25 • [Deering83] mapped the s ta te- trans i t ion diagrams of the X.25 protocol speci f icat ions onto Verex processes, and thus s i g n i f i c a n t l y improved the v e r i f i a b i 1 i t y of his implementation. • [Boyle82] designed and implemented a d i s t r ibuted version of Verex and showed that Cheriton's design can indeed be implemented on a multi-processor system. In fact , a complete d i s t r ibuted version of Verex, ca l l ed the V-system, was implemented at Stanford [Cheriton83]. For the implementation of the Concurrent Prolog interpreter , the Verex system seems well suited for the task. I t ' s two most a t t rac t ive features, inexpensive creation/destruction and low-overhead process switching makes the system ideal for simulating the brea th- f i r s t searching necessary for Concurrent Prolog. Overview of Target Machine/Environment 26 5 . 0 D E S I G N OF T H E I N T E R P R E T E R Two major c r i t e r i a govern the design of the Concurrent Prolog interpreter : 1. Recognizing that a d i s t r ibuted system w i l l necessarily incur more overhead, due to process scheduling and process switching for example, the interpreter must minimize storage and execution time in order to provide the maximum computing power for the resolution process. 2. The design must not preclude the interpreter from being d i s t r ibuted over several physical processors and multiple address-spaces. 5 . 1 R E P R E S E N T A T I O N O F A X I O M S When designing any database, the representation of the data and i t s relat ionships i s of primary concern. In the case of Concurrent Prolog, the problem i s even more c r i t i c a l ( i f we are to consider the requis i te dupl icat ion of data across multiple address spaces). We must f ind a representation which w i l l optimize both storage requirement and execution time. Usually, i t i s a trade-off between execution speed and memory s ize : increasing the amount of redundant data and increasing storage needs w i l l usually increase execution speed, and vice versa. Luck i ly , there are at least two optimizations available to us. Design of the Interpreter 27 5.1 .1 Compacted Representat ion of Axioms | Figure 8. A Lisp CONS-cell | i i F i r s t , we can improve on the representation of t r e e - l i k e structures such as Lisp expressions and, in our case, Prolog axioms by converting e x p l i c i t information to i m p l i c i t knowledge. In par t i cu la r , e x p l i c i t CAR and CDR l inks (Figure 8) to the next item should be replaced by contiguous storage of information whenever possible. In th i s implementation of Concurrent Prolog, such l inks have been removed where possible. Succeeding elements are placed contiguously; the c e l l at posit ion i has an i m p l i c i t CDR pointing to posit ion (i+1). The structure normally pointed to by the CAR of a c e l l i s now inserted " i n - l i n e " . For a s ing le -ce l l element, nothing has changed. But sub-trees now appear i n - l i n e with a indicator at the front of the sub-tree pointing to the c e l l immediately following the last c e l l occupied by the sub-tree (see Figure 9 on page 29). This compaction scheme reduces our overhead in three ways: 1. Storage is not wasted for l i n k s . Design of the Interpreter 28 P ( x, Q ( y , z ) ) . Lisp Representation: 0 Compacted Representation: 0 Q Q y 0 Figure 9. Compacted/Contiguous Representation of Axioms Execution cycles are not required to dereference l inks (nor to page-in a larger working set under a v i r t u a l memory system). Main memory becomes less fragmented. Al loca t ion i s done in blocks instead of in small c e l l - s i z e chunks. (Less fragmentation w i l l l i k e l y resul t in increased performance of any garbage-collection scheme and decrease paging a c t i v i t y . ) Design of the Interpreter 29 5.1.2 Structure-Sharing The second improvement to our representation i s a technique known as structure-sharing (see Figure 10 on page 31). This i s a scheme developed by Boyer and Moore [Boyer,Moore72] [Warren77] for Sequential Prolog which i s also applicable to Concurrent Prolog in minimizing both storage and execution time. The technique divides an axiom into two parts: the invariant part (or the skeleton of the axiom) and the variables of the axiom. The variables in the skeleton are replaced by "place-holders". The f i r s t unique variable i s replaced with a " 0 " , the second with a " 1 " , and so on. The replacement numbers are, in fact , offsets into a vector of the variables of the axiom. So, an axiom i s now represented as pointers to two vectors: a skeleton vector and a vector of var iables . This representation has the fol lowing advantages: • The separation of skeleton and variables allows the non-changing skeleton to be shared between processes residing in the same address space; thus storage i s reduced by not having to duplicate axioms with common skeletons. • When one of the variables become instant ia ted , only one location has to be updated even i f the variable appears more than once in the axiom. Al so , addit ional storage i s not required for subsequent appearances of the var iab le . Design of the Interpreter 30 Axiom P (*x) <- Q (*y) & R (*z) & S (*x). Skeleton Variables P (0) <- Q (1) & R (2) & S (0). V 1 r Figure 10. Structure Sharing: Skeleton and Variables of An Axiom If the dupl icat ion of an axiom i s necessary within the same address space, the requirements in both storage and time i s proportional only to the number of variables in the axiom. The c e l l s in the skeleton need not be duplicated, only the address of the skeleton need to be copied. Design of the Interpreter 31 5 . 2 U N I F I C A T I O N U N D E R O U R R E P R E S E N T A T I O N For the most part, un i f i ca t ion i s simply two-way pattern matching: • Two atomic terms match only i f they have the same value. (Or in our case, each atomic value i s given a unique id/address and we need only match i d ' s . ) • Two structures (eg. cons(a,b)) match only i f each corresponding sub-structures or sub-terms match recurs ive ly . • I f one of the terms i s an unbound variable and the other i s an atomic value or a structure, then that value i s assigned to the var iable . (For a structure, the actual value assigned may simply be a p o i n t e r / i d e n t i f i e r of the form Struct (struct_num, offset) or a tag [Lee84] of the form Struct ( processed, struct_num, offset ) where process_id i s the i d e n t i f i e r of the process attempting to solve the structure in question, struct_num i s a unique i d e n t i f i e r for an axiom and offset i s the posit ion of the subterm re l a t ive to the beginning of the structure. • I f one or both of the terms i s an instantiated var iable , then uni f i ca t ion proceeds as above using the binding of the var iab le ( s ) . The only case that normal pattern-matching f a i l s to handle i s when both terms are unbound variables . Consider the terms: Design of the Interpreter 32 Unifying P ( * a , *b , *b ) with P ( * c , * c , 2 ) would y i e l d a b c Ref ( b ) Ref ( c ) Ref ( a ) match a with c and f i n a l l y a=b=c=2 match b with c implicit reference between a ana D Figure 11. Reference Loops - Unifying Two Unbound Variables P ( * a , *b , *b ) and P ( * c , * c , 2 ) . We would l i k e uni f ica t ion to y i e l d a=2, b=2, and c=2 but ( i f matching i s done in l e f t to r ight order) we would need to unify two unbound var iables . We need a pattern-matcher that would "remember" the relat ionships between a, b, and c. I n i t i a l l y , a references b, then a and b reference c. I f any one of these variables subsequently become instant iated , then a l l three variables need to be instant iated. A straight forward implementation is to l i n k the three variables together into a c i r c u l a r - l i s t , a reference-1oop, by assigning indicators such as Ref (b) 6 , Ref(c), and Ref(a) to variables a, b, and c, respectively (see Figure 11). In the actual implementation, the variables would be represented s imi lar to that of a structure (eg. Ref (struct_num, o f f se t ) ) . Design of the Interpreter 33 When a variable in one reference loop la ter becomes bound to a variable in a d i f ferent reference loop, the two loops are merged into one single loop. The ordering within the new loop i s unimportant but a self-reference test must be made to ensure that they are indeed two d i s t i n c t loops. As an example, unifying P ( * a , *a ) with P ( *b , *b ) w i l l y i e l d "two" loops jo in ing a and b and an attempt to merge the loops w i l l l i k e l y require a great deal of computer time. One should note that a loop i s preferred over a simply-linked l i s t such as those used in [Warren77], [Levy84], and [Lee84]. When one of the variables in the loop becomes instant iated , a traversal of the loop w i l l make sure a l l variables in the loop are updated. In a simply-linked l i s t such as P? -> Q -> R, i f a variable in the middle of the l i s t , say Q, gets instantiated only the variables in the t a i l of the l i s t are updated. P, in th i s case, w i l l s t i l l not have a binding and may lead to deadlock i f the remaining variables have read-only annotations. Design of the Interpreter 34 5 . 3 D I V I S I O N O F W O R K L O A D BETWEEN PROCESSES A log ica l d i v i s i o n of tasks i s to take the And-Or solution tree (described in a previous section) and create a process for each node in the tree (see Figure 12 on page 36). For each And-node (conjunction of the terms of a clause) , create an And-process (or Clause-process). For each Or-node (a choice of solutions in solving a goal) , create an Or-process (or Goal-process). 5 . 3 . 1 Goal P r o c e s s ( O r - N o d e ) When invoked with a Concurrent Prolog process (a term in Sequential Prolog), a goal-process executes as fol lows: 1. I t searches through the axioms database for axioms whose head i s po tent ia l ly uni f iable with the given term. The searching algorithm may be expedited using the predicate name or pr inc ipa l functor as the primary key and the a r i t y of the predicate as the secondary key. 2. For each of these axioms, i t creates a clause-process and invokes i t with the given term and the t r i a l axiom. 3. I t then waits for one of the clause-processes to commit ( i . e . solve the guard clause) . 4. I f one of the clause-processes does commit, then the goal-process waits for th i s c h i l d to successfully solve the body. If and when the c h i l d process reports success, the goal process, in turn, reports success to i t s parent. Design of the Interpreter 35 1 P (*x) Clause Process | Q d ) . Q(2). R(2)L R(3). I j Clause Processes | | Figure 12. Process Tree from An And-Or Tree: (compare with Figure 3 on | I Page 7) | i i 5. At any time, a c h i l d process which does not contribute to the solution of the goal is destroyed and resources al located to i t reclaimed. 5.3.2 Clause Process (And-node) A clause process i s responsible for the solution of a spec i f ic term, T such as cons (a ,b ) , with a spec i f ic axiom, H <- Gl & G2 & . . . & Gm | Bl & B2 & . . . & Bn. where H i s the head of the axiom, Gl through Gm are the guards, and B l through Bn are the terms of the body. Design of the Interpreter 36 1. I t f i r s t makes local copies of T and the given axiom, so that any bindings i t generates w i l l not affect other brother clause-processes. Note that i f one of the variables references another structure which has unbound var iables , that structure must also be copied. Care must be taken to avoid recurs ively copying the same axioms. For example, i f we unif ied 1. P ( * a , Q ( 1 ) ) . with 2. P ( R ( 1 ), *b ) . variable a would be bound to a subexpression within axiom A l while variable b would be bound to a subexpression within axiom A2. I f the implementation copies the entire axiom instead of only the variables in question, then a loop exists between A l and A2. and a naive implementation would try to create copies of A l and A2 i n d e f i n i t e l y . A simple solution i s to modify the copying mechanism to return a mapping between or ig ina l axioms and the i r copies. Pr ior to a l locat ing a new copy of an axiom, a check of the current * map must be made to determine whether the axiom has already been duplicated. (More on the use of the map in the Mutual Exclusion section.) 2. I t t r i e s to unify T' with H ' , then for each of the guards, i t spawns a goal-process. 3. When a l l of the goal-processes report success, the clause-process commits and reports to i t s parent goal-process. 4. After solving the guards, a goal-process i s generated for each of B l ' through Bn1 and the clause-process again waits. Design of the Interpreter 37 5. When a l l of i t s chi ldren have reported success, i t reports back to i t s parent. Otherwise, when any c h i l d f a i l s , i t reports f a i l u r e . Design of the Interpreter 38 5.4 D E A L I N G W I T H S U C C E S S E S / C O P I N G W I T H F A I L U R E S If a goal-process commits or terminates successfully, the parent clause-process must make public any instant iat ions made by the goal-process. F i r s t , the scratch-copy from the goal-process must be unif ied with the global copy from clause-process. Here, only the variables need be unified but d i rec t copying i s not su f f i c i en t : a brother goal-process may have already instantiated a variable to some par t i cu lar value and th i s value must be matched with those from the reporting process for consistency. If uni f ica t ion f a i l s , then a l l c h i l d goal-processes must be destroyed along with the f a i lure of the clause-process. If un i f i ca t ion succeeds, any new information must be made public to ALL the descendents of the clause-process. In addi t ion, i f the success of the reporting process causes the clause-process to commit or to complete then a report must, in turn , be made to the parent of the clause-process. The problem of broadcasting new instant iat ions i s not a t r i v i a l one. Suggested solutions include: Ignore Broadcasting All-Together We may choose to avoid broadcasting and allow the descendents of the clause process to continue with old information; when descendents commit then l e t uni f i ca t ion f i l t e r out incompatible solutions from conjuncts as f a i lu re of the This i s the same solution (ca l led "Delayed Propagation") suggested by [Levy84]. Design of the Interpreter 39 c lause . 7 On the surface, i t seems that the only draw back to th i s scheme i s late detection of inconsistent bindings. But th i s solution w i l l only work i f there are no read-only variables . With the introduction of read-only var iables , th i s scheme may lead to deadlock. For example, i f the axiom at the clause-process i s P ( *a ) <- Q ( *a ) & R ( a? ) . and the only axioms that are potent ia l ly uni f iable with Q and R are Q ( 2 ) . and R ( 2 ) . We would l i k e the resul t ing computation to succeed with a=2. But when Q commits with a=2, the clause-process updates i t s copy of a and continues waiting for R to f i n i s h computing but by the d e f i n i t i o n of read-only var iables , the goal-process solving R(a?) remains blocked waiting for the ins tant ia t ion of a? before continuing. Let the Parent Clause-Process Handle the Broadcasting When a goal-process reports with new information, the clause-process can f i r s t update the global copy of the variables and then signal each of i t s descendents (except for the one that i n i t i a t e d th i s chain of actions) to update t h e i r copies. The problem i s again one of deadlock. If two c h i l d processes report simultaneously, both would be blocked waiting for reply. The c h i l d that i s serviced f i r s t i s happy but when the clause-process t r i e s to broadcast to the second c h i l d , both c h i l d and parent become blocked waiting for each other to reply (Figure 13 on page 41) Design of the Interpreter 40 1 © Goal Goal A A ildl Child2 Childl Child2 Childl Child2 Two Children Report At Same Time Goal Replies to cnlldi *> Non-blocking Reply Blocking Sena © Goal Childl \ Child2 Deadlock when Goal Broadcasts to Child2 (Deadlock) Figure 13. Deadlock: Broadcast by Parent Clause-Process Let the Reporting Goal-Process Handle the Broadcasting The clause-process may supply the reporting c h i l d with a l i s t of chi ldren to s i g n a l . A s imilar s i tuat ion as for the above scheme arises when two or more goal-processes t ry to broadcast to each other (Figure 14 on page 42). The problem is that information must be passed both ways: c h i l d processes must report upwards and broadcast information must travel downwards. This necessity v io la tes the well-known rule-of-thumb (eg. [Lockhart79] [Deering82] in a Verex environment) that only child-processes should use the blocking send pr imit ive and parent-processes should only use the non-blocking receive pr imit ive to communicate; that i s , "send" up the process tree - never down. Design of the Interpreter 41 © Goal © Goal A 7\ Childl Child2 Childl Child2 Two Children Report At Same Time Goal Replies to Childl Non-Dlocking Reply Blocking send © Goal \ Childl _^Child2 Childl Broadcasts to Child 2 (Deadlock) Figure 14. Deadlock: Broadcast by Reporting Process Create a Broadcast Server As explained in the previous scheme, the problem l i e s in messages being sent both up and down the process tree. What i s needed is a mechanism in which the parent clause-process can i n i t i a t e information down the tree without becoming blocked. By exploi t ing the Verex philosophy of creating multiple servers, there appears to be such a mechanism. When a clause-process receives a report from a c h i l d , i t creates a server process. The broadcast server i s given a l i s t of processes and an updated copy of the clause-process' axiom and i s expected to broadcast to each of the given processes in turn. The clause-process remains free to handle other tasks. Design of the Interpreter 42 Let 's examine, again, the case of simultaneous reports. The clause-process receives one of the reports, updates i t s axiom, unblocks the reporting c h i l d and delegates the re spons ib i l i ty of broadcasting to a new server. I t then i s free to accept a subsequent report and create a second broadcast server (Figure 15 on page 43). The clause-process i s not blocked waiting for broadcasting to complete and neither i s the reporting process. Even i f mult iple broadcast servers exis t at one time, no deadlock can resul t since no process issues a blocking send to these servers. I t i s the broadcaster that issues the send primit ive and a l l i t s receivers are guaranteed to become unblocked in a bounded period of time (needed for a new server to be created). Broadcasterl Broadcasterl Broadcasterz Childl Child2 Childl Child2 Childl Child2 Two Children Report Goal Replys Childl Goal Replys Child2 At Same Time and Creates Broadcasterl and Creates Broadcaster2 Chlld2 may now Receive — • Non-diocklng Reply from Broadcasterl and • Blocking Send Childl may Receive from Broadcaster2 Figure 15. Creating a Broadcast Server Design of the Interpreter 43 Propagation By Request Yet another possible solution [Levy84] [Lee84] i s to broadcast only to processes which have been suspended or have child-processes suspended waiting for the ins tant ia t ion of a read-only var iable . Levy's scheme employs a queue of read-only variables . Whenever a process must wait for the ins tant ia t ion of a var iable , i t f i r s t puts a request in the queue with the var iab le ' s i d e n t i f i e r and i t s own process i d e n t i f i e r and then suspends i t s e l f . When a process instantiates a read-only var iable , i t must "wake-up" a l l processes associated with the var iable . Lee suggests that a process should make a d i rec t request v ia a "need-binding" message to i t s parent. • I f the parent's copy of the variable has been instant ia ted , i t w i l l allow the requesting process to continue with the new bindings. • I f the variable i s unbound and the variable has the read-only annotation, then the parent process waits u n t i l one of i t s other committing child-processes instantiates the requested var iable . • I f the variable i s unbound and the variable i s non-read-only, then" the requesting process i s allowed to continue but i s required to pol l the parent u n t i l the variable becomes instant iated. Design of the Interpreter 44 F i n a l l y , i f the variable references a variable higher-up in the process tree then the parent i s forced to issue a need-binding message of i t s own. Either scheme w i l l probably work . . . providing enough book-keeping information i s ava i lable . Consider the system of processes 1. P ( * x , *y ) <- Q ( * x , *y ) & . . . . 2. Q ( * z , *z ) <- R ( z? ) & 3. R ( 1 ). 4. <- P ( * x , *y ). In t ry ing to unify R (z?) with R (1), process 3 sends a need-binding message for z to i t s parent, process 2. But since z references both x and y , i t now must send a need-binding message for instant iat ion of e i ther of x or y. Continuing up a "degenerate" tree , the overhead in book-keeping w i l l match that of using a broadcast server. Design of the Interpreter 45 5 . 5 M U T U A L E X C L U S I O N C O N S I D E R A T I O N S In the two previous s ec t ions . i t was mentioned that a scratch copy of the axiom was made by the clause-process. The procedure was necessitated by the need to keep uncommitted values local to the t r i a l process. A more general problem, when dealing with any multiprocessing system, i s mutual exclusion - the problem of updating shared data. Ignoring the problems of multiple address spaces, there i s l i t t l e need to duplicate the axioms database. Normally, there i s no mutual exclusion problems associated with the database, since i t i s read-only. Additions are performed usually at the s h e l l - or top- level when no clause- or goal- processes are present. But when we begin allowing Concurrent Prolog programs to generate new axioms, we would then need to introduce a database server or associate some mutual exclusion mechanism (eg. semaphores) with the axioms to synchronize the creation and reading of axioms. We w i l l examine th i s topic further in a l a ter section. A more pressing problem i s the mutual exclusion of the scratch-copy axioms between clause- and goal- processes. Consider the conjunction P ( * a ) & Q ( * a ) being committed with the two axioms P ( *b ) <- Assign ( *b , 2 ) . (note empty guard) Q ( *c ) <- Assign ( * c , 3 ) . (Assume Assign instantiates the f i r s t variable with that of i t s second argument.) Design of the Interpreter 46 1 I P (*a) <- . . . Q (*t>) <- . . . A f t e r G o a l processes | I Goal Process 1 Goal Process 2 commit I I Figure 16. Mutual Exclusion Problems of "Cross-Layer" Reference j j Loops: I f both Goal Processes 1 and 2 commit and the i r local | j copies of x are l inked together as a reference loop, the j | variable "x" becomes "shared" by a l l three processes and j | mutual exclusion mechanisms must be incorporated to prevent j | simultaneous updates to x. | i i In theory, both (empty) guards are solved simultaneously. We can remove the obvious c o n f l i c t by making the parent clause-process (at and-node) s e r i a l i z e the two committals to y i e l d a reference loop of a, b, c. But by creating an e x p l i c i t loop, we would then be vulnerable to concurrent updates of the loop by the two c h i l d "Assign" goal-processes (see Figure 16). One possible solution requires that we associate a semaphore with each loop and store i t s id in each c e l l of the loop. Every update and query must f i r s t secure the semaphore for th i s par t i cu lar loop. An a l ternat ive to such a complex mutual exclusion scheme i s to eliminate the c r i t i c a l section (the loop) a l l - together by removing interprocess l i n k s . In the process of removing interprocess l i n k s , however, we must be careful not to remove intraprocess l i n k s . Consider the fo l lowing: 1. P ( * x , *y ) <- Q ( * x , *y ) & R ( *y ). Design of the Interpreter 47 2. Q ( *x, *x ) . 3. R ( 1 ) . 4. <- P ( *x, *y ) . We would l i k e the resul t to be P (1 ,1) . Hence, in unifying the local copy of Q ( *x , *y) in axiom A l with Q ( *x , *x) in axiom A2, we must keep the intraprocess l inks between *x to *y in A l . We must use the mapping between or ig ina l axioms and t h e i r duplicates (obtained from the copying mechanism) to reproduce any local-copy to local-copy references in the global copy (Figure 17). Only references that can be translated using the "copy-map" should be duplicated. Any other references should be ignored. i | Before Publ i c i z ing | i After Pub l i c i z ing | | Q ( * x , * y ) | x y | x y | I Q ( *x' , V ) | x ' y ' | x ' y 1 j 1 | \ / | \ / 1 1 1 \ / 1 \ / ' 1 j Q ( *x, *x ) | x | x 1 | Figure 17. Pub l i c i z ing References i i Design of the Interpreter 48 5.6 READ-ONLY VARIABLES Read-only variables have already been discussed in the implementation of broadcast servers and the avoidance of mutual exclusion c o n f l i c t s . Here, we w i l l t ry to t i e up the loose ends of the i r implementation. A process t ry ing to unify an unbound read-only variable to some concrete value must f i r s t wait for the variable to be instant iated. To eliminate busy-waits, the process should somehow block i t s e l f u n t i l in s tant i a t ion . An i n i t i a l idea i s to have a process (such a Name-Server) be responsible for a l l read-only var iables . The.owning process would send a request to the server to instantiate the var iable . The server would flag the variable as being requested. When some other process instantiates the variable and recognizes the f lag , i t would send a message to the server which would then unblock the or ig inal requestor. The problem with th i s suggestion i s that because of mutual exclusion considerations, cross-layer l inks have been removed. Unless a process shares and instant iates the requested var iable , the variable can never be reached via a reference l i n k and the requestor w i l l wait i n d e f i n i t e l y . The solution current ly implemented i s to make use of new information as soon as i t become ava i lab le . When some other process instantiates a variable and commits to i t , i t s parent process w i l l make the value public v ia a broadcast server. The information w i l l eventually f i l t e r down the tree to the process owning the read-only variable (which i s now waiting only for a message from a broadcast server) . I f the message i s not an ins tant ia t ion of the read-only var iable , then the process continues waiting after updating i t s copy of the axiom. Design of the Interpreter 49 5.7 SUPPORTING DYNAMIC DATABASES As mentioned in proceeding sections, the database of axioms w i l l usually be s t a t i c . Except for the i n i t i a l loading of the axioms, we rarely require the power of axiom-creation and destruction since state information may be maintained via perpetual processes. Hence no mutual exclusion mechanisms were needed for the database to synchronize accesses from multiple processes. Once in a whi le , however, we would l i k e to exploi t the fact that data may be used as part of the executable source code. For example, a professor may have access to a Prolog interpreter but i s instruct ing a course on a form of logic which has a super-operator ca l led "S" which i s simply a composition of the normal log ica l operators. He requires an interpreter for a programming language ca l led "S_Logic" which w i l l accept normal Prolog source plus the "S" operator. One solution i s to write the S_Logic interpreter on top of the Prolog interpreter . The S_Logic interpreter w i l l need to read in an S_logic axiom, expand the axiom wherever i t encounters the "S" operator, and then pass the new axiom to Prolog. The S_logic interpreter w i l l necessarily create new Prolog axioms when i t loads the S_logic database. By allowing a program to dynamically create and destroy axioms, we now need to synchronize the queries on the database with the addition and deletion of axioms. In l ine with the Verex philosophy, we may create a Database Server to s e r i a l i z e these requests. The server w i l l be required to supply three major services in addition to routine maintenance of the database: Design of the Interpreter 50 1. Find a l i s t of axioms whose head is potent ia l ly uni f iable with a given predicate. 2. Add an axiom to the database. 3. Delete a specified axiom from the database, (eg. Delete the f i r s t axiom whose head i s potent ia l ly uni f iable with a given predicate) . A process requiring one of these services w i l l request i t v ia a message to the database server. The c l i e n t process w i l l then block i t s e l f u n t i l the request has been f u l f i l l e d . Note that service #1 now returns a l j of the axioms that are potent ia l ly uni f iab le instead of only the f i r s t axiom of the l i s t . The server should actual ly create a copy of these axioms to prevent another c l i e n t from making additions or deletions while the f i r s t c l i e n t i s manipulating the l i s t . That i s , a process querying the database should work with a "snapshot" of the database taken at the time of query. This i s consistent with the view that an Or-node "creates" a l l i t s descendants in p a r a l l e l . Design of the Interpreter 51 6.0 EVALUATION AND CONCLUSIONS We have successfully implemented a " f i r s t -at tempt" interpreter has been successfully implemented on the (multi-user) Verex Operating System running on a TI/990. The interpreter i s an experimental one and lacks the power and elegance of those from Edinburgh [Kowalski74] [Warren77], Waterloo [Lee84], and Vancouver [Goebel80]. I t lacks almost a l l of the necessary " b u i l t - i n " predicates (eg.math, predicates) of a production interpreter and only has syntax resembling that of Lisp (Figure 18 on page 53). In addi t ion, a look at the performance character i s t ic s (eg. Figure 19 on page 54) indicates that i t i s s t i l l premature to consider using the current system to support any substantial piece of Concurrent Prolog program: the maximum number of processes that may be active at one time i s too low; there i s currently no garbage co l l ec t ion of processor memory (except for the processor stacks) when a process f a i l s 8 , and the execution speed i s slow. Garbage c o l l e c t i o n was omitted from the current implementation because i t i s considered as part of the normal cycle of resource reclaimation when a process i s destroyed. 52 Evaluation and Conclusions < i dentif ier> <atom> <normal variable> <readonly variable> <variable> <variable l i s t> <function> <argument> <arg l i s t> <predicate name> <term> <term l i s t> <guard> <head> <body> <axiom> <query> examples a sequence of 1 to 30 characters from the set [ , A , . . . I Z ' , ' a , . . ' z \ , 0 ' . . , 9 r ] <identifier> *<identi fier> ?<identifier> <normal variable> | <readonly variable> <variable> | <variable> <variable l i s t> ( <atom> [ <variable l i s t> ] ) <atom> | <variable> | <function> <argument> | <argument> <arg l i s t> <atom> ( <predicate name> [ <arg l i s t> ] ) <term> | <term> <term 1ist> ( GUARD <term l i s t > ) <atom> <term 1i st> ( : - <head> [ <guard> ] <body> ). | ( <head> ). := ( : - <head> ). (append n i l *12 *12). ( : - (append ( cons *h (append * t ) k t ) *12 ( cons *h * re s t ) ) *12 V e s t ) Figure 18. BNF description of Syntax Accepted by Current Interpreter Evaluation and Conclusions 53 i : i I Database of Axioms | j Merge ( *xs , n i l , *xs ). j j Merge ( n i l , *y s , *ys ) . | j Merge ( * x . * x s , *ys , * x . * z s ) <- Merge ( xs?, *ys , *zs ). j j Merge ( *xs , * y . * y s , * y . * z s ) <- Merge ( *xs , ys?, *zs ) . j j Top-Level Goal j | <- Merge ( a l . b l . c l . n i l , a 2 . b 2 . c 2 . n i l , *z ). | j Performance Measurements | j Fifteen invocations of the top-level goal required about j j 430 resolutions j j 27 seconds of real time j j under l i ght - load conditions. j | This translates roughly to 23 resolutions per second. j | A trace of the execution of the program la ter showed that over f i f t y j j percent of the CPU time was spent in message passing. | j Figure 19. Performance Measurement on a Bounded-Wait Merge j i i Evaluation and Conclusions 54 6 . 1 . 1 P o s s i b l e O p t i m i z a t i o n s Noting that over f i f t y percent of the execution time is spent in process communication,9 the following optimization is suggested: In the current system, a process that commits to a path must broadcast (v ia i t s parent process and a broadcast server) to a l l s ib l ing processes which w i l l , in turn , broadcast to a l l the i r descendants. I f we examine th i s procedure, we f ind that only the parent need be informed; the remaining processes need only be informed i f the committing process has changed a variable which w i l l influence the i r outcome. Recalling cross-layer reference loops were removed due to mutual-exclusion considerations, the optimization s impl i f ie s to the following ru le : 1. When a process commits, i t always informs i t s parent process. 2. The parent process t r i e s to unify the new variables with i t s copy of the axiom. 3. I f the uni f i ca t ion f a i l s , the committing process i s deleted as before. 4. I f the uni f i ca t ion succeeds and one or more variables of the parent process was instantiated then the parent process creates a broadcast server as before. I f , however, none of the variables changed then broadcasting i s complete. One should keep in mind that portions of th i s time are used to invoke various servers of the operating system (eg. process creation and destruction, memory a l l o c a t i o n , f i l e system services) . The current version of the Verex Operating System supports only about 30 processes. Evaluation and Conclusions 55 We can apply a s imi lar optimization to re l ieve the problem of a l imi ted number of avai lable processes. 1 0 Recall that when a process resides on the solution path, i t cannot be destroyed since i t may contain variables in i t s address space which contribute to the so lut ion. Destruction of the process w i l l result in the destruction of i t s local memory space. We are free to destroy processes which do not contribute to the so lut ion. So when a parent process successfully unif ies the axiom from a reporting c h i l d process with i t s own axiom and determines that no new information was gained, i t may release that subtree of processes to be used by some other part of the solution tree. This so lut ion , however, i s only a temporary measure since the described s i tuat ion i s not too common. What i s needed is an increase in the number of allowable processes in the operating system. 6 . 1 . 2 S u m m a r y Despite the interpreter ' s current l i m i t a t i o n s , i t has allowed us to examine the implications of the constructs of Concurrent Prolog in terms of system requirements and has demonstrated, to a certa in extent, the f e a s i b i l i t y of implementing a d i s t r ibuted interpreter for the language. From th i s work, several points came to l i g h t : • The semantics of the language can be made cleaner with a minor modification to the behaviour of the interpreter when attempting to unify an unbound read-only variable with an unbound non-read-only var iable . Evaluation and Conclusions 56 New bindings should be propagated throughout the tree as soon as they become avai lable instead of delaying them. Delayed propagation [Levy84] i s possible only i f read-only variables are treated outside of the normal scheme. Due to the above desire to instantiate read-only variables at the ea r l i e s t stage, reference loops were introduced in preference over the normal simply-linked l i s t implementation. To minimize the p o s s i b i l i t y of deadlock, a broadcast server should be created to propagate new bindings to child-processes. The use of an extra server w i l l server the dependency loop between parent and c h i l d processes. In order to avoid c h i l d processes from affecting each other, each c h i l d clause process must make a scratch-pad copy of the axiom. This procedure w i l l necessarily enta i l recursively copying the subexpressions bound to var iables . A mapping between the or ig ina l subexpressions to the scratch-pad copies w i l l aid in the copying process. To avoid deadlock and mutual exclusion problems, interprocess pointers (or tags [Lee84]) should not be used to form reference-loops. But in el iminat ing these references, one must be sure to duplicate intraprocess references. That i s , i f a c h i l d process creates a reference between two variables in i t s local copy and la ter commits, th i s reference must be duplicated in the parent's copy. The mapping from the copying mechanism w i l l be useful in determining whether the reference i s interprocess or i ntraprocess. Evaluation and Conclusions 57 Future work on th i s interpreter should include a re-implementation using separate address-spaces for each process ( i . e . d i f ferent teams) and optimizations such as a Copy-on-demand [Levy84] scheme to reduce the number of subexpressions that are duplicated. Hopefully further examination of the implementation obstacles w i l l open up the f u l l potential of the language and c l a r i f y i t s desired semantics. Evaluation and Conclusions 58 7 . 0 R E F E R E N C E S [ A h o 7 7 ] [ B o y l e 8 2 ] [ B o y e r , Moo r e 72 ] [ B r i n c h H a n s e n 7 5 ] [ C h e r i t o n 7 9 . 1 ] [ C h e r i t o n 7 9 . 2 ] [ C h e r i t o n 7 9 . 3 ] [ C h e r i t o n 8 1 ] [ D e e r i n g 8 2 ] [ D i j k s t r a 7 6 ] Aho, A . V . , and Ullman', J .D. Pr inc ip les of Compiler Design Addison-Wesley, 1977 Boyle, P.D. The Design of a Distributed Kernel for a  Multiprocessor System M.Sc. Thesis, University of B r i t i s h Columbia, Vancouver, 1982 Boyer, R.S. and Moore, J .S . The Sharing of Structure in Theorem Proving Programs, Machine Intel l igence 7 (ed. Meltzer & Michie) , Edinburgh UP. 1972. Brinch Hansen, P. The Programming Language Concurrent  Pascal IEEE Transactions on Software Engineering SE-1(2):199-207, 1975 Cheriton. D.R. Multi-process Structuring and the Thoth  Operating System Technical Report 79-5, University of B r i t i s h Columbia, Vancouver, 1979 (Reprint of the author's Ph.D. thesis from the University of Waterloo) Cheriton. D.R. Interactive Verex Technical Report 79-1, University of B r i t i s h Columbia, Vancouver, 1979 Cheriton, D.R., and Steeves, P . J . The Zed Reference  Manual Technical Report 79-2, University of B r i t i s h Columbia, Vancouver, 1979 Cheriton, D.R. Distributed I/O Using an Object-Based  Protocol Technical Report 81-1, University of B r i t i s h Columbia, Vancouver, 1981 Deering, S.E. Multi-Process Structuring of X.25 Software Technical Report 82-11, University of B r i t i s h Columbia, Vancouver, 1982 D i j k s t r a , E.W. A Disc ip l ine of Programming Prent ice-Hal l , 1976 [ G o e b e l 8 0 ] Goebel, R. PROLOG/MTS Users' Manual Technical Manual 80-25, University of B r i t i s h Columbia, Vancouver, 1980 [ K o w a l s k i 7 4 ] Kowalski, R.A. Logic For Problem Solving DCL Memo 75, Dept of A . I . , Edinburgh, 1974 [ K u s a l i k 8 4 ] Kusalik, A . J . Bounded-Wait Merge in Shapiro's Concurrent Prolog New Generation Computing, 2 (1984), Ohmsha and Springer-Verlag, 1984 [ L e e 8 4 ] Lee, R.K.S. Concurrent Prolog in a Multi-Process Environment Inst i tute for Computer Research Report 24, References 59 University of Waterloo, September 1984 (Reprint of the author's M.Sc. thesis at the University of Waterloo) [ L e v y 8 4 ] Levy, J . A Uni f icat ion Algorithm for Concurrent Prolog Proceedings of the Second International Logic Programming Conference, Uppsola, Sweden, July 1984 [ L o c k h a r t 7 9 ] Lockhart, T.W. The Design of A Ver i f i ab le Operating System Kernel Technical Report 79-15, University of B r i t i s h Columbia, Vancouver, 1979 [ N i l s s o n 8 0 ] Ni l s son, N. J . Pr inc ip les of A r t i f i c i a l Intel l igence Tioga, 1980 [ R e i t e r 7 9 ] Reiter , R., On Close World DataBases, (1979) Readings in A r t i f i c i a l Intel l igence (ed. Webb & Ni l s son) , Tioga, 1981 [ R o b i n s o n 6 5 ] Robinson, J .A . A Machine Oriented Logic Based on the Resolution Pr inc ip le JACM 12, 1965. [ S h a p i r o 8 3 ] Shapiro, E.Y. A Subset of Concurrent Prolog and Its Interpreter Technical Report TR-003, ICOT-Institute for New Generation Computer Technology, 1983. [ W a r r e n 7 7 ] Warren, D.H.D. Implementing Prolog - Compiling Predicate Logic Programs DAI Research Reports 39,40, University of Edinburgh, 1977 References 60 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0051857/manifest

Comment

Related Items