F0O@psuvm.psu.edu (08/28/90)
The build_board predicates will set up a beginning tic-tac-toe board.
The predicates work ok, but they are both non-deterministic. However,
our old friend length is deterministic.
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?
build_board1(10).
build_board1(SquareNum) :-
NextSquare = SquareNum + 1,
build_board1(NextSquare),
assert(board(SquareNum," ")).
build_board2(10).
build_board2(SquareNum) :-
assert(board(SquareNum," ")),
NextSquare = SquareNum + 1,
build_board2(NextSquare).
length([],0).
length([_|T],Len) :-
length(T,Tmp),
Len = Tmp + 1.
Thanks muchly,
[Tim]ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) (08/28/90)
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.
dave@quintus.UUCP (David Bowen) (08/29/90)
In article <3631@goanna.cs.rmit.oz.au> Richard A. O'Keefe writes: >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. It is not correct that `assert is "compile"' in Quintus Prolog Release 3.0. Dynamic code in Quintus Prolog continues to be represented in a form that is optimized for speed of assert/retract rather than for speed of execution. The change that may have misled Richard is that we no longer distinguish between "compile" and "consult"; that is, there is no special way that you have to load your code in order to be able to debug it - all code is debuggable. Since release 2.5, it is possible to access the clause-compiler via a built-in predicate called multifile_assertz which compiles a clause and adds it to the end of a predicate. There is no corresponding retract operation (only abolish). Also, multifile_assertz is not available in runtime systems, since the built-in compiler is not included in those systems.
jgarland@kean.ucs.mun.ca (08/29/90)
In article <3631@goanna.cs.rmit.oz.au>, ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes: > 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''. !!!!! Don't be so cute, you *know* it is--you've seen, and answered, Tim's queries before. >> 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. ^^^^^^^^^^^^^^^^^^^^^^^^^ I'm not sure exactly what T/PDC Prolog will do here...I intend to check it out the second I'm free...it's an interesting point. I *think* it will try the first clause, then the next and then quit, but check it out for yourself. > or however you do that in Turbo/PDC Prolog, it will loop forever. > > The answer is simple: say what you *really* mean. ^^^^^^^^^^^^^^^^^^^^^^^^^^ About the best Prolog advice ever. Or turn it around: Prolog does what you *really* say...often in a way that is non-obvious to procedural thinking. Anyway, this is a perfect place to use a cut. You're essentially trying to implement a while-do loop. And given the order of the clauses, tail recursion optimization takes care of any stack problems. [In terms of the basic loop, that is. Not asserts.] ********listing****************************************** predicates while_do(integer) clauses while_do(0) :- !. while_do(X) :- write("Countdown: ",X),nl, X1=X-1, while_do(X1). goal while_do(10). ***********end of listing*************************************** Your stuff is looking much more elegant. JG jgarland@mun Bitnet jgarland@kean.ucs.mun.ca Internet
F0O@psuvm.psu.edu (08/29/90)
In article <3631@goanna.cs.rmit.oz.au>, ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) says: >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''. Sorry about not mentioning that before. You are right, this is(drum roll please) PDC PROLOG! :-) >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. Running the above code does stop the code from looping forever. However, in PDC Prolog there are diagnostics you can run on your code. It still tells me the above routine is non-deterministic. Here is the output: DIAGNOSTICS FOR MODULE: C:\PROLOG\DETERM.PRO Predicate Name Type Determ Size Domains -- flowpattern ---------------- ------ ------ ----- ---------------------------- _PROLOG_Goal local YES 26 -- build_board1 local NO 138 integer -- i board NOT USED integer,string ---------------- ------ ------ ----- ---------------------------- Total size 164 Size of symbol table= 393 bytes >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) > ). Pretty much the same way. However, and this is a *big* however, you can only enclose arithmetic expressions in parenthesis. Trying a similar program like above with the parenthesis would generate an error. :-( This means that many times you have to split the code into two or more predicates. I've asked PDC to change this on their next release; I'm hoping they do. [Tim]
jgarland@kean.ucs.mun.ca (08/29/90)
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
ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) (08/31/90)
In article <129469@kean.ucs.mun.ca>, jgarland@kean.ucs.mun.ca writes: > In article <3631@goanna.cs.rmit.oz.au>, ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes: > > 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''. > !!!!! > Don't be so cute, you *know* it is--you've seen, and answered, Tim's queries > before. I wasn't being cute. I didn't recognise the poster (I didn't even _look_ at the name). And even if I had recognised the poster, I have no reason to believe that he has access to only one Prolog system. (Or have I forgotten something from one of his postings?) -- You can lie with statistics ... but not to a statistician.
jgarland@kean.ucs.mun.ca (08/31/90)
In article <3648@goanna.cs.rmit.oz.au>, ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes: > In article <129469@kean.ucs.mun.ca>, jgarland@kean.ucs.mun.ca writes: >> In article <3631@goanna.cs.rmit.oz.au>, ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes: >> > 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''. >> !!!!! > >> Don't be so cute, you *know* it is--you've seen, and answered, Tim's queries >> before. > > I wasn't being cute. I didn't recognise the poster (I didn't even _look_ > at the name). And even if I had recognised the poster, I have no reason > to believe that he has access to only one Prolog system. (Or have I > forgotten something from one of his postings?) > -- > You can lie with statistics ... but not to a statistician. Your dead right. I apologize. I guess I thought you were coming down a little heavily on someone who seems to me to obviously be a (1) student and (2) beginner. Won't happen again. John Garland jgarland@mun Bitnet jgarland@kean.ucs.mun.ca Internet