PPDP 2009 over and Prological SYB code goes live

Just tried to send an email to what I thought would be the cafe mailing list of the Association of Logic Programming (ALP). My message bounced. Sigh! Anyway, here is the message and below you also see the content of the README file for the tiny code distribution for scrap[p]ing boilerplate prologically.

From: Ralf Laemmel rlaemmel@gmail.com

To: Alp-cafe-request@babel.ls.fi.upm.es

Date: Thu, 10 Sep 2009 22:57:11 +0100

Subject: post-PPDP 2009 greeting

Not sure whether this mailing list is actually working (because I haven't seen any traffic since June when it all started) but I thought it couldn't hurt to send a short post-PPDP 2009 greeting. António Porto, Francisco J. López-Fraguas, Pedro Quaresma, Ana Paula Tomás, and their collaborators have put together a great conference event. The program was really packed; perhaps even a bit stressful :-) I would have loved to interact a bit more during additional breaks and panels.

For what it's worth, I have uploaded the SYB sources for my invited talk to a google code repository.

http://code.google.com/p/strafunski/source/browse/#svn/trunk/ppdp09

Regards,
Ralf

README follows

These are sources that I release with my PPDP 2009 invited talk.
Please understand that this is *illustrative* code.
I have merely sketched certain aspects.
It is really just illustration for a talk!
It may be useful though.

Here is quick inventory of this file system:

shared: basic lib functionality used by several "experiments"
* holp: higher-order logic programming convenience
* syb: very little to be shared of SYB among experiments
* lists: (mainly higher-order) list processing
* meta: metaprogramming convenience
* vars: operations on lists/sets of logical/nonground variables
* msft: test data

experiments: experiments or illustrations used in the talk
* basic: the most basic SYB experiment
* backtracking: illustration of backtracking traversal
* nonground: illustration of traversal of nonground terms
* bidirectional: crazy inquiry into multi-mode traversal
* optimized: a generative and optimized model of SYB

All the experiments consist of two parts:
* lib: all library (generic) functionality
* app: specific illustrations (using msft typically)

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