RESTIVO@SU-SCORE.ARPA (03/11/85)
From: Chuck Restivo (The Moderator) <PROLOG-REQUEST@SU-SCORE.ARPA>
PROLOG Digest Monday, 11 Mar 1985 Volume 3 : Issue 8
Today's Topics:
Implementaion - 'Numbersvar/3'Definition & Nrev & CP
----------------------------------------------------------------------
Date: Tue, 5-Mar-85 10:52:26 PST
From: nbs-amrf!hopp
Subject: Definition of 'numbervars/3'
I recently obtained a listing of Dave Warren's WARPLAN
planner and put it up on our system, running C-Prolog
1.3. Everything went smoothly except for a predicate
"numbervars/3", which was evidently part of the prolog
he was using (DEC-10 Prolog?), but is not part of our
Prolog. I did find a description of it, which described
it something like this (this is off the top of my head):
numbervars(T,N,M)
Binds all variables in T to special terms such that
the variables print as consecutive integers from N to M.
I defined a numbervars and it seems to work, but I have
no idea if it is right. My definition is:
numbervars(T,N,N) :- atomic(T),!.
numbervars(T,N,M) :- var(T),!,M is N+1,T=M.
numbervars([H|T],N,M) :- !,numbervars(H,N,M1),numbervars(T,M1,M).
numbervars(T,N,M) :- T=..[_|Args],!,numbervars(Args,N,M).
That is, I bind each variable in T to an integer. Is
this, forpractical purposes, different that binding
to "special terms" that print as integers? In
particular, the goal:
numbervars(X,0,1),numbervars(Y,0,1),X=Y.
succeeds with my definition; does it with the built-in
numbervars on those Prologs that have it?
As a secondary question, if my definition is operationally
correct, is there a more efficient definition? WARPLAN
seems to spend a lot of time numbering variables, and it
would be nice if this were as efficient as possible.
-- Ted Hopp
------------------------------
Date: Wed, 6 Mar 85 15:29:05 gmt
From: William Clocksin <WFC%Cl.Cam@ucl-cs.arpa>
Subject: Compilation of nrev using Warren Instructions
Several people have kindly replied to my earlier query
concerning the instruction set of Warren's SRI paper 309.
Yes, the deallocate instruction may stay as it has been
defined, provided the instructions for unsafe variables
are used appropriately. However, Warren's rules for
unsafe variables cause a further problem. Consider the
clause
nrev([X|L0],L) :- nrev(L0,L1), conc(L1,[X],L).
Look at the last goal. According to Warrens rules, only
L1 is considered unsafe. However, for this to work properly
(including "backwards"), L should also be considered unsafe
(if [deallocate] is not to be altered). But because L
appears first in the head, L is considered safe.
What gives? The absence of an example of nrev from
Warren's SRI-309 compounds my confusion. Should L
be considered unsafe? Or have I gone astray somewhere
else?
------------------------------
Date: Tue, 5 Mar 85 18:25:13 -0200
From: Jacob Levy <Jaakov%Wisdom.bitnet@WISCVM.ARPA>
Subject: Concurrent Prolog semantics
Hi!
My, aren't we stirring up a storm here! All this discussion of
the semantics of Concurrent Prolog certainly had to happen
sometime, but I didn't expect it to take on such dimensions
and heat (-:).
I am glad that finally there is a concencus that the current
state of things re the semantics of Concurrent Prolog cannot
continue. Thanks to Vijai Saraswat for pointing out some
ambiguities and to Tony Kusalik for raising some more points
to discuss. I have started to work on a definition of the
abstract semantics of Concurrent Prolog, and Ran Ever-hadani
(RAAN@TECHUNIX.BITNET) is also looking into this.
Here's the final word concerning unification of read-only vars
appearing in the head of a clause. The idea is that the read
only sign says that this clause is the producer of the
variable's final value, and thus no-one should be allowed to
write on it. It is desirable to disallow a variable becoming
read-only as a result of unification, as would occur if we
allowed
goal - g(X)
clause - g(Y?) <- some_other_computation.
to succeed - X would become read-only. Therefore, the unification of a
variable in the head of a clause that is annotated with a read-only
with any goal argument is defined to fail. This is in divergence with
the table shown by Tony - sorry. The reason we don't want to change
the semantics along the lines proposed by Tony is that we must plan
ahead for the days when we have a distributed Concurrent Prolog system
available - the possibility of a variable rooted on some processor
becoming read-only through unification must be avoided. Imagine what
complications will arise if a processor has a normal reference to a
variable, unifies it with some structure, then suddenly is informed
that the variable became read-only on some other processor... This is
possible if time and communication lag are taken into account. Thus we
want to avoid this issue from the start. The table should therefore be
H E A D
|----------|---------------|---------------|---------------|
| | TERM | VAR | RO |
|----------|---------------|---------------|---------------|
| TERM | unify_terms( | trail(HD) | fail |
G| | GL,HD) | HD := REF(GL) | |
|----------|---------------|---------------|---------------|
O| VAR | trail(GL) | trail(HD) | fail |
| | GL := REF(HD) | HD := REF(GL) | |
A|----------|---------------|---------------|---------------|
| RO | suspend(GL) | trail(HD) | fail |
L| | | HD := RO(GL) | |
|----------|---------------|---------------|---------------|
The reason for this controversy is that the semantics as proposed here
are impossible to enforce in an interpreter-based system. Only by com-
pilation can we ensure that this behaviour is adhered to. Therefore it
was necessary to approximate a reasonable behaviour in the interpreter
systems.
Another point raised by Tony - whether we should allow many
attempt to commit for a given goal. This is still not decided; on the
one hand, since in Flat Concurrent Prolog we effectively have this
feature, it would be desirable to have the same semantics of commit in
Concurrent Prolog also. On the other hand, the handling of distributed
commitment is complicated - many people have spent a lifetime solving
this problem in various forms, and so far no solution that is really
suitable for Concurrent Prolog has emerged. The initial inclination of
Udi was to avoid distributed commitment, but now we are rethinking the
issue.
I have debugged an interpreter for Concurrent Prolog, written
in C, that uses eager broadcasting to propagate values of variables to
guards. It is painfully slow, and currently I am analyzing the reasons
for this. Since we think that the overhead of propagating values into
guards may be the cause, we have started rethinking this issue also. A
system that allows multiple attempts to commit without using eager
broadcasting has provably weaker semantics than one that allows only a
single attempt to commit but uses eager broadcasting. The reason is
that with eager broadcasting failures of candidate clauses are always
detected before they reach commitment, so when a clause finally does
attempt to commit, this is guaranteed to succeed. So the real question
is whether the semantics provided by the multiple-commit-attempt and
no-eager-broadcasting system are still sufficiently expressive.
Cheers,
-- Jacob Levy
------------------------------
Date: Sun 10 Mar 85 21:38:41-EST
From: Vijay <Vijay.Saraswat@CMU-CS-C.ARPA>
Subject: The read-only annotation in CP.
Discovering how the read-only annotation behaves in CP is
an interesting exercise. The following is a discussion of
what it does, together with a discussion of its various
idiosyncracies. In brief, I think unrestricted '?' is
very powerful, and can easily give rise to all kinds of
obscure and probably undesirable behaviour.
In the following discussion, `X' and `Y' represent
variables and `T' and `Term' represent a compund term.
To understand the following discussion it is necessary to
bear in mind that in CP, processes are goals, and the
input and output channels for the process are represented
by the occurrences of variables in the atomic formula
representing the goal. The only action that can be taken
by a goal is to unify against the head of a clause. This
unification typically would lead to an instantiation of
various variables in the goal. However it is undesirable
that variables that are supposed to represent input
channels should be instantiated. Also, typically a goal
implements some kind of a (possibly multi-valued) function
from its input arguments to its output arguments and hence
it is unwise for process reduction to continue until
values for the input arguments are available. Both of
these objectives are sought to be achieved by the
introduction of a 'read-only annotation' (?) which can
decorate instances of a terms in goals and clause heads
and whose semantics is specified below. Thus ? has two
roles: ?-as-read-only-designator and ?-as-input-designator.
Semantics of ?.
---------------
1. unify(X?, Term) suspends until X gets a value (that
is, is instantiated to a non-variable term), after which
X is unified with Term.
2. unify(X?, Y) succeeds with Y becoming a
read-only version of X, in all its occurrences.
3. unify(X?, Y?) suspends until both X and Y are
instantiated, after which X and Y are recursively unified.
4. unify/2 is symmetric.
Note that as defined above, suspension in 1. is critical.
It allows a process to effectively do a CASE on various
combinations of conditions which depend upon the
availability of specific kinds of inputs on (possibly
multiple) channels. But this suspension is really only
justified in the very special case in which a guarded
occurrence of a variable in a goal matches different terms
in different clause heads for the given process and the
actual value of the variable is needed at run-time to
select some of all those paths.
This gives a `reasonable' meaning to `?' provided you
assume that:
Condition 1. AT RUNTIME, in every goal call, if even one
occurrence of a variable is read-only, then all instances
are read-only. (Hence that variable may legitimately be
considered a read-only variable to the call. This
corresponds to the normal restrictions in data-flow
languages that an input stream to a process cannot also be
an output stream. Note that calls such as fibonacci(1.X,
0.1.X, X) (where fib(X,Y,Z):- add(X,Y,Z).) do not need
any '?' annotations at all. )
Condition 2. In every clause-head if even one occurrence
of a variable is read-only, all occurrences of that
variable should be read only.
Condition 3. If a variable is read-only annotated at some
occurrence in a clause-head, then ensure that all goals
that would reduce via this clause have a variable
(possibly read-annotated... see section V.) at that
occurrence.
Condition 2 is symmetric to condition 1, but for
?-occurrences in goal-calls, a restriction corresponding
to condition 3 is not required; this is a fundamental
diffeence between the use of ? in goals and in
clause-heads in CP.
Now let us look at the problems associated with it. Let us
start with the simple ones.
I. What should happen with unify(X?, X) ? (Don't even
think of trying to answer this by running any
'implementation' of ?-unification, least of all the
unificationalgorithm in The Paper, unless you would enjoy
a tete-a-tete with an infinite list of '('s. Don't believe
me? Switch on your debugger and settle into your most
comfortable arm-chair.)
According to the definition given above for X?-Y, X should
now become a read-only version of X in ALL ITS OCCURRENCES
throughout the world so that there will be no more
producers for X left! Somehow that doesn't sound very
appealing so lets make a special case of this and say that
X?-X should succeed and do nothing.
(It is easy to see that if Conditions 1 and 2 are
satisfied, such a call to unify can never arise because
variables in the head of a clause are `standardised apart'
before unification against a goal. Otherwise, consider
the case "?-foo(X?,X), X=2." where the clause is
"foo(Y,Y)." If X? unifies with Y as given above, then
unifying the second arguments to foo will lead to X being
unified with X?, i.e. X becoming a read-only version of X.
When the clause commits, the X in X=2 will become X?=2,
leading to deadlock, which seems "wrong".)
II. What happens with unify(X?, X?) ? According to the
above definition, this unification should suspend until X
gets a binding, when it would be checked against itself!
On the other hand, the interpretation of '?-as-read-only'
would be consistent with just succeeding and doing nothing
else because even potentially X can hardly get a 'new'
binding from X. (?-as-input-designator interpretation does
not seem applicable.) (In a private communication, Ehud
agrees that perhaps X?-X? should be allowed to succeed.)
III. Unification is now order-dependent.
Typically to unify a term (T1) against another (T2),
you check the functors are the same (i.e. they have the
same name and the same no. of arguments) and then you
unify the corresponding arguments inthe two terms IN ANY
ORDER. This no longer works. e.g. unify(foo(X?, X),
foo(a,a)) suspends if you match the first arguments before
the second but succeeds if you match the second before the
first. (Apparently this behaviour is well-known.) This
implies that we must now introduce some bias in the
unification: either specifying an order in which
unification will be done or else saying that
(conceptually) all possible orders will be tried and if
anyone leads to sucess (without suspension) then that will
be chosen. The first alternative seems unpalatable, and
the second probably complicates the unification algorithm.
If the second alternative is chosen, we will call it
`desperate unification' because it implies that unify is
desperate to avoid a suspension.
Again, if Conditions 1 & 2 are satisfied, then this
order-dependence goes away.
IV. The view ?-as-input-designator is useful ONLY for ?
occurrences in goals (i.e. in bodies of clauses) NOT in
heads of clauses. This has the following consequences:
1. If X? occurs in the head of a clause at argument i, and
there is a constant (or an instantiated term) at argument
i in the goal call, then SUSPENDING till X gets a value is
in general meaningless because the only way you can get a
binding for X is by executing some goal in the body of the
clause which generates a value for X. BUT YOU CANT DO
THAT IF YOU SUSPEND. Catch-22.
The only way you can avoid this certain permanant
blocking is if there is some other occurrence of X in the
head of the clause which is not read-protected and its
corresponding argument in the call gets instantiated at
some time in the future and unify is desperate.
2. The same is true if an X? occurrence in the clause
head matches a Y? occurrence in the goal call. SUSPENSION
is SUICIDAL.
3. The only use then for X? in a clause head, it would
seem, is to check if its corresponding argument in the
goal call is a variable (Y). If it is, Y becomes a
read-only copy of X in all its occurences as soon as the
clause guard commits, if it commits. For this to happen
it must be the case that Y is a variable when the call is
unified with the clause head and can still unify with X?
without suspending when the clause guard commits. This is
such a strong condition that only very very limted uses of
`?' in clause-heads are feasible.
For example, see `Implementing Parallel Algorithms in
Concurrent Prolog: The MAXFLOW experience' by Hellerstein
and Shapiro, ISLP, 1984 and the bounded-merge solution in
this Digest for another way of using a X?-Y match which
avoids this deadlock. Hellerstein and Shapiro use the ?
embedded in a term, as in [X|Y?],in the head of a clause.
If it can be guaranteed that this term is always matched
by a variable in a goal call,and the variable remains
uninstantiated through the hiatus between Or-guard
initiation and commitment, then such a use is always safe.
Thus it is almost impossible to put '?' in clause heads.
IV. If X?-Y succeeds with the variable Y becoming a
read-only copy of X in all its instances, then two kinds
of undesirable behaviours are possible:
1. At run time, read-only copies of variables can be
created through very long-chains of X?-Y followed by Y-Z
kinds of unification so that a seemingly innocuous goal
such as foo(R, S) would suspend because R got bound at
run-time to X?. A static analysis of the clauses for a
process is not enough to describe its behaviour; in
addition all the calls to the procedure must be examined,
and then all the goals in the clause in which the call
occurs which share variables with this call, and their
clauses, ad infintum. This makes writing modular code and
proving properties of programs very diffcult.
2. If a process has a writeable access to a channel X, it
can cause that channel to become a read-only copy of some
other channel thereby effectively blocking all other
processes which might be writing to the channel. Maybe
the solution is to have an explicit producer annotation in
CP alongwith a read-only annotation, with some priorities
between the two.
V. There is really no a priori justification for causing
unification of X?-Y? to suspend until both X and Y get
values and then to recursively unify them. It makes sense
to suspend only if suspension would lead to more
information being available at some time in the future
(e.g. in the form of X's bindings in a X?-Term
unification) which could lead to the selection of a few of
possibly many clauses. But if, for example, a X?-Y?
unification were to occur with an X? occurrence in a goal
and a Y? occurrence in a clause-head, it is not possible
EVER for a binding of Y to be produced, in most
circumstances, so X?-Y? definition serves no purpose at
all; it may as well have been defined to FAIL always, at
least that way it wouldn't cause deadlock.
The other possibility is that X? and Y? both occur in
the goal call (e.g. ?-foo(X?,Y?), producer(X),
producer(Y).), and the clauses head 'equivalences' them
by, for example, unifying them both against Z (Clause:
foo(Z,Z).). In such cases, it certainly makes sense to
succeed with X and Y unified (that is, identified). This
is becaue if in the future X and Y do not both produce the
same value, they will anyway be doomed to failure. In
case foo(Z,Z) was only one of many clauses and it is
possible that some other clause might succeed if X? and Y?
produce different values, then it certainly makes more
sense to have a clause foo(A.Z, A.Z) instead of foo(Z,Z).
The same holds if the goal was ?-foo(Z,Z) and the clause
head was foo(X?,Y?):- producer(X), producer(Y).
Therefore, a certainly useful alternative semantics for
the X?-Y? case would be to treat it like X-Y. Succeed
immediately and unify X with Y. Essentially the two ?
cancel themselves out.
Such a change would also cause suspension to happen iff
there was a read-only violation of the form X?-Term. This
allows the use of X? in the head of a clause to check for
whether the corresponding argument in the goal call is
instantiated or not, something that has been done till now
with the another extra-logical primitive var/1. This was
the philosophy on which my original solution to the
bounded merge problem (see previous issue) was based.
Another possible use of channels also becomes evident. If
a goal contains an occurrence of X? and is unified against
a clause head which contains a Y? in that argument
position, then the result is as if the process becomes a
producer for the channel, even though it was earlier
passed just a read-only reference at run-time. Thus if a
process always wants write-access to a channel, it can do
that by placing a X? at the argument position in the
clause-head where it expects the channel to be supplied.
In this fashion,a process has to make fewer assumptions
about the behaviour of its environment at run-time.
Note that the treatment of X? in clause heads as the
export of a stream called X is still troublesome because
the clause may be invoked with the corresponding argument
in the call instantiated. Clearly suspension is not
needed here. What has happened is that some process which
was to have read-only rights to the channel has already
read something off which has yet to be written. This
should probably be signalled as a run-time error and
computation aborted. It indicates that the process which
wrote something on the channel should not have had the
right to do that; it should have been called with the
channel protected.
To sum up, then, I would argue that the intuitive
interpretation of '?' makes sense in only some of the many
possible ways in which it can be used. Maybe the language
should then provide syntactic restrictions which encourage
such use. Conditions 1-3 are a step in that direction.
On the other hand, a suitable choice of definitions can
expand the generality of the '?' primitive, providing
concurrent programming facilities which Cp doesn't at this
time provide, but can lead to complicated implementations
and semantics.
------------------------------
End of PROLOG Digest
********************