Why you must know about Prolog

I've head about Prolog many times and I'm sure you have too. It's a general purpose  logic programming language with some very attractive features. The last few days I have experimenting with it and I've gotten a feel for the language but I'm by no means remotely close to fully understand it. I have, however, seen how useful it can be and I well here explain why Prolog is awesome. I will start by explaining Prolog as if it would be a imperative language with some weird syntax and limitations. The example I will use is a simple simulator of a simple instruction set:

1. load Imm, Dst-- loads immediate Imm to register Dst.
2. add Src, Dst-- store the sum of registers Src and Dst in register Dst.
3. mul Src, Dst -- store the product of register Src and Dst in register Dst.

As can be seen this is a very, very small instruction set. Suitably, it will execute on a very very small processor -- it's only storage is it's for general purpose registers r0, r1, r2 and r3. For simplicity of implementing the simulator, each register can hold arbitrarily many bits (as many needed by the value held by the register).

First thing to implement is the register file. The simplest way to implement reading from the register file is like this:

read_rf(r0, rf(R0,  _,  _,  _), R0).

read_rf(r1, rf( _, R1,  _,  _), R1).

read_rf(r2, rf( _,  _,  R2, _), R2).

read_rf(r3, rf( _,  _,  _, R3), R3).

First off, tokens starting with upper case are variables and an underscore represents a variable that is not of interest. Lower case tokens, on the other hand, represent things that must be exactly matched.

So, for instance, the first line tells the Prolog compiler how to read register r0, and that a register file consists of four values bundled together into something called an rf. It also tells that when reading r0, all values but the first one in rf is not of interest. Finally, the result of reading the register file is put into the last parameter, in this case R0. The three remaining lines can be understood in similar fashion. This looks a bit like a function declaration, but it is actually also the implementation. Now, let's continue with writing to the register file. This is done as follows:

write_rf(r0, rf( _, R1, R2, R3), V, rf( V, R1, R2, R3)).

write_rf(r1, rf(R0,  _, R2, R3), V, rf(R0,  V, R2, R3)).

write_rf(r2, rf(R0, R1,  _, R3), V, rf(R0, R1,  V, R3)).

write_rf(r3, rf(R0, R1, R2,  _), V, rf(R0, R1, R2,  V)).

The first line here tells the Prolog compiler what it means to write to register r0 of the register file rf which consists of four values (of which the first is not of interest). The variable V represents the value to be written, and it is put into the first position of the last parameter (the rf( V, R1, R2, R3)-part). Ok, now we continue with defining the instructions:

instruction(load(Imm, Dst), InRf, OutRf) :-

    write_rf(Dst, InRf, Imm, OutRf).

instruction(add(Src, Dst), InRf, OutRf) :-

    read_rf(Src, InRf, Value0),

    read_rf(Dst, InRf, Value1),

    Sum is Value0 + Value1,

    write_rf(Dst, InRf, Sum, OutRf).

instruction(mul(Src, Dst), InRf, OutRf) :-

    read_rf(Src, InRf, Value0),

    read_rf(Dst, InRf, Value1),

    Prod is Value0 * Value1,

    write_rf(Dst, InRf, Prod, OutRf).

This tells the compiler that the definition of load(Imm, Dst) is to write Imm to the register Dst in the register file. Furthermore, the definition of add(Src, Dst) is to read registers Src and Dst and write the sum to register Dst. The definition of mul is analog to add.

Ok, now let's try to run this to get feeling of what Prolog can do. The following is the output from the interactive prompt provided by SWI Prolog.

?- instruction(load(10, r0), rf(1, 1, 1, 1), OutRf).
OutRf = rf(10, 1, 1, 1).

?- instruction(add(r1, r0), rf(2, 2, 2, 2), OutRf).
OutRf = rf(4, 2, 2, 2).

?- instruction(mul(r1, r0), rf(3, 3, 3, 3), OutRf).
OutRf = rf(9, 3, 3, 3).

Ok, that's seems reasonable, right? Prolog tells us that loading 10 to register r0 of a register file consiting of 1, 1, 1, 1 results in a register file consisting of 10, 1, 1, 1. It tells us similar thing about the add and mul instruction. But nothing of this is particularly unique to Prolog, is it? We could have done this in any other language. But let's continue. Now we'll do a bit more symbolic things with Prolog:

?- instruction(load(Imm, r0), rf(0, 0, 0, 0), OutRf).
OutRf = rf(Imm, 0, 0, 0).

?- instruction(load(10, Dst), rf(0, 0, 0, 0), OutRf).
Dst = r0,
OutRf = rf(10, 0, 0, 0) ;
Dst = r1,
OutRf = rf(0, 10, 0, 0) ;
Dst = r2,
OutRf = rf(0, 0, 10, 0) ;
Dst = r3,
OutRf = rf(0, 0, 0, 10).

Now it starts to get fancy, isn't it? The first example shows that Prolog can load a symbol to register r0. The second example show that Prolog also understand what it means to load 10 to the symbolic register Dst; it either means loading to r0, r1, r2, or r3 and it also tells us what the resulting register file is in each case. We now continue to show Prolog's symbolic powers even more:

?- instruction(load(Imm, r0), rf(0, 1, 2, 3), rf(10, 1, 2, 3)).
Imm = 10.

Now this is cool. Given a input and and output register file (here, rf(0, 1, 2, 3) and rf(10, 1, 2, 3)) Prolog can figures out the value of Imm required in the load instruction. Let's see what more it can do:

?- instruction(Instr, rf(0, 1, 2, 3), rf(3, 1, 2, 3)).
Instr = load(3, r0) ;
Instr = add(r3, r0) ;
false.

Awesome right? Prolog actually figures out what instructions that given rf(0, 1, 2, 3) results in rf(3, 1, 2, 3). Try to do that in a normal imperative language... oh, right, we can't do that. And this brings me to (one of) the point(s) of Prolog: given a solution from going from A to B it also (in some cases, like here) gives you a solution for going from B to A. For example, if we wrote an assembler for the above instruction set in Prolog we would automatically get the disassembler.