Adapted by Paul
Brna and Tamsin
Treasure-Jones..
Go to www.amzi.com to download a free version of prolog. There is a good tutorial associated with this product. You may choose to use it rather than this document.
To use the prolog system:
1.Enter and edit your source code (using File/New to create a new file)
2.Consult your source code file into the listener (using Listener/Consult)
3.Issue Prolog queries to test your code and use the listener debugger, as
needed (using Listener/Debug on)
4.Respond to runtime errors by either continuing or failing
5.Modify your source code to fix the problems
6.Reconsult your source code file into the listener (using Listener/Reconsult,
which will automatically save all modified source files/windows)
7.Goto step 3 until your module works
Prolog is a logic language that is particularly suited to programs that involve symbolic or non-numeric computation. For this reason it is a frequently used language in Artificial Intelligence where manipulation of symbols and inference about them is a common task.
In Prolog, there are no looping constructs. Instead, repetition is achieved by recursion.
Prolog consists of a series of rules and facts. A program is run by presenting some query and seeing if this can be proved against these known rules and facts. In this tutorial we will attempt to give you a flavour of how all this is achieved and teach you how to write a simple program for yourself.
Here is a two-line program, meant to help you learn the mechanics of the editor and your listener.
mortal(joe).
mortal(socrates).
From the Amzi! Interactive Development Environment (IDE), select File/New from the main menu. Enter the program in the edit window, paying careful attention to upper and lowercase letters and punctuation. Then select File/Save As from the menu and save it as 'mortal.pro'.
Next, start the Prolog listener using either the Listener/Start menu item, [CtrlI], or the ALIS toolbar button. You should see the typical listener prompt.
?-
Entering the source code in the Listener is called consulting. Select Listener/Consult from the main menu, and select 'mortal.pro' from the file menu. You can also consult a Prolog source file directly from the listener prompt like this.
?- consult(mortal).
yes
Once you've loaded the program, try the following Prolog queries.
?- mortal(socrates).
yes
?- mortal(X).
X = joe
This example shows a feature of Prolog called unification. Two things can be unified if they can be made to match.
You can also write strings to the output. Here is an example:
% This is the syntax for comments.
% MORTAL - The first illustrative Prolog program
mortal(X) :- person(X). // The :- is called the neck. It
is sometimes read as if
person(socrates).
person(plato).
person(aristotle).
mortal_report:-
write('Known mortals are:'),nl,
mortal(X),
write(X),nl,
fail. // Because this
always fails, it forces other things to be tried.
mortal_report.
Note that functors of different
arities (parameter length) are different.
Thus mortal(X,Y) will not be confused with
mortal(X).
In AMZI Prolog, if you change your file, be sure to do a “reconsult”. Otherwise you may get duplicate rules which could be used twice in the search. Also, the command “listing” may be helpful as you get a listing of all the predicates that you provided to the system. In the IDE, simply
selecting Listener/Reconsult will reconsult the last file
consulted.
In Prolog we can make some statements by using facts. Facts either consist of a particular item or a relation between items. For example we can represent the fact that it is sunny by writing the program:
sunny.
We can now ask a query of Prolog by asking
?- sunny.
?- is the Prolog prompt. To this query, Prolog will answer yes. sunny is true because (from above) Prolog matches it in its database of facts.
Facts have some simple rules of syntax. Facts should always begin with a lowercase letter and end with a period. The facts themselves can consist of any letter or number combination, as well as the underscore _ character. However, names containing the characters -,+,*,/, or other mathematical operators should be avoided.
Here are some simple facts about an imaginary world. /* and */ are comment delimiters
john_is_cold. /* john is cold */
raining.
/* it is raining */
john_Forgot_His_Raincoat.
/* john forgot his raincoat
*/
fred_lost_his_car_keys.
/* fred lost is car keys */
peter_footballer.
/* peter plays football */
These describe a particular set of circumstances for some character john. We can interrogate this database of facts, by again posing a query. For example: {note the responses of the Prolog interpreter are shown in italics}
?- john_Forgot_His_Raincoat.
yes
?-
raining.
yes
?-
foggy.
no
The first two queries succeed since they can be matched against facts in the database above. However, foggy fails (since it cannot be matched) and Prolog answers no since we have not told it this fact.
More complicated facts consist of a relation and the items that this refers to. These items are called arguments. Facts can have arbitrary number of arguments from zero upwards. A general model is shown below:
relation(<argument1>,<argument2>,....,<argumentN> ).
Relation names must begin with a lowercase letter
likes(john,mary). likes is termed a functor or a predicate. It has arity two (as there are two parameters).
The above fact says that a relationship likes links john and mary. This fact may be read as either john likes mary or mary likes john. This reversibility can be very useful to the programmer, however it can also lead to some pitfalls. Thus you should always be clear and consistent how you intend to interpret the relation and when.
Finally, remember names of the relations are defined by you. With the exception of a few relations that the system has built into it, the system only knows about relations that you tell it about.
An example database. It details who eats what in some world model.
eats(fred,oranges). /* "Fred eats oranges" */eats(fred,t_bone_steaks).
/* "Fred eats T-bone steaks" */
eats(tony,apples).
/* "Tony eats apples" */
eats(john,apples).
/* "John eats apples" */
eats(john,grapefruit).
/* "John eats grapefruit" */
If we now ask some queries we would get the following interaction:
?- eats(fred,oranges). /* does this match anything in the database? */yes
/* yes, matches the first clause in the database */
?-
eats(john,apples).
/* do we have a fact that
says john eats apples? */
yes
/* yes we do, clause 4
of our eats database */
?-
eats(mike,apples).
/* how about this query, does mike eat apples */
no
/* not according to the above database. */
?-
eats(fred,apples).
/* does fred eat apples */
no
/* again no, we don't know whether fred eats apples
*/
In Prolog, variables are typeless. They can bind to an atom or to a structure.
How do we say something like "What does Fred eat"? Suppose we had the following fact in our database:
eats(fred,mangoes).eats(fred, meal(hambuger, frenchfries))
How do we ask what fred eats. We could type in something like
?- eats(fred,what).
However
Prolog will say no. The reason for this is that what does not match with mangoes
or with meal(hamburger,frenchfries). In order to match arguments in this way we
must use a Variable. The process of matching items with variables is known as
unification. Variables are distinguished by starting with a capital letter.
Thus returning to our first question we can find out what fred eats by typing
?- eats(fred,What).
What=mangoes
yes
As a result of this query, the variable What has matched (or unified) with mangoes. We say that the variable What now has the binding mangoes. When we pose a query, if the query is successful, Prolog prints both the variable and the variable name, as we see above.
Let's consider some examples using facts. First consider the following database.
loves(john,mary).
loves(fred,hobbies).
Now let's look at some simple queries using variables
?-
loves(john,Who).
/* Who does john love? */
Who=mary
/* yes , Who gets bound to mary */
yes
/* and the query
succeeds*/
?-
loves(arnold,Who)
/* does arnold love anybody */
no
/* no, arnold doesn't match
john or fred */
?-
loves(fred,Who).
/* Who does fred love */
Who
= hobbies
/* Note the to Prolog Who is
just the name of a variable, it */
yes
/* semantic connotations are not picked up, hence Who unifies */
/* with hobbies */
Here are some more difficult object/variable comparisons. Consider the following database showing a library of cassette tapes. Notice the final argument to tape, which is the name of a favourite song from the album.
tape(1,van_morrison,astral_weeks,madam_george).tape(2,beatles,sgt_pepper,a_day_in_the_life).
tape(3,beatles,abbey_road,something).
tape(4,rolling_stones,sticky_fingers,brown_sugar).
tape(5,eagles,hotel_california,new_kid_in_town).
Let's now look at some queries.
?- tape(5,Artist,Album,Fave_Song). /* what are the contents of tape 5 */Artist=eagles
Album=hotel_california
Fave_Song=new_kid_in_town
yes
?-
tape(4,rolling_stones,sticky_fingers,Song). /* find just song */
Song=brown_sugar
/*
which you like best from the album */
yes
So far we have looked at how to represent facts and to query them. Now we move on to rules. Rules allow us to make conditional statements about our world. Each rule can have several variations, called clauses. These clauses give us different choices about how to perform inference about our world. Let's take an example to make things clearer.
Consider the following
'All people are mortal':
We
can express this as the following Prolog rule
mortal(X) :-person(X).
The clause can be read in two ways (called either a declarative or a procedural interpretation). The declarative interpretation is "For a given X, X is mortal if X is a person." The procedural interpretation is "To prove the main goal that X is mortal, prove the subgoal that X is a person."
To continue our previous example (which defined Rule 1 as person(socrates)) , lets us define the fact 'Socrates is a person' so that our program now looks as follows:
mortal(X) :-
person(X).
person(socrates).
If we now pose the question to Prolog
?- mortal(socrates).
The Prolog interpreter would respond as follows:
yes
Why was this? Well in order to solve the query ?- mortal(socrates)., we used the rule we saw previously. This said that in order to prove someone mortal, we had to prove them to be people. Thus from the goal Prolog generates the subgoal of showing person(socrates).
In the above example we were able to match person(socrates) against the database described at the top of this card. In Prolog we say that the subgoal succeeded, and as a result the overall goal succeeded. We know when this happens because Prolog prints yes.
We can also use variables within queries. For example, we might wish to see if there is somebody who is mortal. This is done by the following line.
?- mortal(P).
The Prolog interpreter responds.
P = socrates
yes
This means that Prolog was able to prove the goal by binding the variable P to socrates. This was done by again proving someone was mortal by proving the subgoal that they were persons. Prolog thus asked if there was any P that was a person. This matches against the clause person(socrates) thereby binding P to socrates. This binding is then passed back to the parent goal, and the results in the printout we saw above.
Sometimes we may wish to specify alternative ways of proving a particular thing. This we can do by using different rules and facts with the same name. For example, we can represent the sentence 'Something is fun if its a red car or a blue bike or it is ice cream' as follows:
fun(X) :- /* an item is fun if */
red(X),
/* the item is red */
car(X).
/* and it is a car */
fun(X)
:-
/* or an item is fun if
*/
blue(X),
/* the item is blue */
bike(X).
/* and it is a bike */
fun(ice_cream).
/* and ice cream is also fun. */
This program says that we have three ways of finding out if something is fun. Something is fun if it is a red and a car or blue and a bike, or if it is ice cream. These three options are represent in Prolog by three clauses of the predicate fun. Just like we saw for pure facts, Prolog will start from the first clause (be it a rule or fact) of fun and try that. If that does not succeed, we try the next clause. We only fail when we run out of rules or facts to try.
Try the following: Using your own ideas, write rules for fun_class(X). Write rules for isSister(Sister,Person). Write rules for takeJob(Person,Job).
All identically-named variables within a particular rule (e.g. all occurrences of, say, X in the first fun rule below) are constrained to have one and the same instantiation for each solution to a particular query. Identical variable names in separate rules are totally independent, just as if different variable names had been used. Because the consequences of the preceding two sentences are so fundamental to Prolog (and so often misunderstood), we recommend that you read them again.
Thus variable name scoping is per-individual rule (often called a clause). The same variable name may appear in different clauses of a rule, or rules with different names. Each time it is treated as something specific to its context. A variable X may occur in the program many times with many different bindings. It will only have the same bindings when you tell it to.
Consider the following program:
fun(X) :-
red(X),
car(X).
fun(X) :-
blue(X),
bike(X).
car(vw_beatle).
car(ford_escort).
bike(harley_davidson).
red(vw_beatle).
red(ford_escort).
blue(harley_davidson).
Above is both our previous program for finding fun items and facts describing some red and blue items and some cars and bikes. Let's now use the above program and see if a harley_davidson is fun. To do this we can ask Prolog the following question.
?- fun(harley_davidson). /* to which Prolog will reply */yes
/* to show the program succeeded */
To execute this query, Prolog will first see if harley_davidson is red, however only vw_beatles and ford_escorts are defined as being red. Hence the query red(harley_davidson) will fail. This means that the first clause of fun will fail. As a result, we now try the second clause of fun. This will mean that we will attempt the subgoals blue(harley_davidson) and bike(harley_davidson). Both these goals match facts in the database. As a result fun succeeds as we saw above.
We can also ask our program to find fun items for us. To do this we can pose the following question.
?- fun(What).To which Prolog will reply
What=vw_beatle
yes
Let's see how Prolog deals with this query. Firstly we will try the first clause of fun. This results in us trying the goal red(What). This succeeds matching the first clause of red with the binding What=vw_beatle. Now we attempt the goal car(vw_beatle). This matches the first clause of car, and, as a result, the fun goal succeeds.
Try the following: write the code to determine isSibling(Person1,Person2), make sure you don’t list yourself as your own sibling. The operator \= is not equal. Also try isParent(Parent,Child) and isUncle(Uncle, Child). Try isAncestor(Person1, Person2).
Suppose that we have the following database
eats(fred,pears).eats(fred,t_bone_steak).
eats(fred,apples).
So far we have only been able to ask if fred eats specific things. Suppose that I wish to instead answer the question, "What are all the things that fred eats". To answer this I can use variables again. Thus I can type in the query
?- eats(fred,FoodItem).
As we have seen earlier, Prolog will answer with
FoodItem = pears
This is because it has found the first clause in the database. At this point Prolog allows us to ask if there are other possible solutions. We do so by typing a semi-colon. When we do so we get the following.
FoodItem = t_bone_steak
if I ask for another solution, Prolog will then give us.
FoodItem = apples
If we ask for further solutions, Prolog will answer no, since there are only three ways to prove fred eats something. The mechanism for finding multiple solution is called backtracking. This is an essential mechanism in Prolog and we shall see more of it later.
We can also have backtracking in rules. For example consider the following program.
hold_party(X):-
birthday(X),
happy(X).
birthday(tom).
birthday(fred).
birthday(helen).
happy(mary).
happy(jane).
happy(helen).
Notice that we normally keep predicates of the same name together.
If we now pose the query
?- hold_party(Who).
In order to solve the above, Prolog first attempts to find a clause of birthday, it being the first subgoal of birthday. This binds X to tom. We then attempt the goal happy(tom). This will fail, since it doesn't match the above database. As a result, Prolog backtracks. This means that Prolog goes back to its last choice point and sees if there is an alternative solution. In this case, this means going back and attempting to find another clause of birthday. This time we can use clause two, binding X to fred. This then causes us to try the goal happy(fred). Again this will fail to match our database. As a result, we backtrack again. This time we find clause three of birthday, and bind X to helen, and attempt the goal happy(helen). This goal matches against clause 3 of our happy database. As a result, hold_party will succeed with X=helen.
Consider the following examples.
fun(X) :- /* something is either fun because its ....*/
red(X),
/* red */
car(X).
/* and a car */
fun(X)
:-
/* or its fun if its.... */
blue(X),
/* blue */
bike(X).
/* and a bike */
/*
database of red items */
red(apple_1).
red(block_1).
red(car_27).
/*
database of cars */
car(desoto_48).
car(edsel_57).
This program says that red cars or blue bikes are fun. It then goes on to name some examples of each type of object.
Consider the ! command. It freezes choices made so far . In the following example, once you have found something red, you cannot consider anything else.
fun(X) :- /* something is either fun because its ....*/
red(X), !;
/* red */
car(X).
/* and a car */
fun(X)
:-
/* or its fun if its.... */
blue(X),
/* blue */
bike(X).
/* and a bike */
/*
database of red items */
red(apple_1).
red(block_1).
red(car_27).
/*
database of cars */
car(desoto_48).
car(edsel_57).
Let's now ask what is a fun item. To do this we first must enter the following query
?- fun(What).We first attempt to prove something is fun. To do this we have two clauses of fun that we can use
/* clause 1 */fun(X)
:-
red(X),
car(X).
/*
clause 2 */
fun(X)
:-
blue(X),
bike(X).
Using the first clause, we can now look to see if we can find some red object
First let's retrieve a red object from the red database
/* database of red items */red(apple_1). first
choice
red(block_1).
red(car_27).
The first red item that we find is apple_1. This gives us the instantiation X=apple_1. Next we have to see if this is a car, so we ask the question car(apple_1). Does this match with our existing database of facts about cars?
/* database of cars */
car(desoto_48).
car(edsel_57).
The answers is that it will not. apple_1 will not match with desoto_48 or with edsel_57. So what do we do next? In such cases, Prolog backtracks in order to find another solution. Thus we go back to the red database, and see if we can find another possible solution. In this case we can
red(apple_1).
red(block_1). second
choice // implied or between choices.
red(car_27).
We can use the next clause and see if block_1 is a red car.
Debug From AMZI Prolog, debug. causes you to enter the debugger. Try it. Nesting is used to show you which rules are tried as part of which goal. Something like
2-1 EXIT(7) location(crackers,kitcher)
says that the exit occurred at the second level, first goal using clause #7 for predicate location.
Debuggers use the concept of “ports” to describe the state of the query. A goal as four ports: CALL, EXIT, REDO, and FAIL. The picture is
drawn as follows:
|
CALL
EXIT FAIL
REDO |
1. a:- b,c,d.
2. a:- e,f.
3. b:- f.
4. e.
5. f.
6. a:-f.
The rules for search space form a depth first search:
1. Match against the first of the goals.
2. Try to match the rules in order
3. The child node is like the parent node, except that the first goal is replaced by the tail (RHS) of the rule.
Because of the order, we can get an infinite search (and find nothing) even when a solution exists.
Consider:
1. a:- f,a.
2. a:- e,f.
3. b:- f.
4. e.
5. f.
6. a:- b,c,d.
As is commonly the case in many programming tasks, we often wish to repeatedly perform some operation either over a whole data-structure, or until a certain point is reached. The way we typically do this in Prolog is by recursion. This simply means a program calls itself typically until some final point is reached. Frequently in Prolog what this means is that we have a first fact that acts as some stopping condition followed up by some rule(s) that performs some operation before reinvoking itself.
Recursion is often found to be a hard concept to grasp. For this reason we will present two detailed examples of how it works.
on_route(rome). // important that base case is listed first
on_route(Place):-
move(Place,Method,NewPlace),
on_route(NewPlace).
move(home,taxi,halifax).
move(halifax,train,gatwick).
move(gatwick,plane,rome).
on_route is a recursive predicate. This program sees if it is possible to travel to rome from a particular place. The first clause sees if we have already reached rome, in which case we stop. The second clause sees if there is a move from the current place, to somewhere new, and then recursive sees if the NewPlace is on_route to rome. The database of moves that we can make is on the right.
If there are two unbound variables that match, they are bound (but not to a value) to each other. So if (in the future) one takes on a value, the other does as well.
Query: where_food(X1,Kitchen)
Rule: where_food(X2,Y2) :- location(X2,Y2), edible(X2).
X1=_01
X2 = _01
Y2=Kitchen.
(second level query)
Let's now consider what happens when we pose the query ?- on_route(home). This matches clause two of on_route (it can't match clause one because home and rome don't unify). The second on_route clause consists of two subgoals. The first asks whether you can move from home to some new location i.e. move(home,Method,NewPlace). This succeeds with Method = taxi, NewPlace = halifax. This says that yes we can move from home by taking a taxi to halifax. Next we recursively see if we can find a route from halifax to rome by doing the same thing again. This is done by executing the new subgoal on_route(halifax).
The goal on_route(halifax) will fail to unify on clause one, so again we'll use the recursive clause two and find some new place to go to. Hence we try the goal on_route(halifax,Method,NewPlace) this succeeds because we can catch a train from halifax to gatwick airport. Hence Method=train, NewPlace=gatwick. As a result we then try the recursive call on_route(gatwick), i.e. we see if there is a move from gatwick which will get us to rome.
We now try on_route(gatwick), again this only unifies with the second clause. As a result we try the move clause again this time with Place bound to gatwick. This query will match the third clause of the move database. The results in Method=place, NewPlace=rome. Next we try the recursive goal on_route(rome). This now matches clause one of on_route. This is just a fact and succeeds. As a result all the other on_route goals in turn succeed. Thus finally our first goal ?- on_route(home) succeeds and Prolog responds yes
parent(john,paul). /* paul is john's parent */
parent(paul,tom). /* tom is paul's parent */
parent(tom,mary). /* mary is tom's parent */
ancestor(X,Y):- parent(X,Y). /* someone is your ancestor if there are your parent */
ancestor(X,Y):- parent(X,Z), /* or somebody is your ancestor if they are the parent */
ancestor(Z,Y). /* of someone who is your ancestor */
The above program finds ancestors, by trying to link up people according to the database of parents at the top to the card. So let's try it out by asking
?- ancestor(john,tom).
The first clause of ancestor looks to see if there exists a clause that could match the goal parent(john,tom). This fails to match, as a result we try the second clause of ancestor. We now pose the query parent(john,Z). This results in us choosing clause one of parent and binding Z=paul. As a result, we now pose the recursive query ancestor(paul,tom). Applying the ancestor rule again, we first try the first clause. This means we check for parent(paul,tom). which successfully matches the second clause of parent. As a result the goal ancestor(paul,tom) succeeds. This in turn leads to the goal ancestor(john,tom) succeeding and Prolog responding yes
1. Given facts such as
Bob is taller than Mike.
Mike is taller than
Jim
Jim is taller than
George
Write a recursive program that will determine that Bob's height is greater than George's.
town1----->-----town2---->----town3---->----town4--->----town5---->---town6
A one way road links 6 towns. Write a program that can work out if you can travel on that road. For example. Here are two sample program behaviours.
?- can_get(town2,town5).
yes
?-
can_get(town3,town1).
no
So far we have only considered simple items as arguments to our programs. However in Prolog a very common data-structure is the list.
Lists themselves have the following syntax. They always start and end with square brackets, and each of the items they contain is separated by a comma. Here is a simple list [a,freddie,A_Variable,apple]
Prolog also has a special facility to split the first part of the list (called the head) away from the rest of the list (known as the tail). We can place a special symbol | (pronounced 'bar') in the list to distinguish between the first item in the list and the remaining list. For example, consider the following.
[first,second,third] = [A|B]
where A = first and B=[second,third]
The unification here succeeds. A is bound to the first item in the list, and B to the remaining list.
Here are some example simple lists
[a,b,c,d,e,f,g][apple,pear,bananas,breadfruit]
[
] /* this is a special list, it is
called the empty list because it
contains nothing */
Now lets consider some comparisons of lists:
[a,b,c] unifies with [Head|Tail] resulting in Head=a and Tail=[b,c]
[a] unifies with [H|T] resulting in H=a and T=[]
[a,b,c] unifies with [a|T] resulting in T=[b,c]
[a,b,c] doesn't unify with [b|T]
[] doesn't unify with [H|T]
[] unifies with []. Two empty lists always match
Consider the following fact.
p([H|T], H, T).
Lets see what happens when we ask some simple queries.
?- p([a,b,c], X, Y).X=a
Y=[b,c]
yes
?-
p([a], X, Y).
X=a
Y=[]
yes
?-
p([], X, Y).
no
We can use lists within facts and rules. One common way of using lists is to store information within a list and then subsequently search for this information when we run our programs. In order to search a list, Prolog inspects the first item in a list and then goes on to repeat the same process on the rest of the list. This is done by using recursion. The search can either stop when we find a particular item at the start of the list or when we have searched the whole list, in which case the list to be searched will be the empty list. In order to do this, we have to be able to selectively pull the list apart. We have already seen how we can go about doing this. In the previous section we showed how to take the head and a tail of a list:
[Head|Tail]
This method constitutes the basis of the searching method. We shall use it to pull apart a list, looking at the first item each time, recursively looking at the tail, until we reach the empty list [], when we will stop.
Consider the following problem. How can I see if a particular item is on a particular list? For example I want to test to see if item apples is on the list [pears, tomatoes, apples, grapes]. One possible method of doing this is by going through the list, an item at a time, to see if we can find the item we are looking for. The way we do this in Prolog is to say that we could definitely prove an item was on a list if we knew that the target item was the first one on the list. ie.
on(Item,[Item|Rest]). /* is the target item the head of the list */
Otherwise we could prove something was on a list if we could prove that although it didn't match the existing head of the list, it nonetheless would match another head of the list if we disregarded the first item and just considered the rest of the list i.e.
on(Item,[DisregardHead|Tail]):-
on(Item,Tail).
We now have a program consisting of a fact and a rule for testing if something is on a rule. To recap, it sees if something is the first item in the list. If it is we succeed. If it is not, then we throw away the first item in the list and look at the rest.
Try: CountAll: counts the number of things in a list.
Factor: creates a list of factors of a number
MyReverse: reverses the list
HalfList: create a list containing every other element of a list.
InsertNew: insert an element only if not in original list
Flatten.
The last example showed how we could strip off the front items on a list and recursively search the rest. We can also use the same method to build lists. For example take one existing list, say List1. We can make a new list List2 which contains List1 but with the new head prolog, as follows:
List2 = [prolog|List1]
This again is pure unification. List2 now consists of the head prolog plus whatever List1 was bound to. If List1 were to be bound e.g. List1 = [list,c,pascal,basic], List2 would now be the list [prolog,lisp,c,pascal,basic]
We can use this construction technique to build lists during recursion. We'll present three examples of this.
An example use of list construction is when we wish to create a new list out of two existing lists. We'll illustrate this by defining a predicate called append that takes three arguments. The first two are lists. The predicate uses these two lists to produce a third list which combines the original two. For example,
?- append([a,b,c],[one,two,three],Result).
Result
= [a,b,c,one,two,three]
Note,
this is not the same as append(one,two,Result) which yields
Result=[one|two]
The way we do this in Prolog uses both list construction and list deconstruction. Recall that on the previous card we saw how we could glue an item onto the front of a list to produce a new list. Thus we can produce the list [c,one,two,three] from the list [one,two three] by saying NewList = [c|[one,two,three]. This results in NewList being bound to the list [c,one,two,three]. This is the clue to how we write append in Prolog. We can recursively split the first list into single items by the deconstruction techniques discussed earlier. We can then use the construction method above to glue together a new list, which we shall illustrate next.
We can’t do [a|b c d] as after the bar you must have a list.
In order to write append we shall first search through the first list, and taking each item in turn, add it to the second list. This we'll do recursively, by searching for the end of the first list, and then adding the items in the first list to the items in the second list in reverse order. Thus the last item in the first list is the first to be added to the second list. We illustrate this more clearly with an example. First lets see what the code to do this look like. First we must deal with the case when the first list is an empty list. In this case the result of appending the two lists will just be the second list. Thus this gives
append([],List,List).
Now for the rule which does most of the work. This says search through the first list can each time stick the first thing on the first list onto the resulting list.
append([Head|Tail],List2,[Head|Result]):-
append(Tail,List2,Result).
.
Let's now consider a second example of constructing lists. Taking the list [1,12,3,14,5,8], lets construct a new list out of the old that contains only numbers greater than 6. To do this we can search the list as we have seen before. If the item passes our test, then we can add it to the output list. If it does not, then we can disgard the item. To make a start, if the list to search is empty, we will return the empty list. Hence we get the base case of the recursion.
sift([],[]).
Next we need to say that if the item passes our test, put it in the output list
sift([X|T],[X|Result]):- X > 6, /* is X greater than 6 */ sift(T,Result).
/* if so then go find the rest */
Otherwise
we are will disgard the head and look for other hits in the
tail
sift([ThrowAway|Tail],Result):- /* disgard the head */
sift(Tail,Result).
/* and look in the tail */
Let us now see how our program responds to the query
?- sift([1,12,3,14,5,8], Result).
To this goal, we first unify with clause 2. The result is to evaluate the subgoal 1 > 6, this clearly fails, so we move on to the third clause and try the goal sift([12,3,14,5,8],Result). This again matches on the second clause of sift. We now try the subgoal 12>6, this succeeds and we now attempt the goal sift([3,14,5,8],Result). However, notice what also happens. By using this clause we also place 12 on our output list.
Stepping further through our example, we see that greater than subgoal in clause 2 succeeds for 14 and 8, till finally we get the goal sift([],Result). This matches the first goal, with Result bound to []. As we come out of the recursion, we see that clause 2 builds up the result for to the list [8], then [14,8], then finally [12,14,8], before the query finally succeeds.
Write a program to delete all reference of a particular item from a list. It should have three arguments. The list you wish to use, the item to delete, and the resulting list. Here are some example of it behaviour
?- delete_all([a,b,a,c,a,d],a,Result).Result
= [b,c,d]
?-
delete_all([a,b,a,c,a,d],b,Result).
Result
= [a,a,c,a,d]
?-
delete_all([a,b,a,c,a,d],prolog,Result).
Result
= [a,b,a,c,a,d]
Write a program to replaces all occurrences of one item in a list with another. It should have four arguments. The list you wish to use. The item to replace. The item to replace it with, and the resulting list. Here are some example of its behaviour
?- replace_all([a,b,a,c,a,d],a,mike,Result).Result
= [mike,b,mike,c,mike,d]
?-
replace_all([a,b,a,c,a,d],b,foo,Result).
Result
= [a,foo,a,c,a,d]
?-
replace_all([a,b,a,c,a,d],prolog,logic,Result).
Result
= [a,b,a,c,a,d]
Updating
the Data Base
You
can update the data base as follows:
asserta(X). Adds the clause X as the first clause
for its predicate. (Will not be undone on
backtracking)
assertz(X).
same as asserta only it adds the clause X as the last clause for its
prediate.
retract(X). Removes X from the data base.
abolish(Name,Arity). removes all predicates with Name and Arity from dynamic data base.
To save the contents of your dynamic data base, simply type
tell(“myout.pro”). // sets output to go to file myout.pro.
listing. // does a listing of all current predicates, sending output to myout.pro.
Arithmetic
The
operator is is used to assign arithmetic
values:
cToF(C,F)
:- F is C*9/5+32
The
operator = does unification.
The
operator == tests if two operands unify with no variable bindings taking
place.
The
operator =:= checks for arithmetic equality.
The
variable _ is used when we don’t care to reference the variable
specifically.