PROLOG-REQUEST@SU-SCORE.ARPA (07/11/83)
From: Chuck Restivo (The Moderator) <PROLOG-REQUEST@SU-SCORE.ARPA>
PROLOG Digest Tuesday, 12 Jul 1983 Volume 1 : Issue 13
Today's Topics:
Representation - Declaring Predicates Transitive,
Implementations - Performance In Programs,
Prolog Availability,
LP Library - Trace Routine
----------------------------------------------------------------------
Date: Thu 7 Jul 83 17:58:09-PDT
From: Vivek Sarkar <JLH.Vivek@SU-SIERRA>
Subject: More On Declaring Predicates Transitive
Having only read the initial issues of the Digest a few days ago, I
hope that I may be forgiven for bringing up an old problem:
The problem was to come up with a predicate, transitive(R) which
checks if R is a transitive (binary) relation.
This is what my solution looks like:
transitive( R ) :- not( nontransitive(R) ).
nontransitive( R ) :- R(A, B), R(B, C), not( R(A, C) ) .
The reason that this kind of problem arises is because a Prolog goal
with uninstantiated variables is like a predicate with an
*existential* ("there exists ...") quantifier. I.e. p(X) is true if
there exists some value a, such that p(a) is true (this is only in the
case that X is uninstantiated to start with). So when we approach
this transitivity problem we may think of
transitive( R ) :- R(A, B), R(B, C), R(A, C).
Then we pause because what we really want to say is "for all possible
A, B & C". But what this says is that R is transitive if we can find
any one set of values for A,B & C such that the above RHS holds. We
want to use a *universal* ("for all ...") quantifier for a goal, but
Prolog goals only lend themselves to existential quantifiers. This is
where the "not" predicate comes into play. From predicate calculus we
know that a universal quantifier can be written as the negation of an
existential quantifier, and so we can expect the "not" predicate to
help us. It turns out to be straightforward to write a predicate for
non-transitivity, since it's an existential assertion. The predicate
for transitivity then follows by a simple negation.
This issue of existential vs. universal quantifiers is a bit of an
anomaly in Prolog. The semantics of variables which occur in the LHS
(or head) of a clause is that they are bound by universal quantifiers.
I.e.
p(X) :- q(X), r(X).
is a statement about *all* X. But if the variable occurs only in the
RHS, then it is effectively bound by an quantifier. I.e.
p(X) :- q(X), r(X, Y).
is a statement which holds for *all* X and *some* Y.
A final note on the solution:
Since most Prolog implementations do not allow a variable functor in a
goal (I.e. R(A, B), where R is a variable), =.. & call have to be used
to actually get it to work:
transitive( R ) :- nott( nontransitive(R) ) .
nontransitive( R ) :- X =.. [R, A, B], call( X ),
Y =.. [R, B, C], call( Y ),
Z =.. [R, A, C], NZ =.. [nott, Z], call( NZ ) .
nott( P ) :- call( P ), !, fail. nott( _ ) .
I have tried this on the DEC-10 Prolog interpreter, and found that it
works. You may notice that I have defined my on negation predicate
"nott"; for some reason, the standard "not" didn't work correctly.
( Even '' ?- not(fail). '' was not satisfied! )
-- Vivek Sarkar
------------------------------
Date: Thu 7 Jul 83 19:37:44-EDT
From: STEVE@COLUMBIA-20
Subject: Performance In Prolog Programs
I would like to do some statistical analysis on large Prolog programs.
I am particularly interested in AI programs in the following areas:
1) Expert Systems
2) Data Bases,
3) Planning or Robotics,
4) NLP
Can anyone provide sample programs that I can use? They should be
large programs that run on Edinburgh Prolog 3.47 (Dec-20) or C-Prolog
1.2 (Unix 4.1/Vax). I would like to collect a good variety, so any
programs will be useful. I would also appreciate a sample journal of
a session with the program so that it can be exercised quickly and
effectively.
Many Thanks,
--Stephen Taylor
------------------------------
Date: 2 Jul 83 13:11:36 EDT (Sat)
From: Bruce T. Smith <BTS.UNC@UDel-Relay>
Subject: How Many Prologs Are There ?
Here's Randy Harr's latest list of Prolog systems. He's away
from CWRU for the summer, and he asked me to keep up the list for him.
Since there have been several requests for information on finding a
Prolog lately, I've recently submitted it to net.lang.prolog. The
info on MU-Prolog is the only thing I've added this summer, from a
recent mailing from the U. of Melbourne. (Now, if I could only find
$100, I would like to try it...)
--Bruce T. Smith, UNC-CH
duke!unc!bts (USENET)
bts.unc@udel-relay (lesser NETworks)
list compiled by: Randolph E. Harr
Case Western Reserve University
decvax!cwruecmp!harr
harr.Case@UDEL-RELAY
{ the list can be FTP'd as [SU-SCORE]PS:<PROLOG>Prolog.Availability.
SU-SCORE observes Anonymous Login convention. If you cannot FTP,
I have a limited number of hard copies I could mail. -ed }
------------------------------
Date: 8 July 1983 1344-PDT (Friday)
From: Foonberg at AEROSPACE (Alan Foonberg)
Subject: Trace Routine
Trace - July 8, 1983 By Russ Abbott and Allen Foonberg
Included is a trace routine which may be useful to users debugging
Prolog programs. If you have any questions, please contact Alan
Foonberg (Foonberg@Aerospace) or Russ Abbott (Abbott@Aerospace).
This is a trace program similar to that provided by the Prolog system.
A term's execution is traced step-by-step by typing "trace(term).",
where term is that term to be traced. At each step of the trace, you
have an option to enter a different trace mode. The list of modes can
be obtained by answering this question with a '?'. A typical trace
line looks like this:
2. (3) enter b(Var, constant)
The number before the period indicates the count, the number in
parenthesis is the depth, the following phrase indicates the port, and
the rest is the current term being traced. To obtain the full trace
as a parameter, type "trace(term, Full_Trace)." Full_Trace will
contain a list of the trace lines, which can be printed out formatted
by typing "trace$_write_term(trace_list(Full_Trace)." A 'true trace'
is also provided by adding a third parameter to the trace call, and
this can be printed in a manner similar to that used to print the full
trace. The true trace contains only those calls that succeeded which
led to the satsification of the main goal. If you have any questions
or suggestions, please send network mail to Foonberg@Aerospace or
Abbott@Aerospace.
[ Trace can be FTP'd as {SU-SCORE}PS:<PROLOG>Trace.Pl or
{SRI-AI}PS:<PROLOG>Trace.Pl
Note: The syntax used is only valid in C-Prolog, not in
DEC-10/20 Prolog or other available Prologs. The problem
is that C-Prolog accepts $ as an alphabetic character. -ed ]
------------------------------
End of PROLOG Digest
********************