Subject:
Re: Are cuts theoretically necessary?
From:
Markus Triska <triska@logic.at>
Date:
Thu, 01 Mar 2007 23:59:29 +0100
Newsgroups:
comp.lang.prolog
Path:
newssvr11.news.prodigy.net!newsdbm03.news.prodigy.net!newsdst01.news.prodigy.net!prodigy.com!newscon04.news.prodigy.net!prodigy.net!newshub.sdsu.edu!news.germany.com!newsfeed.utanet.at!newsfeed.wu-wien.ac.at!aconews-feed.univie.ac.at!aconews.univie.ac.at!not-for-mail
Newsgroups:
comp.lang.prolog
References:
<1172775758.974693.325770@k78g2000cwa.googlegroups.com>
Message-ID:
<87lkigr2ni.fsf@logic.at>
Cancel-Lock:
sha1:tFVSUXGJwoQsxlrnQQJAY0SM6kA=
MIME-Version:
1.0
Content-Type:
text/plain; charset=us-ascii
Lines:
59
NNTP-Posting-Host:
news-access-from.tuwien.ac.at
X-Trace:
1172789970 tunews.univie.ac.at 12384 192.35.241.118
X-Complaints-To:
abuse@tuwien.ac.at
Xref:
prodigy.net comp.lang.prolog:38111

dave_140390@hotmail.com wrote:

> > Is there any algorithm that can't be implemented, even
> > inefficiently, without cuts?

No, since pure Prolog (= Horn clauses with Prolog's proof procedure)
is Turing complete. Proof: Simulate a Turing machine with pure Prolog.
For a start, consider member/2. To simulate a TM, it (by far) suffices
to restrict ourselves to lists of natural numbers 0,s(0),s(s(0)) etc.:

    nat_member(_, [], no).
    nat_member(M, [L|_], yes) :-
        nat_unify(M, L, yes).
    nat_member(M, [L|Ls], Result) :-
        nat_unify(M, L, no),
        nat_member(M, Ls, Result).

    nat_unify(0, 0, yes).
    nat_unify(s(_), 0, no).
    nat_unify(0, s(_), no).
    nat_unify(s(X), s(Y), Result) :-
        nat_unify(X, Y, Result).

On natural numbers, nat_member/3 always succeeds, and success/failure
of the check we are interested in is reified in the third argument.
That can be used to distinguish mutually exclusive clauses without
negation, just like we distinguished two separate cases in
nat_member/2 itself already (nat_unify: yes/no). This makes commitment
to a particular clause semantically unnecessary. And instead of:

    not_nat_member(M, Ls) :-
        nat_member(M, Ls, yes),
        !,
        fail.
    not_nat_member(_, _).    

you can now write the cut-free version:

    not_nat_member(M, Ls) :- nat_member(M, Ls, no).

As an aside, efficiency isn't the only thing affected - you also
*gain* something from the purity:

    %?- not_nat_member(X, [s(0)]).
    %@% X = 0 ;
    %@% X = s(s(_G260))

whereas the version with the cut yields:

    %?- not_nat_member(X, [s(0)]).
    %@% No

Other predicates you need for the TM are translated analogously.

All the best,
Markus

-- comp.lang.prolog FAQ: http://www.logic.at/prolog/faq/