The hunt for a generic sort

WikiCFP is quite useful for collecting together information about conferences you may be interested in submitting to. It even has a nice google calendar view, where you can see the deadlines of your selected conferences coming up. However, you may need to have additional information about each conference, so it's conceivable that a small database may be a good idea here.

We will use Prolog as our database engine, not only because we absolutely love it, but because XSB offers a very generic sorting routine, called parsort/4:

parsort(+L1, +SortSpec, +ElimDupl, ?L2)

  - L1 is the list we want to sort

  - SortSpec is a sorting specification; can be asc(I) or dsc(I), where I is an argument number. So asc(1) means sort in ascending order with respect to the first argument of the terms in List, desc(3) means sort in descending order with respect to the third argument of the terms in List e.t.c.

  - if ElimDupl is non-zero, then the duplicate elimination is performed before returning the output, and if it's zero duplicate elimination is not performed

  - L2 is the variable that holds the final result.

Okay, so let's start with defining our facts. We will use a separate source file that will contain information about the conferences that we are interested in, stored as Prolog facts of the form

conf(ShortName,FullName,Dates,Deadline,Website).

The first thing we need is a prediate that will take as input a list of conf/5 facts and print out their contents in a pretty way:

print_list(PD,PW,[pconf(Name,Descr,When,Deadline,Web)|Confs]) :-
        write(Name),
        atom_length(Name,NLen), T1 is 10 - NLen, tab(T1),
        ( PD == 1
        -> write(Descr), atom_length(Descr,DLen), T2 is 80 - DLen, tab(T2)
        ; true
        ),
        write(When), atom_length(When,WLen), T3 is 20 - WLen, tab(T3),
        write_deadline(Deadline), tab(2),
        ( PW == 1
        -> write(Web), atom_length(Web,WeLen), T5 is 20 - WeLen, tab(T5)
        ; true
        ),
        nl,
        print_list(PD,PW,Confs),
        fail.

I call the technique used here "print-by-failure"; the call to "fail" in the end of the definition of print_list/3 ensures that things will continue to get printed out until the list is empty. Deadlines are represented by terms of the form deadline(Month,Day,Year). We want to print out information just for the conferences for which the deadline hasn't passed yet, so the following predicate is also useful:



before(today(M,D1,Y),deadline(M,D,Y)) :-
        D1 < D, !.
before(today(M1,_D1,Y),deadline(M,_D,Y)) :-
        M1 < M, !.
before(today(_M1,_D1,Y1),deadline(_M,_D,Y)) :-
        Y1 < Y.

And last but not least, the predicate that will generate a list containing the information needed from the conf/5 facts, print out a nice table and then call print_list/3 to do the rest:



show_confs(PD,PW) :-
        findall(pconf(Name,Descr,When,deadline(M,D,Y),Web),
                ( conf(Name,Descr,When,deadline(M,D,Y),Web), datime(datime(Y1,M1,D1,_,_,_)), 
                  before(today(M1,D1,Y1),deadline(M,D,Y)) ),
                List),
        write('Name'), tab(6), %10
        ( PD == 1
        -> write('Description'), tab(69) % 80
        ; true
        ),
        write('Date'), tab(16), % 20
        write('Deadline'), tab(8), % 16
        ( PW == 1
        -> write('Web'), tab(17) % 20
        ; true
        ),nl,
        writeln('------------------------------------------------------------------------------------------------------------------------------------------------------'),
        parsort(List,[asc(4)],1,SList),
        print_list(PD,PW,SList).

The nice thing with parsort/4 is that we can change the way our output will look like without any change to the sorting routine at all! The only thing we need is a different specification of the sorting specifications. Here, for example, I want to sort in ascending order with respect to the deadline of each conference, which is pretty handy. Try to do all this with 50 lines of C code... :)

Drawing Prolog-generated graphs with graphviz

While I was TAing for a "Computing with Logic" course, one of the assignments had to do with graphs and computing the transitive closure over them with various ways. There was a question in the assignment asking students to identify the form of each graph described. Most of them did a very good job in either using simple text to "draw" the graph, or either use one of the many available software that helps with this kind of stuff. However, drawing the graph yourself means that you actually understand the form. What if you have some really complex graph specification in Prolog; how can you draw it without understanding how it looks like?

Well, the answer is pretty much straightforward; just as when you use writeln's to print out helpful information while the graph is being generated, why don't just output that exact information in a more "concrete" manner which can be parsed by graphviz, and let that draw the graph for you?

