Decreasing salaries with addition

There are some parts of my PPDP 2009 invited talk that didn't make it into the short paper for that talk. In particular, I played a bit with the feature interaction of traversal (SYB) and using predicates in different modes. The use of multi-mode predicates is one of the exciting aspects of logic programming. (It is somewhat disputed how crucial or useful it is, but it is impressive/expressive anyhow.) For instance, beginners are always surprised to see that one can use append/3 to both .... well ... append but also take apart lists.

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)

everywhere(T,X,Z) :-
 gmapT(everywhere(T),X,Y),
 apply(T,[Y,Z]).

% One-layer traversal

gmapT(T,X,Y) :-
 X =.. [C|Kids1],
 map(T,Kids1,Kids2),
 Y =.. [C|Kids2].

% "Make transformation"

mkT(T,X,Y) :- choice(T,id,X,Y).

% Left-biased choice

choice(F,G,X,Y) :-
 apply(F,[X,Y]) ->
     true
   ; apply(G,[X,Y]).

% Identity

id(X,X).

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.

add(X,Y,Z) :-
( \+ 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:

gmapT(T,X,Y) :-
 var(X), var(Y),
 Y = X
;
 \+ var(X),
 X =.. [C|Kids1],
 map(T,Kids1,Kids2),
 Y =.. [C|Kids2]
;
 var(X), \+ var(Y),
 Y =.. [C|Kids2],
 map(T,Kids1,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!).

everywhere(T,X,Z) :-
 Apply = apply(T,[Y,Z]),
 Recurse = gmapT(everywhere(T),X,Y),
 ( var(X), \+ var(Z) ->
     Apply, Recurse
   ; Recurse, Apply ).

That's it, we can do backward traversal and hence decrease salaries with incSalary/2.

PF