The theme of this little blog sequence is the logic programming language Prolog. It is associated with artificial intelligence and computational linguistics.
Karl Valentin once said. “Am besten beginnt man mit dem Anfang, das hat sich bewährt“. Which roughly translates into, “Experience shows that it’s best to start at the beginning”. Since I mentioned Karl Valentin you might want to have a look at Lisl Karlstadt, there are hints that she contributed much to the work of the duo.
New programming languages are popping up like mushrooms. Why looking yet at another one? Does it provide an easy syntax, a powerful framework, or is it easy to learn? No, no and no again. The clue is that Prolog is a logical programming language, this provides new possibilities!
Do you know the movie ‘2001: A Space Odyssey’? Short abstract: chimps, bones, monolith, Thus Spoke Zarathustra, old man, baby, the end. One character in the movie is HAL 9000 he is a computer. HAL mimics human behavior or even develops his own consciousness and takes measures to protect himself. The dream or nightmare of artificial intelligence becomes true.
Most people start with programming languages like Java or C#. If you know that Twix is the retired Raider you might have started with C, or C++ and have been forced to implement your own double linked lists, but that’s another story. What have all these languages in common? They are all imperative, which means that you have to tell the computer what to do. You as a developer have to figure out how the problem is solved, you create an algorithm.
Whereas in a logical programming language like Prolog, you as a developer have to describe the logical connections of the problem. You have to answer the question what the problem is. This approach is more abstract and provides the benefit of a formal verification. But this comes not for free, the solution isn’t obvious and you are forced to think a bit like Sheldon Cooper.
Let’s play a little game. Imagine someone gives you the task to implement the following requirement. Add two lists into a third one, the resulting third list is the concatenation of the first and second list. Sketch your solution with any programming language of your choice.
I will show you how this is done in Prolog. We create a function named palappend/3, palappend is the name and the 3 indicates the number of the parameters the function takes. In Prolog functions are called predicates because originally Prolog was developed to automatically prove mathematical theorems.
Don’t mind the syntax, the square brackets are used to indicate a list, and the upper case letter X is a so-called free variable. The result X contains both lists, as was to be expected. Not much magic yet.
Before I explain how this is done in Prolog I will show you how the predicate behaves with different input arguments. Maybe the lazy developer forgot to check the arguments for sanity.
Let’s be destructive. What happens when we – on purpose – call the predicate with some obvious invalid arguments. We start by omitting one of the two “input” arguments.
No error message and the missing part of the solution is provided. By the way, how is your solution dealing with this input?
Now we omit both “input” variables.
Again no error and all possible solutions for the asked question are provided.
Now let’s see how palappend deals with this arguments.
The reply indicates that the predicate found an answer to our question, the answer “yes”, is replied.
Seems that Prolog doesn’t find an answer, therefore “no” is replied.
You have seen how the predicate behaves, now it is time to think about the problem. It can be described like this.
- If the first list is empty, then the third list is the same as the second list.
- If the first list contains at least one element, then this element is also the first element of the third list. The rest of the third list results from the concatenation of the remaining first list and the second list.
This results into a neat Prolog source like this. Two lines, not more.
palappend([H|R],L,[H|RundL]) :- palappend(R,L,RundL).
How Prolog in general works will be part of the upcoming posts. So if you want to know what unification and resolution principle means stay tuned.