Extending Prolog to a parallel object oriented language

\label{des/ext} -- A sceptical lady patient has a rather long dream, in which certain persons tell her of my book on Wit, and praise it highly. Then something is said about a 'channel', perhaps another book in which 'channel' occurs, or something else to do with 'channel'... she doesn't know; it is quite vague -- Sigmund Freud, The Interpretation of Dreams

Introduction

We will investigate the constructs that are needed for extending Prolog to produce a language suited for parallel and distributed computation, and which fit in the framework imposed by the object oriented programming paradigm. The constructs introduced are all incorporated in the language DLP, of which an overview is given in section \ref{des/dlp}. This chapter is of an exploratory nature. We will reflect on the design considerations in chapter \ref{des/per}. In section \ref{des/ext/objects} we will introduce objects as a means for providing modularization, and for encapsulating data. The information contained in an object is accessible by methods that are defined by clauses. We will briefly discuss inheritance among objects. We will make a distinction between passive, having no activity, and active objects, having own activity. Section \ref{des/ext/channel} may be regarded as an intermezzo exploring communication between active objects via channels. In section \ref{des/ext/rendez} we treat a synchronous rendez-vous mechanism for handling method calls to active objects. A discussion of the distributed backtracking that may occur in a rendez-vous is given in section \ref{des/ext/back}. Section \ref{des/ext/accept} deals with a construct for the conditional acceptance of method calls. In section \ref{des/ext/proc} we treat an asynchronous rendez-vous mechanism which gives the programmer additional control over the parallel evaluation of goals. In section \ref{des/ext/alloc} we deal with the constructs needed for the allocation of objects and processes. In section \ref{des/dlp} we define the language DLP as the collection of constructs introduced. And, finally, in section \ref{dlp:family} we will delineate a number of subsets of DLP that will be studied from a formal semantic perspective in part II. Since the primary intention here is to give the intuition behind the mechanisms needed for parallel object oriented logic programming, and give motivations for the constructs proposed by means of examples, the description of the constructs will be informal.

Objects and processes

\label{des/ext/objects} We start by introducing the notion of objects. Throughout, a program is a Prolog-like program and a collection of object declarations. In its most simple form an object declaration looks as follows. \dlpindex{object}
  object name {
clauses
}

As we continue, we will gradually introduce features giving more functionality to an object.

Objects as modules

The first view that we will take of objects is simply to regard them as modules, containing a collection of clauses. As an example of such an object, look at the declaration for a library of list manipulation predicates.
  object lib {

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

append([],L,L).
append([H|T],L,[H|R]):- append(T,L,R).

}

Clauses can be activated by a goal of the form
• name!goal
which is a request for the evaluation of goal using the clauses defined for the object with that name. An example of the use of such a goal could be
  ?- lib!member(X,[amsterdam, paris, london]).

which, following ordinary Prolog evaluation rules, would bind the logical variable X successively to the cities mentioned in the second argument of member.

Method call

The intended semantics for an object as declared above does not deviate in any significant way from the semantics of an ordinary Prolog program. In other words, evaluating the goal lib!member(X,L) will give the same results as evaluating the goal member(X,L) when the clauses for member are directly added to the program. This holds in particular for backtracking. When a goal has multiple solutions, these solutions will be tried just as for an ordinary goal. Below we have pictured how communication with an object takes place. Assume that we have an object c. The goal c!m(t) asks the object c to evaluate m(t), where m is a predicate name and t represents the arguments of the call. We use a predicate name m since, adopting standard terminology, we will speak of the methods of an object, which in our case are ordinary clauses. While the goal m(t) is being evaluated, the caller waits for an answer. Backtracking over the results, indicated by %h_1,..., may take place as long as there are alternative solutions. Backtracking is initiated by the object that called for the method. The obvious advantage of having the clauses for a predicate assembled in a module-like object is that, when a different functionality for these predicates is required, another object can simply be asked to do the evaluation.

Use

We may extend the facilities for modular programming by allowing an object to use the clauses of another object. For example, when defining a predicate inboth(X,L1,L2), which checks whether X occurs both in list L1 and L2, it is convenient to be able to use the definition for member directly by using the clauses of lib, instead of explicitly addressing each call of member at the object lib. This is realized in the declaration for the object check.

object check {
use lib.
inboth(X,L1,L2) :- member(X,L1), member(X,L2).
}


Objects with states

\label{des/ext/obj:states} Modules of the kind treated above, however useful they may be, do not deserve to be classified as objects, since they do not contain any private data nor do they have an internal state. Below we will introduce non-logical variables, for which we allow destructive assignment. Non-logical variables are usually called instance variables in object oriented terminology. In addition, we will introduce a facility to make instances, or rather copies, of declared objects. Furthermore, we will briefly discuss how objects may inherit non-logical variables and clauses from other objects.

Non-logical variables

Objects may contain private data. We introduce non-logical variables for storing such data. As an example consider the declaration for the object travel.

object travel {
use lib.
var city = [amsterdam, paris, london].

reachable(X) :- member(X, city).

}

We may ask such an object to evaluate the goal reachable(tokyo) as in
  ?- travel!reachable(tokyo).

for which the answer is, perhaps unfortunately, no. When the goal reachable(tokyo) is evaluated we assume that the non-logical variable city is replaced by its value, the list of cities to which it is initialized. Moreover, because of the backtracking provided by Prolog, we could ask the object travel to list all reachable cities. The advantage of overloading predicate names becomes apparent when we imagine the situation in which we have a number of travel agencies, implemented by the objects travel _1,...,travel_n, similar to the object travel but with (possibly) different values for the non-logical variable city, which allows us to ask
  ?- lib!member(O,[travel_1,...,travel_n]), O!reachable(tokyo).

