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
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
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 will
give the same results as evaluating the goal
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 asks the object c to
evaluate , 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 is being evaluated,
the caller waits for an answer.
Backtracking over the results, indicated by ,
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 ,
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
as in
?- travel!reachable(tokyo).
for which the answer is, perhaps unfortunately, no.
When the goal 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 ,
similar to the object travel but with (possibly) different
values for the non-logical variable city, which allows us to
ask
?- lib!member(O,[]), 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
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).
add(X):- append([X],city,R), city := R.
}
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
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),
O1!add(berlin), O2!add(antwerpen).
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 are arbitrary terms.
The term is called the constructor,
since, when creating a new object,
a process is started to evaluate the goal .
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 results in a new instance of the object c
together with a constructor process evaluating .
Both the calls and , 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
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),
add(X),
fail.
agency(_):- run().
run():- accept(any), run().
reachable(X) :- member(X,city).
add(X):- append([X],city,R), city := R.
}
The declaration for agency differs from the declaration for
the object travel only in having constructor clauses
and an auxiliary clause for ,
that define the own activity of each instance of an agency.
Suppose now that we wish to combine four travel agencies,
of the old kind into two new agencies,
then we may state as a goal
?-
O1 = new(agency([])),
O2 = new(agency([])),...
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 , 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
to create an active instance of the object c.
To create new channels we use a goal of the form
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
where C refers to a channel and t is an arbitrary term.
Also, we need an input
statement of the form
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
, 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
that is used to increment the value of the counter.
The second clause contains the input statement
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
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
and , 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 , consist of executing run.
An active object outputs a term over
over channel C. Initially, N is zero.
When evaluating the goal
?- C = new(channel), new(a(C)), C!f(X,1).
an object , that is initialized with channel C.
The newly created object runs indepently of the process
evaluating the original goal.
Since both and 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 is evaluated by simplifying 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.
- ---
to assign the value of a term to the non-logical variable x
- ---
to create an active instance of c, to which O will refer
- ---
to call the method m of the object to which O refers
- ---
to state the willingness to accept calls for
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 and .
Despite the notational similarity with communication over channels,
the calls and
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 will be suspended,
because of the statement ;
otherwise both and may occur,
since when n is not zero the statement 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 and .
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 that calls , with O
bound to the object of which evaluates the constructor.
When reaches an accept statement the activity
of is interrupted,
and a new process is started to evaluate
which refers to the same object as .
Process resumes the evaluation of the constructor as soon as
the first answer, say , is produced.
Thereafter continues to produce alternative solutions,
as may be requested by .
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).
add(X):- append([X],city,R), city := R.
}
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).
add(X):- append([X],city,R), city := R.
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
[]
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
requires more effort.
When a method is called, say by ,
then it is first tried whether the call can be unified
with the expression .
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 .
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 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 .
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
- --- accepts all calls that unify with
- --- accepts all calls for m if the guard holds
- --- accepts all calls that unify with
for which the guard holds
- --- executes goal for all calls to m if
the guard holds
In addition we have
-
m(t1,...,t_n):guard -> goal
that executes goal for all calls
unifying with 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),
add(X): true -> append([X],L,L1)
), 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
to request the object to which O refers to create
a process to evaluate the goal . The variable Q thereafter
refers to that process.
For the request of the result we introduce
that asks the process, referred to by Q, for an (other) answer.
Informal semantics
Using somewhat contradictory terminology,
a call of the form may be regarded as an
asynchronous method call,
since receiving the (possibly multiple) answers
requires an explicit request of the form .
The variable Q is bound to a pointer to the process
evaluating .
The method call must
explicitly be accepted by an accept goal of the object
to which O refers.
We call the goal 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
, G,
Between the creation of the process evaluating
the goal and stating the
resumption request to collect the answers to ,
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 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 succeeds when the answer is received.
The asynchronous rendez-vous preserves completeness
in coupling the solutions produced by evaluating
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 .
However, if 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 .
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
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
where G is a goal and N is a node number.
The meaning of a goal
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.
Node expressions
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-1I0:I1:...:I_nI1,...,I_n, giving the path $1,2,1N1 # N2N1 # N2N1 # N2 + 1...v:=tO=new(c(t))O!m(t)m(t)accept(m1,...,m_n)m1,...,m_nC = new(channel)C!tC?tmethod:guard -> goal Q = O!G Q?O = new(obj@N)G@Nt1 = t2