Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!caip!clyde!cbatt!cbosgd!ucbvax!techunix.BITNET!raan
From: raan@techunix.BITNET (Ran Ever-Hadani)
Newsgroups: net.lang.prolog
Subject: Answer to fixed-points query of #41
Message-ID: <8608311221.AA07327@techunix.bitnet>
Date: Sun, 31-Aug-86 08:24:39 EDT
Article-I.D.: techunix.8608311221.AA07327
Posted: Sun Aug 31 08:24:39 1986
Date-Received: Sun, 31-Aug-86 19:59:07 EDT
Sender: daemon@ucbvax.BERKELEY.EDU
Organization: University of California at Berkeley
Lines: 46

In pure prolog, it is not possible to construct a single clause, self/1
with non-empty body that yields any answer to a query; it can either fail
or go into infinite loop.  If the clause is Head:-Body then the initial
goal is Head, and no reduction can ever produce the empty goal.

self/1 with no body is also not possible, since it will have to contain
itself.

The sollution below is a procedure is self/2, which contains two clauses
and is true when fed these clauses as parameters.

self(Y,self(Y,0)) :- self(Y,0).
self((self(Y,self(Y,0)):-self(Y,0)),0).

This it not perfect, since if we ask  ?- self(A,B). then apart from
A=.. clause1 ..   B=.. clause2 ..   which is the sollution we want,
we also get  A=.. clause1 ..  B=0 (by unifying directly to clause2).

This can only be avoided using a cut (which is not pure prolog) as
shown in a slightly different version of self/2 below:

Script started on Sun Aug 31 14:58:20 1986
% cprolog
C-Prolog version 1.4a
| ?- [user].
|
| self(Y,self(Y,0)) :- self(Y,0), !.
|
| self((self(Y,self(Y,0)):-self(Y,0),!),0).
| ^D
user consulted 416 bytes 0.116667 sec.

yes
| ?- self(A,B).

A = self(_9,self(_9,0)):-self(_9,0),!
B = self((self(_9,self(_9,0)):-self(_9,0),!),0) ;

no
| ?- ^D
[ Prolog execution halted ]
%
Script done on Sun Aug 31 14:59:33 1986

-- Ran Ever-Hadani
raan@techunix.BITNET