And so I set programming this small idea. It ended up not being to painful to do; it was a good exercise, and the result is quite pretty :)

First, here is the specification of three distinct graphs: trees, cycles and something called a "dline":

size(cycle,8).
size(tree,4).
size(dline,12).


cycle(M,0) :- size(cycle,M). % size(M) 
cycle(I,I1) :- 
          size(cycle,M), % size(M) 
          0 =< I, I < M, I1 is I + 1. 

tree(I,I1) :- size(tree,M), % size(M)
          0 =< I, I < M, I2 is I * 2, I1 is I2 + 1. 
tree(I,I1) :- size(tree,M), % size(M) 
          0 =< I, I < M, I2 is I * 2, I1 is I2 + 2. 

dline(I,I1) :- size(dline,M), % size(M) 
          0 =< I, I < M, 0 is I mod 4, I1 is I + 1. 
dline(I,I1) :- size(dline,M), % size(M) 
          0 =< I, I < M, 0 is I mod 4, I1 is I + 2. 
dline(I1,I2) :- size(dline,M), % size(M) 
          I is I1 - 1, 0 =< I, I < M, 0 is I mod 4, I2 is I + 4. 
dline(I1,I2) :- size(dline,M), % size(M) 
          I is I1 - 2, 0 =< I, I < M, 0 is I mod 4, I2 is I + 4.

All right, now that we have our graph specifications, let's see how can we generate a valid graphviz source code and let it draw our graphs. The first thing we need to do is transform a list of generated edges into valid graphviz code:

draw_graph(_Dest,_Shape,[]).
draw_graph(Dest,Name,[Shape|Edges]) :-
        functor(Shape,Name,2),
        arg(1,Shape,X),
        arg(2,Shape,Y),
        write(Dest,'"'),write(Dest,X),write(Dest,'"'),
        write(Dest,' -> '),
        write(Dest,'"'),write(Dest,Y),write(Dest,'"'),writeln(Dest,''),
        draw_graph(Dest,Name,Edges).

The variable Dest holds the IOhandler for the file we want to write our graphviz code in. Name is the name of the graph (cycle/tree/dline) and the list contains elements of the form [name(1,2),name(2,3),...], which means that for the graph "name" there is an edge from vertex 1 to vertex 2, from vertex 2 to vertex 3 and so on. So we just split each element into a functor name and its arguments using functor/3 and arg/3, and then just output everything in graphviz syntax, i.e. lines of the form "1" -> "2" e.t.c.

Next, we need a predicate that will generate the list of edges we talked about above for a given graph name, and call draw_graph/3 to output the graphviz code:

draw(Dest,Name) :-
        size(Name,M),
        get_list(M,[],List), 
        functor(Shape,Name,2),
        arg(1,Shape,X),
        findall(Shape,(member(X,List),Shape),L), writeln(L), 
        draw_graph(Dest,Name,L).


get_list(0,List,[0|List]).
get_list(M,List1,List) :- M > 0,
        M1 is M - 1,
        get_list(M1,[M|List1],List).



Again Dest holds the IOhandler for the output file, and Name is a valid graph name (cycle/tree/dline). get_list/2 just generates a list of numbers starting from M and ending at 0. We then construct a term of the form "name(From,To)" that will be bound to the facts generated by our specifications for graphs from above, thus generating in L the list of needed edges.

The final predicate we need is the one that will do all the file opening/closing, graphviz code generating, and will also run graphviz to draw each graph:



draw1(Fil) :- writeln(Fil),
        atom_concat(Fil,'.gv',File), 
        atom_concat(Fil,'.png',Out),
        open(File,write,Dest),
        writeln(Dest,'digraph G {'),
        draw(Dest,Fil), 
        writeln(Dest,'}'),
        close(Dest),
        atom_concat('dot -Tpng ',File,Cmd1),
        atom_concat(Cmd1,' > ',Cmd2),
        atom_concat(Cmd2,Out,Cmd),
        shell(Cmd).

File holds the name of the output file (which must be a valid graph name as discussed above). We open 2 separate files; the one in which we will put the graphviz code (ending in .gv), and the final PNG picture file. I used atom_concat/3 to concatenate the necessary strings to create a valid graphviz command, and just call it with shell/1. That's pretty much it! Now you can just fire XSB, load the source file containing the code we wrote here, and ask for draw1(tree), draw1(cycle) or draw1(dline). You'll then get some really pretty pictures from graphviz :)