I am tackling a third language from the book today. This is Prolog and we are not complete strangers. I remember using it at uni for some lab practices and I can remember we didn’t get along like a house on fire. I found Prolog strange and at odds with imperative mindset I held back then. Now that I am a bit older, I find the fact that language is a bit different appealing and intriguing and I look forward to see why was it designed in such manner and what benefits it’s approach brings.
Day 1 explains the very basic concepts behind the language. It explains its syntax which is very simple. Main constructs are atoms, variables, facts and rules.
%atoms me. brother. mother. granddad. %facts parent(me, mother). parent(brother, mother). parent(mother, granddad). %rules grandparent(X, Y) :- parent(X, Z), parent(Z, Y). sibling(X, Y) :- \+(X = Y), parent(X, Z), parent(Y, Z). % X, Y and Z are variables
No syntax highlighting is available – I guess that the “hip crowd” does not grok Prolog.
Atom is a general purpose name without an inherent meaning. Atoms are written as words starting with a lower case letter, if spaces, special characters or capital letter are required atoms have to be quoted using single quotes.
Variables are place holders for arbitrary terms. They are written as words starting with capital letter or an underscore. A single underscore stands for an anonymous variable matching any term.
Facts are expressed as expressions consisting a name (functor) and a comma separated list of arguments in parenthesis. Functor must following naming convention for atoms.
Rules are expressed as expression consisting of head and body that are separated by :- operator. Head is expressed as a functor followed by arguments. Body consists of sub goals that need to be met in order for the rule to be true.
We use these constructs to express our knowledge about our domain at hand. The idea is that we define a knowledge base about our domain and then question (query) Prolog for possible solutions to our problems within the scope of the defined domain.
So in the example above I’ve defined (somewhat abstract) knowledge base about my family. Facts define that mother is parent to both me and brother and that granddad is parent of mother.
Then I’ve defined two rules grandparent and sibling. If I try to read the grandparent rule it reads like this: X is grandparent of Y if there are such X, Y and Z that Z is parent of X and Y is parent of Z. If you look at the rule definition it shouldn’t be too difficult to map between the previous sentence and rule itself.
Now that I have this knowledge base defined I can query Prolog about it like so:
%is mother my parent? | ?- parent(me, mother). yes %is granddad brother's parent? | ?- parent(brother, granddad). no
These were very simple queries and Prolog did not have much work as I was just asking it to return the facts I stated. But even with only facts we can still have some fun. When we use a query with a variable Prolog will try to find if there is such combination of facts and rules which can satisfy the query. If it finds it it will print it out.
%Who is parent of brother? | ?- parent(brother, Who). Who = mother yes %Who's parent is mother? | ?- parent(Who, mother). Who = me ? ; Who = brother ? ; no
In first query we have used Who variable and Prolog was trying to find the value of the variable that would satisfy the query. It finds that mother value fits and prints it out. In second query Prolog finds more than one match: me and brother. When Prolog finds more than one match it will print out the first one it finds and wait. You can then type ; to get next solution, a to get all solutions or <Enter> to stop looking for more solutions. no at the last line of my interaction means that Prolog could not find any more solutions.
And we can have just as much fun with rules that build on top of facts. I will just provide some queries but will not go into detailed explanation of them as you should “get the drill” by now:
%is granddad brother's grandparent. | ?- grandparent(brother, granddad). yes %is brother my sibling. | ?- sibling(me, brother). yes %Who is granddad grandparent of? | ?- grandparent(Who, granddad). Who = me ? a Who = brother no %Who is Grandparent of a Grandchild? %(Find all Grandparent, Grandchild pairs.) | ?- grandparent(Grandchild, Grandparent). Grandchild = me Grandparent = granddad ? a Grandchild = brother Grandparent = granddad no
At first all of this building of knowledgebase and then querying of it seems a bit unnatural to most programmers (including me when I first saw it). To begin there is no explanation about how Prolog came to the solutions it offers. It doesn’t print any algorithms and it can be quite frustrating when you are expecting a certain result and Prolog just says: no. But if you think of it it’s not that much different from creating a database and and then using SQL statements to query it. When using SQL you also don’t specify search algorithms and and the DBMS merely presents you with result.
First day with Prolog ends with two homework assignments:
HW1: Make a simple knowledge base. Represent some of your favorite books and authors. Find all books in your knowledge base written by one author.
%books.pl book('The Metamorphosis', 'Franz Kafka'). book('The Trial', 'Franz Kafka'). book('1984', 'George Orwell'). book('Catch 22', 'Joseph Heller'). book('Breakfast of Champions', 'Kurt Vonnegut'). book('Slaughterhouse-Five', 'Kurt Vonnegut').
| ?- book(Which, 'Franz Kafka'). Which = 'The Metamorphosis' ? a Which = 'The Trial' no
This was the simplest way of tackling this task that I could come up with.
HW2: Make a knowledge base representing musicians and instruments. Also represent musicians and their genre of music. Find all musicians who play the guitar.
%musicians.pl musician('Jimi Hendrix'). musician('Bob Marley'). musician('Ringo Starr'). musician('Terminator X'). musician('Peter Tosh'). musician('Fela Kuti'). musician('Johnny Stulic'). instrument(guitar). instrument(drums). instrument(keyboard). instrument(turntables). instrument(saxophone). genre(rock). genre(reggae). genre(hip-hop). genre(afrobeat). plays('Jimi Hendrix', guitar). plays('Bob Marley', guitar). plays('Ringo Starr', drums). plays('Ringo Starr', keyboard). plays('Terminator X', turntables). plays('Peter Tosh', guitar). plays('Peter Tosh', keyboard). plays('Fela Kuti', saxophone). plays('Fela Kuti', keyboard). plays('Johnny Stulic', guitar). plays('Jimi Hendrix', rock). plays('Bob Marley', reggae). plays('Ringo Starr', rock). plays('Terminator X', hip-hop). plays('Peter Tosh', reggae). plays('Fela Kuti', afrobeat). plays('Johnny Stulic', rock). plays_instrument(Musician, Instrument) :- musician(Musician), instrument(Instrument), plays(Musician, Instrument). plays_genre(Musician, Genre) :- musician(Musician), genre(Genre), plays(Musician, Genre). genre_instrumentalist(Musician, Instrument, Genre) :- plays_instrument(Musician, Instrument), plays_genre(Musician, Genre). rock_guitarist(Musician) :- genre_instrumentalist(Musician, guitar, rock). genre_instrument(Genre, Instrument) :- genre_instrumentalist(_, Instrument, Genre).
%Who plays the guitar? | ?- plays_instrument(Who, guitar). Who = 'Jimi Hendrix' ? ; Who = 'Bob Marley' ? ; Who = 'Peter Tosh' ? ; Who = 'Johnny Stulic' ? ; no %Does Jimi Hendrix play the guitar? | ?- plays_instrument('Jimi Hendrix', guitar). true ? yes %Which instruments does Ringo Starr play? | ?- plays_instrument('Ringo Starr', Which). Which = drums ? ; Which = keyboard ? ; no %Who is a rock guitarist? | ?- rock_guitarist(Who). Who = 'Jimi Hendrix' ? ; Who = 'Johnny Stulic' ? ; no %Is Bob Marley a rock guitarist? | ?- rock_guitarist('Bob Marley'). no %Which instruments are used to play rock? | ?- genre_instrument(rock, Which). Which = guitar ? ; Which = drums ? ; Which = keyboard ? ; Which = guitar ? ; no
In the second task I have expanded a bit on requirements as it was otherwise almost completely the same as the first one. I have also used the same rule (plays) for instruments and genres to make the task more interesting and challenging.
After the first day with Prolog I must say I like it quite a lot. The language is very simple and logical (PROgramming in LOGic) and has low barrier to entry even for non programmers. I have explained basic structure of last program to my girlfriend who understood it quite quickly and was happy making queries on her own. When she once asked me to show her what I was working on at the moment (in Java), she gave up on it quite quickly as there was so much “noise” to explain before I could explain what am I actually trying to do. I think the barriers that exist around Prolog are result of it tackling problems from a different (even though as shown with the SQL analogy not completely unusual) angle and the lack of willingness amongst programmers to accept different approach to problems. But it’s only the end of the first day so my opinions are still only forming.