that may after all get us where we want to be. Non-logical variables, that allow to store persistent data and that enable search over these data by backtracking, are of relevance for the implementation of knowledge based systems. For a small example it may not seem worthwhile to introduce non-logical variables, but in a real life situation the data may be stored in a large database. Only the clauses declared for an object have access to the non-logical variables. This justifies our speaking of clauses as methods, since the clauses provide an interface to the object encapsulating these data.

Assignment

Having non-logical variables, the question immediately arises as to whether we may change the value of such a variable or not. It seems unnatural to have to answer no, since, for example, a travel agency may decide to change the service it offers now and again. We introduce a goal of the form
• variable := term
for assigning values to non-logical variables. The use of such a goal is illustrated in the following version of travel.

object travel {
use lib.
var city = [amsterdam, paris, london].

reachable(X):- member(X,city).

}

So, as an example, when we have as a goal
  ?- travel!add(berlin).

each successive request to travel includes berlin as a reachable city. For convenience we have assumed that the list of destinations always grows longer. In general, assignment to a non-logical variable is destructive, in that the previous value is lost. We will discuss the protection needed in the presence of concurrency in section \ref{des/ext/rendez}, where we treat the rendez-vous mechanism.

Instances of objects

Objects with mutable states require to have the possibility to create instances of objects of a particular kind. For example, we might wish to have a number of instances of the object travel, which differ in the destinations they offer. Each instance of an object contains both a copy of the non-logical variables of the object and a copy of its clauses. The non-logical variables of an instance are initialized to the current value of the non-logical variables of the object. Apart from the clauses declared for the object, a copy is also made of the clauses contained in the objects occurring in the use list. To create an instance of an object we introduce a goal
•  O = new(name)
that results in binding the newly created instance of the object to the logical variable O. Its use is illustrated by a goal like
?-
O1 = new(travel), O2 = new(travel),

in which two instances of the object travel are created, which differ in that they respectively include berlin and antwerpen in their offer of reachable destinations. Notice that instances of objects are also objects.\ftn{ We have deviated from standard terminology, in not speaking of objects as instances of classes, since both the named object declared in the program and its instances (that is copies) may be used as objects. }

Inheritance

As we have seen, an object may use the clauses of the objects contained in its use list. We propose another feature to enable an object to inherit the non-logical variables of other objects. This type of inheritance is exemplified in the declaration
  object travel {
var city = [amsterdam, paris, london].
}

object agency {
isa travel.
...
}

This declaration ensures that the object agency, and all its instances, will have a non-logical variable city, initialized to the list above. In most cases the inheritance relation is such that the inheriting object contains both the non-logical variables and the clauses of the objects it inherits. We have introduced the notation
  object a:b { ... }

as a shorthand for
  object a {
isa b.
use b.
...
}

As an example, consider the declaration below.
  object travel {
use lib.
var city = [amsterdam, paris, london].

reachable(X):- member(X,city).
}

object agency : travel {

book(X) :- reachable(X), price(X,Y), write( pay(Y) ).
price(amsterdam,5).
...
}

} The object agency may use all the clauses of travel, and in addition has access to the non-logical variable city. Inheritance is effected by code-sharing, in a static way. Conceptually, the inheriting object contains a copy of the objects it inherits. We will discuss how we deal with clashes that may arise in multiple inheritance in chapter \ref{des/know}, where we will also provide some examples of how inheritance may be used for knowledge representation.

Active objects

So far, we have not given any clue as to how we will deal with concurrent programming in our (yet to be proposed) language. The first idea that comes to mind is to make passive (instances of) objects active, by letting them have activity of their own. Having a number of objects concurrently executing some activity of their own is, however, not of much help when there is no means to communicate with these objects. Thus, in addition to providing the means to create active instances of objects, it is also necessary to provide a way by which their activity can be interrupted in order to evaluate some goal. An active object is created by a goal of the form
• O = new(name(t1,...,t_n))
where name is the name of the declared object, and t1,...,t_n are arbitrary terms. The term name(t1,...,t_n) is called the constructor, since, when creating a new object, a process is started to evaluate the goal name(t1,...,t_n). In order to avoid failure, clauses must be defined by which the constructor can be evaluated. The predicate name of the head of these clauses which, for obvious reasons we call constructor clauses, is identical to the name of the declared object.

Processes

Multiple processes may refer to a single object. Apart from the constructor process, a process is created for each method call in order to keep track of the backtracking over the results of that call. We have pictured an object and some processes referring to it below. The call O = new(c(t)) results in a new instance of the object c together with a constructor process evaluating c(t). Both the calls O!m1(t1) and O!m2(t2), which may come from different processes, result in a separate process for evaluating these calls.

Acceptance

The constructor clauses specify what may be called the body of an object, which determines its own activity. To interrupt this own activity we provide the goal
• accept(any)
that forces the object to wait until it is requested to evaluate a goal. Later on we will encounter accept goals of a more complex nature. When this has happened --that is when the goal is evaluated and an answer has been sent back-- the accept goal succeeds and the object may continue with its own activity. As an example, consider the object declaration for an agency that, in a naive way, implements the amalgamation of a number of travel agencies of the old kind.

object agency {
use lib.
var city = [].

agency(L):-
member(O,L),
O!reachable(X),
fail.

agency(_):- run().

run():- accept(any), run().

reachable(X) :- member(X,city).

}

The declaration for agency differs from the declaration for the object travel only in having constructor clauses and an auxiliary clause for run(), that define the own activity of each instance of an agency. Suppose now that we wish to combine four travel agencies, travel1,...,travel4 of the old kind into two new agencies, then we may state as a goal
?-
O1 = new(agency([travel1,travel2])),
O2 = new(agency([travel3,travel4])),...

