RESTIVO@SU-SCORE.ARPA (05/01/85)
From: Chuck Restivo (The Moderator) <PROLOG-REQUEST@SU-SCORE.ARPA>
PROLOG Digest Wednesday, 1 May 1985 Volume 3 : Issue 20
Today's Topics:
Puzzles - AVG's Riddle
Implementation - C-Prolog & Semantics & Control & CP
LP Library - Update
----------------------------------------------------------------------
Date: Wed, 17 Apr 85 18:16:35 pst
From: Allen VanGelder <AVG@Diablo>
Subject: Answer to Allen VanGelder's Riddle
From: Ran Ever-Hadani
Subject: Answer to Allen VanGelder's riddle
p('6').
-- Ran Ever-Hadani
This does NOT work in C Prolog to produce my results.
?- p(X). answers X = '6', and not X = 6. However,
Ran's program does work in DEC-20 Prolog, but only if
you use write instead of writeq. My riddle (see
Digest Vol 3 Issue 16) has the same output if writeq
is used instead of write, but works only on C Prolog,
not DEC-20 Prolog. So this is very much an
implementation dependent riddle.
------------------------------
Date: 23 Apr 85 16:43:06 +1000 (Tue)
From: decvax!mulga!mungunni.oz!Lee@Berkeley
Subject: Bugs in listing
Here's a little test for the listing predicate of
your favourite Prolog system with DEC-10 style
syntax. The test is to read in a clause, write it
out with listing then read it in again and see if
it is the same. Many systems will get syntax
errors when they try to read it back in or just
get it wrong.
=======================consult this=====================
p((a,b)) :-
q(','),
- -r,
s(['+x+',(-),'Fred']),
t('/*', '%'),
(+)-(+)=(.)-(.),
not not v is w,
w(','(a,b,'.')),
a = && .
?- write('TESTING...'), nl,
tell(lstest), listing(p), told,
seeing(S), see(lstest), read(X), see(S),
clause(p(Y), Z),
X=(p(Y):-Z),
write('SUCCESS'), nl.
=========================================================
With C-Prolog 1.4d, the extra parentheses on line 1 are
missing and there is no space (or parenthesis) between
"&&" and ".", so it runs into the end of file.
With UNSW Prolog (the test needed to be modified
slightly) the "-" in the list should have been
parenthesised but wasn't, "." was not quoted or
parenthesised and there was no space after "&&".
With previous versions of MU-Prolog, there were
several problems with lack of quotes, spaces and
parentheses. The current version works, though
it does print some unnecessary parentheses and
spaces (as does C Prolog). If anyone has any other
nasty tests, please post them.
-- Lee Naish
------------------------------
Date: Thu 18 Apr 85 12:11:06-MST
From: Uday Reddy <U-REDDY@UTAH-20.ARPA>
Subject: Semantics
Notwithstanding our differences in the styles and
approaches to semantic specification, I think Joseph
Goguen and I agree on the essentials. My summary of the
whole discussion is the following.
Firstly, programming languages need a semantics that is
compositional, whereby the meaning of composite
constructs is expressed solely in terms of the meanings
of their constituents. This is necessary so that we can
understand predicates or functions defined by the
programs by abstracting over the implementation/
definition details. Whether this semantic specification
is done using conventional model theory or domain theory
or any of their variants or extensions is open to
debate, taste and choice.
Secondly, the operational semantics/proof theory of the
language has to be sound and complete with respect to
the semantics. This should be so, for the semantics to
have any real use in practice, so that what we
understand by the programs is exactly what is computed
by the machine.
The so called "control" mechanisms currently used with
various logic languages create a wide gap between the
proof theory and the semantics. For instance, the van
Emden-Kowalski semantics is too far from sequential
Prolog. We, the users, are then left with a semantics
that is simple and well-understood, but useless in
practice, and a language which can only be understood by
tracing the states of a machine (however abstract the
machine may be).
The first possible solution is to specify clearly the
conditions under which the the operational semantics is
complete with respect to the compositional semantics
(assuming that it is at least sound). For instance,
rewriting languages specify that the implementations are
complete with respect to the initial model, only if the
rewriting system is strongly terminating.
A second solution is to specify the compositional
semantics in a theory that can account for control
aspects (termination, failure and so on). Possibly all
control features can be explained in an adequately
general theory, but the theory may be too complex to be
of any pragmatic relevance. We should then reject
languages based on the complexity of the theory required
for their compositional semantics. This is the solution
I favor.
A third and longer-term solution is to find control
mechanisms that retain completeness, at least under
well-understood sufficient conditions. This is the
solution Joseph favors.
With my experience in the use of logic languages and
their implementations, I am personally skeptical about
the viability of the third solution.
-- Uday Reddy
------------------------------
Date: 19 Apr 1985 1625-CST
From: THRIFT%ti-csl.csnet@csnet-relay.arpa
Subject: Control annotation in CP
There has been much recent discussion [3] on the
'correct' unification definition when read-only
variables are concerned (as whether two read-onlys
can unify, whether a read-only can unify with a
regular variable, etc.) My basic objection to this
particular control annotation is as follows:
Variables may 'become' read-only during execution
(at least in the original definition of unification
with read-onlys [1,2]). This makes understanding
of a program difficult. I basically believe it is
confusing when a control annotation passed around
during execution.
A control annotation (bearing some similarities some
some of the recent suggestions in [3]) is what I call
a 'mode' annotation, somewhat like the mode declaration
for the DEC-10 compiler. There are two symbols '+' and
'-' which may annotate the (surface) arguments of the
head. The annotations describe preconditions before
unification can be attempted: a '+' argument can only
be unified with a nonvar term and a '-' argument can
only be unified with a var term (input and output
restrictions).
An example is the merge definition:
merge([]+,Y,Y).
merge(X,[]+,X).
merge([X1|Xs]+,Y,[X1|Z]) :-
merge(Y,Xs,Z).
merge(X,[Y1|Ys]+,Z) :-
merge(Ys,X,Z).
which implements a fair merge (stable machine).
Suppose for some reason one wanted to specify a
priority merge (that if there are elements on one
stream they are guaranteed to be output before
elements of the other, which have to wait until
until the first stream is 'waiting'). This could
be done as follows:
merge([]+,Y,Y).
merge(X,[]+,X).
merge([X1|Xs]+,Y,[X1|Z]) :-
merge(Xs,Y,Z).
merge(X-,[Y1|Ys]+,Z) :- % The second stream is ouput only
merge(X,Ys,Z). % when the first is 'waiting'
This could not be done as neatly with the read-only
annotation (this depends I guess on which definition
of read-only unification you choose).
With this notation a definition of lt(X,Y) as given
in [1]:
lt(X,Y) :- wait(X,X1),wait(Y,Y1) | X1<Y1.
is simply
lt(X+,Y+) :- X<Y.
'plus' as in [2] is:
plus(X+,Y+,Z) :- Z is X+Y.
plus(X,Y+,Z+) :- X is Z-Y.
plus(X+,Y,Z+) :- Y is Z-X.
I basically feel that this control annotation
1. Makes programs much easier to understand in that
a. the control is associated with the definition of
a process and not its execution
b. the control annotation is never passed around
c. no wait/2 built-in is required
2. Is sufficient for most of what one wanted the original
'?' notation (I believe it is completely sufficient for
practical purposes)
3. Could possibly make for a more efficient implementation.
[1] Shapiro,E.Y.:A Subset of Concurrent Prolog and Its
Interpreter,ICOT Technical Report TR-003 (1983)
[2] Shapiro,E.Y.:Object Oriented Programming in Concurrent
Prolog,New Generation Computing,1 (1983)
[3] Prolog@SU-Score:Prolog Digest Vol3 ...
------------------------------
Date: Tue 30 Apr 85 12:03:21-PDT
From: Chuck Restivo (The Moderator) <RESTIVO@SU-SCORE.ARPA>
Subject: Update
[cwr] Professor Zohar Manna and Richard Waldinger
authored a new book that might be interesting to
to some readers.
"The Logical Basis for Computer Programming"
Volume 1: Deductive Reasoning
ISBN: 0-201-18620-2 Addison Wesley
------------------------------
End of PROLOG Digest
********************