Prolog -- A Personal Revival

λ June 20, 2019
Tags: prolog, mercury

As mentioned before, I first learned GNU Prolog back in 2012, had a flurry of creativity and productivity with it, click to follow the link to the GitHub repo…

Over the years I tried to remain with it (GNU Prolog) but it has become a little unmaintained IMO and the last time I tried to build it it had issues and so I moved to SWI Prolog which is an amazing free system. If you are considering Prolog or have to because it’s on your college course then check it out.

At the end of this article I will list some great book references and web references to get you started on the very very satisfying journey that is learning to think differently with prolog! You won’t regret it, in fact it’s even more profound than learning functional programming IMHO. And I know both.

Mercury!

I think the reason for this post is that, having decided to really try to learn to use Mercury, it has re-awakened my interest in Prolog again. I’ve used Haskell as much as I can for things but always in the back of my mind there was that itch that needed scratching!

And…back to Prolog…

With everything else going on around me at the moment, I will now be adding Prolog to my “top mind” list; things I like to keep in mind every day so, if you are interested in Prolog and fancy giving it a go, I just might be able to keep you interested.

A Brief History of Prolog

Basically, it’s pretty old! From the venerable Wikipedia page for Prolog

The language was first conceived by Alain Colmerauer and his group in Marseille, France, in the early 1970s and the first Prolog system was developed in 1972 by Colmerauer with Philippe Roussel.

If you are familiar with “programming paradigms” then you may well have heard of “procedural”, “object oriented” and “functional”…well, Prolog fits into another different paradigm, “logical”.

Live Long and Prosper

Although Prolog is “logical”, it’s not actually Vulcan technology although sometimes reading the older books I have it feels like it! The header image on this page is in fact my entire collection of Prolog books I’ve picked up since 2012 and they are all still pretty good reads.

Why I like Prolog

Unless you have actually tried to learn Prolog, it’s kind of hard to put it into words, especially if all that you know is imperative programming. Having been a functional programming convert for at least a decade, some things from that paradigm are present in Prolog, most notably I guess that concept of using recursion as the only looping construct unless an implicit map or fold is used.

Unification

Where to start?! Unification and back-tracking are the two most fundamental things you need to get your head around if you are to get along with Prolog. The first concept, unification, is essentially the process of trying to make two things match each other. Given a left hand side and a right hand side of the unification operator =, the run-time will try to see if in fact they can be “unified”. It does this through a series of simple steps which are repeated recursively until the process fails or succeeds. This means it can be used with simple variables or deeply complex nested data structure with the same ease.

I won’t attempt to explain it here, it’s been done better

Back-tracking

In a nutshell, back-tracking is pretty much what it sounds like. As the Prolog engine works through each part of a predicate, trying to prove it is “true” (it ‘succeeds’), it will look in its predicate database (essentially your code) trying to find something that answers true for the given inputs. If it finds such a match it moves on to the next predicate. This is why , is read as AND. Because this line AND the next AND the next etc must all succeed for your predicate to succeed. If during the execution of a predicate, a sub-predicate fails, it looks for another match and another until giving up and causing the predicate under execution to fail.

This is a good YouTube video explanation of it: prolog backtracking 2

Two way operation

One of the things that struck me early on was the two-way nature of predicates; in a traditional imperative language, you might have two functions for translating a character from upper-case to lower-case or vice-versa, whereas in Prolog you use the same predicate but you pass in the thing you have and the thing you want as a value and an unbound variable, here is Java:

class Main {
  public static void main(String[] args) {
    char upperCased = Character.toUpperCase('f');
    char lowerCased = Character.toLowerCase('F');
    System.out.println(upperCased);
    System.out.println(lowerCased);
  }
}

And the equivalent GNU Prolog code to do the conversion would be:

lower_upper(f, Result).
lower_upper(Result, F).

Basically, the “unknown” (unbound) variable result will be “unified” with the correct character…because, in trying to “solve” or “prove true” the predicate, it will know how to look for the correct character. The reality is that functions like this that are core, are probably just calls to the underlying libc on your platform, for efficiency reasons.

You will find this everywhere in Prolog. Because of the way that it uses back-tracking and choice-points it can find “a solution” to the “query” that you posed it. Get used to thinking like that.

Things that hurt in Prolog

Once you start writing more than a few lines of code, you get hit by problems that appear very daunting at first. This is why I would always recommend SWI Prolog as it has one of the best debuggers I’ve ever seen, never mind that it’s for Prolog.