the result of which is that both agencies start with initializing their list of cities concurrently. The body of an agency consists, after initialization, of a tail-recursive loop stating the willingness to accept any goal. Each time the accept goal is reached, the object waits until it is requested to evaluate a goal. A request to evaluate a goal, in its turn, must wait until the object is willing to accept such a request.

Concurrency and synchronization

We have sketched here the simplest form of the evaluation of a goal by an object. We call this remote goal evaluation since we have not yet provided the means to be selective about what is acceptable as a request. Clearly, apart from the initialization and the fact that the own activity of an object must explicitly be interrupted, the semantics of an active object must be similar to that of a passive object. Conceptually, we may regard a passive object obj to be executing its constructor obj(), defined by
  obj() :- accept(any), obj().

In contrast with active objects, however, passive objects have unlimited internal concurrency as explained below.

Backtracking

A question we have not addressed when treating the remote evaluation of a goal by an active object is how to deal with the possible occurrence of backtracking over the resulting answers. Our approach is colored by our intention to have a semantics which coincides with that for ordinary Prolog, as far as backtracking is concerned. In our proposal we deal with the backtracking that may occur in a method call by creating a new process for each request to evaluate a goal. The backtracking information needed for finding all solutions for the goal is maintained by that process.

Internal concurrency

When multiple processes referring to a single object are active concurrently we speak of internal concurrency. For active objects we provide mutual exclusion between method calls in order to protect the access of non-logical variables. Mutual exclusion, however, restricts the degree of internal concurrency of an object. We do not wish to impose any restrictions on the internal concurrency displayed by passive objects. The programmer must take care to provide the protection necessary for safely accessing non-logical variables. Active objects allow only a limited form of internal concurrency, namely for backtracking over multiple answers to a method call.

Synchronization

We consider remote goal evaluation as an important means for objects to communicate with each other. Moreover, by requiring it to be stated explicitly whether an object is willing to accept a request, we have provided a means for synchronizing the behavior of objects. However, we may wish to be more selective in what to accept as a request. For instance, what is acceptable may depend on the state of the object, or even on conditions imposed on the arguments of the call. When the object is selective in this sense, it seems more apt to speak of a rendez-vous, since both the object and the process that requests the evaluation of a goal participate in establishing the communication.

Summarizing, what we have described to this point is more or less a fully-fledged object oriented language. We may regard the clauses defined for an object as methods, having access to private data stored in the non-logical variables. Calling a method is to engage in a rendez-vous, when the object is willing to accept the call. Before continuing our description of this approach, however, we wish to reflect on the possibility of realizing objects with states that communicate by means of message passing. Do we need non-logical variables to implement states? And, do we need a synchronous rendez-vous to communicate with objects? We will deal with these questions in the next section, where we explore the possibility of using channels as the medium of communication between active objects.

Communication over channels

\label{des/ext/channel} We may implement objects as continuously running processes communicating with each other over channels. C.f.  [ST83],  [PN84]. Before going into details we will present the language constructs involved. First of all we need a facility to create processes. We will use a goal of the form
• new(c(t1,...,t_n))
to create an active instance of the object c. To create new channels we use a goal of the form
• C = new(channel)M
which results in binding the newly created channel to the logical variable C. Further we need, what we call an output statement of the form
• C!t
where C refers to a channel and t is an arbitrary term. Also, we need an input statement of the form
• C?t
where C is assumed to refer to a channel and t is an arbitrary term.

Counter

We will characterize the semantics of communication over channels by giving a simple example, adapted from  [PN84], but originally given in  [ST83]. Assume that we wish to implement a counter that allows us to ask for its value and to increment its value. Clearly, we must have some means to store the state of the object, and also some means to send it the corresponding messages. With the constructs introduced, our implementation looks as follows.

object ctr {

ctr(C):- run(C,0).

run(C,N):-
C?inc(),
N1 = N + 1,
run(C,N1).

run(C,N):-
C?value(N),
run(C,N).
}

The first clause encountered is the constructor for an instance of ctr. The argument C is assumed to refer to a channel. Evaluating the constructor results in calling run(C,0), initializing the (logical) state variable holding the value of the counter to zero. The remaining two clauses define the body of the object. The first clause contains the input statement C?inc() that is used to increment the value of the counter. The second clause contains the input statement C?value(N) that is used to answer requests for the value of the counter. The value of the counter is maintained appropriately by passing it as an argument to the tail-recursive call to run. A typical example of the use of such a counter is the goal

?-
C = new(channel),
new(ctr(C)),
C!inc(),
C!value(X).

that modifies the binding of X to one. The example given illustrates the use of such objects to implement server processes. Let us now give a more detailed description of the semantics of communication over channels.

Bi-directional unification

Communication over channels is synchronous, in that both sides wait until there are complementary communication requests for that channel. For the example above this means that the body of the counter will remain at the goal C?inc() until the user process reaches an output statement. We call a communication successful if the term on the input side, or more briefly the input term, is unifiable with the output term, the term on the output side. When these terms do not unify, as in the case for inc() and value(X), the input side is allowed to backtrack until it finds another input statement for that channel and the procedure is repeated. As long as the input side is backtracking the output side waits with its request to communicate. The asymmetry with respect to backtracking is exemplified above. We must remark, however, that Delta Prolog adopts a communication mechanism that is symmetric in its backtracking behavior but is rather complex. We stress that both in Delta Prolog and in our proposal communication over channels is bi-directional, in the sense that variables in both the input term and the output term may receive a value through unification. As an example consider the following object declaration

object a {
a(C):- run(C,0).
run(C,N):- C?f(N,Y), run(C,Y).
}

The body of the object a, which is defined by the clauses constructor a(C), consist of executing run. An active object outputs a term f(N,Y) over over channel C. Initially, N is zero. When evaluating the goal

