The list is a simple data structure widely used in non-numeric programming.

A list is a sequence of any number of items, such as ann, tennis, tom, skiing. Such a list can be written in Prolog as:

[ann,tennis,tom,skiing]

Lists can be empty or non-empty. Empty list is shown as [] atom. Non-empty list can be viewed as consisting of two things:

The first item called head,

The remaining part called tail.

## Sunday, 18 January 2009

### Unification Rules

Unification rules

A constant unifies only with itself.

Two structures unify if and only if they have the same functor and the same number of arguments, and the corresponding arguments unify recursively.

A variable unifies with anything.

Unification = Matching + Occurs check

What happens when we ask Prolog:

?- X = f(X).

Matching succeeds, unification fails

A constant unifies only with itself.

Two structures unify if and only if they have the same functor and the same number of arguments, and the corresponding arguments unify recursively.

A variable unifies with anything.

Unification = Matching + Occurs check

What happens when we ask Prolog:

?- X = f(X).

Matching succeeds, unification fails

Labels:
prolog,
rules,
Unification

### Unification

How do we ask: ''what does Fred eat ?'‘

eats(fred,oranges).

How do we ask: “what Fred eats” ?

?- eats(fred,what).

But Prolog will say “no” to this question. The reason is that Prolog can't find the relation “eats(fred,what)” in its database.

In this case we have to use a variable which will be unified to match a relation given in the program. This process is known as unification.

Now that we know how to use a variables, we can ask the same question as before using the variable What instead of an atom.

?- eats(fred,What).

What=orange

Yes

In this case Prolog try to unify the variable with an atom. ''What=oranges'' means that the query is successfull when “what” is unified with oranges.

With the same program if we ask :

?- eats(Who,oranges).

Which means who eats oranges. To this query Prolog should answer :

?- eats(Who,oranges).

Who=fred

yes

eats(fred,oranges).

How do we ask: “what Fred eats” ?

?- eats(fred,what).

But Prolog will say “no” to this question. The reason is that Prolog can't find the relation “eats(fred,what)” in its database.

In this case we have to use a variable which will be unified to match a relation given in the program. This process is known as unification.

Now that we know how to use a variables, we can ask the same question as before using the variable What instead of an atom.

?- eats(fred,What).

What=orange

Yes

In this case Prolog try to unify the variable with an atom. ''What=oranges'' means that the query is successfull when “what” is unified with oranges.

With the same program if we ask :

?- eats(Who,oranges).

Which means who eats oranges. To this query Prolog should answer :

?- eats(Who,oranges).

Who=fred

yes

Labels:
program,
prolog,
Unification

### Monkey and Banana

A monkey is in a room. Suspended from the ceiling is a bunch of bananas, beyond the monkey's reach. In the corner of the room is a box.

How can the monkey get the bananas?

The solution is that the monkey must push the box under the bananas, then stand on the box, and then grab the bananas.

In other variants of the problem, the bananas are in a chest and the monkey first has to open the chest using a key.

move( state(middle, onbox, middle, hasnot),grasp, % Grasp banana

state(middle, onbox, middle, has) ).

move( state(P, onfloor, P, H), climb, % Climb box

state(P, onbox, P, H) ).

move( state(P1, onfloor, P1, H), push(P1, P2), % Push box from P1 to P2

state(P2, onfloor, P2, H) ).

move( state(P1, onfloor, B, H), walk(P1, P2), % Walk from P1 to P2

state(P2, onfloor, B, H) ).

% canget(State,Moves): monkey in State can get banana by performing Moves

canget( state(_,_,_,has), [] ).

canget(State1,[M|List]) :- move(State1,M,State2), canget(State2,List).

solve(Moves) :- canget(state(atdoor,onfloor,atwindow,hasnot),Moves).

For help, use ?- help(Topic). or ?- apropos(Word).

?- [mb].

% mb compiled 0.00 sec, 2,280 bytes

Yes

?- solve(Moves).

Moves = [walk(atdoor, atwindow), push(atwindow, middle), climb, grasp]

Yes

How can the monkey get the bananas?

The solution is that the monkey must push the box under the bananas, then stand on the box, and then grab the bananas.

In other variants of the problem, the bananas are in a chest and the monkey first has to open the chest using a key.

move( state(middle, onbox, middle, hasnot),grasp, % Grasp banana

state(middle, onbox, middle, has) ).

move( state(P, onfloor, P, H), climb, % Climb box

state(P, onbox, P, H) ).

move( state(P1, onfloor, P1, H), push(P1, P2), % Push box from P1 to P2

state(P2, onfloor, P2, H) ).

move( state(P1, onfloor, B, H), walk(P1, P2), % Walk from P1 to P2

state(P2, onfloor, B, H) ).

% canget(State,Moves): monkey in State can get banana by performing Moves

canget( state(_,_,_,has), [] ).

canget(State1,[M|List]) :- move(State1,M,State2), canget(State2,List).

solve(Moves) :- canget(state(atdoor,onfloor,atwindow,hasnot),Moves).

For help, use ?- help(Topic). or ?- apropos(Word).

?- [mb].

% mb compiled 0.00 sec, 2,280 bytes

Yes

?- solve(Moves).

Moves = [walk(atdoor, atwindow), push(atwindow, middle), climb, grasp]