Failure

Failure always hurts but when you have a Prolog predicate that looks like this, and knowing that , is read as AND,

do_something(Filename, Output) :-
    open_the_file(Filename, Handle),
    process_the_file(Handle, Output),
    close_the_file(Handler).

You learn to read it as "For do_something to be true (i.e. to succeed) it has to be true that open_the_file succeeds AND process_the_file succeeds AND close_the_file succeeds. Iff (if and only if) those three succeed will do_something also succeed. Note that the Output from the processing predicate is the the last variable in the signature. This is how you return values from Prolog predicates. There is no return value as such. You could think of it as every predicate returns a boolean and that will get you so far into it for a while I guess but it’s not what’s going on.

The problem is that any one of those could fail and you won’t know which one it was unless you step through it. If you called that from the REPL and all it says is “false” then did the file not exist? Did the processing fail? Did it fail to close the file?? Mercury somewhat alleviates this my forcing the developer to state whether or not a predicate is expected to always succeed, might succeed etc and then at compile time it analyses the code and politely tells you that it thinks you’ve written code that might cause a silent failure at run-time because you have not actually covered all bases. It usually comes down to having an if-then-else to handle something but not always.

The Output variable beings me nicely to…

Threading of state variables

Or just variables in general. Mercury treats IO such that every use of a function that “modifies the world” returns a new instance of the IO state, and if you want your output to come out in the order you think it should, you have to use that mew state for the next IO call, ad nausea and it can get very very messy. A contrived Prolog example might be something like this, see how we call predicates and chain through the result of one into the next?…

my_pred(In, Out) :-
    process_a(In, Out0),   % process In generating Out0 on success
    process_b(Out0, Out1), % turns Out0 into Out1 on success
    process_c(Out1, Out2),
    process_d(Out2, Out3), % finally we go one more and not that
    process_e(Out3, Out).  % the output is Out, the 2nd parameter.

This is ugly, no way around it? Yes! In Mercury there is the concept of a threaded state variable which makes this all go away! Stealing the example from that page:

main(IO0, IO) :-
    io.write_string("The answer is ", IO0, IO1),
    io.write_int(calculate_answer(), IO1, IO2),
    io.nl(IO3, IO).

%% using state variable syntax one could write

main(!IO) :-
    io.write_string("The answer is ", !IO),
    io.write_int(calculate_answer(), !IO),
    io.nl(!IO).

The compiler will automatically expand !IO into the correct sequence of variables for you. I look forward to learning more about this very soon.

Enter, “Mercury”

As I have mentioned before, a few years ago I blogged about my “perfect” language, something between Prolog and Haskell and at the time I had no idea about the existence of Mercury!

Mercury attempts to remove and / or highlight to the developer during the compilation phase all of those things that would have a typical Prolog developer scratching his head and reaching for the debugger. SWI has a most excellent graphical debugger.

Determinism, Modes and Types.

These are the things that set Mercury apart from Prolog. Right now, with less than 20 hours of exposure to mercury I am only just getting used to the ideas it present but I’ve already written some little test programs and I will soon be writing a series of posts on how I progress. I have set myself a lofty initial goal which I sincerely hope to achieve, at least in part as I am terrible for being distracted by the next shiny thing to learn!

Resources

There are some pretty excellent resources out there and some pretty generous people out there too. I would like to just mention some people whom I’ve had the pleasure of interacting with over the years mostly through forums but also directly (GNU Prolog’s creator no less) as well.

Danial Diaz

Or “Professor Diaz” as I liked to call him. He created GNU Prolog and it was that distribution that kept me hooked for so long, inspired me to write quite a lot of code (see my github pages) and eventually outgrow it and move on to SWI Prolog.

Jan Wielemaker

Jan is the original creator of SWI-Prolog. There are many versions of Prolog out there but ultimately, after learning GNU Prolog I eventually outgrew it and SWI was there, ready to pick up the pieces of my mind. Jan is a very active person on the SWI forums and his replies are always on the money. As are those of Anne Ogborn and many others.

Prologs

These are just a couple of the ones I have used.

Books

I have been very fortunate to have found real books that are either college texts or “well known” books down the ages! There are some I’d like to get still but I have found these to be very useful, some of them I believe are also freely available online too!

These are just the first search result links for each book I have read, I have no affiliate links with the sites.

Conclusion

I hope that piques your interest and has given you some resources to start your journey. For me, the future is Mercury!

Comments