PROLOG-REQUEST@SCORE.STANFORD.EDU.UUCP (02/13/87)
PROLOG Digest Friday, 13 Feb 1987 Volume 5 : Issue 8
Today's Topics:
Implementation - Debugging,
Programming - 91 function,
LP Library - Conference Proceedings & Announcement (UPenn)
----------------------------------------------------------------------
Date: Wed, 11 Feb 87 14:28:16 EST
From: Jan Komorowski <jan@harvard.HARVARD.EDU>
Subject: Debugging
The problem should be seen in a broader perspective.
Afterall, discovering typos is a rather minor issue. What is
interesting is the kind of knowledge the programmers seem to have
about non-deterministic languages, and which, at best, is passed as
the "rules of thumb". We can take here a "model-theoretic" approach,
or a theory-extension one, i.e. syntactic, or a mixture of them.
Shapiro's "Algosithmic Diagnosing" is an excellent instance of the
first one. I have taken a syntactic approach and tried to capture
this general rules of thumb in the form of integrity constraints. At
present they include heuristics for recursive, exhaustive,
non-redundant specifications and elements of data flow analysis and
functional dependencies used to verify the hypothesis concerning an
addition of a unit of a program (cf. a clause).
There is a prototype meta-interpreter implementation which
provides more support than the author expected. For example, out of
the six bugs in Shapiro's buggy qsort, five are "never" made. The
system is able to discover them incrementally as the clauses are
incrementally added. Not surpsingly, the sixth one, i.e. putting the
sort key in the "wrong" place, escapes the analysis.
The paper titled "A Declarative Logic Programming Environment"
which describes the work will appear in the Journal of Systems and
Software and is available from the author. A related paper on logic
programming methodology by Jan Maluszynski and me will appear in the
journal Science of Computer Programming and is also available from me.
Copies of these papers can be obtained from:
Jan Komorowski
Aiken Computation Lab.
Harvard University
33 Oxford Street,
Cambridge, MA 02138
USA
Regards,
Jan Komorowski
------------------------------
Date: 8 Feb 87 22:37:35 GMT
From: Bruce T. Smith <ihnp4!inuxc!iuvax!bsmith@ucbvax.Berkeley.EDU>
Subject: Debugging
Typo-caused errors in Prolog programs can be hard to find. The errors fall
into two classes:
(i) in a predicate -- In the head of a clause, this causes the clause
to be part of the definition of the wrong (possibly new) procedure.
In the body, it causes a call to the wrong (and possibly undefined)
procedure.
(ii) in a variable -- A typo can either make a variable name the same or
not the same as another variable in the clause. In either case, the
misspelled variable gets the wrong binding.
Typos in punctuation and non-variable terms are easier to catch. At least I
seldom have any problems with them. Of course, the reader screams at me if
my parentheses or brackets don't match. And, I tend to use longer names for
variables and predicates than for atoms or functors.
Style rules, as in Quintus Prolog, catch lots of these. In particular,
(i) clauses defining a procedure should come together in a file -- A typo
in the head of a clause may violate this rule, either by not matching
the clauses around it or by matching a clause somewhere else.
(ii) the anonymous variable '_' should be used for singleton variables --
A misspelled variable name that makes a non-singleton variable into a
singleton variable violates this rule.
Of course they don't catch everything. (And, yes, if you're annoyed by them,
it is possible to turn them off.)
------------------------------
Date: 12 Feb 87 02:11:24 GMT
From: decvax!mcnc!ece-csc!ncrcae!ncr-sd!milano!varghese@ucbvax.Berkeley.EDU
Subject: 91 function
A "fix" to make it converge to 91:
(defun f91 (x)
(cond ((= x 91) 91)
((> x 111) (f91 (f91 (- x 10))))
((> x 100) (f91 (- x 10)))
(t (f91 (f91 (+ x 11))))))
or, if you don't speak LISP, a Prolog version:
f91(91,91) :- !.
f91(X,Y) :- X > 111, !, Z is X - 10, f91(Z,W), f91(W,Y).
f91(X,Y) :- X > 100, !, Z is X - 10, f91(Z,Y).
f91(X,Y) :- Z is X + 10, f91(Z,W), f91(W,Y).
{The engineer's fix: (defun f91 (x) 91) }
------------------------------
Date: 9 Feb 87 08:56:06 GMT
From: Lars-Henrik Eriksson <mcvax!enea!sicsten!lhe@seismo.css.gov>
Subject: 2nd International Logic Programming Conference?
In article <2645@iuvax.UUCP> bsmith@iuvax.UUCP (Bruce T. Smith) writes:
>Does anyone know how to get the proceedings from the Second International
>Conference (Uppsala, SWEDEN, in July, 1984)? I've seen the 1st (Marseille,
You can order it from:
UPMAIL
Box 520
S-751 20 UPPSALA
SWEDEN
------------------------------
Date: Tue, 10 Feb 87 16:53 EST
From: Tim Finin <Tim@cis.upenn.edu>
Subject: Colloquium
Penn Math/CS Logic Seminar
RIGID E-UNIFICATION AND EQUATIONAL MATINGS
Jean Gallier
(jean@cis.upenn.edu)
16 Feb, 10:30 - 12:00
Math Seminar Room, DRL
Rigid E-Unification is a restricted type of E-unification that comes
up naturally in generalizing the method of matings due to Andrews to
first-order languages with equality. Let E={(s_1 = t_1),...,(s_m =
t_m)} be a finite set of equations, and u = v any equation. Problem:
It is decidable whether there is some substitution theta such that the
set {theta(s_1 = t_1),...,theta(s_m = t_m), ~ theta(u = v)} is
unsatisfiable? Equivalently, denoting by Rewrites{theta(E)} the least
congruence induced by theta(E), treating the equations in theta(E) as
ground equations, does theta(u) Rewrites{theta(E)} theta(v) hold, for
some substitution theta?
Any substitution theta satisfying the above property is an E-unifier
of u and v. However, the equations in E are used in a restricted
fashion. Contrary to E-unification, in which there is no bound on the
number of instances of the equations in E used to show that theta(u)
Rewrites{E} theta(v), in our situation, only the m instances in
theta(E) can be used. For this reason, we call a substitution
satisfying our problem a rigid E-unifier.
We show that rigid E-unification is NP-complete in some nontrivial
subcases and we conjecture that it is decidable in general.
This is joint work with Stan Raatz and Wayne Snyder.
------------------------------
End of PROLOG Digest
********************