PROLOG-REQUEST@SU-SCORE.ARPA (Chuck Restivo, The Moderator) (09/24/86)
PROLOG Digest Wednesday, 24 Sep 1986 Volume 4 : Issue 53
Today's Topics:
Implementation - "For All" & Cut,
----------------------------------------------------------------------
Date: 23 Sep 86 12:58:57 GMT
From: Douglas Baldwin <baldwin@rochester.arpa>
Subject: "For All" in Prolog
Thanks to everyone who answered my question a few
weeks ago about implementing "for all" in Prolog.
The general consensus was that
forall X in S, Body
can be re-expressed as
"there is no X in S such that Body doesn't hold"
which can be written in Prolog as
not( In_S(X), not Body(X,...) )
(This is a mix of syntaxes from several Prologs, my original
description of the problem, etc., but the idea is clear I
hope.) This is clearly what I need.
Special thanks to Lee Naish, David Morley, Heiner Marxen
and Steve Jones for their discussions of this solution.
------------------------------
Date: Mon, 22 Sep 86 15:20:06 MET DST
From: Norbert%Germany.csnet@CSNET-RELAY.ARPA
Subject: Experiments with Cut
At the Third International Conference on Logic Programming, Chris
Moss compared several Prolog implementations with regard to their
interpretations of cuts in control structures. The results were
quite impressive: eleven different interpretations for 24
implementations!
But I suppose, he would have found even more differences, if he
had compared the effect of combining more than two control
structures. I experimented a bit with our C-Prolog 1.5
interpreter and got some results, that increased my doubts about
Prolog being a logic language quite a lot.
Try the following:
---------------------- cut here for prolog source ---------------
all_tests :-
nl, test1(A), write(A), fail;
nl, test2(A), write(A), fail;
nl, test3(A), write(A), fail;
nl, test4(A), write(A), fail;
nl, test5(A), write(A), fail;
nl, test6(A), write(A), fail;
nl, test7(A), write(A), fail;
nl, test8(A), write(A), fail;
true.
test1(A) :- Goal = (A = 1, !), Goal.
test1(A) :- A = 2.
% Cut does not act through a metacall, it does not cut the choice
% point built by test1. Solutions for A are 1 and 2.
% Now add an alternative:
test2(A) :- Goal = (A = 1, !), (Goal; A = 2).
test2(A) :- A = 3.
% You get less for more - the only solution is 1. The same holds,
% if the call to cut is constructed in the disjunction:
test3(A) :- Goal = (A = 1, !), Goal; A = 2.
test3(A) :- A = 3.
% The C-Prolog manual states that a metacall X is "exactly the
% same as call(X)":
test4(A) :- Goal = (A = 1, !), call(Goal); A = 2.
test4(A) :- A = 3.
% Solutions are 1, 2, and 3.
% Let's try some more: we use the body of test1, but construct
% it at runtime:
test5(A) :- Metacall = (Body = (Goal = (A = 1, !), Goal), Body),
(Metacall; A = 2).
test5(A) :- A = 3.
% A sharpened cut prevents any solutions other than 1.
% You don't even need the disjunction, some brackets suffice:
test6(A) :- (Goal = (A = 1, !), Goal), true.
test6(A) :- A = 2.
% Once again, the only solution is 1.
% That's not what I would expect of a programming language often
% termed "logic".
% If you follow Moss' proposal, that cut should not act through
% metacalls, another problem arises, that he did not mention: you
% first have to define, what *is* a metacall! Or: how can an
% interpreter detect that the term it now starts to interpret is
% a metacall, and that the effect of all cuts occurring in it
% should be restricted to choice points built after starting to
% interprete this call?
% What, e.g., should be the solutions for the following
% predicates?
test7(A) :- Call = (A = 1, Cut; A = 2), Cut = !, (Call; A = 3).
test7(A) :- A = 4.
test8(A) :- Call = (A = 1, Cut = !, Cut; A = 2), (Call; A = 3).
test8(A) :- A = 4.
% While Cut in test7 is already instantiated when Call is called,
% it isn't yet in test8.
------------------- end of prolog source ------------------------
I'd like to hear
- about the results you obtain when running the tests on your
interpreter or compiler and
- your opinion on cuts in control structures.
The KA-Prolog group at Universitaet Karlsruhe / GMD Karlsruhe,
that I am a member of, has decided to restrict the use of cut to
that as a (pseudo) literal in the (arbitrarily bracketed)
conjunction that forms the body of a clause. Any attempt to use a
cut in a metacall or another language-defined control structure
will be rejected by the compiler or cause a program abort at
runtime.
As we do supply a quite comprehensive set of control structures -
including Moss' backtrack predicate -, we do not think this to be
too hard a restriction.
-- Norbert Lindenberg
Universitaet Karlsruhe
norbert@germany.csnet
------------------------------
End of PROLOG Digest
********************