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 ?-

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).

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

Copyright © 2014 Barry Watson. All rights reserved.