PROLOG-REQUEST@SU-SCORE.ARPA@sri-unix.UUCP (06/05/83)
From: Chuck Restivo (The Moderator) <PROLOG-REQUEST@SU-SCORE.ARPA>
PROLOG Digest Sunday, 5 Jun 1983 Volume 1 : Issue 8
Today's Topics:
Query - Equivalence & A Puzzle,
Representation - Declaring Predicates Transitive,
LP Library List Available!
----------------------------------------------------------------------
Date: 4 June 1983 1650-PDT (Saturday)
From: Abbott at AEROSPACE (Russ Abbott)
Subject: Equivalence
This may seem like a stupid question, but I'll risk looking stupid and
ask it anyway. How does one deal with equivalence in Prolog?
Imagine that one is building a system that interactively constructs a
knowledge base in the form of Prolog rules. While interacting with a
user one stores a number of predicates that are defined in terms of
some predicate p(X).
a(x) :- ..., p(x), ..., .
Also, one stores a number of predicates that are defined in terms of
some other predicate q(X).
b(x) :- ..., q(x), ..., .
Various definitions for p and q are also given by the user. The user
then tells you that p(X) means the same thing as q(X), i.e.,
p(X) :- q(X). and
q(X) :- p(X).
One can't put both of these rules into the database for fear of
infinite loops. Are there any clean ways out of this predicament?
------------------------------
Date: 2 Jun 83 04:52:02 EDT (Thu)
From: Bruce T. Smith <bts.unc@UDel-Relay>
Subject: Prolog puzzle
Starting with problem #26 in his book "What is the Name of this
Book?", Raymond Smullyan presents a number of variations on a
familiar logic puzzle. Here's his introduction to the section:
There is a wide variety of puzzles about an island in
which certain inhabitants called "knights" always tell
the truth, and others called "knaves" always lie. It
is assumed that every inhabitant is either a knight or
a knave.
All the puzzles involve meeting a small party of the island's
inhabitants. Sometimes a question must be asked, other times
information is volunteered. In all cases, the goal is to determine
which are knights and which are knaves. A sample of this type of
puzzle is the following:
#31. Again we have three people, A,B,C, each of whom is
either a knight or a knave. A and B make the following
statements:
A: All of us are knaves.
B: Exactly one of us is a knight.
What are A,B,C?
I've played around at solving these puzzles using Prolog, with
only mixed results. Here's the challenge for Prolog programmers:
Write a Prolog program which will solve this type of problem, where a
problem description is a list of names (e.g. A,B,C) and statements.
Restrict the statements the people may make, but at least let them
make claims about which groups they and their companions belong to.
This simplest puzzle may seem too easy, the set of possible
solutions is small enough to examine them all, for instance. The
puzzles in the book quickly increase in difficulty, however. One
simple variation is introduced in problem #39, with the addition of
"normals", who sometimes tell the truth and sometimes lie. (By the
end of the book, Smullyan is playing around with Godel's Theorem.)
I'd be interested in seeing how far people can get with knights and
knaves problems (or beyond), comments on solving this type of puzzle
(where the truth or falsity of statements must be determined before
they can be used), etc.
-- Bruce Smith, UNC-CH
duke!unc!bts (USENET)
bts.unc@udel-relay (other NETworks)
------------------------------
Date: 3 June 1983 0916-PDT (Friday)
From: Abbott at AEROSPACE (Russ Abbott)
Subject: Still trying to Declare Predicates Transitive
Vijay,
Thanks for your answer to my question concerning declaring predicates
transitive. I have two problems with your solution.
1) If there is a cycle longer than just one step, your X \== Z
and X \== Y tests won't catch it. But as I originally suggested
that's fairly easy to fix by keeping track of all the elements
seen so far.
2) Your solution depends implicitly on your added predicates never
being tried more than once. That is assured for the particular
example I gave because:
(a) Your added predicates come last in the database, and
(b) There are (implicilty) an unbounded number of values that are
greater than some given value. I.e., your solution never says
"no."
What would you do if I changed the example as follows. (It really
shouldn't matter what the R is that is being declared transitive.)
The following makes two modifications:
a) R(X, Y) if floor(X/3) and floor(Y/3) are equal.
E.g., 3, 4, and 5 are all in the same equivalence class.
b) The set of values is finite.
less_than_or_equal(X, Y) :-
integer(X),
0 is floor(X/10), % X is equivalent to Y if
1 is floor((X+1)/3) - floor(X/3), % floor(X/3) = floor(Y/3).
Y is X - 2. less_than_or_equal(X, Y) :-
integer(Y),
0 is floor(Y/10), % X is equivalent to Y if
1 is floor(Y/3) - floor((Y-1)/3), % floor(X/3) = floor(Y/3).
X is Y + 2. less_than_or_equal(0, 1).
less_than_or_equal(X,Y) :-
integer(X),
0 is floor(X/10),
Y is X + 1. less_than_or_equal(X, Y) :-
integer(Y),
0 is floor(Y/10),
X is Y - 1.
------------------------------
Date: Sat 4 Jun 83 23:50:34-PDT
From: PEREIRA@SRI-AI.ARPA
Subject: Prolog Library List Available!
The following describes the Prolog programs available on directory
<PROLOG> at SRI-AI. They are all accessible to an anonymous FTP login.
This file is PROLOG-LIBRARY.LIST in that directory.
The programs have been tested on DEC-10s and DEC-20s with the
Edinburgh Prolog system. They might need minor changes to run under
other Prolog systems, such as C-Prolog.
Copy and enjoy!
Fernando Pereira
======================================================================
* The utilities package from the Department of Artificial Intelligence,
University of Endinburgh. Contributors include Alan Bundy, Lawrence
Byrd and Richard O'Keefe.
util The top level file, which loads all the others
util.hlp A minimal (and outdated) help file
writef.pl Formatted write (writef)
trace.pl Tracing routines
readin.pl Read in a sentence
listro.pl List routines
setrou.pl Set routines
applic.pl Application routines
multil.pl Multi list routines
flagro.pl Flag handling
struct.pl Structure crunching
cmisce.pl Miscellaneous
long.pl Rational arithmatic package
tidy.pl Expression tidy/evaluator
invoca.pl Invocation routines
imisce.pl Miscellaneous (interpreted)
writef.hlp Documentation for the formatted write
* Pretty printer and utilities from Harry Barrow, Fairchild.
pp Pretty printer utils Utilities
* Tutorial programs and text by Ernie Davis and Udi Shapiro, Yale and
Weizmann Institute.
tutori.pl Programs
tutori.lpt Text
* Teach-yourself Prolog program, by William Wong, Rutgers.
To run it, load it into Prolog and then call the predicate 'hi'.
cai.pl
* Prolog cross-reference program from Edinburgh
xref.hlp Documentation (ignore the installation-specific stuff)
xref.pl The cross-referencer (compile it, otherwise it will
run out of space very quickly)
xref.mic MIC command file to create a runnable XREF image
(installation-specific)
xref.tec TEC124 macros to update Prolog sources with public
declarations.
* Richard O'Keefe's Prolog ToolKit.
Richard has started to develop an integrated Prolog toolkit. A nice
feature is a general help facility that allows interactive perusal
of keyword-indexed help files from inside Prolog. I have made some
minor modifications to make the toolkit behave better with TOPS-20
filenames, but there might be other installation dependencies. In
my version, all files mentioned in the code come from directory
<PROLOG>.
toolkit.hlp The basic help file for the ToolKit distribution
toolkit.pl Compiles and sets up the toolkit. It should be loaded
on top of the Edinburgh UTIL package (you can avoid
this if you scan the "imports" comments to find which
UTIL predicates are used, and load just those).
toolkit.exe Created by calling 'save_toolkit' after loading the above.
Due to excessive cleverness in the 'save' evaluable
predicate, saved images are installation-dependent,
so this is irrelevant outside SRI-AI; rebuild it locally
as described above.
helper.pl Prolog help facilities, hacked for TOPS-20.
helper-10.pl The original TOPS-10 version of the same.
helper.hlp Help for help.
pp.pl Program pretty-printer and browser (has a nice
partial match facility for predicate and functor
names). Do not confuse with pp., Harry Barrow's
term pretty-printer
pp.hlp Help for the same.
ixref.pl Interactive cross-referencer (based on XREF above,
but nicer).
ixref-10.pl The original version, with one Edinburgh-specific
file name.
ixref.def Initial knowledge for the cross-referencer.
ixref.hlp Help.
count.pl Counts the number of clauses in Prolog files (for the
"largest Prolog program" award).
count.hlp Help.
vcheck.pl Checks Prolog files for nonanonymous variables occurring
only once in a clause; invaluable!
vcheck.hlp Help
------------------------------
End of PROLOG Digest
********************