Re: [eclipse-clp-users] Propagators with a state

From: Joachim Schimpf <jschimpf_at_users.sf.net>
Date: Tue, 17 Feb 2009 10:39:52 +1100
Wit Jakuczun wrote:
>>
>> propagator(Vars, state(State0)) :-
>>     update_state(Vars, State0, State1),
>>     ( ground(Vars) -> check_solution(Vars)
>>     ; do_propagate(Vars, State1),
>>       suspend(propagator(Vars, state(State1), Susp), 3, Vars->inst, Susp)).
>>
>> propagator(Vars, State,  Susp) :-
>>     State = state(State0),
>>     update_state(Vars, State0, State1),
>>     ( ground(Vars) -> kill_suspension(Susp), check_solution(Vars)
>>     ; do_propagate(Vars, State1), setarg(1, State, State1)).
>>
>> update_state/3 must be called as there can be more that
>> one variable instantiated comparing to previous call of a propagator.

I do not understand what kind of state you are having that would require
such a treatment.  You would normally store the state that existed at the
end of the previous propagator run, and when the propagator runs again,
compare that old state with the current situation.


>> This is due to priorities!

No, even without priorities you must handle the case that more than one
variable changed since the last run of the propagator.  Just consider the
case that several variables get instantiated in one single unification like
f(X,Y)=f(1,2).  We cannot artificially break this up into two separate
unifications.  Also, any atomic propagator e.g. alldifferent/1, will in
general affect more than one variable at a time, so all other propagators
must deal with this.  Apart from that, it is also more efficient if a
propagator can deal with a whole batch of updates at the same time.

If you are writing propagators that are based on propagating individual
domain value deletions (AC4/6 style), maybe you can contact me directly,
as I am currently doing some work in this area.


Kish Shen wrote:
> You can avoid writing two versions of propagator by checking if there
> is a suspension in the propagator/3 code, e.g.:
> 
> propagator(Vars, State) :-
> 	propagator(Vars, State, _Susp).
> 
> propagator(Vars, State, Susp) :-
> 	State = state(State0),
> 	update_state(Vars, State0, State1),
> 	( ground(Vars) ->
> 		( is_suspension(Susp) -> kill_suspension(Susp) ; true ),
> 		check_solution(Vars)
> 	;
> 		do_propagate(Vars, State1),
> 		(is_suspension(Susp) ->
> 			true
> 		;
> 			suspend(propagator(Vars, ....)
> 		)
> 	).

Two things look wrong here:
1. as i said above, i would expect that do_propagate is interested in
    the difference between the current state and the state at the end
    of the last propagation.
2. do_propagate can presumably instantiate variables, so the re-suspension
    check should be after do_propagate has done it s work.

So I would expect the following pattern:

propagator(Vars) :-
	init_state(Vars, State),
	propagator(Vars, State, _Susp).

propagator(Vars, State, Susp) :-
	do_propagate(Vars, State),
	( ground(Vars) ->
		kill_suspension(Susp)
	;
		update_state(Vars, State),
		( is_suspension(Susp) ->
			true
		;
			suspend(propagate(Vars,State,Susp), ..., Susp)
		)
	).


Wit Jakuczun wrote:
> ... This means that almost all non trivial
> propagators should be called via call_priority/2. This is the only
> way to make propagators atomic.

I plan to implement run-priorities (mentioned in an earlier posting)
for release 6.1.  That would mean woken goals run at high priority
by default, independent of their scheduling priority.


-- Joachim
Received on Mon Feb 16 2009 - 23:40:01 CET

This archive was generated by hypermail 2.2.0 : Thu Feb 02 2012 - 02:31:58 CET