So I considered the question how to use such multi-modeness, if at all, perhaps even usefully, in the context of traversal programming. Here, we would expect traversal predicates to serve the normal forward direction (traverse first argument, compute second argument) and the unusual backward direction.
Let's consider the following, recession-inspired scenario for the sake of the argument:
- We certainly know how to increase salaries (say by 1 $) everywhere.
- However, there is pressure that we need to decrease salaries lately.
- We wish to run an increasing traversal backwards to decrease salaries.
Let's start with the increase-only traversal.
incSalary(X,Y) :- everywhere(mkT(incSalary_),X,Y).
incSalary_(salary(S1),salary(S2)) :- add(S1,1,S2).
add(X,Y,Z) :- Z is X + Y.
everywhere/3, mkT/3 are defined in a straightforward manner:
(See the PPDP 2009 paper for details.)
% Transform everywhere (bottom-up)
% One-layer traversal
X =.. [C|Kids1],
Y =.. [C|Kids2].
% "Make transformation"
mkT(T,X,Y) :- choice(T,id,X,Y).
% Left-biased choice
The above development will not be able to decrease salaries (by traversing "backwards"). Quite obviously, we need an add/3 predicate that can go backwards. That's easy enough. The following revision of add/3 can cope with any combination of 2 argument positions being instantiated with numbers.
( \+ var(X), \+ var(Y), Z is X + Y
; \+ var(X), \+ var(Z), Y is Z - X
; \+ var(Y), \+ var(Z), X is Z - Y
We need to do a few more things before backward traversal works. In particular, one-layer traversal is not prepared to deal with an uninstantiated first argument. There are actually two reasons for an uninstantiated, first argument to make sense. Reason 1 is that we might be traversing terms with logical variables. Reason 2 is related to our current endeavor: backward traversal with the 2nd argument being instantiated and the first one being variable. So here is our blow that resolves both issues:
Y = X
X =.. [C|Kids1],
Y =.. [C|Kids2]
var(X), \+ var(Y),
Y =.. [C|Kids2],
X =.. [C|Kids1].
However, this is still not enough. We also need to make fit the traversal scheme everywhere/3. We need to adjust the sequential order of the body of everywhere/3 depending on instantiation. Please note that the resulting traversal is still to be considered a bottom-up traversal (which is good news!).
Apply = apply(T,[Y,Z]),
Recurse = gmapT(everywhere(T),X,Y),
( var(X), \+ var(Z) ->
; Recurse, Apply ).
That's it, we can do backward traversal and hence decrease salaries with incSalary/2.