Painting graphs

Some time ago, a question was asked in StackOverflow about how we can use Prolog to compute the (or a single) coloring for a graph. After some thought, I came up with the following solution, which of course I am not really sure is correct, although it seems to give the correct results on the cases I looked at.


Let's start with describing our graph; we will use edge/2 facts to represent eges. A fact edge(a,b) means that there exists an edge between vertices a and b, as usual. Similarly for the colors, we will use color/1 to represent the available colors for our...painting :) So the initial database looks like this:

edge(a,b).
edge(b,c)
edge(b,d).
edge(c,d).

color(blue).
color(red).
color(green).




And now, for the real work :) We will represent the final coloring as a list of Vertice-Color pairs, where of course there should be no more than 1 pairs with the same vertex as the first element. As a base case, we will use what intuition says: vertex a gets a color c if there is no edge going out of a, assuming that we have colored the path(s) leading to a. In Prolog, this gets translated as:


coloring([V-C]) :- 
 color(C), 
 \+ edge(V,_).



Next, the recursive case. We will append a V-C pair on the front of the coloring list, if we can paint V with a color C, there is an edge from V to another vertex V1, and coloring the rest of the graph yields a color to V1 different than C. This is a brute-force algorithm; it tries to assign all the possible colors to vertices, until it finds a particular coloring that satisfies all the constraints. Translated in Prolog:


coloring([V-C,V1-C1|Coloring]) :-
        color(C),
        edge(V,V1),
        V \== V1,
        coloring([V1-C1|Coloring]),
        C1 \== C. 



Finally, we need a way of getting all the possible colorings for a graph. That's easy, using the findall/3 predicate. It works as follows; given an answer pattern in the first argument, calls the goal given in the second argument, and returns a list with all the results in the third. Pretty cool, huh? :)


:- import length/2 from basics.


colors(X) :-
        coloring(X),
        findall(V,edge(V,_),List),
        length(List,Len),
        length(X,Len). 



We just need one more thing; to check that the length of the solution is actually as long as the number of distinct vertices of the graph (we don't want solutions that only give colors to some of the vertices, right?). And that's it! Just call 


|?- colors(X). 


from your favorite Prolog interpreter, and you'll get all the possible colorings for your graph! Feeling like Picasso already? :)

The art of Term Expansion

One of the features I most love about Prolog, is the built-in availability of "Term Expansion". That means that the programmer has the power to change code on-the-fly, as it's loaded into the compiler. It's basically a preprocessing step (in XSB I think it's the last preprocessing step before actually feeding the code into the compiler), and the user can enable it whenever they wish. Actually, DCG's in Prolog get handled using term expansion; remember that in DCG's, we have to add 2 more arguments to each head predicate.


Okay, now that we know what Term Expansion is, let's see how we can use it. In XSB (and I think in every other commercial Prolog compiler), there's a term_expansion/2 builtin, which describes how the first argument should be transformed into the second before it gets fed into the compiler. That means that we won't have access into the old version of our code after term expansion, and that's fine. If we need the old form of the code as well, we can always assert it dynamically :)


I usually start off my term-expansion-preprocessors with the following assertion:


:- assertz((term_expansion(X,Y) :- !, do_term_expansion(X,Y))).


That means that this rule will be asserted last (in the end of the database). So,  term_expansion/2 will automatically be called while loading the file, and control will be handed to our  do_term_expansion/2  routines. Next, let's handle the "end of file" case. Luckily, XSB has a builtin predicate  end_of_file/1  which we can write at any point of our program, and will signal...well...the end of the file :) We want our preprocessing to stop when the end of the file is reached, so voila:


do_term_expansion(end_of_file,_) :- !, (import member/2 from basics),
writeln('end of file!'), fail.


In this case, I just want to import something from the basics module, write that the file has ended, and fail. Now for the interesting part. Firstly, suppose the original program contains static facts of the form  uses(A,B) and distr(A,B). Let's just assert them in our post-processed version:


do_term_expansion((uses(A,B)),_) :- !, assert(uses(A,B)).
do_term_expansion((distr(A,B,C)),_) :- !, assert(distr(A,B,C)).



Now these will be available to the post-processed version. Finally, let's say we want to just throw away the body of each clause (not a very useful transformation huh? :) ); that's easily done as follows:

do_term_expansion((Head :- Body), (Head :- true)) :- !,


And that should work :) You can do a bunch of helpful things with Term Expansion; like DCG argument-adding (that I mentioned before). I used Term Expansion in a project for adding probabilities in Well-Founded Semantics (where we wanted to add extra arguments in each predicate - sounds familiar? :) ).



Moral of the day: Use term expansion. It's (sometimes) easier than writing regular expressions in Perl or sed!

Hello World!

Okay, so I have been thinking for some time to start a blog, and write about what bothers me, what keeps me up at nights, what keeps me sleeping at days... :)

I guess I'll start with the title; append/3 is the first Prolog predicate I actually understood how it works. And believe me when I say "there became light".


append([],L,L).
append([X|L1],L2,[X|L3]) :-
    append(L1,L2,L3).




append/3 appends its second argument in the end of its first, and returns the result in the third argument. But not just this. Let's first say we want to concatenate two lists. So, we'll call append/3 with arguments 1 and 2 bound, and 3 unbound:

| ?- append([1,2,3],[4,5,6],L).

L = [1,2,3,4,5,6];

no

Cool, so it does what we want it to do. How about something...kinky? :) Say we want to call append/3 with arguments 1 and 2 unbound (i.e. replaced by variables), and argument 3 bound. Then, magic kicks in, and argument 3 is split into all the possible lists that when concatenated together give that as a result:



| ?- append(X,Y,[1,2,3]).

X = []
Y = [1,2,3];

X = [1]
Y = [2,3];

X = [1,2]
Y = [3];

X = [1,2,3]
Y = [];

no



That "magic" is the power of Prolog, and computer science people call it "non-determinism". It means that one Prolog query can have multiple answers. And that's just the beginning of it :)




Prolog uses assign-once variables; that means that once a variable gets a value, that value can't change throughout the execution of a program. You'd ask yourself why on earth can something like this be useful. And I'll just reply with a quote: "In Logic, variables are also assign-once; you can't change the value of a logic variable during the evaluation of a logic formula. And since Logic has been around long before Programming Languages were, you can see who messed-up the meaning of 'variables'".