# Stochastic Prolog

Stochastic Prolog is a variant of Prolog where clauses can be marked with weights which determine the probability that the clause will be chosen. The form of a clause with weight `W`, head `H`, and body `B` is:

``` W:H:-B ```

Imagine we had several clauses with the same head functor:

``` W1:H(a):-B1 % Clause 1 W2:H(b):-B2 % Clause 2 W3:H(c):-B3 % Clause 3 ```

The probability that Clause 3 is chosen when a query of `H(X)` is given is `W3/(W1+W2+W3)`. Should the chosen clause fail then the other clauses are not tried - there is no backtracking as this mechanism works like a stochastic cut. A call of `H(c)` will always succeed.

The following example of a Stochastic Prolog program simulates the tossing of a coin where the probability of either heads or tails is 49.5% and the probability of the coin falling down a manhole is 1%.

``` 49.5:coin(heads). 49.5:coin(tails). 1:coin(manhole). toss :- coin(X), continuation(X). continuation(manhole) :- format('Manhole!~n', []). continuation(heads) :- format('Heads~n', []), toss. continuation(tails) :- format('Tails~n', []), toss. ```

When the predicate `toss/0` is run, the program outputs a list of either "Heads" or "Tails" terminated by a "Manhole" printout. Example:

``` | ?- test_loop. Stochastic Prolog ?- toss. Heads Heads Heads Tails Tails Tails Heads Tails Tails Tails Tails Heads Tails Heads Tails Heads Heads Heads Heads Tails Tails Heads Heads Heads Heads Heads Tails Heads Tails Tails Heads Tails Heads Heads Heads Tails Tails Tails Tails Heads Heads Heads Tails Heads Heads Heads Tails Tails Tails Tails Heads Heads Heads Tails Heads Tails Tails Tails Heads Heads Heads Tails Tails Tails Tails Heads Heads Tails Tails Tails Tails Tails Tails Heads Heads Heads Heads Tails Heads Heads Tails Tails Manhole! % Yes. Stochastic Prolog ?- ```

## Implementation

The following code can be run with the Barry's Prolog distribution.

The operator `':'/2` is first redefined.

``` :- op(0, yfx, ':'). :- op(500, yfx, ':'). ```

The heart of the interpreter is `demo/1` and `demo(+G)` succeeds if `G` can be proven. The is very similar in structure to the typical Prolog interpreter except for the call to `stochastic_clause/2`.

``` demo(true) :- !. demo((Goal1 ; Goal2)) :- !, (demo(Goal1) ; demo(Goal2)). demo((Goal1 , Goal2)) :- !, demo(Goal1), demo(Goal2). demo(Goal) :- functor(Goal, P, A), procedure_property(P/A, (static)), !, call(Goal). demo(Goal) :- clause(Goal, Body), !, demo(Body). demo(Goal) :- stochastic_clause(Goal, Body), !, demo(Body). ```

The predicate `stochastic_clause(+H, -B)` succeeds if there is a stochastic clause chosen with head `H` and body `B`. We first collect all stochastic clauses which match the head then choose one of the clauses according to the weights.

``` stochastic_clause(Head, Body) :- bagof(X:(Head :- B), clause(X:Head, B), Lst), sum_weights(Lst, Sum), random_uniform(0, Sum, Target), stochastic_clause_selection(Lst, Target, 0, _:(Head :- Body)). ```

The predicate `sum_weights(+L, -S)` sums up all the weights in the list `L` giving result `S`.

``` sum_weights(Lst, Sum) :- sum_weights(Lst, 0, Sum). sum_weights([], Acc, Acc). sum_weights([X:_|T], Acc, Sum) :- NewAcc is Acc+X, sum_weights(T, NewAcc, Sum). ```

The choice of stochastic clause is done by the predicate `stochastic_clause_selection(+Clauses, +Target, +Current, -Chosen)`. Here `Clauses` is a list of clauses of the form `Weight:Clause`. `Current` should start at `0` and is used to hold the sum of all the weights seen when running through `Clauses`. `Target` is the weight sum which we want to exceed. We stop when `Current >= Target`. `Chosen` is the element of `Clauses` which causes `Current >= Target`.

``` stochastic_clause_selection([X:G|_], Target, Current, Result) :- Current + X >= Target, !, Result = X:G. stochastic_clause_selection([X:_|T], Target, Current, Result) :- NewCurrent is X+Current, stochastic_clause_selection(T, Target, NewCurrent, Result). ```

The predicate `random_uniform(+A, +B, -F)` succeeds when `F` is a uniformly distributed random number between `A` and `B`.

``` random_uniform(A, B, X) :- random(Ran), X is (B-A)*Ran + A. ```

The predicate `random(-F)` is used to generate random numbers. The argument `F` is a uniformly distributed random number between `0` and `1`. The routines here are specific to Barry's Prolog as they use the implementation's arbitrary precision floating-point numbers.

``` random(F) :- current_prolog_flag(floating_point_precision, Precision), Count is ceiling(Precision/31), build_random(Count, 0, Bits), PrecisionDenormalised is Count*31, RandomDenormalised = '\$float'(Bits, 0, PrecisionDenormalised), '\$fp_normalise'(RandomDenormalised, F). build_random(0, Random, Random) :- !. build_random(N0, Acc0, Random) :- N1 is N0 - 1, '31_random_bits'(Bits), pow(2, 31, Multiplier), Acc1 is Acc0*Multiplier+Bits, build_random(N1, Acc1, Random). :- dynamic '\$seed'/1. '\$seed'(1). '31_random_bits'(Xn) :- ('\$seed'(Seed) -> retract('\$seed'(_)) ; Seed = 1), Xn is (16807 * Seed) mod 2_147_483_647, assert('\$seed'(Xn)). ```

The following predicate is used to get user queries and display the result possibly forcing backtracking. The predicates `\$expand_term/2`, `\$save_cp/1`, and `\$cutto` are specific to Barry's Prolog and are probably given different names in different Prolog implementations. This predicate is used to start the Stochastic Prolog interpreter.

``` test_loop :- ask_query(test_query, [], [], A), Term0-Vars = A, '\$expand_term'(Term0, Term1), ( demo(Term1), ( Vars = [] -> print_message(informational, 'Yes.') ; phrase(substitution_message(Vars), QueryText), '\$savecp'(CP), repeat, ask_query(test_solution, QueryText, ['";" - backtrack for another solution.'-[], nl, '<return> - continue.'-[], nl], A2), ( A2 = yes -> print_message(informational, 'Yes.') ; '\$cutto'(CP), % remove the choicepoint created by repeat/0 above fail ) ) ; print_message(informational, 'No.') ), test_loop. ```

The following hooks are used to configure the user input routines. See the Barry's Prolog manual for details.

``` test_query_class_hook1(test_query, 'Stochastic Prolog ?- ', (T-Vs)^term(T, [variable_names(Vs)]), =, query). :- add_query_class_hook(test_query_class_hook1). test_query_class_hook2(test_solution, ' ? ', line, char([yes-[0'\n], no-";"]), help_query). :- add_query_class_hook(test_query_class_hook2). ```

The following is used to turn a list of variables into the query output.

``` substitution_message([]) --> []. substitution_message([V = Term|Rest]) --> ['~a = '-[V], write_term(Term, []), nl], substitution_message(Rest). ```

## References

Oliva, Gardelli, Viroli, and Omicini. Experimenting with Stochastic Prolog as a Simulation Language.