RESTIVO@SU-SCORE.ARPA (07/09/85)
From: Chuck Restivo (The Moderator) <PROLOG-REQUEST@SU-SCORE.ARPA>
PROLOG Digest Tuesday, 9 Jul 1985 Volume 3 : Issue 30
Today's Topics:
Implementation - A Standard Syntax,
Announcement - DB System,
LP Library - PARLOG
----------------------------------------------------------------------
Date: Fri, 28-Jun-85 01:08:22 PDT
From: mcvax!ukc!icdoc!cdsm@Seismo.ARPA
Subject: Investigating implementations of cut
Implementations of CUT
As part of the BSI Prolog standardisation process I
am looking at the way in which cut is implemented in different
Prolog systems. The following program illustrates the
differences which have been found. I would be grateful if you
could run the program on your system and send me the answers;
if you have an interpreter and compiler please execute it for
both systems.
---------------------------------------------------------
/* Tests to distinguish various implementations of cut */
/* Chris Moss, Imperial College, June 1985 */
test1 :- do('Testing that cut is implemented). ', t1).
test2 :- do('Test if cut acts within disjunction', t2).
test3 :- do('Test if it cuts prev. choice within disjunction',t3).
test4 :- do('Test if cut acts when passed as metacall', t4).
test5 :- do('Test if & cut acts within metacall', t5 ).
test6 :- do('Test if cut acts through not', t6).
do(Message,Test) :- w(Message), Test.
do(Message,Test) :- w('Does act').
w(X) :- write(X), nl.
t :- w('Does not act').
t1 :- (true;w('Did not cut alternatives correctly'),fail),
!, w('Succeeds going forwards'), fail.
t1 :- w('Failed to cut goal').
t2 :- (!;w('Fails to cut disjoint alternatives')), fail.
t2 :- t.
t3 :- t3a(X),(!,fail;w('Fails to cut disjunction')).
t3 :- t.
t3a(!).
t3a(X) :- w('Did not cut alternatives'), fail.
t4 :- t3a(X), X, w('Ok going forwards'),fail.
t4 :- t.
t5 :- t5a(X), X, fail.
t5 :- t.
t5a((true,!)).
t6 :- not(not(!)), fail.
t6 :- t.
-------------------------------------------------
From initial tests we have the following results:
Implementation Test 1 2 3 4 5 6
DEC-10 Compiler Y Y Y Y Y Y
Waterloo, MU-Prolog Y Y Y Y Y N
DEC-10 int, C-Prolog Y Y Y N N N
POPLOG Y Y Y I I I
micro, Sigma Y N N Y Y N
where Y means did cut, N means did not cut and I means
that it was trapped as an illegal use and failed.
Note that in all cases 2=3 and 4=5; however in some
implementations this may not be the case. If there
are any other discriminating cases not covered above
I would be glad to hear of them.
------------------------------
Date: 05 Jul 85 13:45:05 +1000 (Fri)
From: John Shepherd <munnari!mungunni.oz!JAS@Seismo>
Subject: New Deductive Database System
A System for Very Large Deductive Databases
using a Superimposed Codeword Indexing Scheme
=====
This note is to announce the (near) availability of a
deductive database system suitable for dealing with very
large databases of Prolog rules. The indexing scheme used
by the system is based on the method of two-level
superimposed codewords as described in [1], which allows
partial match retrieval. Superimposed codeword schemes
provide a very efficient method of retrieving records from
large databases in only a small number of disk accesses.
Further, the access method can be tuned so that the ratio
of "false matches" can be reduced by an arbitrary amount
(with a corresponding increase in storage costs). Unlike
many earlier systems, this system supports the storage and
retrieval of completely general Prolog terms, including
functors and variables, and it is even possible to store
Prolog rules in the database.
The system is in the final stages of development under
Berkeley Unix (4.2BSD) and has already been interfaced to
the MU-Prolog system[2,3]; it will be incorporated into
release 3.2db of MU-Prolog which will be available soon
for Unix and VMS. It is being developed as part of the
Machine Intelligence Project at the University of
Melbourne on a Pyramid 90x which was loaned to the project
by Pyramid Technology in Australia. The figures given
below are taken from the Pyramid running version 2.3.1 of
the OSx operating system (in the Berkeley universe) with
one 400 Mb disk.
Preliminary tests, on a database of mail transfer pathways
through Usenet containing one million facts, have been
very encouraging. To store these facts, which have an
average length of 60 bytes, required just over 80Mb, which
means a storage overhead of about 30%. In the present
system, with a one-million record database indexed on
three attributes, the rate of insertion is six records per
CPU second. The rate of insertion could be significantly
increased if the system were run as a single-user batch-
type system without locking controls. Specifying just two
of the fields (each record contains four fields),
retrieved on average just 3 records for a query which had
only one correct answer. The system can achieve a record
retrieval rate of around 1000 records per second for a
query on highly clustered records, to about 50 records per
second for a query on unclustered records, even on this
large database; for smaller databases, even faster rates
are achievable. A query with complete information,
required on average 1.1 retrievals, and required 4 disk
accesses (excluding overheads from the Unix file system).
This system overcomes some of the limitations of the Unix
file system. For example, it overcomes the limit of
twenty open files per process by caching on Unix file
descriptors, thus allowing several database relations to
be accessed simultaneously. The system also provides data
buffering to reduce the number of file opens and data
reads. The processing time of logic programs such as the
"ancestor" relation can be minimised by this feature.
We would be interested in hearing from other groups who
are developing similar systems. For further information
on this system, contact Dr. K. Ramamohanarao (Rao) or John
Shepherd at the following addresses:
HardMail:
Department of Computer Science
University of Melbourne
Parkville, Victoria, 3052
AUSTRALIA
SoftMail:
UUCP: {seismo,ukc,prlb2}!munnari!jas
{decvax,eagle,pesnta}!mulga!jas (SLOW)
ARPA: munnari!jas@seismo.ARPA
CSNET: jas@munnari.oz
("jas" can be substituted by "rao")
Also, Dr. Rao will be attending the Logic Programming
Symposium in Boston, and would be willing to discuss the
system there.
[1] R.Sacks-Davis and K.Ramamohanarao "A Two Level
Superimposed Coding Scheme for Partial Match
Retrieval", Information Systems, v.8, n.4, 1983
[2] By way of comparison, this system eliminates a number
of restrictions which were associated with the
deductive database system provided with release 3.1
of MU-Prolog. That system implemented the database
manager as a separate process from the Prolog
interpreter, communicating via Unix pipes. The
present system is designed as a library package which
is compiled into the host system; it could be
incorporated fairly easily into most Prolog
interpreters, or, in fact, into any systems that
wished to perform partial match retrieval. The use of
pipes in the old MU-Prolog system placed severe
limitations (because of Unix file descriptor
limitations) on the number of transactions (queries)
which could be active concurrently; the new system
has eliminated this restriction. Finally, this system
lifts the restriction that only ground facts could be
stored in the database, by allowing the storage of
arbitrary Prolog terms (including rules).
[3] L.Naish "MU-Prolog 3.2db Reference Manual", Technical
Report, Department of Computer Science, University of
Melbourne, 1985.
------------------------------
Date: Thu, 27-Jun-85 21:01:28 PDT
From: mcvax!ukc!icdoc!sg@Seismo.ARPA
Subject: PARLOG system for C-Prolog
Since my recent announcement "PARLOG system available",
in which I offered to mail copies of the PARLOG system
to anyone on request, I have been inundated (!) with
enquiries. Owing to the high cost of transatlantic net
mail and its less-than-100% reliability, I have been
advised to post it instead. So here it is.
The version here runs on top of C-Prolog 1.4 - 1.5. Some
changes may be required to run on compatible Prolog systems.
There are 14 files altogether:
parlog hamming.par
parcomp primes.par
parrts adpairs.par
parstats print.par
orrts prolog.par
editor
par
npar
nparrts
Those with extension ".par" are example PARLOG
programs, the others are Prolog programs
comprising the PARLOG system.
Before use, the article should be run through a
shell to separate out the files: "sh <article".
You will need the manual "How to use PARLOG". To
get it, please send me a postal address, and request
any PARLOG papers you require.
[ PARLOG is available from the SCORE: <Prolog> library as
PAROLOG.PL. You'll need to unpack the file. -ed ]
------------------------------
End of PROLOG Digest
********************