?- C = new(channel), new(a(C)), C!f(X,1).

an object a(C), that is initialized with channel C. The newly created object runs indepently of the process evaluating the original goal. Since both C!f(N,Y) and C?(X,1) share the same channel, an attempt at communication takes place, which results in binding X to zero and Y in the body of a to one.

Sieve

We conclude this intermezzo with an example in which the number of processes can grow indefinitely large. Below we present our implementation of the solution to the problem of generating primes given in  [Ho78]. The solution consists of a chain of processes, the first of which -- called the driver -- produces natural numbers and the others -- representing the primes -- check for divisibility by a prime. The definition of the driver process is as follows.

object driver {

driver(I):-
C = new(channel),
new(sieve(C)),
drive(C,I).

drive(C,I):-
C!I, J = I+2, drive(C,J).

}

The body of the driver produces an infinite sequence of (odd) natural numbers which are sent to the first sieve process.

object sieve {

sieve(C):-
C?P,
collect(P),
Cout = new(channel),
new(sieve(Cout)),
run(P,C,Cout).

run(P,C,Cout):-
C?I,
( I//P != 0 -> Cout!I ; true ),
run(P,C,Cout).

collect(I):- write(I).

}

A sieve contains a prime and checks all incoming numbers for divisibility by that prime. The first number received by a sieve process is known to be a prime. The process then creates a new sieve and checks all incoming naturals for divisibility by the prime it has stored. If the incoming natural is not divisible by the prime stored by the sieve it is sent to the successor process of that sieve. The output is collected by sending each prime with which a new sieve is initialized to a special process. The goal  I // P != 0 is evaluated by simplifying  I // P to I modulo P followed by a test as to whether the result is unequal to zero. The program is started by the goal

?- new(driver(3)).

The structure of the collection of processes may be pictured as where each arrow represents a channel. As sketched here, communication over channels offers a rather limited functionality. In particular, since we have not included guarded commands or annotated variables, synchronization must rely purely on the synchronous nature of communication. Another important limitation is that no backtracking over the results of a communication is allowed, once a successful communication is achieved.

Communication by rendez-vous

\label{des/ext/rendez} In the previous section we have seen how we may implement objects with states without the use of non-logical variables to store the state of such objects. The approach sketched there has a number of limitations. Instead of augmenting the proposal of the previous section, we will take up the main thread of this chapter and will investigate how we may achieve object oriented behavior by regarding clauses as methods. Below we summarize the language features that we treat in this section.
•  x := t --- to assign the value of a term to the non-logical variable x
• O = new(c(t1,...,t_n)) --- to create an active instance of c, to which O will refer
• O!m(t1,...,t_n) --- to call the method m of the object to which O refers
• accept(m1,...,m_n) --- to state the willingness to accept calls for m1,...,m_n

States

As we have indicated in the section introducing objects we may use non-logical variables to store persistent data. We rephrase the declaration of the counter presented in the previous section to recall its use.

object ctr {
var n=0.

ctr():- accept(any), ctr().

inc():- n := n + 1.
value(N):- N = n.
}

This solution differs from the previous one in that the state of the object is not maintained by keeping the value of the counter as an argument in a tail-recursive loop, but as an explicit non-logical variable that can be updated by assignment. We allow for arithmetic simplifications both in the right-hand side of assignments to non-logical variables and in the left- and right-hand sides of an equality. A typical use of such a counter is exemplified by the goal

?-
C = new(ctr()),
C!inc(),
C!value(X).


In this a counter is created, which subsequently receives the method calls inc() and value(X). Despite the notational similarity with communication over channels, the calls C!inc() and C!value(X) are now method calls, that is goals that are evaluated by the object. The evaluation of these goals is taken care of by the clauses defined for inc and value.

Mutual exclusion

Method calls for an active object must be explicitly accepted by an accept statement. To answer a method call an active object must interrupt its own activity. To protect the access to non-logical variables, mutual exclusion between method calls is provided by not allowing any method call to be accepted as long as the evaluation of a method call has not led to an answer being returned. An important question to answer is: when do we allow an object to continue with its own activity? In the absence of backtracking the natural choice is: immediately after the answer has been delivered. In the presence of backtracking we might wish to deliver all answers before allowing an object to continue its own activity. However this is overly restrictive since protection of non-logical variables is not really needed when backtracking over alternative solutions as shown in section \ref{des/ext/back}. Another thorny issue, which arises in the presence of backtracking, is what to do with non-logical variables that may be assigned values in an imperative way. Must these assignments be undone on backtracking or not? As the example of a counter shows, assignment to non-logical variables is of an imperative nature. Consequently, such assignments are not undone on backtracking!

Suspension

The mutual exclusion provided by the counter is meant only to protect the access to non-logical variables. At any time, any method call is acceptable. It is conceivable, however, that whether or not a method call is acceptable depends on the state of the object, as expressed in its non-logical variables. A typical example of such an object is the semaphore, given below.

object sema {
var n = 0.

sema(N):- n := N, run.

p():- n := n - 1.
v():- n := n + 1.

run:-
( n == 0 -> accept(v) ; accept(p,v) ),
run.
}

The constructor for sema causes the semaphore to loop over a conditional that tests the value of the non-logical variable n. When the value of n is zero, calls to p() will be suspended, because of the statement accept(v); otherwise both p() and v() may occur, since when n is not zero the statement accept(p,v) is evaluated. A semaphore of the kind above may be used to regulate the concurrent evaluation of goals by passive objects. To illustrate this we present a modified version of the travel agency described in section 1.2.

object travel {
use lib.
var s = new(sema(1)).
var city = [amsterdam, paris, london].

reachable(X):- member(X,city).

add(X):- s!p(), append([X],city,R), city := R, s!v().
}

The object travel implements a multiple readers/single writers protocol, since adding an item to the city list is embedded in the semaphore calls p() and v(). The initialization of the non-logical variable s to an active instance of sema occurs exactly once for each instance of travel.

Semantics

Let us now take a closer look at the semantics of the accept statement. We only allow accept statements to occur in active objects since we wish method calls for passive objects to be evaluated concurrently. In addition, for active objects we do allow accept statements to occur (possibly nested) in processes for evaluating method calls. In our semantic description, however, we impose the requirement that accept statements may occur only in the constructor process of an object. Calling a method of an active object results in a rendez-vous, when that object is willing to accept the call. The interaction between the processes involved is pictured below. Suppose that we have a process %a that calls O!m(t), with O bound to the object of which %b evaluates the constructor. When %b reaches an accept statement the activity of %b is interrupted, and a new process %b' is started to evaluate m(t) which refers to the same object as %b. Process %b resumes the evaluation of the constructor as soon as the first answer, say %h_1, is produced. Thereafter %b' continues to produce alternative solutions, as may be requested by %a. Operationally, when an accept statement is reached, the evaluation of the current goal is suspended until a method allowed by the arguments of the accept statement is called for. We call the argument of the accept statement the accept list, and by convention take any to stand for all methods of the object. When a method not occurring in the accept list is called for, the call is suspended and the object waits until another call satisfying the accept list occurs. The suspended call will result in a process evaluating the method call whenever the accept list is changed in such a way that the call is allowed. To handle suspended calls the object maintains a so-called accept queue. All suspended calls join in the accept queue, in the order in which they arrive. When the accept list is changed, the object first searches the queue and takes the first call satisfying the new accept list. If no such call is present the object waits for other incoming calls. This procedure guarantees fairness in handling method calls since because of the FIFO behavior of the accept queue, no allowed call will be suspended forever. C.f.  [Am89b].

Dining philosophers

Our pi\ece de r\'esistance is an implementation of a solution for the problem of the Dining Philosophers. Cf.  [Dij71],  [Ho78]. Five philosophers must spent their time thinking and eating. When a philosopher wants to eat he must get hold of two forks. Since only five forks are available, each philosopher must await his turn. To avoid the situation where each philosopher sits waiting with one fork, only four philosophers at a time are allowed in the dining room. Since a philosopher needs to know no more than his name, the dining room and his proper forks he may, after creation, proceed to enter the cycle of thinking, entering the dining room, picking up his forks, eating and leaving the dining room to start thinking again.

object philosopher {
var name.

philosopher(Name,Room,Lf,Rf) :-
name := Name,
proceed(Room,Lf,Rf).

think :-  write(thinking(name)).
eat:-  write(eating(name)).

proceed(Room,Lf,Rf):-
think,
Room!enter(),
Lf!pickup(), Rf!pickup(),
eat,
Lf!putdown(), Rf!putdown(),
Room!exit(),
proceed(Room,Lf,Rf).
}

A philosopher is admitted to the dining room when less than four guests are present, otherwise he must wait for one of his colleagues to leave.

object room {
var occupancy=0.

room():-
(
occupancy == 0 -> accept(enter) ;
occupancy == 4 -> accept(exit) ;
accept(enter, exit)
),
room().

enter():- occupancy := occupancy + 1.
exit():- occupancy := occupancy - 1.

}

Forks can only be picked up and then put down.

object fork {

pickup().
putdown().

fork() :-
accept( pickup ),
accept( putdown ),
fork().

}

The ceremony is started by assigning the philosophers their proper forks and showing them the dining room. We omit the details of their initiation. The example demonstrates the synchronization enforced by accept statements. Such behavior could not be effected by using synchronous communication over channels. In fact, the synchronisation and suspension capability of the rendez-vous mechanism makes communication over channels superfluous. However, communication involving accept statements and non-logical variables is semantically considerably more complex, and seems to preclude a declarative semantics. Apart from this, communication over channels is more efficient.

Distributed backtracking

\label{des/ext/back} Distributed backtracking is an important issue for systems that wish to support don't know non-determinism, in contrast to don't care nondeterminism where, once a choice is made, all alternatives are thrown away. The examples presented previously were deterministic in the sense that only one solution needed to be produced. The object presented in the following example, however, may produce an infinite number of solutions.

object nat {

number(0).
number(s(X)) :- number(X).

}

Its use is illustrated by

?- nat!number(X), write(X), fail.

which will print all natural numbers, eventually. Backtracking is done lazily, in that on backtracking the object evaluating number will start to produce the next solution. Note that the goal
  :- nat!number(X), X = s(s(0)).

differs from the goal
  :- nat!number(s(s(0))).

in that the latter only communicates success, whereas the former has to communicate three bindings for X.

Backtracking in the presence of non-logical variables

In the presence of non-logical variables mutual exclusion is needed for reasons of protection. Mutual exclusion takes effect for active objects only. This protection, however, lasts until the first answer is requested and received. This procedure is motivated by the assumption that any important change of the state of the object can be achieved during the period that the first solution is produced. Backtracking over the second and remaining solutions can be done while other processes are active. We will show how the state of an object can be fixed by binding it to a non-logical variable. Consider another variant of our, by now familiar, travel agency.

object travel {
use lib.
var city = [amsterdam, paris, london].

travel():- accept(any), travel().

reachable(X):- L = city, member(X,L).

}

In the clause for reachable we have made explicit the binding of the second argument of member to the value of the city list. Since an instance of travel is now an active object the mutual exclusion mechanism prevents the city list from being changed while the first answer for reachable is being produced. After that, member may backtrack, but with the value of the city list bound to L, as it was at the time of the call. Now suppose that we declare travel in the following, somewhat contrived, manner.

object travel {
use lib.
var city = [amsterdam, paris, london].

travel():- accept(any), travel().

reachable(X):- length(city,N), get(N,X).

get(N,X):- element(N,city,X).
get(N,X):- N > 1, N1 = N - 1, get(N1,X).

length([],0).
length([H|T],N):- length(T,N1), N = N1 + 1.

element(1,[X|_],X).
element(N,[_|T],X):-
N > 1,
N1 = N - 1,
element(N1,T,X).
}

The reader may check that in this case the city list may be updated, by adding elements to the front, while the process evaluating reachable is backtracking over the possible solutions. In general such interference is not desirable but, as has been shown, this can easily be avoided by binding the state of an object to a logical variable.

Deterministic objects

In many cases we do not need the full power of backtracking over the results in a rendez-vous. For instance, asking the value of a counter results in precisely one answer. Such deterministic behavior is obvious when the call contains no unbound logical variables, since the answer will then be either failure or success. To cope with the cases in which this cannot so easily be decided we have provided a way of declaring an object to be deterministic. Our counter is clearly a deterministic object.

deterministic object ctr {
var n=0.

ctr():- accept(any), ctr().

inc():- n := n + 1.
value(N):- N = n.

}

The prefix deterministic enforces that only one solution will be returned for each method call.

Conditional acceptance

\label{des/ext/accept} The accept statement that we have considered allows only the names of methods for which a call is acceptable. We will now introduce a much more powerful mechanism that allows, among other things, the imposition of arbitrary conditions on the arguments of the call. The format of the conditional accept statement is
• accept(...,m(t1,...,t_n):guard -> goal,...)
The conditional accept statement is similar to the accept statement treated previously except that, instead of a method name m, expressions of the form [] m(t1,...,t_n):guard -> goal and simplifications thereof, as listed below, may occur as arguments.

Semantics

When an accept statement is encountered, for instance when evaluating the constructor of an object, the accept expressions occurring in the statement are stored in the so-called accept list of the object. The accept list is consulted for each request to evaluate a method call. For simple accept statements the accept list consists of method names. Whether a method call is acceptable then only depends on the method name being a member of the accept list. Checking whether a method call satisfies the acceptance condition imposed by an accept expression of the form m(t1,...,t_n):guard -> goal requires more effort. When a method is called, say by m(t1',...,t_n'), then it is first tried whether the call can be unified with the expression m(t1,...,t_n). If the unification is successful then, in addition, the guard will be evaluated, instantiated by the bindings that result from the unification of the call with the method template m(t1,...,t_n). If the evaluation of the guard succeeds also, the call will be answered by evaluating goal, instantiated by the bindings resulting from unifying the call with the template and the evaluation of the guard. It is easy to see that the conditional accept statement subsumes the original accept statement since the statement accept(m) has meaning identical to
  accept(m(t1,...,t_n): true -> m(t1,...,t_n))

Both the guard and the goal of an accept expression may contain variables occurring in the method template m(t1,...,t_n). The bindings computed to answer the caller are determined by the evaluation of the goal and, in addition, by both the unification with the template and the evaluation of the guard. Below we indicate what happens when an accept expression of a simpler form is encountered.

Accept expressions

The arguments of the accept statement are called accept expressions. Accept expressions may take one of the following forms.
• m --- accepts all calls for method m
• m(t1,...,t_n) --- accepts all calls that unify with m(t1,...,t_n)
• m:guard --- accepts all calls for m if the guard holds
• m(t1,...,t_n):guard --- accepts all calls that unify with m(t1,...,t_n) for which the guard holds
• m:guard -> goal --- executes goal for all calls to m if the guard holds
• m(t1,...,t_n):guard -> goal
that executes goal for all calls unifying with m(t1,...,t_n) for which the guard holds. To illustrate the power of the generalized accept statement we re-express some of the examples presented earlier.

Examples

We will first give an alternative declaration for the object sema.

object sema {
var n = 0.

sema(N):- n := N, run.

p():- n := n - 1.
v():- n := n + 1.

run:- N=n, accept(v:N >= 0, p:N>0), run.
}

The behavior of an instance of sema is identical to the behavior of the object sema as defined before. The present declaration differs from the previous one in that the Prolog conditional goal
  n == 0 -> answer(v) ; answer(p,v)

is replaced by the conditional accept statement
  accept(v:N >= 0, p:N>0)

with N bound to n, in which the guards contain the conditions under which the method calls may be accepted.

States

Perhaps somewhat surprisingly, we no longer need to use non-logical variables to maintain the state of an (active) object. We will illustrate this by (re) declaring our familiar counter.

object ctr {
ctr() :- run(0).

run(N):- accept(
inc():true -> N1 = N + 1,
value(N):true -> N1 = N
),run(N1).

}

The state is passed as an argument in a tail-recursive call to run, which implements the body of the object. In a similar way we can implement a semaphore, as shown below.

object sema {

sema(N):- accept(
v:N>=0 -> N1 = N + 1,
p:N>0 -> N1 = N - 1
), sema(N1).
}

which is a rather elegant way of coding a semaphore. Notice that we do not have to specify clauses for the methods but may specify the functionality of a method in the goal part of an accept expression. Non-logical variables are no longer necessary to represent the state of an object because of the enlarged functionality of the accept statement. However, logical state variables, maintained as an argument in a tail-recursive loop, may not be inherited whereas non-logical state variables may be inherited among objects, thus allowing a rather concise description of the functionality of a collection of objects. Another reason not to abandon non-logical variables has to do with efficiency. Passing a complex state as an argument after each method call is clearly less efficient.

Backtracking

The generalized accept statement preserves backtracking over the possible answers delivered in a rendez-vous, as illustrated by our rephrasing of the declaration of a travel agency.

object travel {
use lib.

travel():- run([amsterdam,paris,london]).

run(L):- accept(
reachable(X): L1 = L -> member(X,L),
), run(L1).
}

As before we may generate all reachable cities by stating the goal
  ?- travel!reachable(X).

Since the goal in a conditional accept expression may fail, care must be taken to update the state variable in a proper way, as illustrated in the example above where the parameter for the tail-recursive call to run (L1) is bound to the original list L.

An asynchronous rendez-vous mechanism

\label{des/ext/proc} The rendez-vous presented consists of two parts, the creation of a process to evaluate a method call and the request for an answer. For creation of the evaluating process, one may use the special statement
• Q = O!m(t)
to request the object to which O refers to create a process to evaluate the goal m(t). The variable Q thereafter refers to that process. For the request of the result we introduce
• Q?
that asks the process, referred to by Q, for an (other) answer.

Informal semantics

Using somewhat contradictory terminology, a call of the form Q = O!m(t) may be regarded as an asynchronous method call, since receiving the (possibly multiple) answers requires an explicit request of the form Q?. The variable Q is bound to a pointer to the process evaluating m(t). The method call m(t) must explicitly be accepted by an accept goal of the object to which O refers. We call the goal Q? a resumption request, since it delivers a resumption containing the answer substitutions that result from the call. Evaluating the resumption enables the possible variable bindings of these answers to take effect in the current context. The decomposition of a method call in the request of evaluation and the request of a result allows the programmer to achieve extra parallelism, since the newly created process runs independently of the invoking process, which does not have to wait for an answer. Such overlapping of processes is expressed by a goal of the form
  Q = O!m(t), G, Q?

Between the creation of the process evaluating the goal m(t) and stating the resumption request to collect the answers to m(t), the invoking process can perform any action whatsoever. Below we have depicted the steps that are taken in evaluating a goal such as the one above. When the call Q=O!G is accepted, a process for evaluating G is created. The caller may proceed with the evaluation of A, whereafter it must wait for an answer for G. The resumption goal Q? succeeds when the answer is received. The asynchronous rendez-vous preserves completeness in coupling the solutions produced by evaluating m(t) with the bindings resulting from the evaluation of G. When backtracking occurs each alternative binding resulting from the evaluation of G must be coupled with all possible solutions of m(t). However, if m(t) has infinitely many solutions, G will never be tried for producing alternative bindings.

And-parallelism

The decomposition of the rendez-vous allows to define and-parallelism in a rather straightforward way, as
  A\&B :- Q = self ! B, A, Q?.

where self refers to the object evaluating the goal  A \& B . Such goals may however occur only in passive objects, since only passive objects allow internal concurrency. An advantage of this approach is that the programmer may restrict the cases where parallel evaluation occurs by imposing extra conditions (cf.  [DG84]) as in
  A&B :- ground(B),!, Q = self ! B, A, Q?.
A&B :- A, B.

where splitting of a new process is allowed only when B is ground. Note that the cut in the first clause is used to avoid unwanted backtracking over the second solution of {\small A\&B}.

Example

A typical example of the use of this kind of parallelism is the following, familiar, quicksort program.

qsort([],[]).
qsort([X|T],S):-
split(X,T,L1,L2),
( qsort(L1,S1) & qsort(L2,S2) ),
append(S1,[X|S2],S).

split(X,[],[],[]).
split(X,[Y|T],[Y|L1],L2):-
X > Y,!,
split(X,T,L1,L2).
split(X,[Y|T],L1,[Y|L2]):-
split(X,T,L1,L2).

Each non-empty list is divided into two sublists, one with values less than the values in the other. These are then sorted in parallel and the sorted sublists are concatenated.

Allocation of objects and processes

\label{des/ext/alloc} In the examples given, no attention has been paid to the issue of allocating (instances of) objects and the actual distribution of computation over the available resources. When a new instance of an object is created, it can be allocated to a particular processor node by a statement of the form
• O = new(obj@N)
where N is a so-called node expression denoting a particular processor node and obj is either the name of an object or a constructor, that is an object name with arguments. In addition it is possible to split off a process to evaluate a goal on a particular node by the statement G@N where G is a goal and N is a node number. The meaning of a goal G@N is given by the clause
  G@N :- O = new(self@N), Q = O!G, Q?.

Such a goal may be used only for passive objects.

refer to a processor of the parallel machine on which the system runs. The parallel machine for which our system is intended is assumed to have a limited number of processor nodes that are connected with each other by a communication network. The programmer can refer to each of n processors by its number, $0,...,n-1. To permit a more refined strategy of allocating processes and resources, node expressions may be used, from which a processor number can be calculated. Apart from viewing the network as a linear sequence of processors, the programmer may regard the configuration as an (imaginary) tree, or as a grid of processors. Tree organization A node expression of the form \dlpindex{\attreeexpr}  I0:I1:...:I_n  denotes, with the branching degree (by default) fixed to two, the processor associated with the node in the tree reached by following the path I1,...,I_n from I0. The association of processor numbers with nodes of the tree is done by counting the nodes of tree breadth first. For example the expression$0:1:2:1, giving the path \$1,2,1 from 0, gives the processor number 9. As an example of how such node expressions can be used to distribute the computation load over the available processors, consider the following variant of the quicksort program presented earlier.

qsort(L,R):-  qsort(0,L,R).

qsort(N,[],[]).
qsort(N,[X|T],S):-
split(X,T,L1,L2),
( sort(N:1,L1,S1)@N:1 & sort(N:2,L2,S2)@N:2 ),
append(S1,[X|S2],S).

When splitting off two processes for sorting the sublists, the processes are allocated on the successor nodes of the current node, as long as sufficient processors are available. More refined strategies may be encoded by including tests on the length of the lists.

Matrix organization

The processor topology may also be viewed as a matrix with certain dimensions (say a square array of dimension 4 for 16 processors). The programmer can index this matrix by expressions of the form
  N1 #  N2

which allows the distribution of the load over the available processors by moving, for instance, north from
N1 # N2 to N1 # N2 + 1, over the matrix. Abbreviations such as north, west and so on are provided to facilitate these kinds of turtle movements over the matrix of processors. Cf.  [Sh84].

The language DLP

\label{des/dlp} The constructs that we have explored in previous sections are part of the language DLP, a language for distributed logic programming, that has been the result of the research reported in this book. In this section we provide an overview of the language DLP. In the next section we will isolate the subsets of DLP chosen for studying the semantics of the language.

Declarations

\label{des/dlp:decl} A DLP program consists of a number of object declarations. The clauses occurring in the object declarations may contain special statements for updating non-logical (instance) variables, for creating objects and for communicating with other objects. An object declaration is of the form
  object name {
use objects.
var variables.

clauses
}

Among the clauses may be constructor clauses, that enable to create active instances of an object. The clauses of an object act as methods, in that they have exclusive access to the non-logical variables of an object. Clauses are ordinary Prolog clauses, except for the possible occurrence of special forms by which DLP extends Prolog.

Inheritance

of the non-logical variables of objects is achieved by including the declaration
  isa objects

in the object declaration. The declared object then contains a copy of all the non-logical variables of the objects mentioned in the isa list. Clauses are inherited from objects by including the declaration
  use objects

The declared object then adds the clauses of the objects mentioned in the use list to its own clauses. A declaration of the form
  object a:b { ... }

