RESTIVO@SU-SCORE.ARPA (03/26/85)
From: Chuck Restivo (The Moderator) <PROLOG-REQUEST@SU-SCORE.ARPA>
PROLOG Digest Tuesday, 26 Mar 1985 Volume 3 : Issue 13
Today's Topics:
Implementations - New Engine & C-Prolog Patch & CP,
Denotational Semantics
----------------------------------------------------------------------
Date: Mon 25 Mar 85 03:05:07-PST
From: Tarnlund@SRI-AI.ARPA
Subject: Warren's New Engine
Two questions re: put_unsafe_value:
Says Warren, "This instruction represents the
last occurrence of an unsafe variable...".
Shouldn't it be *all* occurrences of an unsafe
variable in the last goal where it occurs?
I don't see why put_unsafe_value needs to create
a global variable if the engine is in a nondeterminate
state, since in that case the environment is not about
to be discarded.
-- Mats Carlsson
------------------------------
Date: 25 Mar 1985 01:50:54 PST
From: Mike Newton <Newton@CIT-20.ARPA>
Subject: yet more C-Prolog hackery
While using C-Prolog (vsn 1.5) we came up with
the following sample program:
f(Y) :- (true, ! ; X = 0), Y =< 7.
Horrible things happen if one calls f(3).
I have been trying to go through the internals of
C-Prolog to correct this error.
THOUGH I AM NOT SURE OF THIS PATCH, I suggest the
following:
in pl/init change the lines that define semicolon from
(A;B) :- $call(A).
(A;B) :- $call(B).
to
(A;B) :- $hidden_call(A).
(A;B) :- $hidden_call(B).
This SEEMS to correct the problem. If anyone else
could confirm this or can figure out a better patch,
please send me mail. We are using C-Prolog in our
own effort to build a good Prolog compiler.
-- Mike
------------------------------
Date: Sun 24 Mar 85 16:05:54-MST
From: Uday Reddy <U-Reddy@UTAH-20.ARPA>
Subject: Concurrent Prolog and Denotational Semantics
Who would have thought that Vijay's merge program
would'nt work? Excepting the language designers and
the machine, that is. If the previous articles
on Concurrent Prolog annotations went past you, try
this one. Warning: This is a long note.
The problem with CP's read-only annotations is that
their semantics is defined at too low a level (in terms
of how they affect unification) rather than in terms of
how they affect the meanings of the programs. We don't
know what the denotational semantics of CP is, whether
it exists at all, or how complex it is.
The simplest way to understand logic programs is of
course to say that they define predicates. Let me call
this "basic semantics". Under this semantics, a 2-ary
predicate p - for instance - when applied to a ground
tuple (t1, t2), is either "true" or "unspecified". We
very well know how to find the basic semantics of a
given logic program.
The next level of semantics views the action of
predicates on non-ground tuples. Let me call this
"non-ground semantics". Now, a predicate p when
applied to a non-ground tuple (n1, n2) yields a set of
substitutions. Boolean operators can be defined on
this kind of predicates, and logic programs can be
understood in terms of these. But, evidently, non-
ground semantics is significantly more complex than
basic semantics.
However, there is a "vital connection" between basic
semantics and non-ground semantics which makes it quite
unnecessary to understand logic programs in terms of
non-ground semantics. Let p* be the non-ground
predicate corresponding to a basic predicate p.
p*(n1,n2) contains exactly those substitutions which
when applied on (n1,n2) yield ground tuples for which
p is true. More simply, the vital connection can be
stated as "the truth of an atom is preserved by
instantiation". So, if we know the basic semantics of
a predicate symbol, we automatically know its non-
ground semantics as well.
It is a good idea to define a "pure" logic language as
one that maintains this vital connection between its
basic semantics and non-ground semantics. Purity is
thus not a God-given concept, but one that is
determined by pragmatic considerations of simplicity.
Prolog, even with its sequential "and" and "or"
operations would still be pure (it would work in a kind
of non-standard logic), only if it didn't have cut, var
and similar constructs. Take var, for instance.
var(X) is true. But it is not true for any ground
instance of X. Thus, var breaks the vital connection.
All predicates now have to be understood as mapping
non-ground tuples to substitutions instead of as good
old logic predicates. Truth is not anymore preserved
by instantiation. For instance, consider
p(X) :- var(X), X=1.
p(Y) yields the substitution Y -> 1. But, p(1) is
untrue. Another problem is that var does not permit a
commutative "and" operation, thus destroying
parallelism. Cut does not even permit a commutative
"or" operation.
Now, let us get to Concurrent Prolog's read-only
nnotation. What is the meaning of an atom p(n1?,n2)
where n1 and n2 are non-ground terms? First of all,
such an atom is not even legal unless n1 is a variable
(Only variables can be annotated, not terms). This is
rather paradoxical. If impure logic languages don't
preserve truth under instantiation, CP does not even
preserve syntactic legality under instantiation.
This adds another layer of complexity and leads to what
I call "substitution semantics". Note that we have not
so far distinguished between atoms and goals. Atoms
are the ones that occur in clauses, whereas goals -
obtained by applying substitutions on atoms - occur at
run-time. An atom (a predicate applied to a non-ground
tuple) should now be interpreted as a function that
maps a substitution to a set of substitutions. We have
come quite far from basic logical semantics. Maybe
these domain equations help to understand what is going
on.
goal = P(substitution)
atom = substitution -> P(substitution)
predicate = non-ground-tuple ->
substitution -> P(substitution)
Even though these domains may appear strange, I think
we normally reason about Prolog programs using such
denotations. Jones-Mycroft semantics for Prolog uses
this kind of domains.
Now, let us attempt to give a meaning to atoms with
read-only annotations. Suppose we know the meaning of
an atom A. Let A' be another atom obtained by
annotating a variable X in the original atom. A
reasonable candidate for the meaning of the new atom is
M[A'](s) = M[A](s) if s(X) is a non-variable term
{} otherwise
A' performs any computation at all only if X is
instantiated in the input substitution. When it does,
it performs the same computation as A. It appears to
me that this equation does hold for Concurrent Prolog.
But, I leave it to the language designers to correct
me if I am wrong.
Note that the above equation holds only if all
occurrences of a variable in an atom are annotated.
Also, we have not yet dealt with annotations in
clause heads. But, already there are problems.
Firstly, we have to define an "and" operation on these
atoms. It is possible to define a sequential "and"
operation.
M[A1, A2] (s) = {s2 in M[A2](s1) | s1 in M[A1](s)}
But, I don't see how one can define a commutative "and"
operation. This is important because, unless we have
a commutative "and" operation, we can't sensibly
execute A1 and A2 in parallel. The inability to define
a commutative "and" operation means that substitution
semantics is not adequate for Concurrent Prolog. Let
me illustrate the problem with an example:
p([A|L]) :- p(L?).
p([]).
Now consider the meaning of p(X). If the input
substitution instantiates X to a ground or non-ground
list, the atom holds. (The output set contains only
the identity substitution). But, what if the input
substitution does not instantiate X? The atom can
instantiate X to [A|L] and reduce to p(L?). If we go
by substitution semantics, computation should get stuck
here because L is a new variable introduced in the
output substitution of the atom and so L cannot have an
instantiation in the input substitution. But, in
Concurrent Prolog, p(X) can be used in conjunction with
other atoms which can "cooperate" to produce an
instantiation for X. That is, the other atoms used in
conjunction can accept X->[A|L] in their input
substitutions, and produce instantiations for L which
would then be accepted as the input substitution by
p(X). The meaning of p(X) should capture such dynamic
cooperation that may occur at run-time. Simple-minded
substitution semantics is not enough.
The second problem is that annotations do not just
occur in atoms. They occur in instantiations as well.
The definition says "If Y is a variable then the
unification of X? and Y succeeds, and the result is a
read-only variable". So, if Y occurs in the head of a
clause, the input substitution instantiates Y to a read
-only variable Y->X?. Needless to mention that this
adds another layer of complexity to the denotations.
So, there are enough problems with Concurrent Prolog
even without allowing annotations in clause heads. I
think annotations in clause heads with the standard
definition of unification is a very bad idea. If we
have a clause
A :- B.
the meaning of :- in substituion semantics is the
superset relation.
M[A](s) superset-of M[B](s)
For any input subsitution s, all the output
substitutions that B can produce are included in the
output subsitutions that A can produce. This meaning
of :- breaks down if annotations are allowed in clause
heads. Who knows what more needs to be added to
rehabilitate :- ?
I am ending on a pessimistic note because that is what
I intended to do. Concurrent Prolog is too complex.
Don't be misled by the simplicity of a three-line
definition of unification. Concepts that look very
simple operationally can turn out to be very complex
denotationally. The imperative "go to" is the classic
example of this. Denotations are meanings that
"compose". Only denotational semantics can tell us how
a simple three-line definition can affect the overall
meanings of programs.
PS: Both in this note and the earlier one on
denotational semantics, I misuse the term
"non-ground-tuple" to include both ground and non-
ground tuples. Sorry.
Uday Reddy
------------------------------
End of PROLOG Digest
********************