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'".