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.