Prolog: Forwards and Backwards

27th May 2018

A key idiom in Prolog is the idea that it runs both forwards and backwards. If you've never programmed in Prolog before, this can be mind-blowing! You can write one "function" and get many different uses out of it. In this post we'll take a look at what this means as a teaser that might tempt you into giving Prolog a go.

AS A seasoned programmer, there’s always a reason to learn a new language. Sometimes it’s for work, because you need it for particular jobs. But there are also times you learn a new language just because you encountered something in it that was so awesome it enticed you to learn more. The best languages to learn for yourself are these languages, they’re the ones that change how you think about programming, and even how you think! Prolog is such a language.

Let’s take a look at a standard task in any programming language, joining two lists together. Like in many languages this is usually a built-in for Prolog, so you can see the awesomeness of forwards and backwards programming without even needing to write your own code, yet. If you need to install Prolog, try Swi-Prolog or GNU Prolog, you can fire up a REPL by typing swipl or gprolog respectively. halt. is how you quit! Then you can follow along. Watch out for full-stops, Prolog uses sentences, and sentences end with them.

Using Append/3

THIS IS the append/3 predicate. The /3 means it takes 3 parameters. If you put in two lists and a third, which is the other two joined, append/3 will tell you that is correct: the third list is the same as the first two joined together. So we have append\3 as a test.

?- append([1, 2, 3], [a, b, c], [1, 2, 3, a, b, c]).

?- append([1, 2, 3], [a, b, c], [c, a, k, e]).

You can also use append with a variable, to actually append two lists. Variables start with uppercase letters.

?- append([1, 2, 3], [a, b, c], X).
X = [1, 2, 3, a, b, c]

That would be using append forwards, but we also get to use it backwards. We can do this in three ways. The last query I’ll let you run yourself, it will generate every possible variation of two lists that you can append to get the result. You’ll need to hit “;” to ask for more results from Prolog.

?- append(X, [a, b, c], [1, 2, 3, a, b, c]).
X = [1, 2, 3]

?- append([1, 2, 3], X, [1, 2, 3, a, b, c]).
X = [a, b, c]

?- append(X, Y, [1, 2, 3, a, b, c]).

Look at that, so many different ways of using the same predicate! Such versatile code!

Writing Append/3

IMAGINE HAVING to write all those functions in another language, it’d be so long! As we’ve not coded append ourselves, you’d be forgiven for thinking that it must take some serious code to get all that functionality. Well, here’s the thing, when writing Prolog, you write what the truth is, rather than how to do something. So here’s one way to implement your own my_append\3 that’ll do all of the above.

my_append([], List, List).
my_append([H|Tail1], List, [H|Tail2]) :- append(Tail1, List, Tail2).

Yep, that’s a whole two lines! It’s a recursive function that’s using pattern matching. How it executes is left to Prolog to worry about, but you can see what it’s doing by running trace, append([1, 2, 3], [a, b, c], X). I’ll admit that for a non-Prolog programmer it looks pretty strange and like it’d be pretty difficult to figure out what’s going on, but this is actually less than half-way through the beginners books I’ve read. Prolog is just a little different.

Give It A Go

HOPEFULLY THIS has whet your appetite enough to look into Prolog. A good book to start with is Learn Prolog Now! You can get it on dead-trees or electric-powered-device formats for free.

Prolog is a pretty off-beat language, I can’t pretend that if you learn Prolog job vacancies will be lining up for you. But Prolog is also a pretty unique language, it’s one of the few Logic Programming languages and it will expand your programming horizons. Among the implementations of Prolog out there, I’d recommend Swi-Prolog because of their active and friendly community, plus a fine implementation.

Until next time, happy coding.

Post Tags

All Tags

LIFE IS better when we share.