Prolog Programming for AI - Chapter 7 Notes and Exercises

Summary

The type of a term can be tested by the following predicates:
- var(X) X is a (non-instantiated) variable
- nonvar(X) X is not a variable
- atom(X) X is an atom
- integer(X) X is an integer
- atomic(X) X is either an atom or an integer
Terms can be constructed or decomposed:

Term = .. [Functor | ArgumentList]

functor( Term, Functor, Arity)

arg(N, Term, Argument)

name(Atom, CharacterCodes)
A prolog program can be viewed as a relational database that can be updated by the following procedures:

assert(Clause) add Clause to the program

asserta(Clause) add at the beginning

assertz(Clause) add at the end

retract(Clause) remove a clause that matches Clause
All the objects that satisfy a given condition can be collected into a list by the predicates:

bagof(X, P, L) L is the list of all X that satisfy condition P

setof(X, P, L) L is the sorted list of all X that satisfy condition P

findall(X, P, L) similar to bagof
repeat is a control facility that generates an unlimited number of alternatives for backtracking

Testing the type of terms

Predicates var, nonvar, atom, integer, atomic

var(X)

This goal succeeds if X is currently an uninstantiated variable.

nonvar(X)

This goal succeeds if X is a term other than a variable, or X is an already instantiated variable.

atom(X)

This is true if X curretly stands for an atom.

integer(X)

This goal is true if X currently stands for an integer.

atomic(X)

This goal is true if X currently stands for an integer or an atom.

Question: Why do we need atom?

count(A, L, N) where A is the atom, L is the list and N is the number of occurrences.

count(_, [], 0).
count(A, [B | L], N) :-
    atom(B),
    A = B,             % B is atom A?
    !,
    count(A, L, N1),   % Count in tail
    N is N1 + 1;
    count(A, L, N).    ％ Otherwise just count the tail

A cryptarithmetic puzzle using nonvar

A popular example of a cryptarithmetic puzzle is

D O N A L D

+ G E R A L D

=============
R O B E R T

We will define a relation sum(N1, N2, N) where N1, N2, N represent the three numbers of a given cryptarithmetic puzzle. The goal sum(N1, N2, N) is true if an assignment of digits to letters such that N1 + N2 = N.

The puzzle can be stated to Prolog by the question:

1	?- sum([D, O, N, A, L, D], [G, E, R, A, L, D], [R, O, B, E, R, T]).

to define the sum relation on lists of digits, we have to implement the actual rules for doing summation in the decimal number system.

In general, some additional information is involved, besides the three numbers N1, N2 and N:

carry digit before the summation of the numbers
carry digit after the summation
set of digits available before the summation
remaining digits, not used in the summation

To formulate the sum relation we will use the principle of generalization of the problem: we will introduce an auxiliary sum1. (sum1(N1, N2, N, C1, C, Digits1, Digits), where N1, N2 and N are our three numbers, C1 is carry from the right, before summation of N1 and N2, and C is carry to the left, after the summation.)

% Solving cryptarithmetic puzzles
sum(N1, N2, N) :-                            % Numbers represented as lists of digits
    sum1(N1, N2, N,
         0, 0,                               % Carries from right and to left both 0
         [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, _])  % All digits available
         
sum1([], [], [], 0, 0, Digits, Digits).
sum1([D1 | N1], [D2 | N2], [D | N], C1, C, Digs1, Digs) :-
    sum1(N1, N2, N, C1, C2, Digs1, Digs2) :-
    digitsum(D1, D2, C2, D, C, Digs2, Digs).

digitsum(D1, D2, C1, D, C, Digs1, Digs) :-
    del(D1, Digs1, Digs2),    % select an available digit for D1
    del(D2, Digs2, Digs3),    % select an available digit for D2
    del(D, Digs3, Digs),      % select an available digit for D
    S is D1 + D2 + C1,
    D is S mod 10,
    C is S div 10.

del(A, L, L) :-
    nonvar(A), !.    % A already instantiated
del(A, [A | L], L).
del(A, [B | L], [B | L1]) :-
    del(A, L, L1).

Exercises

Write a procedure simplify to symbolically simplify summation expressions with numbers and symbols (lower-case letters). Let the procedure rearrange the expressions so that all the symbols precede numbers. Theses are examples of its use:
1
2
3
4
5
?- simplify(1 + 1 + a, E).
E = a + 2
?- simplify(1 + a + 4 + 2 + b + c, E).
E = a + b + c + 7
?- simplify (3 + x + x, E).
Define the procedure add(Item, List) to store a new element into a list. Assume that all of the elements that can be stored are atoms. List contains all the stored elements followed by a tail that is not instantiated and can thus accommodate new elements. For example, let the existing elements stored be a, b and c.

Then List = [a, b, c | Tail] where Tail is a variable.

The goal add(d, List) will cause the instantiation:Tail=[d | NewTail] and List=[a, b, c, d | NewTail]

