[mercury-users] Trailed version arrays?

[Peter Hawkins]

Hi...

I don't suppose anyone has a trailed version array implementation hanging 
around? Backtracking and version arrays don't mix too well... (to the extent 
that varray ^ elem is taking something like 25% of my program's runtime).

Let me explain. I'm playing with constraint solvers. The relevant bits of the 
program look a little like this:

% Constraint network
:- type c_network ---> net(vars :: varray(c_var), ...).

% Constraint variable
:- type c_var	    ---> c_var(domain :: my_c_type, ...).

There are then two predicates:
:- pred propagate(c_network::in, c_network::out) is semidet.
:- pred labelling(c_network::in, c_network::out) is nondet.

Propagate performs constraint propagation, so it repeatedly updates the 
domains of variables. It can fail if a domain becomes empty, otherwise it 
always succeeds deterministically. Propagate will usually access every 
variable domain at least once during propagation.

Labelling performs a backtracking search, calling propagate on each search 
step, backtracking if propagate fails.

However, this has terrible performance. Propagate might be called 1000 times, 
each time accessing/updating 1000 variable domains. This leads to 1000000 
calls to varray^elem, many of which occur after backtracking, and so cost 
linear time themselves.

How could I implement this both efficiently and cleanly?

My first thought was to do this:
:- type c_var	    ---> c_var(domain :: reference(my_c_type), ...).

where reference is Peter Schachte's backtracking modifiable storage type 
(which uses trailing). This would be quicker since the variables themselves 
would not be modified, thus circumventing the problem.

Unfortunately, this means that I have the pleasant task of marking just about 
every predicate in my program impure or semipure.

I'm now tempted to try a version array implementation that understands 
backtracking instead.

Suggestions? How would an experienced mercury programmer approach this 
problem?

=)
Peter
--------------------------------------------------------------------------
mercury-users mailing list
post:  mercury-users at cs.mu.oz.au
administrative address: owner-mercury-users at cs.mu.oz.au
unsubscribe: Address: mercury-users-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-users-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------