Yes

### Order of Clauses and Goals: Infinite Loops

Consider the following clause:

P:-p.

This means ‘p is true if p is true’. This is declaratively perfectly correct, but procedurally is quite useless.

?-p.

Using the clause above, the goal p is replaced by the same goal p; this will be in turn replaced by p, etc. Prolog will enter an infinite loop not noticing that no progress is being made.

Any differences in order of the clauses may cause finite loops. For example you can’t move if you don’t get up.

Different variation of clauses produces different answers.

The predecessor procedure consists of two clauses, and one of them has two goals in the body. There are,therefore, 4 variations of this program, which have the same declarative meaning, can be obtained by:

Swapping both clauses, and

Swapping the goals for each order of clause.

The Original version:

pred1(X, Z) :- parent(X, Z).

pred1(X, Z) :- parent(X, Y), pred1( Y, Z).

Variation a:

pred2(X, Z) :- parent(X, Y), pred2( Y, Z).

pred2(X, Z) :- parent(X, Z).

Variation b:

pred3(X, Z) :- parent(X, Z).

pred3(X, Z) :- pred3( X, Y), parent(Y, Z).

Variation c:

pred4(X, Z) :- pred4( X, Y), parent(Y, Z).

pred4(X, Z) :- parent(X, Z).

Let’s see what happens if we ask whether Tom is a predecessor of Pat using the four variations of the predecessor relation:

?- pred1(tom, pat).

yes

?- pred2(tom, pat).

yes

?- pred3(tom, pat).

yes

?- pred4(tom, pat).

Prolog can not find the answer and this is manifested on the terminal by a Prolog message such as “More core needed” or “Stack Overflow”.

P:-p.

This means ‘p is true if p is true’. This is declaratively perfectly correct, but procedurally is quite useless.

?-p.

Using the clause above, the goal p is replaced by the same goal p; this will be in turn replaced by p, etc. Prolog will enter an infinite loop not noticing that no progress is being made.

Any differences in order of the clauses may cause finite loops. For example you can’t move if you don’t get up.

Different variation of clauses produces different answers.

The predecessor procedure consists of two clauses, and one of them has two goals in the body. There are,therefore, 4 variations of this program, which have the same declarative meaning, can be obtained by:

Swapping both clauses, and

Swapping the goals for each order of clause.

The Original version:

pred1(X, Z) :- parent(X, Z).

pred1(X, Z) :- parent(X, Y), pred1( Y, Z).

Variation a:

pred2(X, Z) :- parent(X, Y), pred2( Y, Z).

pred2(X, Z) :- parent(X, Z).

Variation b:

pred3(X, Z) :- parent(X, Z).

pred3(X, Z) :- pred3( X, Y), parent(Y, Z).

Variation c:

pred4(X, Z) :- pred4( X, Y), parent(Y, Z).

pred4(X, Z) :- parent(X, Z).

Let’s see what happens if we ask whether Tom is a predecessor of Pat using the four variations of the predecessor relation:

?- pred1(tom, pat).

yes

?- pred2(tom, pat).

yes

?- pred3(tom, pat).

yes

?- pred4(tom, pat).

Prolog can not find the answer and this is manifested on the terminal by a Prolog message such as “More core needed” or “Stack Overflow”.

### Procedural Meaning

The procedural meaning specifies how Prolog answers questions.

Input: a program and a goal list.

Output: a success/failure indicator and an instantiation of variables.

The meaning of the two output results is as follows:

The success/failure indicator is ‘yes’ if the goals are satisfiable and ‘no’ otherwise.

An instantiation of variables is only produced in the case of a successful termination; in the case of failure there is no instantiation.

Input: a program and a goal list.

Output: a success/failure indicator and an instantiation of variables.

The meaning of the two output results is as follows:

The success/failure indicator is ‘yes’ if the goals are satisfiable and ‘no’ otherwise.

An instantiation of variables is only produced in the case of a successful termination; in the case of failure there is no instantiation.

Labels:
Meaning,
Procedural,
prolog

### Declerative Meaning

Declarative reading of the clause “P:-Q,R” are:

P is true if Q and R are true.

From Q and R follows P.

Procedural readings of this clause are:

To solve the problem P, first solve the subproblem Q and then R.

To satisfy P, satisfy Q and then R.

Note that ‘,’ character indicates AND operator.

Note that ‘;’ character indicates OR operator.

AND operator has a higher priority then the OR operator.

“P :- Q, R; S, T, U.” and “P :- (Q, R); (S, T, U).” clauses gives the same results.

Same clauses can be written as:

P :- Q, R.

P :- S, T, U.

P is true if Q and R are true.

From Q and R follows P.

Procedural readings of this clause are:

To solve the problem P, first solve the subproblem Q and then R.

To satisfy P, satisfy Q and then R.

Note that ‘,’ character indicates AND operator.

Note that ‘;’ character indicates OR operator.

AND operator has a higher priority then the OR operator.

“P :- Q, R; S, T, U.” and “P :- (Q, R); (S, T, U).” clauses gives the same results.

Same clauses can be written as:

P :- Q, R.

P :- S, T, U.

Labels:
Declerative,
Meaning,
prolog

Subscribe to:
Posts (Atom)