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.

An update on Protest (the testing framework that doesn't suck)

Protest (see wiki for more information) is a unit test framework for C++ that is like most other test frameworks, except that it does checks in a innovative way and handles test fixtures really well. I first wrote about Protest here, and since then I've done some more work. Well, actually I rewrote the whole thing.

Why rewriting? Well, the initial solution was a proof-of-concept and not worth spending any effort making production worthy. The rewrite is cleaner, but not as clean as I want it.

Anyway, the version that's in the repository has a proper main function, a memory leak detector, and handles of segmentation faults and similar error. It also has preliminary support for JUnit XML output. None of these features distinguish Protest from the rest of the testing framework pack. The distinguishing feature of Protest is how fixtures and assertions are handled. Here's an example:

suite("my suite") {

  int one = 1; // This is the fixture!

  test("1 should equal 1") {

    check(one == 1);

  } 

  test("1 should be less than 2") {

    check(one < 2) << "What? your compiler is broken";

  }

}

Note that there is only one assert macro, check, which handles all kinds of comparisons. If the check fails, the expression is split into left-hand side and right-hand side before printed.
Also, note how the fixture is setup just as local variables -- this is because fixtures in Protest is local variables. This is much more convenient than class-based fixtures that all (to my knowledge) other test-framework uses

Actually, Protest support class-based fixtures as well. This is done as follows:

struct Fixture { int one() { return 1; } };

suite("my suite", Fixture) {

   test("1 == 1") {

      check(one() == 1);

   }

}
This is where I'm not yet fully happy with Protest -- I'd like to make it possible for the test-case to provide the fixture with arguments. Something along the lines:

struct Fixture {

  int m_value;

  Fixture(int value) : m_value(value) { }

  int value() { return m_value; }

};

suite("my suite", Fixture) {

  test("1 == 1", (1)) { check(value() == 1); }

  test("2 <= 4", (4)) { check(2 <= value()); }

}

That is, the test macro takes optional arguments that is used for initializing the fixture. I'm not fully sure this is possible right now, but I'll give it a go soon.