Backtrackable Mutable Objects = Bad Style?

Appeared in Volume 9/3, August 1996

Keywords: backtracking.

rwab1@cl.cam.ac.uk
Ralph Becket
15th March 1996

I'm writing a suite of modules that have to work together, namely an abductive equivalential translation unit (good name that), an abductive theorem prover and a planner. In each case there is a lot of context to be passed around, both internally and between modules. And in each case, I am only ever interested in the most up-to-date version of the context. In order to make life simple I've opted to hide all the context in one structure, so code looks something like this:

do_something(DataIn, DataOut, Context)

where:
Context = ctxt(Plan, Assumptions, Constraints, etc.)

and I have a module which manipulates the context as required.

Now, I have elected to make each part of the context a backtrackable mutable object (a facility provided by Sicstus Prolog, amongst others) so I don't have to write code of the form:

do_something(DataIn, DataOut, ContextIn, ContextOut)

While this latter style is logically cleaner, it also makes the code much harder to read and debug. As I am only ever concerned with the most up-to-date version of the Context, I feel I am justified in using mutable objects, since the increase in readability is well worthwhile (and there are big red warning signs all over it pointing out that context is mutable). Moreover, because some parts of the context structures are free variables (e.g. I have a connectivity matrix which is constructed incrementally by variable unification in an array of functors), not all context updating predicates need to pass out an updated version (as in the line of code above). Now everything takes precisely one context argument.

Question: am I really justified in taking this approach?

fjh@mundook.cs.mu.oz.au
Fergus Henderson
17th March 1996

My approach in this situations has been to use DCG notation. Instead of writing:

do_something(..., Context0, Context) :-
    do_this(..., Context0, Context1),
    do_that(..., Context1, Context2),
    call_something_unrelated(...),
    do_the_other(..., Context2, Context).

I write:

do_something(...) -->
    do_this(...),
    do_that(...),
    { call_something_unrelated(...) },
    do_the_other(...).

This approach is as you say "logically cleaner" than using backtrackable mutable objects, but still avoids the notational disadvantage of having to spell out all those contexts all over the place.

thomasl@kim.csd.uu.se
Thomas Lindgren
16th March 1996

Personally, I thread all mutables through the program, when I use them. The reason is that it is easy to change the representation to something declarative when needed. This means that the program is easier to change and easier to debug (sometimes). For instance, one can add invariant checks to the code to see that input and output states correspond on exit.

Your second problem was that you need twice the arguments to the predicate to stay declarative. I have the same problem with most of my programs, and have attacked it as follows:

Use extended DCG:s or HAGs (as in BinProlog). I have used extended DCG:s, but found it a bit too difficult to debug (the extra arguments appear in the code you have to debug, and it's hard to relate them to the source code).
Pass all extra state arguments wrapped in a tuple. This is actually quite useful because (a) you can define portray/1 to hide the tuple from view, or show it the way you want it to be shown, and (b) you can easily add and subtract extra state arguments. The usefulness of these points is not to be underestimated. Plus, you stay declarative.

This is more or less the psi-term/records approach that some logic languages use, though less flexible.
Sacrifice some performance for maintainability, and recompute the information from time to time. For instance, various passes over data in my code nowadays tend to take just an input and an output argument. Even though the passes could share some information between them, I tend to recompute it. This means it is easier to debug and reuse the code.

To return to point 2, I specify the abstract datatypes like:

gen_cfa_state(File) :-
    exchgen_to_file(exch_cfa,get_cfa,set_cfa,initial_state_cfa,
                    [cut_vars:[],
                     constr_lst:L-L,
                     options:[]
                    ],File).

(I.e., names of accessors, etc., and a list of the state parts.)

Then I access the state like:

...
get_cfa(cut_vars,S0,S1,CutVars),
set_cfa(cut_vars,S1,S2,[CutV|CutVars]),
...

And of course, it is easy to autogenerate getting and setting lists of state variables. Note the presence of 'exchange' in the code below, which is useful to short out get-then-set of states.

A program finally generates the state accessors given this info, and the generated code then looks like:

% initial state %
initial_state_cfa(s([],A-A,[])).

% exchange contents %
exch_cfa(cut_vars, s(A,C,D), s(B,C,D), A, B).
exch_cfa(constr_lst, s(C,A,D), s(C,B,D), A, B).
exch_cfa(options, s(C,D,A), s(C,D,B), A, B).

% get/set contents %
get_cfa(C, B, A) :-
    exch_cfa(C, B, _, A, _).

set_cfa(D, B, C, A) :-
    exch_cfa(D, C, A, _, B).

I think SICStus nowadays could make this even more efficient with goal_expansion/2, but I haven't looked at that option too closely. Of course, one could always use mutables to the same effect above, but I shan't argue that point :-)

Ralph.Becket@cl.cam.ac.uk
Ralph Becket
21st June 1996

I no longer feel that backtrackable mutable objects are a valid style, for the reasons given by the respondents.

In SICStus Prolog speed trials, backtrackable mutable objects are over 20% slower than the cleaner approaches.