  object a {
isa b.
use b.
...
}

Inheritance is static. It is effected before an object starts to evaluate a goal. In other words, there is no interaction between objects, except on the occasion of an explicit communication. See chapter \ref{des/know} for a more precise characterization of inheritance, and the resolution of possible name conflicts.

Statements

\label{des/dlp:stat} The core of DLP consists of the special forms
• v:=t --- to assign (the value of) the term t to the non-logical variable v
• O=new(c(t)) --- to create an active instance of the object c
• O!m(t) --- to call the method m(t) for the object O
• accept(m1,...,m_n) --- to state the willingness to accept methods m1,...,m_n
These are the extensions that play a prominent role in part sem, treating the semantics of DLP. Moreover, the constructs listed above are sufficient to solve most of the knowledge representation problems presented in chapter \ref{des/know}.

Channels

In addition, however, we have special forms that allow to communicate over channels.
• C = new(channel) --- to create a new channel
• C!t --- to put output term t on channel C
• C?t --- to put t as an input term on channel C

Conditional acceptance

Apart from the regular accept statement we have introduced a generalized accept statement, that may contain conditional accept expressions of the form
• method:guard -> goal
that result in the goal being evaluated, if the method template matches the call and moreover the guard holds. (C.f. section \ref{des/ext/accept})

Process creation and resumptions

For those wishing to squeeze out the last drop of parallelism we have included the primitives
• Q = O!G --- to create a process to evaluate G
• Q? --- to ask for the results of process Q
These are the primitives that have been used to implement the synchronous rendez-vous as
  O!G :- Q = O!G, Q?.
`

Allocation

Lastly, since effective parallelism requires some strategy of allocating resources we have provided node-expressions that can be used to allocate an object or a process, evaluating a goal. The special forms
• O = new(obj@N)
• G@N
where obj is either an object name or a constructor, respectively allocate an object or a goal at the processor node denoted by N.

Remarks

Since we have striven for full compatibility with Prolog, we have retained the backtracking behavior to the extent possible. We support both local backtracking, that occurs within the confines of a process, and global (or distributed) backtracking in which multiple processes are involved. We have made a distinction between active objects, which have own activity that must explicitly be interrupted to answer method calls; and passive objects that may answer a method any time. Active objects are allowed to have a limited amount of internal concurrency, in that multiple processes may be active backtracking over the results of a method call. Passive objects, on the other hand, display full internal concurrency. Method calls may be evaluated concurrently. Providing the needed protection is in this case the duty of the programmer.

DLP as a family of languages

\label{des/dlp/tab} For studying the semantic aspects of the language, it has appeared profitable to isolate a number of subsets of DLP. Due to the static nature of the inheritance mechanism we may ignore inheritance. For all the sub-languages DLP0 -- DLP2 (see below) we have provided both an operational and a denotational (continuation) semantics in chapter \ref{sem/com}. We have not included a semantic characterization of conditional acceptance since, despite the elegance of the construct, this seems rather complex. Features such as allocation are omitted since they are simply not interesting from a semantic point of view. Neither have we included a treatment of the cut, nor a treatment of assert and retract statements. The reader not interested in semantic issues is advised to jump to the next chapter.

Backtracking and non-logical variables

\paragraphindex{backtracking} We consider DLP0 to be the base language of DLP. It extends Prolog (without cut) with a construct to assign values to non-logical variables. Moreover, in unification goals of the form
t1 = t2, and in the right hand side of assignments, non-logical variables are replaced by their values and arithmetical expressions are simplified.

Communication over channels.

The sub-language DLP1 extends DLP0 by a construct to create active instances of objects. Also, communication over channels is introduced. Communication over channels is relatively simple, since the backtracking that occurs during a communication is a local phenomenon, restricted to the process at the input side of the channel.

Communication by rendez-vous

Our next extension is called DLP2. It extends DLP0 by constructs for synchronizing on method calls. As a restriction for DLP2, which does not hold for DLP, we require that accept statements occur only in constructor processes. We have given an operational semantics of DLP2 in chapter \ref{sem/op}. The backtracking that may occur during a rendez-vous is global. We speak of global or distributed backtracking, since the process calling the method may force the answering process to backtrack over any remaining answers.