Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!samsung!munnari.oz.au!goanna!ok
From: ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe)
Newsgroups: comp.lang.prolog
Subject: Re: Deterministic predicate question
Message-ID: <3631@goanna.cs.rmit.oz.au>
Date: 28 Aug 90 07:50:05 GMT
References: <90239.224751F0O@psuvm.psu.edu>
Organization: Comp Sci, RMIT, Melbourne, Australia
Lines: 80

In article <90239.224751F0O@psuvm.psu.edu>, F0O@psuvm.psu.edu writes:
>     I'm curious as to why length is deterministic where both of the
> build_board predicates are not.  Also, is there a way to make one of the
> build_board predicates deterministic, without using the cut?

It would help if you indicated the language you are using.
From the extremely confusing use of '=' for arithmetic, I
infer this is Turbo/PDC ``Prolog''.

>     build_board1(10).
>     build_board1(SquareNum) :-
>          NextSquare = SquareNum + 1,
>          build_board1(NextSquare),
>          assert(board(SquareNum," ")).

This predicate is non-determinate for the very simple reason that
any query (such as ?- build_board1(10)) which matches the first
clause will *also* match the second clause.  That's what it _means_
to be non-determinate.  If you call

	?- build_board1(0), fail.

or however you do that in Turbo/PDC Prolog, it will loop forever.

The answer is simple:  say what you *really* mean.

    build_board1(10).
    build_board1(SquareNum) :-
	SquareNum < 10,			% <--- I added this condition.
	NextSquare = SquareNum + 1,
	build_board1(NextSquare),
	assert(board(SquareNum," ")).

Turbo/PDC Prolog may well be smart enough to notice that the argument
to build_board1/1 is a strict input and that therefore cases matching
the first clause _won't_ get far into the second.  SB Prolog certainly
would.

Many Prolog compilers operate a clause at a time (in some, such as ALS
Prolog and QP3.0, assert _is_ "compile"), so won't spot this.  In such
cases you must resort to an if->then;else (how does Turbo Prolog express
if->then;else?) or use a cut:

    build_board1(M) :-
	(   M =:= 10 -> true
	;   M  <  10 ->
	    N is M+1,
	    assert(board(N, ' ')),
	    build_board1(N)
	).

By the way, I really don't like the way the magic number 10 is
buried inside this predicate.  It would be better to have the
predicate count DOWN (I find that it is almost always better to
have the predicate count down) and then the magic number can be
in the call, and you won't have to change the code for a different
board size:

    build_board_down(N) :-
	(   N =:= 0 -> true
	;   N  >  0 ->
	    asserta(board(N, ' ')),
	    M is N-1,
	    build_board_down(M)
	).

    ?- build_board_down(10).		% to make board(1,' ')...board(10,' ')

>     length([], 0).
>     length([_|T], Len) :-
>          length(T,Tmp),
>          Len = Tmp + 1.

If you call this predicate with a non-variable first argument, it can
match the first clause *only*, the second clause *only*, or neither.
The compiler has only to notice that [] and [_|T] are both non-variables
and that they have different functors (namely []/0 and (.)/2).

-- 
The taxonomy of Pleistocene equids is in a state of confusion.