Thus the structure can grow by accepting new items. Define also the corresponding membership relation.

Constructing and decomposing term: =…, functor, arg, name

The goal Term =.. L is true if L is a list that contains the principal functor of Term, followed by its arguments. The following examples illustrate:

?- f(a, b) =.. L.
L = [f, a, b]
?- T =.. [rectangle, 3, 5].
T = rectangle(3, 5)
?- Z =.. [p, X, f(X,Y)].
Z = p(X, f(X, Y))

Exercises

Define the predicate ground(Term) so that it is true if Term does not contain any uninstantiated variables.

Various kinds of equality

X = Y

This is true if X and Y match
X is E

This is true if X matches the value of the arithmetic expression E
E1 =:= E2

This is true if the values of the arithmetic expressions E1 and E2 are equal
E1 =\= E2

This is true if the values of the arithmetic expression E1 and E2 are not equal
T1 == T2

This is true if terms T1 and T2 are identical
- This is a stricter kind of equality: the literal equality of two terms
T1 \== T2

This is true if terms T1 and T2 are not identical

?- f(a, b) == f(a, b).
yes
?- f(a, b) == f(a, X).
no
?- f(a, X) == f(a, Y).
no
?- X \== Y.
yes
?- t(X, f(a, Y)) == t(X, f(a, Y)).
yes

count(Term, List, N)
count(_, [], 0).
count(Term, [Head | L], N) :-
    Term == Head, !,
      count(Term, L, N1),
      N is N1 + 1,
    count(Term, L, N).

Database manipulation

assert(C)

this goal always succeeds and causes a clause C to be ‘asserted’
retract(C)

this goal deletes a clause that matches C

?- crisis.
no
?- assert(crisis).
yes
?- crisis.
yes
?- retract(crisis).
yes
?- crisis.
no

?- assert(
         (faster(X, Y) :-
             fast(X), slow(Y))).
yes
?- assert(fast(ann)).
yes
?- assert(slow(tom)).
yes
?- assert(slow(pat)).
?- faster(A, B).
A = ann,
B = tom
?- retract(slow(X)).
X = tom;
X = pat;
no
?- faster(ann, _).
no

asserta(C)

this goal adds C at the beginning of the database
assertz(C)

this goal adds C at the end of the database

1
2
3

% memoization!
?- solve(problem1, Solution),
asserta(solve(problem1, Solution)).

Exercises

(a) Write a Prolog question to remove the whole product table from the database
1
?- retract(product(_, _, _)), fail; true.
(b) Modify the question so that it only removes those entries where the product is 0
1
?- retract(product(_, _, 0)), fail; true.
Define the relation copy(Term, Copy) which will produce a copy of Term so that Copy is Term with all its variables renamed. This can be easily programmed by using assert and retract

Control facilities

cut, written as ‘!’

prevents backtracking
fail

is a goal that always fails
true

is a goal that always succeeds
not(P)

is a type of negation that behaves exactly as if defined as

not(P) :- P, !, fail; true.
call(P)

invokes a goal P. It succeeds if P succeeds.

repeat

is a goal that always succeeds. Its special property is that it is non-deterministic; therefore, each time it is reached by backtracking it generates another alternative execution branch. Repeat behaves as if defined by:

repeat.

repeat :- repeat.

A typical way of using repeat is illustrated by the following procedure dosquares which reads a sequence of numbers and outputs their squares.

dosquares :-
    repeat,
    read(X),
    (X = stop, !;
     Y is X * X, write(Y), fail).

bagof, setof and findall

class(a, vow).
class(b, con).
class(c, con).
class(d, con).
class(e, vow).
class(f, con).

?- bagof(Letter, class(Letter, con), Letters).
Letters = [b, c, d, f]
?- bagof(Letter, class(Letter, Class), Letters).
Class = vow,
Letters = [a, e];
Class = con,
Letters = [b, c, d, f]

if there is no solution for P in the goal bagof(X, P, L) then the bagof goal simply fails.

1 2	?- setof(Class/Letter, class(Letter, Class), List). List = [con/b, con/c, con/d, con/f, vow/a, vow/e]

1 2	?- findall(Letter, class(Letter, Class), Letters). Letters = [a, b, c, d, e, f]

If there is no object X that satisfies P then findall will succeed with L = [].

findall(X, Goal, Xlist):-
    call(Goal),
    assertz(stack(X)),
    fail;
    assertz(stack(bottom)),
    collect(Xlist).
collect(L) :-
    retract(stack(X)), !,
    (
     X == bottom, !, L =[];
     L = [X | Rest], collect(Rest)).

Exercises

Use bagof to define the relation powerset(Set, Subsets) to compute the set of all subsets of a given set (all sets represented as lists)
Use bagof to define the relation copy(Term, Copy) such that Copy is Term with all its variables renamed.