My experience with day two of exploring Prolog through Seven Languages in Seven Weeks.
Onto the second day of Prolog and after a simple first day I’m looking forward to delving deeper. Little did I know by the end of the chapter I’d have discovered some weird and wonderful Prolog facts like did you know it is used in Australia to determine how best to rear pigs! More on that later.
The first example takes a look at the use of recursion to solve problems. In the following example we have a list of facts which specify father child relationships and we want to determine if X is an ancestor of Y. In the sample you can see the ancestor rule has two clauses. Only one of these needs to be true to make the rule true. If X is the father of Y he is an ancestor of Y. If X is the father of an ancestor of Y he is an ancestor of Y e.g. your father’s father or your grandfather.
The recursive subgoal has been placed at the end of the rule to optimize the performance. This is called tail recursion optimization.
Lists and tuples are containers in Prolog. A list is a container of variable length
[1,2,3]. A tuple has a fixed length
The example below shows how Prolog tries to make the left and right sides match. This is called unification.
Prolog cannot find a solution to the second query as X would have to be set to two different values.
You can use the functions
Head, which takes the value of the first element in a list, and
Tail, which takes the value of the rest of the list, to achieve lots of different things.
Selecting a Particular Element.
_ is a wildcard used in the following example to select the third element.
Lists and Maths
It took me a bit to get my head round the code above. The first subgoal handles if the list is empty. In our case we’re sending through a list with a value. So it goes into the second sub goal with Head taking the value 1 and Tail taking the value
. This matches the first rule so TailCount is set to 0 so Count = 0+1 i.e. 1.
This is a similar idea to count. We have two subgoals, one to handle an empty list and the other to handle one which contains elements. Our list has elements so we go to the second subgoal. Head takes the value 1 and Tail the value
[2,3]. The sum subgoal is called recursively until it matches empty list. Initialises sum to 0 and then adds the head value i.e. an individual element to it.
We can reuse our rules to build other rules for example we can use sum and count to create an average rule.
The append rule
This rule returns true if two lists combined equal a third list.
append(List1, List2, List3) is true if List3 = List1 + List2
The append rule can be used to achieve lots of different things. You can use it to build lists
It computes possible splits
Some implementations of a Fibonacci series and factorials. How do they work?
By definition, the first two numbers in the Fibonacci sequence are 0 and 1, and each subsequent number is the sum of the previous two.
The first two subgoals handle the special cases of 0 and 1 which do not have two previous number to sum. For 0 the fibonacci sequence value is 0 for 1 the fibonacci sequence value is 1.
succ(int1, int2) is true if int 2 = int1 + 1 where int1 is greater than 0. In the above example we are using it to calculate N-1 and N-2. Then we find the N-1 fibonacci number and N-2 fibonacci number and add together to give the N Fibonacci number.
The product of all positive integers less than or equal to n.
The first subgoal handles the special case of X = 0 which has a factorial of 1. For every other number we recursively call factorial for the previous number (X-1) and then multiply the value returned by X.
A real-world community using Prolog. What problems are they solving with it today?
It was really interesting reading about all the different uses of Prolog. Some of the areas it is used in include farming, sporting events and weather monitoring. Very wide ranging. There is an article in Dr Dobbs on it which although it is 10 years old led me to some interesting sites.
AusPig is a decision support system for the Australian pork industry which helps farmers determine how to improve the productivity and returns of their farm. PigE is its intelligent backend. The Auspig model simulates the growth and reproduction of pigs, identifies factors that limit optimal performance of the pig, and suggest management strategies that maximize profits such as diet and housing changes.
Toernooi Assistant automates everything about tennis tournaments. It provides optimal planning and scheduling of matches, fast replanning in case of rain, player administration, seeding and drawing of lots for the arrangement of the players, processing of the match results, generation of press releases, and financial support.
An implementation of the Towers of Hanoi. How does it work?
What are some of the problems of dealing with “not” expressions? Why do you have to be careful with negation in Prolog?
When you use not(x) in Prolog it does not mean x is false it means x cannot be proven to be true.
An example of how this can lead to some unexpected behavior
Reverse the elements of a list.
Find the smallest element of a list.
Sort the elements of a list.
View my code at github