Randomizing priority in Prolog predicates

Question

One of the main differences between Prolog and first order logic is in the strict rule for the priority of the right parts in predicate. I would like to know if there any way to randomize this priority without renouncing at the normal backtracking behaviour. In particular I'm working with SWI-Prolog so it would be good also a solution that works only with that interpreter.

Answer 1

Although there is no built-in way to use randomness as a search strategy in the Prolog theorem prover, there are native functions there to generate random numbers which could then be used (in a roundabout way) to randomize which instance of a predicate is chosen for consideration next.

To elaborate, you might include with each instance of a predicate path/n two additional tests which represent the range within 0 and 1 that predicate holds. This range (Lo, Hi) should be chosen such that Hi - Lo = 1 / k, where k is the total number of instances that the predicate path/n has in the knowledgebase.

path(N, ...) :- N >= 0.0, N < 0.2, ...
path(N, ...) :- N >= 0.2, N < 0.4, ...
path(N, ...) :- N >= 0.4, N < 0.6, ...
path(N, ...) :- N >= 0.6, N < 0.8, ...
path(N, ...) :- N >= 0.8, N <= 1.0, ...

With this embedding of ranges, we are making all the instances of path/n equally likely to be considered. Whenever path/n is called in the RHS of a rule or production (right of :- or -->), it should be preceded by the generation of a random float between 0 and 1 which is passed as the first argument to path/n; e.g. foo :- random(N), path(N, ...)..

This would of course become cumbersome over time as the knowledge base increases in size, so you might want to write a compiler (like the DCG compiler) that generates the randomness threading for you. Writing these sorts of compilers in Prolog is surprisingly not too much work thanks to predicates like asserta and assertz.

If you are using this "random derivation search" as a method to avoid infinite left recursion, know that a much nicer method might simply be to write the solution so that it uses breadth-first search rather than Prolog's intuitive depth-first. This involved threading a State argument into all your predicates (worth a google: Prolog breadth-first).

EDIT: Prolog is also higher-order logic (HOL), except in the strict left-derivation, first-predicate-first-considered way, which leads to problems with left recursion. You could use the (HOL) features of Prolog to model a search approach that considers all predicates evenly (assuming the predicates are pure predicates, no arithmetic, etc.). For example, store all the right hand sides as a list of predicates [[p1, p1a1,...],[p2,p2a1,...]|_], randomize the list before evaluation, then evaluate the shuffled list of predicates iteratively by building up the predicate using the =.. operator, i.e. X =.. [p1, p1a1, p1a2], X. The X in this snippet is unified with p1(p1a1,p1a2), and is then searched for satisfiability.