PROLOG-REQUEST@SUSHI.STANFORD.EDU (Chuck Restivo, The Moderator) (11/25/87)
PROLOG Digest Thursday, 26 Nov 1987 Volume 5 : Issue 93
Today's Topics:
Implementation - Constraint LP & Algorithmic Debugging,
& Transitive Closure
----------------------------------------------------------------------
Date: 24 Nov 87 17:25:44 GMT
From: PT.CS.CMU.EDU!A.GP.CS.CMU.EDU!spiro@cs.rochester.edu (Spiro
Michaylov)
Subject: Constraint Logic Programming info sought
As one of the four implementors of the CLP(R) system developed at Monash
University in 1986, I'd like to provide some pointers for getting information
on CLP.
The system that we developed in 1986 was an interpreter, and our current
research is largely on compilation issues -- although no compiler is as yet
available.
The source code for the interpreter is being licensed by Monash University,
and further information on obtaining it can be requested from:
ACSNET: clp@moncsbruce.oz
ARPANET,CSNET: clp@moncsbruce.oz.au
UUCP: seismo!munnari!moncsbruce.oz!clp
If all else fails: munnari!moncsbruce!clp@uunet.UU.NET .
CLP(R) Distribution
Department of Computer Science
Monash University
Clayton
Victoria 3168
It is NOT in the public domain, and to my knowledge no other implementation
exists.
The list of implementors with addresses is given below. All of us would be
more than happy to answer questions about the CLP scheme, the CLP(R) system,
etc. Additionally, I would be glad to send copies of any or all of the
relevant publications to anybody who is interested.
Joxan Jaffar
H1-D46,
IBM Thomas J. Watson Research Center,
PO Box 704,
Yorktown Heights, NY 10598
( joxan@ibm.com )
Spiro Michaylov
Department of Computer Science,
Carnegie-Mellon University,
Pittsburgh, PA 15213
( spiro@a.gp.cs.cmu.edu )
Peter Stuckey and Roland Yap
Department of Computer Science,
Monash University,
Clayton, 3168
Victoria,
AUSTRALIA
( munnari!moncsbruce!pjs@uunet.UU.NET )
( munnari!moncsbruce!roland@uunet.UU.NET )
Further information can be found in the following papers:
1. J. Jaffar and J-L. Lassez, "Constraint Logic
Programming", Proc. 14th ACM-POPL, Munich, January
1987.
2. J. Jaffar and S. Michaylov, "Methodology and
Implementation of a CLP System", Proc. 4th ICLP,
Melbourne, May 1987.
3. N.C. Heintze, S. Michaylov and P.J. Stuckey, "CLP(R)
and Some Electrical Engineering Problems", Proc. 4th
ICLP, Melbourne, May 1987.
4. C. Lassez, K. McAloon and R. Yap, "Constraint Logic
Programming and Option Trading", IEEE Expert, Fall
Issue 1987.
Disclaimer:
While I am continuing to do research in this area, I no longer
have any affiliation with Monash University. The licensing of the
CLP(R) system is a non-commercial venture in which I have
no involment beyond giving people pointers.
------------------------------
Date: Tue, 24 Nov 87 16:24:47 PST
From: quintus!ok@Sun.COM (Richard A. O'Keefe)
Subject: Reply to Dongwook Shin
Dongwook Shin presents the program
g(X, Y) :- even(X), Y is X//2.
g(X, X).
To paraphrase him, he says that "the user may take the second clause as
being correct, because he may think that it is executed only when the
first clause fails. That is, he thinks the second clause is equivalent to
g(X, X) :- \+ even(X).
However, we might not blame him, as the one to be blamed is the non-fair
search mechanism in Prolog, and he is only a victim of this mechanism."
No, this hypothetical user is not a victim of any mechanism. He is
simply WRONG. If Dongwook Shin will refer back in the Digest to the
issue where I discussed various kinds of problems, he will find that I
called this "backwards incorrectness". [Please suggest a better name.]
If the programmer's intention was to realise the relation
g(X, Y) iff X and Y are integers and
X is even and 2Y = X or
X is odd and Y = X
then the program as written is just plain WRONG, whether you are using
forwards chaining, backwards chaining, top-down evaluation, bottom-up
evaluation, SLD, Earley Deduction, or are tossing yarrow stalks.
Dongwook Shin's point was that there were two mistakes. The other one is
even(X) :- X mod 3 =:= 0.
rather than the intended
even(X) :- X mod 2 =:= 0.
and he would like the debugger to help find this mistake, rather than
focussing on the second clause of g/2. But he should note that
correcting even/1 does NOT render the whole program correct! The
"corrected" program is
g(X, Y) :- X mod 2 =:= 0, Y is X // 2.
g(X, X).
THAT program is incorrect. Even with the "sequential" strategy that
Dongwook Shin sneers at, the second clause WILL be used, and it WILL
give the wrong answer. Surely we want a debugging tool that will help
us notice this blunder rather than one which will look the other way and
pretend that a mistake is not a mistake?
Having once again demonstrated that I can write more exposition
on a smaller subject than anyone else :-), I now return you to
your regular netnews. [Chris Torek]
------------------------------
Date: Wed, 25 Nov 87 12:55:05 EST
From: munnari!mulga.oz.au!lee@uunet.UU.NET (Lee Naish)
Subject: Algorithmic debugging
> Will Lee Naish also attack this policy with his electronic
> butcher's knife?
(I wasnt going to, but since you insist...:-)
In the program you gave g(X,X) is wrong (with respect to the user's
intended interpretation), whether the user's brain is contaminated with
Prolog's sequentiality, LSD, television or nothing at all. A
declarative debugger should tell you this.
The original program you gave had two bugs. The declarative debugging
work that I know of only attempts to look for one bug at a time. This
can greatly reduce the search space of the debugger (if it is written in
the right way), so that if the user gives inconsistent answers the
debugger fails instead of searching for other possible bugs.
After fixing one bug, you can go on to fix the others.
In your example, you fix one bug and say the other bug does not show up
after that. This is wrong - you need to consider all answers, not just
the first one.
There are several ways heuristic knowledge about common kinds of bugs
can be used. For example, discovering exactly what is wrong with an
incorrect clause (eg, missing a test), guiding the search of the
debugger (eg, trying clauses in reverse order) or just static analysis
(eg, detecting clauses which subsume other clauses). These could all be
helpful in the example you gave, without denying not g(2,2) => not all X
g(X,X).
We are currently doing some work on integrating several of the debugging
tools we (and others) have developed, including type checkers (we have
five so far!), other static analysers and "dynamic" tools such as
declarative debuggers, spy points, etc.
-- Lee
------------------------------
Date: Tue, 24 Nov 87 11:21:16 GMT
From: Fernando Pereira <pereira%cam.sri.com@drakes.ai.sri.com>
Subject: Old Chestnuts, Transitive Closure
The problems discussed by Richard O'Keefe and previous contributors have
been extensively studied by researchers in the area of deductive databases.
It is worth starting with
@ARTICLE{ullman,
AUTHOR = {Jeffrey D. Ullman},
TITLE = {Implementation of Logical Query Languages for Databases},
JOURNAL = {{ACM} Transactions on Database Systems},
YEAR = {1985},
VOLUME = {10},
NUMBER = {3},
PAGES = {289-321}
}
and then look at more recent papers on the same subject by Bancillon,
Zaniolo, Ullman and others. Basically, these authors consider specialized
efficient (eg. polynomial) proof procedures whose applicability to
solving a particular query can be decided by program analysis algorithms.
-- Fernando Pereira
------------------------------
End of PROLOG Digest
********************