Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!cs.utexas.edu!uunet!stretch.cs.mun.ca!leif!jgarland
From: jgarland@kean.ucs.mun.ca
Newsgroups: comp.lang.prolog
Subject: Re: Deterministic predicate question
Message-ID: <129740@kean.ucs.mun.ca>
Date: 29 Aug 90 10:19:48 GMT
References: <90239.224751F0O@psuvm.psu.edu> <3631@goanna.cs.rmit.oz.au> <90240.210843F0O@psuvm.psu.edu>
Organization: Memorial University. St.John's Nfld, Canada
Lines: 42

In article <90240.210843F0O@psuvm.psu.edu>, F0O@psuvm.psu.edu writes:
> In article <3631@goanna.cs.rmit.oz.au>, ok@goanna.cs.rmit.oz.au (Richard A.
> O'Keefe) says:

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

Tim replies: (paraphrased) "Yes, but it's still nondeterministic.  See 
below.  What gives?"
 
> DIAGNOSTICS FOR MODULE: C:\PROLOG\DETERM.PRO
> 
> Predicate Name   Type   Determ Size  Domains -- flowpattern
> ---------------- ------ ------ ----- ----------------------------
> build_board1     local  NO       138 integer -- i
> ---------------- ------ ------ ----- ----------------------------

Determinism and nondetermism in T/PDC Prolog are not *bad* or *good* per se.
They are descriptive terms stating whether the predicate is capable of gener- 
ating backtracking points (alternate solutions).  As ND predicates can (if they 
can't be optimized) take huge chunks of memory, it's nice to have them ID'd.

For some purposes, however, you *want* ND predicates.  Consider append/3.  It is
*not* optimizable under the T/PDC compiler and therefore makes extensive use of
the stack during its operation.  Maybe it canbe done, but I've never been able
to construct a deterministic version of it (in T/PDC).  [FYI, making one which
constructs a FILO appended list is trivial, but then you have to turn it around
with a 2nd deterministic predicate.  And, in any case, you lose the other inter-
esting features of append/3 like interchangeablility.]  Anyway, since many lists
that you process do not need to be infinitely extensible, you use ND append/3.
Where you do need relatively great extensibility you use one or another form of
assert [or you save your beer money for year or two and buy OS/2, the OS/2
version of PDC, and lots and lots and lots of RAM].  

John Garland

jgarland@mun              Bitnet
jgarland@kean.ucs.mun.ca  Internet