PROLOG-REQUEST@SU-SCORE.ARPA (Chuck Restivo, The Moderator) (05/27/86)
PROLOG Digest Wednesday, 28 May 1986 Volume 4 : Issue 15
Today's Topics:
Announcement - Call for Papers,
Queries - Translation & CP & Circularity,
Implementations - Standard Behavior & Benchmarking KBES Tools,
Humor - Programmers
----------------------------------------------------------------------
Date: Fri, 23 May 86 11:07:24 pdt
From: Moshe Vardi <vardi@diablo>
Subject: Call for Papers
CALL FOR PAPERS
Sixth ACM SIGACT-SIGMOD-SIGART Symposium on
PRINCIPLES OF DATABASE SYSTEMS
San Diego, California, March 23-25, 1987
The conference will cover new developments in both the
theoretical and practical aspects of database and
knowledge-base systems. Papers are solicited which describe
original and novel research about the theory, design,
specification, or implementation of database and knowledge-
base systems.
Some suggested, although not exclusive, topics of interest
are: architecture, concurrency control, database and expert
systems, database machines, data models, data structures for
physical implementation, deductive databases, dependency
theory, distributed systems, incomplete information, user
interfaces, knowledge and data management, performance
evaluation, physical and logical design, query languages,
recursive rules, spatial and temporal data, statistical
databases, and transaction management.
You are invited to submit ten copies of a detailed abstract
(not a complete paper) to the program chairman:
Moshe Y. Vardi
IBM Research K55/801
650 Harry Rd.
San Jose, CA 95120-6099, USA
(408) 927-1784
vardi@ibm.com
Submissions will be evaluated on the basis of significance,
originality, and overall quality. Each abstract should 1)
contain enough information to enable the program committee
to identify the main contribution of the work; 2) explain
the importance of the work - its novelty and its practical
or theoretical relevance to database and knowledge-base sys-
tems; and 3) include comparisons with and references to
relevant literature. Abstracts should be no longer than ten
double-spaced pages. Deviations from these guidelines may
affect the program committee's evaluation of the paper.
The program committee consists of Umesh Dayal, Tomasz Imiel-
inski, Paris Kanellakis, Hank Korth, Per-Ake Larson,
Yehoshua Sagiv, Kari-Jouko Raiha, Moshe Vardi, and Mihalis
Yannakakis.
The deadline for submission of abstracts is October 10,
1986. Authors will be notified of acceptance or rejection
by December 8, 1986 (authors who supply an electronic
address might be notified earlier). The accepted papers,
typed on special forms, will be due at the above address by
January 9, 1987. All authors of accepted papers will be
expected to sign copyright release forms. Proceedings will
be distributed at the conference, and will be subsequently
available for purchase through ACM.
General Chairman: Local Arrangements:
Ashok K. Chandra Victor Vianu
IBM Research Center Dept. of Computer Science
P.O.Box 218 Univ. of California
Yorktown Heights, NY 10598 La Jolla, CA 92093
(914) 945-1752 (619) 452-6227
ashok%yktvmx@ibm.com vianu@sdcsvax.ucsd.edu
------------------------------
Date: 10 Apr 86 15:16:48 GMT
From: Andy Cheese abc@ucbvax.berkeley.edu
Subject: translation wanted
Does anybody out there have an english translation of ICOT
technical report TR-054, I can't even make out the title.
-- Andy Cheese
------------------------------
Date: 10 Apr 86 15:26:21 GMT
From: Andy Cheese abc@ucbvax.berkeley.edu
Subject: Concurrent Prolog
ICOT report tr-092 states that a Concurrent Prolog
compiler is available which runs on top of Prolog,
does anybody have such a compiler ?
-- Andy Cheese
------------------------------
Date: 11 May 86 07:55:18 GMT
From: David Sherman <dave@ucbvax.berkeley.edu>
Subject: Help - how do I avoid circularity here?
I'm designing a large Prolog program for corporate
tax planning under Canadian income tax law. I want
to include the following definitions:
tptype(Taxpayer, corporation) :- tptype(Taxpayer,
ccpc).
Let's call this a "type 1" definition. ccpc stands for
Canadian-controlled private corporation, a term used in
our income tax system. The purpose of this definition,
and dozens like it, is to say "if I'm told as part of
the facts entered by the user that we have a CCPC, then
of course it's a corporation". Of course, if the facts
contain the statement "tptype(xyzcorp, ccpc).", then
any rules which depend on xyzcorp being a corporation,
a private corporation, a Canadian corporation
or a CCPC should all be satisfied.
Now I have another set of rules. Let's call them "type
2". Type 2 rules let Prolog figure out, from the various
facts given, WHETHER a corporation is, for example, a
CCPC. A type 2 rule might be:
tptype(Taxpayer, ccpc) :-
tptype(Taxpayer, corporation),
resident(Taxpayer, canada),
[etc.... various other things which need to be tested,
for the corporation to be both Canadian-controlled and
private].
So if the person entering the facts has entered facts
sufficient to deduce that a corporation is a CCPC, without
having explicitly said so, any rules which depend on a
corporation being a CCPC can still be satisfied.
Now comes the problem. When I have both type 1 and
type 2 rules in place, I get circularity. Putting in a
cut doesn't help if the rules are never satisfied (when
the rule is tested against a taxpayer who is an individual,
for example). (I can't put a cut right after the ":-",
because there may be lots of different facts which would
cause tptype(Taxpayer, corporation) to be true, and I
want to test them all. I just don't want one of them to
come back and ask tptype(Taxpayer, corporation) again.)
Now, I've come up with a partial solution. I can say:
tptype(Taxpayer, corporation) :-
clause(tptype(Taxpayer, ccpc), true).
which stops the circularity. However, then I lose the
deductive ability, which means that for a chain of
reasoning I have to test each case individually with
"clause". (For example, CCPC implies private corporation a
And private corporation implies corporation. But if I'm
testing for the facts with "clause", I have to have three
rules: corporation if privatecorporation; privatecorporation
if ccpc; and corporation if ccpc.)
Is there any other solution which will stop the circularity?
Is there a way I can tell Prolog "if you've been here before
with these facts, you're in a loop, so fail", without saying,
as the cut does, that it should then fail for all of the
various definitions of the predicate?
Thanks in advance for any suggestions. I'm using C-Prolog
1.2a, if it matters.
-- David Sherman
------------------------------
Date: 15 May 86 14:56:37 GMT
From: Chris Moss <cdsm@ucbvax.berkeley.edu>
Subject: Help - how do I avoid circularity here?
In article <1211@lsuc.UUCP> dave@lsuc.UUCP (David Sherman) writes:
>I'm designing a large Prolog program for corporate tax planning
>under Canadian income tax law. I want to include the following
>definitions:
>
>tptype(Taxpayer, corporation) :- tptype(Taxpayer, ccpc).
>
>Let's call this a "type 1" definition. ... A type
>2 rule might be:
>
>tptype(Taxpayer, ccpc) :-
> tptype(Taxpayer, corporation),
>Now comes the problem. When I have both type 1 and type 2
>rules in place, I get circularity.
Well known problem. Structural solution as follows: split
your predicate into two parts, one of rules, the other
facts which do not have any recursive calls. Add a
reference from first to second. By this time you will
rarely if ever need directly recursive calls.
e.g.
tptype(Taxpayer, corporation) :- tptypefact(Taxpayer, ccpc).
tptype(Taxpayer, ccpc) :- tptypefact(Taxpayer, corporation).
tptype(Taxpayer, Type) :- tptypefact(Taxpayer, Type).
-- Chris Moss
------------------------------
Date: 9 May 86 18:44:00 GMT
From: gooley@ucbvax.berkeley.edu
Subject: Standard behavior?
Consider the following trivial predicate:
a([]).
a(_).
Given the query :-a([]). , C-Prolog finds one match and
UNSW Prolog finds two. Which is standard behavior? How
do other implementations behave?
-- Mark Gooley
------------------------------
Date: 12 May 86 12:46:30 GMT
From: Craig D. Singer <cds@ucbvax.berkeley.edu>
Subject: Standard behavior?
In article <6500005@uicsl> gooley@uicsl.UUCP writes:
>
>Consider the following trivial predicate:
>
>a([]).
>a(_).
>
>Given the query :-a([]). , C-Prolog finds one match and
>UNSW Prolog finds two.Which is standard behavior? How
>do other implementations behave?
I do not have the authority to say which is "standard"
behavior, if by that you mean which is found more commonly
in implementations. However, any book on "vanilla" Prolog
will tell you that "_" matches to anything, including a null
list, so I would indeed be annoyed by C-Prolog if it did
not find two matches. Anybody disagree?
-- Craig D. Singer
------------------------------
Date: 12 May 86 20:57:35 GMT
From: Andrews@ucbvax.berkeley.edu
Subject: Standard behavior?
In article <6500005@uicsl> gooley@uicsl.UUCP writes:
>Consider the following trivial predicate:
>a([]).
>a(_).
>Given the query :-a([]). , C-Prolog finds one match and UNSW
>Prolog finds two. Which is standard behavior? How do other
>implementations behave?
It depends what you mean by "one match". I should think all
Prolog systems would just tell you that the query succeeds,
since there are no free variables to get bindings for in the
query.
The standard reading of the predicate in FOL with identity
would be
a(X) <- X = [] \/ X = X.
...which, given the standard computation algorithm, should
probably give two responses to the query
:-a(X).
... namely, X=[] and X=X.
--Jamie.
------------------------------
Date: 12 May 86 12:56:24 GMT
From: Craig D. Singer
In article <7233@duke.UUCP> cds@duke.UUCP (Craig D. Singer)
writes:
>In article <6500005@uicsl> gooley@uicsl.UUCP writes:
>>
>>Consider the following trivial predicate:
>>
>>a([]).
>>a(_).
>>
>>Given the query :-a([]). , C-Prolog finds one match and UNSW
Prolog finds two.
>>Which is standard behavior? How do other implementations
>>behave?
>
>I do not have the authority to say which is "standard"
behavior, if by that you mean which is found more commonly in
implementations. However, any book on "vanilla" Prolog will
tell you that "_" matches to anything, including a null list,
so I would indeed be annoyed by C-Prolog if it did not find
two matches. Anybody disagree?
Well, after I posted the above response I went ahead and
checked out the version of C-Prolog which comes with 4.2/4.3
BSD and it DOES find two matches. The way to note this is to
expand the predicate as follows:
a([],2).
a(_,3).
Then ask the query a([],X). The response will be:
X = 2
after which you can type a semicolon and hit return, which
produces:
X = 3
yes
So C-Prolog (and, I would guess, any prolog) finds both
matches.
-- Craig D. Singer
------------------------------
Date: 13 May 86 13:52:01 GMT
From: James H. Cox <jhc@ucbvax.berkeley.edu>
Subject: Standard behavior?
In article <6500005@uicsl> gooley@uicsl.UUCP writes:
>
>Consider the following trivial predicate:
>
>a([]).
>a(_).
>
>Given the query :-a([]). , C-Prolog finds one match and
>UNSW Prolog finds two. Which is standard behavior? How
>do other implementations behave?
>
Hmmmm, not exactly.
Depends on what you mean by finding a match and how you
apply the query. If you type
a([]).
to the C-Prolog interpreter it comes back and says 'yes',
i.e. the predicate can be satisfied. However, when you
present such a query to the C-Prolog top level interpreter
it does not give you any opportunity to backtrack, you only
get this opportunity if there are any variables given in
your query, and you make use of this opportunity by typing
';' which invites the interpreter to backtrack.
Below follows two dialogs with C-Prolog that indicate there
are indeed two solutions to the query you mentioned. (Note
that '?-' is the interpreter's prompt for you to type a
query, and that ^ appears under user input)
?- a(X). -- initial query
^^^^^
X = [] ; -- first solution, ; typed so invoke
^ backtracking.
X = _0 ; -- second solution..
^
no -- prolog says no more solutions.
?- a([]), write(a), fail.-- need to phrase it like this to
^^^^^^^^^^^^^^^^^^^^^^ invoke backtracking since the
interpreter will not give us the
opportunity..
aa -- indicates 'write(a)' called twice.
no -- no more solutions.
?-
------------------------------
Date: 13 May 86 16:39:01 GMT
From: Randy Goebel <rggoebel@ucbvax.berkeley.edu>
Subject: Standard behavior?
> >Consider the following trivial predicate:
> >a([]).
> >a(_).
> >
> >Given the query :-a([]). , C-Prolog finds one match
> >and UNSW Prolog finds two.
> >Which is standard behavior? How do other implementations
> >behave?
_____________
> I do not have the authority to say which is "standard"
>behavior, if by that you mean which is found more commonly in
>implementations. However, any book on "vanilla" Prolog will
>tell you that "_" matches to anything, including a null list,
>so I would indeed be annoyed by C-Prolog if it did not find
>two matches. Anybody disagree?
-------------
Hmmm. The reason for logic programming's existence is
to dispense with guesses about what behaviour should be.
The formulae assert that the individual constant named
`[]' and everthing else (i.e., `_') is in the class named
by the predicate `a'. If you believe that the anonymous
variable is a universially quantified variable, then there
are two resolution proofs of the query a([]).
Implementors' treatment of `_' can produce non-standard
behaviour; non-standard means not consistent with the
logical interpretation.
------------------------------
Date: 13 May 86 23:49:05 GMT
From: bts@ucbvax.berkeley.edu
Subject: Standard behavior?
C-Prolog finds one solution at a time, UNSW looks
for all solutions to a goal. C-Prolog (and many
others) only give you a chance to ask for more
solutions at the top level if there are free non
-anonymous variables in your query. An easy way
to show that C-Prolog was finding both solutions
in the original program is
?- a([]), write(hello), nl, fail.
Count the number of 'hello's.
-- Bruce T. Smith
------------------------------
Date: 14 May 86 12:47:18 GMT
From: Tom Frauenhofer <tfra@ucbvax.berkeley.edu>
Subject: Standard behavior?
>>In article <7233@duke.UUCP> cds@duke.UUCP (Craig D.
>>Singer) writes: >>In article <6500005@uicsl>
>>gooley@uicsl.UUCP writes:
>>>
>>>Consider the following trivial predicate:
>>>
>>>a([]).
>>>a(_).
>>>
>>>Given the query :-a([]). , C-Prolog finds one match
>>>and UNSW Prolog finds two. Which is standard behavior?
>>>How do other implementations behave?
>>
>>I do not have the authority to say which is "standard"
>>behavior, if by that you mean which is found more commonly
>>in implementations. However, any book on "vanilla" Prolog
>>will tell you that "_" matches to anything, including a
>>null list, so I would indeed be annoyed by C-Prolog if it
>>did not find two matches. Anybody disagree?
>Well, after I posted the above response I went ahead and
checked out the version of C-Prolog which comes with 4.2/4.3
BSD and it DOES find two matches. The way to note this is to
expand the predicate as follows:
>a([],2).
>a(_,3).
>Then ask the query a([],X). The response will be:
>X = 2
>after which you can type a semicolon and hit return,
>which produces:
>X = 3
>So C-Prolog (and, I would guess, any prolog) finds both
>matches.
For whoever is collecting /interested in this information:
I tried both of the above scenarios in Turbo Prolog and the
PD version of A.D.A Prolog. The results:
Turbo Prolog:
First scenario: 1 match
Second scenario: 2 matches
A.D.A PDProlog:
First scenario: 2 matches
Second scenario: 2 matches
-- Tom Frauenhofer
------------------------------
Date: 14 May 86 16:19:42 GMT
From: Nabiel Elshiewy <nabiel@ucbvax.berkeley.edu>
Subject: Standard behavior?
In article <6500005@uicsl> Mark Gooley (gooley@uicsl.UUCP)
writes:
>
>Consider the following trivial predicate:
>
>a([]).
>a(_).
>
>Given the query :-a([]). , C-Prolog finds one match and
>UNSW Prolog finds two. Which is standard behavior? How do
>other implementations behave?
Intuitively C-Prolog's one match is the expected standard
behaviour. The two assertions describe a choice; it is either
an empty list or something else which differs from an empty
list.
Aside: Also both Quintus Prolog and Mu-Prolog find one match.
------------------------------
Date: 15 May 86 15:54:00 GMT
From: Gooley@ucbvax.berkeley.edu
Subject: Standard behavior?
It seems that C-Prolog v1.3 (which I use) finds one
match, but v1.5 finds two. I suppose it was a bug
that's now been fixed. Thanks to all who replied.
-- Mark Gooley
------------------------------
Date: 24 May 86 05:41:35 GMT
From: Ludemann@ucbvax.berkeley.edu
Subject: Standard behavior?
In article <980@watdragon.UUCP> rggoebel@watdragon.UUCP
(Randy Goebel LPAIG) writes:
>> >Consider the following trivial predicate:
>> >a([]).
>> >a(_).
>> >
>> >Given the query :-a([]). , C-Prolog finds one match
>> >and UNSW Prolog finds two.
>> >Which is standard behavior? How do other
>> >implementations behave?
>Hmmm. The reason for logic programming's existence is
>to dispense with guesses about what behaviour should be.
>The formulae assert that the individual constant named
>`[]' and everthing else (i.e., `_') is in the class
>named by the predicate `a'. If you believe that the
>anonymous variable is a universially quantified variable,
>then there are two resolution proofs of the query a([]).
>
>Implementors' treatment of `_' can produce non-standard
>behaviour; non-standard means not consistent with the
>logical interpretation.
I have to disagree, Randy. The query merely asks whether
or not there is a proof of "a([])". Not how many there
are. Although by Prolog's execution order, there are only
two ways of generating the answer, there are of course an
_infinite_ number of logical proofs. There is no point
in trying to list them all :-).
Furthermore, if the goal "a([])" is within a predicate (for
example, q(X) :- a([]), b(X).), then a smart implementation
would notice that if "b(X)" fails, there is no need to re
-try "a([])". Isn't that what all the work on intelligent
backtracking has been about?
Now, a general philosophical point. Prolog is certainly
_not_ logic programming, although it is a large step in
that direction. A true logic programming language would
not have nor need "cut" ("!"), "var", "nonvar", etc.
("=..", "name", "is" and even "call" are legitimate because
they can be considered as an infinite number of rules.
"var" and "nonvar" can't be described that way). One of
the advantages of logic programming is that it allows us
to consider computations without knowing (precisely) the
underlying execution strategy. Indeed, for "pure" programs,
the execution strategy could change, yet the programs would
still execute correctly. Let us strive to produce true
logic programming languages which get over the minor
failings of Prolog.
------------------------------
Date: 22 May 86 12:42:30 GMT
From: Chris Moss <cdsm@ucbvax.berkeley.edu>
Subject: Standard behavior?
In article <980@watdragon.UUCP> rggoebel@watdragon.UUCP writes:
>> >Consider the following trivial predicate:
>> >a([]).
>> >a(_).
>> >
>> >Given the query :-a([]). , C-Prolog finds one match and
>> >UNSW Prolog finds two.
>> >Which is standard behavior? How do other implementations
>> >behave?
>> I do not have the authority to say which is "standard"
>> behavior, if by that you mean which is found more commonly
>> in implementations.
Most of this discussion is not about how Prolog behaves, but
how the top level query evaluator behaves. As a member of the
Prolog standards committee but NOT speaking officially I should
say that most environmental questions are being RULED OUT by
the standards committee. Whether it will specify exactly what
is the answer to a top level query is not yet sorted out.
[To repeat what has been said already, the confusion is just
about what response CProlog makes to a top-level query - if
the query contains no variables it just answers "yes" and
doesn't give the opportunity to look for another solution
(all ways of solving it are equivalent so why bother).
UNSW gives ALL solutions by default, even in this rather
unnecessary case. If it was part of a larger problem,
every Prolog I know would backtrack and find both, even
though it was strictly equivalent]
-- Chris Moss
------------------------------
Date: 28 May 86 16:01:39 GMT
From: Marco Valtorta <mgv@ucbvax.berkeley.edu>
Subject: Standard behavior?
I find UNSW's behavior to be intuitively more
correct, since it seems that the empty list "[]"
should match the anonymous variable "_". This
wouldn't be the first time that I find UNSW to
act in a way that is closer to my "mental model"
of Prolog. Maybe someone involved in a
standardization effort could contribute something
on this topic?
------------------------------
Date: 26 May 86 03:07:18 GMT
From: rggoebel@ucbvax.berkeley.edu
Subject: Standard behavior?
> In article <980@watdragon.UUCP> rggoebel@watdragon
> writes:
>Consider the following trivial predicate:
>a([]).
>a(_).
>Given the query :-a([]). , C-Prolog finds one
>match and UNSW Prolog finds two. Which is
standard behavior? How do other implementations
behave?
I did not! My response to whoever wrote that question
was that if _ is a universally quantified variable,
then the logic defines the correct answer; NOT the
implementation. Isn't that what logic programming is
for? 8-).
-- Randy Goebel
------------------------------
Date: 26 May 86 03:21:44 GMT
From: rggoebel@ucbvax.berkeley.edu
Subject: Standard behavior?
Now, a general philosophical point. Prolog is certainly
_not_ logic programming, although it is a large step in
that direction. A true logic programming language would
not have nor need "cut" ("!"), "var", "nonvar", etc.
("=..", "name", "is" and even "call" are legitimate
because they can be considered as an infinite number of
rules. "var" and "nonvar" can't be described that way).
One of the advantages of logic programming is that it
allows us to consider computations without knowing
(precisely) the underlying execution strategy. Indeed,
for "pure" programs, the execution strategy could change,
yet the programs would still execute correctly. Let us
strive to produce true logic programming languages which
get over the minor failings of Prolog.
Many claim that "logic programming" is an oxymoron. The
logic of pure Prolog is well defined...that's all I said.
I don't believe that cut, var, and nonvar cannot be
described logically, just because they aren't in Prolog
implementations.
------------------------------
Date: 26 May 86 03:16:30 GMT
From: rggoebel@ucbvax.berkeley.edu
Subject: Standard behavior?
>Consider the following trivial predicate:
>a([]).
>a(_).
>Given the query :-a([]). , C-Prolog finds one match
>and UNSW Prolog finds two.
>Which is standard behavior? How do other implementa
>-tions behave?
>Hmmm. The reason for logic programming's existence is
>to dispense with guesses about what behaviour should be.
>The formulae assert that the individual constant named
>`[]' and everthing else (i.e., `_') is in the class named
>by the predicate `a'. If you believe that the anonymous
>variable is a universially quantified variable, then
>there are two resolution proofs of the query a([]).
>Implementors' treatment of `_' can produce non-standard
>behaviour; non-standard means not consistent with the
>logical interpretation.
>I have to disagree, Randy. The query merely asks whether
>or not there is a proof of "a([])". Not how many there
>are.
There is nothing in my reply that says anything about what
an implementation should do with such proofs (count them,
print them, ignore them, etc.). All it says is that there
are two proofs. If you ask for all proofs, then there
had better be two. 8-).
------------------------------
Date: 29 Apr 1986 18:51-EDT
From: VERACSD@USC-ISI.ARPA
Subject: Benchmarking KBES-Toools
I have come across some recent benchmarks from NASA (U.S.
Gov't MEMORANDUM from the FM7/AI Section, April 3, 1986)
which compared various KBES tools' (ART, OP, KEE & CLIPS)
times for solving the MONKEY-AND-BANANA problem. (This toy
prob- lem is explained in detail along with OPS source in
Brownston et. al.'s "Programming Expert Systems in OPS5".)
Although the benchmarks include backward-chaining solutions
to the problem in both KEE and ART (along with forward
-chaining counterparts), there is no PROLOG implementation in
the comparison. I am very interested in a PROLOG comparison,
and am in the process of implementing one.
Unfortunately, I am not (yet) a competent PROLOG programmer
and am currently learning my way around PROLOG on a DEC-20.
Consequently, any advice/suggestions regarding implementing
this benchmark and timing it effectively would be useful and
appreciated. (By the way, the time to beat is 1.2 secs. for
a forward-chaing implementation using ART on a 3640 with 4MB
main-memory.)
I would be glad to share the results with anyone who offers
assistance. (Or for that matter with whomever is interested.)
------------------------------
Date: 9 May 86 01:14:23 GMT
From: mnl@ucbvax.berkeley.edu
Subject: Prolog programmers
Prolog programmers must be humorless people. After all,
they use :- instead of :-) or :-(
-- Mark Nelson
"This function is occasionally useful as the arguement to
a function which requires a function as an arguement."
-- Guy Steele
------------------------------
End of PROLOG Digest
********************