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,

**scenario for the sake of the argument:***recession-inspired*- 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

## No comments:

## Post a Comment