Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!linus!philabs!cmcl2!seismo!caip!cbmvax!bpa!burdvax!blenko
From: blenko@burdvax.UUCP
Newsgroups: net.lang.prolog
Subject: Re: Standard behavior?
Message-ID: <2517@burdvax.UUCP>
Date: Sun, 1-Jun-86 19:10:42 EDT
Article-I.D.: burdvax.2517
Posted: Sun Jun  1 19:10:42 1986
Date-Received: Wed, 4-Jun-86 00:20:14 EDT
References: <980@watdragon.UUCP> <253@ubc-cs.UUCP> <1021@watdragon.UUCP> <1163@sicsten.UUCP>
Reply-To: blenko@burdvax.UUCP (Tom Blenko)
Organization: System Development Corp., Paoli, PA
Lines: 32

In article <1163@sicsten.UUCP> lhe@sicsten.UUCP (Lars-Henrik Eriksson) writes:
>In article <1021@watdragon.UUCP> rggoebel@watdragon.UUCP writes:
>>I don't believe that cut, var, and nonvar cannot be described
>>logically, just because they aren't in Prolog implementations.

>The reason why cut, var and nonvar cannot be "described logically" is
>that they are non-logical (or meta-logical, if you wish) primitives,
>that is primitives used to control the search for proofs.

>The meaning of these primitives are dependent of the particular way an
>implementation looks for proofs. With a different implementation you
>could be forced to give a different meaning to cut, var and nonvar, or
>even find that they couldn't be given any meaning at all.

I disagree with the latter comment. If call() and negation-by-failure
are provided, I claim that you can define if-then-else() (with your
favorite syntax, say P->Q;R), and that if-then-else() is more
expressive than cut(). In particular, you need a scoping construct for
cut() to make it as expressive as if-then-else().

It is a short exercise to show that that var() and nonvar() can be
expressed using call() and cut() (or if-then-else()).

So the discussion reduces to establishing the logical or non-logical
character of call() and negation-by-failure(). I will speculate that
the meaning of call() can be captured by a suitable application of
first-order logic, due to its definition in terms of constructive
proofs (I have something along the lines of Perlis' AIJ (1985) article
in mind here). I am side-stepping the problem of incompleteness of
logic-programming interpreters w.r.t resolution.

	Tom