Path: utzoo!attcan!uunet!mcvax!tuvie!tuhold!thom
From: thom@tuhold (Thom Fruehwirth)
Newsgroups: comp.lang.prolog
Subject: Random Clause Selection (was: re:probabilstic or)
Keywords: meta interpreter, random, probabilistic, completeness, loops
Message-ID: <1171@tuhold>
Date: 22 Aug 88 17:56:10 GMT
Organization: Institut f. Angewandte Informatik, TU Vienna
Lines: 204



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