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

From: Wit Jakuczun <wit.jakuczun_at_gmail.com>
Date: Tue, 17 Feb 2009 22:49:34 +0100
2009/2/17 Joachim Schimpf <jschimpf_at_users.sf.net>:

>>> 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.
>
   The state could be for example a kind of graph that is incrementally
updated during propagation. If I were able to catch each particular
variable's domain change I would not have to use update_state/3
predicate. This predicate is to calculate a state that is synchronised
with Vars domains. In most situations when, entering propagator,
state will not be synchronised.  The states cannot be simply
compared as I create a new state from the old one using information
from Vars.

   This could be solved via recalculation state from scratch. From
an efficiency reasons it is sometimes better not to recalculate, although
it is not always wiser and/or simpler :).

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

Yes, you are right! I am just not the fan of the priorities and treat them
as a simple excuse for my incompetence sometimes :). Nevertheless
I was testing Sicstus and have never got into such problems as with
ECLiPSe.

> 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.
>
And sometimes it is much simpler....

> 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.
>
I will

>
> 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.
Yes exactly. Domains of Vars imply exactly one state. In my case I
calculate a new state from an old one and then propagate using
this new state.

> 2. do_propagate can presumably instantiate variables, so the re-suspension
>    check should be after do_propagate has done it s work.
>
Only during first "call". If there is already suspension activated this
instantiation should call the propagator once again, right?

>> ... 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.
>
That is a very good idea.

Best regards
-- 
[ Wit Jakuczun  w.jakuczun_at_wlogsolutions.com ]
[ WLOG Solutions http://wlogsolutions.com   ]
Received on Wed Feb 18 2009 - 00:02:47 CET

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