thom@tuhold (Thom Fruehwirth) (08/23/88)
In <256@quintus.uucp> Richard O'Keefe sketched how to try clauses in random order: > > p(~Args~):- > random_permutation([1,2,3,4,5,6,7],Perm), > member(Index,Perm), > p(Index,~Args~). As Jamie Andrews in <628@etive.ed.ac.uk> pointed out, O'Keefe probably intended to have a cut between random_permutation/2 and member/2. Given that the call (R is random) binds R to a positive or negative integer, then the possibility for success of (random>0) is about 1/2 . Suppose we write a meta-interpreter for random clause selection: prove(true). prove((A,B)):- prove(A), prove(B). prove(H):- clause_number(H,N), % finds the number of clauses of H randomize(N,I), rule(I,H,B), % never use clause/2 here, use your own predicate prove(B). randomize(N,I):- generate_list(N,L), random_perm(L,P), !, member(I,P). generate_list(0,[]). generate_list(N,[N|L]):- N>0, M is N-1, generate_list(M,L). random_perm([],[]):-!. random_perm([X],[X]):-!. random_perm(X,Y):- random_split(A,B,X), random_perm(A,A1), random_perm(B,B1), merge(A1,B1,Y). random_split([X],[],[X]):-!. random_split([X|L1],L2,[X|L3]) :- random>0,!, random_split(L1,L2,L3). random_split(L1,[X|L2],[X|L3]) :- random_split(L1,L2,L3). merge(X,[],X):-!. merge([],X,X):-!. merge([X|L1],L2,[X|L3]) :- merge(L1,L2,L3). merge(L1,[X|L2],[X|L3]) :- merge(L1,L2,L3). In this optimized version random_perm/2 is twice as slow as left- recursive permutation, but more than twice as fast as naive, tail- recursive permutation (on the average). We now gonna transform randomize/2 into a more efficient version. We move replace (random_perm(L,P),!,member(I,P)) by random_index(L,I) by moving (!,member(I,P)) into random_perm/2: random_index([],I):-!, !, member(I,[]). random_index([X],I):-!, !, member(I,[X]). random_index(L,I):- random_split(A,B,L), random_perm(A,A1), random_perm(B,B1), merge(A1,B1,P), !, member(I,P). Partial evaluation gives: random_index([],I):-!,fail. random_index([X],X):-!. random_index(L,I):- random_split(A,B,L), random_perm(A,A1), random_perm(B,B1), merge(A1,B1,Y), !, member(I,Y). Moving the cut into merge/3 gives an optimized version of append/3: append(L,[],L):-!. append([],L,L):-!. append([X|L1],L2,[X|L3]) :-!,append(L1,L2,L3). It is easy to see that (append(A1,B1,Y),member(I,Y)) <=> (member(I,A1),member(I,B1)) therefore (with the explicit failure of the first clause removed): random_index([X],X). random_index(L,I):- L=[X,Y|_], % avoid problems with L=[] and L=[X] random_split(A,B,L), random_perm(A,A1), random_perm(B,B1), (member(I,A1); member(I,B1)). But this is random_index([X],X). random_index(L,I):- L=[X,Y|_], random_split(A,B,L), (random_perm(A,A1), member(I,A1); random_perm(B,B1), member(I,B1)). and according to our initial replacement we result in: random_index([X],X). random_index(L,I):- L=[X,Y|_], random_split(A,B,L), (random_index(A,I); random_index(B,I)). We can further move the first application of random_index/2 into generate_list/2, this finally results in: randomize(N,I):- generate_lists(N,A,B), (random_index(A,I); random_index(B,I)). generate_lists(0,[],[]). generate_lists(N,[N|L1],L2):- N>0,random>0,!, M is N-1, generate_lists(M,L1,L2). generate_lists(N,L1,[N|L2]):- N>0, M is N-1, generate_lists(M,L1,L2). ---------------- Lee Naish pointed out, that even randomized clause selection is not complete using the example (or the like): P:-true. p:-loop. loop:-loop. This seems to indeicate that depth-bound computation is necessary. But instead of having a depth bound meta-interpreter, we could have one with a randomized depth bound: prove(P,true). prove(P,(A,B)):- prove(P,A), prove(P,B). prove(P,H):- random>P, rule(H,B), prove(P,B). Combining this with our random clause selection meta interpreter means that some clauses may not be called, that not all indizes are produced. After some transformations (ommitted here) we result in: prove(P,true). prove(P,(A,B)):- prove(P,A), prove(P,B). prove(P,H):- clause_number(H,N), randomize(P,N,I), rule(I,H,B), prove(P,B). randomize(P,N,I):- generate_lists(P,N,A,B), (random_index(A,I); random_index(B,I)). generate_lists(P,0,[],[]). generate_lists(P,N,L1,L2):- N>0,random>P,!, % probably ignore N M is N-1, generate_lists(P,M,L1,L2). generate_lists(P,N,[N|L1],L2):- N>0,random>0,!, M is N-1, generate_lists(P,M,L1,L2). generate_lists(P,N,L1,[N|L2]):- N>0, M is N-1, generate_lists(P,M,L1,L2). ughhh, I think thats enough... thom fruehwirth
ok@quintus.uucp (Richard A. O'Keefe) (08/24/88)
In article <1171@tuhold> thom@tuhold (Thom Fruehwirth) writes: >In <256@quintus.uucp> Richard O'Keefe sketched how to try clauses >in random order: >> >> p(~Args~):- >> random_permutation([1,2,3,4,5,6,7], Perm), >> member(Index, Perm), >> p(Index, ~Args~). > >As Jamie Andrews in <628@etive.ed.ac.uk> pointed out, O'Keefe probably >intended to have a cut between random_permutation/2 and member/2. NO WAY! What would it do? random_permutation/2 generates *ONE* random permutation between its two arguments. This is the only clause of p(~Args~), and random_permutation/2 doesn't leave any choice points, so there is nothing for a cut to do. What this code fragment does is to try the (original) clauses of p in a random order; for that we want *ONE* random permutation. random(-X) generates *ONE* pseudo-random float uniformly distributed between 0.0 and 1.0. You wouldn't expect it to generate another if you backtrack into it. Why should random_permutation/2 be any different?
jha@lfcs.ed.ac.uk (Jamie Andrews) (08/25/88)
>In article <1171@tuhold> thom@tuhold (Thom Fruehwirth) writes: >>As Jamie Andrews in <628@etive.ed.ac.uk> pointed out, O'Keefe probably >>intended to have a cut between random_permutation/2 and member/2. Actually, the point I was making was that random_permutation/2 would either return 7! results (not good) or else introduce additional incompleteness into the system (returns only one of the possible results) which random clause selection would not. If we accept the incompleteness arising from allowing cut, though, it wouldn't make much difference that random_permutation/2 returned only one result, since the effect of it would be the same as if it were followed by a cut. In article <308@quintus.UUCP> ok@quintus.UUCP (Richard A. O'Keefe) writes: <random(-X) generates *ONE* pseudo-random float uniformly distributed <between 0.0 and 1.0. You wouldn't expect it to generate another if you <backtrack into it. Why should random_permutation/2 be any different? I agree, from a practical point of view. But I would rather have the whole thing hidden, or the randomization explained by a hidden seed parameter, or something like that, just because I'm perversely theoretical. (Trilogy anyone? :-)) BTW, (referring to a previous ok article) I also agree that having random clause selection might not help very much for some tasks requiring randomization (such as selecting a random element of an arbitrary-length list) and that specific solutions might need to be found for them. --Jamie. jha@lfcs.ed.ac.uk "I always find mathematics so difficult" -- David Hilbert
thom@tuhold (Thom Fruehwirth) (08/26/88)
I still think that random_permutation/2 should do the same think as permutation/2, but return solutions in random order. This is also how I specified random_perm/2 in my recent posting. Besides, I think there is a more natural solutions to random clause selection, which avoids indexing clauses: random_solve(true). random_solve((A,B)):- random_solve(A), random_solve(B). random_solve(A):- findall((A:-B),rule(A,B),RuleList), random_perm(RuleList,RulePerm), !, member((A:-B),RulePerm), random_solve(B). Note that this is no implementation version. thom