2

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.

false
  • 10,264
  • 13
  • 101
  • 209
Gioleppo
  • 21
  • 3
  • What is the point of this? Anyway, no, there is no built-in facility for that. – Eugene Sh. Aug 14 '17 at 19:24
  • Can you give a simple example? What do you mean by "priority"? Do you mean the order? – lurker Aug 14 '17 at 19:31
  • Simply the fact that left parts are executed in the order in which they compare in the program: if one fail the interpreter backtracks to another predicate. – Gioleppo Aug 14 '17 at 22:48
  • I'm not sure what "left parts" are or what you mean by "they compare". I think it would be a better question if you described a use case of what you're trying to do. – lurker Aug 15 '17 at 00:56
  • @lurker I suspect it's about the order of goal selection, i.e. left-to-right. randomizing could maybe simulate a *parallel* Prolog. Kind of like [guarded command language by Dijkstra](https://en.wikipedia.org/wiki/Guarded_Command_Language), where a guard is chosen nondeterministically from among the matching guards (in the [`do`](https://en.wikipedia.org/wiki/Guarded_Command_Language#Semantics_4) construct). – Will Ness Aug 15 '17 at 07:45
  • [tag:minikanren] is advertised to have "fair scheduling", which probably means that the results of all goals in a disjunction are mixed / interleaved, instead of having all the results of the first (left-most) goal processed before any of the results from the other goals, as in the regular, sequential Prolog (like SWI is an implementation of). (see `++/` and `||/` [here](https://stackoverflow.com/questions/10843563/conda-condi-conde-condu/10848902#10848902)). Changing order of goals in a conjunction is more subtle, can change the overall meaning if goals are non-pure. – Will Ness Aug 15 '17 at 08:00
  • @lurker also, "priority" may refer to "prioritized choice" of simple linear lists, where we always pick the leftmost element (`[H|T]` --> `H-T`). But we could pick one randomly, as in math with set expressions where order of choice is (presumably) unspecified: `{ x | x <- {1..4}, even x}` could result in `{4,2}` as well. – Will Ness Aug 15 '17 at 08:06
  • @WillNess I "suspect" some interpretations, too, and think the terminology being used here "may" refer to certain things. But I was hoping the OP would explain their question more clearly with examples rather than rely on my own speculations. – lurker Aug 15 '17 at 09:58

1 Answers1

3

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.