Path: utzoo!attcan!uunet!mcvax!inria!geocub!billaud
From: billaud@geocub.greco-prog.fr (Michel Billaud)
Newsgroups: comp.lang.prolog
Subject: Re: Committed Choice
Keywords: Semantics
Message-ID: <1077@geocub.greco-prog.fr>
Date: 15 Mar 89 16:15:28 GMT
Reply-To: billaud@geocub.greco-prog.fr (Michel Billaud)
Organization: Greco-Programmation, Bordeaux, France.
Lines: 50

In article <11500012@hpldola.HP.COM> patch@hpldola.HP.COM (Pat Chkoreff) writes:
>It seems to me that the if-then-else construct in Prolog completely
>eliminates the need for the cut, and is a far superior mechanism for
>enforcing committed choice.  Am I right?

If you restrict yourself to 'flat clauses' with no ";" in their body part :
Theorem 1
	Any 'flat' procedure with cut can be translated into an equivalent
	procedure using if-then-else instead.
	
But if you remove the restriction, some Prolog "program schemes" with cut 
just *cannot* be translated into equivalent schemes with if-then-else. 
For example :
		p(X) :- g(X),( (f(X),!,fail) ; true) .
		
Think of g as a 'generator' which produces values for X. f is a 'filter' 
which accepts or rejects these values. The whole thing p produces the
'stream' of the first answers of g which are rejected by f .

Theorem 2:
   You *cannot* express such a combination of g and f without cut. 

Proofs
   Formal proofs need a formal framework (sorry for hackers .. :-) )
   see 		Prolog Control Structures, a Formalization
   		and its Applications, by Michel Billaud,
		in Programming for Future Generations Systems (?)
		eds Prof Fuchi & Nivat. Elsevier 
		(Proceedings of the France-Japan Symposium
		on Artificial Intelligence and Computer Science Tokyo 87)
[]

But Prolog authors never read my papers :-) ! 

Michel Billaud

#include 'self/advertisement'








-- 
Michel BILLAUD                 :  billaud@geocub.greco-prog.fr
Departement d'Informatique     :  ...!decvax!mcvax!inria!geocub!billaud
IUT "A", Universite Bordeaux I :  
33405 Talence  (FRANCE)        :  phone: 56.84.57.92  // 56.84.60.79