Prolog: Forwards and Backwards
As a seasoned programmer, there’s always a reason to learn a new language. Sometimes it’s for work; other times, you need it for particular jobs. But there are also times you learn a new language just because you encountered something in it so awesome it enticed you to dive deeper. The best languages to learn for yourself are these ones; 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
We’ll use the append/3 predicate. On this page, we’re using
Tau Prolog, so behind the scenes, we’re importing
the lists library. If you’re using SWI-Prolog or GNU Prolog, you won’t need to
do that.
The “/3” in append/3 means it takes three parameters. If you give it two
lists and their joined result, append/3 confirms that’s correct: the third
list matches the first two joined together. So we have append/3 as a test.
The false at the end of the results means no more solutions could be found.
?-
?-
You can also use append/3 with a variable to actually append two lists.
Variables start with uppercase letters.
?-
That would be using append/3 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 Prolog for more results, which we’ve
done for you here. Remember: the false means no more solutions could be
found.
?-
?-
?-
Look at that—so many different ways of using the same predicate! Such versatile code!
Writing append/3
Imagine having to write all those variations in another language—it’d be much
longer! As we’ve not coded append/3 ourselves, you’d be forgiven for thinking
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.
?-
Yep, that’s a whole two lines! It’s a recursive predicate 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). in your
own install. I’ll admit that for a non-Prolog programmer, it looks pretty
strange and like it’d be tricky to figure out what’s going on, but this is
actually less than halfway through the beginner 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 in dead-tree or digital formats for free.
Prolog is an off-beat and unique language. Learning Prolog—one of the very few Logic Programming languages—will certainly expand your programming horizons. Among Prolog implementations, I’d recommend SWI-Prolog because of its active and friendly community, plus a fine implementation.
Until next time, Happy Prologing!
Paul