## Prolog notes

Posted by Peter W on March 26, 2007

These are my notes about Prolog stuff for my discrete math class. I’m working through part of Jim Hein’s Prolog Lab Manual. Note: blockquotes are from the lab manual, and sometimes but not always the “Yes” or “No” results are left out if unimportant.

### Chapter 1

Here is my modified familyTree.pl program listing:

[user]. % Here is a set of facts describing parental relationships. par(lloyd, james). par(lloyd, janet). par(ruth, james). par(ruth, janet). par(emma, lloyd). par(katherine, ruth). par(adolph, lloyd). par(edgar, ruth). % we need some cousins par(james, jamesjr). par(janet, janetjr). % The grandparent relationship. Any rule of the form % A :- B, C is read, A is true if B is true and C is true. grand(X, Z) :- par(Y, Z), par(X, Y). sib(X, Y) :- par(Z, X), par(Z, Y), X == Y. cous(X, Y) :- par(A, X),par(B, Y),sib(A, B).

Checking that the cousin relation works:

?- cous(A, B). A = jamesjr B = janetjr ; A = jamesjr B = janetjr ; A = janetjr B = jamesjr ; A = janetjr B = jamesjr ; No ?- listing(cous). cous(A, B) :- par(C, A), par(D, B), sib(C, D). Yes ?-

Now I want to check that ‘cous’ works:

?- cous(jamesjr, X). X = janetjr ; X = janetjr ; No

Hmm… it returned ‘janetjr’ twice. If I cared to make it so it only returned one match per cousin, I would load the smallest possible database which contains cousins in it and use ‘spy(cous).’ to stop the interpreter at the cousin clause, then use [ENTER] to “creep” and ‘l’ to “leap” (continue until we reach a spy point again) , and later ‘nospy(cous).’ to remove the “spy point” (or use “nospyall” to remove all spy points). It is weird that even after doing that the input prompt looks like “[debug] ?-“.

I then tried loading the system library which appeared to work, but running a system command failed. I either missed something in the manual, or it is incomplete.

>> library(system) compiled into swi_system_utilities 0.01 sec, 1,944 bytes Yes ?- system('ls'). ERROR: (user://2:187): Undefined procedure: system/1 ?- system('vi filename'). ERROR: (user://2:190): Undefined procedure: system/1 ?- use_module(library(foo)). ERROR: (user://2:193): source_sink `library(foo)' does not exist ?- use_module(liber(fo)). ERROR: (user://2:196): source_sink `liber(fo)' does not exist

I may have a newer version of swi-prolog. The manual says to use shell(), which does work for me.

>> ?- shell(ls) Desktop School letter.txt

Thats it for chapter 1.

### Chapter 2.1

If a, b, and c are clauses, we can say that c is a or b by typing:

c :- a;b.

1. Input the program consisting of the two clauses p(a) and p(b). Then ask

the following questions:

|?- p(a).

|?- p(b).

|?- p(c).

17

Beginning Experiments

Use backtracking to find all possible answers to the following question.

|?- p(X).

OK:

?- [user]. |: p(a). |: p(b). |: % user://1 compiled 0.00 sec, 432 bytes Yes ?- p(a). Yes ?- p(b). Yes ?- p(c). No ?- p(X). X = a ; X = b ; No

2. Input the single clause q(_). Then ask the following questions:

|?- q(a).

|?- q(b).

|?- q(c).

Describe what happens when you try to find all possible answers to the

following question.

|?- q(X).

?- [user]. |: q(_). |: % user://1 compiled 0.00 sec, 428 bytes Yes ?- q(a). Yes ?- q(b). Yes ?- q(c). Yes ?- q(X). X = _G157 ; No

I think _G157 is the name for an anonymous variable that the Prolog interpreter uses when it is trying to find matches. This is the closest match it finds, and when I tell it to look for more it comes back and says it can’t (“No”).

3. Input the following three clauses.

r(a).

r(b).

s(X) :- r(X).

Now ask the following questions:

|?- s(a).

|?- s(b).

|?- s(c).

Use backtracking to find all possible answers to the following questions.

|?- s(A).

|?- r(A).

?- s(a). Yes ?- s(b). Yes ?- s(c). No ?- s(A). A = a ; A = b ; No ?- r(A). A = a ; A = b ; No

4. Verify that the conjunction of clauses with the same head can be

represented by a single clause using the “or” construction by doing the

following tests. For each input the given data and then ask the question

|?- p(a).

Perform each test separately with only the given clauses as input.

a. p(b). b. p(c).

p(a) :- p(b). p(a) :- p(b).

p(a) :- p(c). p(a) :- p(c).

c. p(b). d. p(c).

p(a) :- p(b) ; p(c). p(a) :- p(b) ; p(c).

These all return Yes, because they’re all true.

### Chapter 2.2

Equality operators: syntactic (==), semantic aka numeric (=:=) and unification (=).

1. Try out some unification experiments like the following. First find the

answers by hand. Then check your answers with Prolog.

|?- p(X) = p(a).

|?- p(X, f(Y)) = p(a, Z).

|?- p(X, a, Y) = p(b, Y, Z).

|?- p(X, f(Y, a), Y) = p(f(a, b), V, Z).

|?- p(f(X, g(Y)), Y) = p(f(g(a), Z), b).

- X=a (obviously).
- X=a, Z=f(Y), Y=Y
- X=b, Y=a, Z=Y=a
- X= f(a,b), V=f(Y,a), Z=Y
- X=g(a), Y=b, Z=g(b)

An algorithm that tries to match terms is called a unification algorithm.

These algorithms have an “occurs check” that stops the process if an

attempt is made to unify a variable X with a non-variable term in which

X occurs. For example, X and p(X) do not unify. However, most versions

of Prolog do not implement the occurs check to save processing time. Try

the following tests to see whether Prolog implements the occurs check.

|?- p(X) = p(g(X)).

|?- p(f(a, X)) = p(X).

|?- f(X) = X.

|?- [a|X] = X.

?- p(X) = p(g(X)). X = g(g(g(g(g(g(g(g(g(g(...)))))))))) ; No ?- p(f(a, X)) = p(X). X = f(a, f(a, f(a, f(a, f(a, f(a, f(a, f(a, f(a, f(..., ...)))))))))) No ?- f(X) = X. X = f(f(f(f(f(f(f(f(f(f(...)))))))))) ; No ?- [a|X] = X. X = [a, a, a, a, a, a, a, a, a|...] ; No

Yeah, looks like swi-prolog doesn’t have the “occurs check”.

The international standard ISO Prolog has a predicate for unification

with the occurs check. The name of the predicate is

unify_with_occurs_check.

In SICStus Prolog the predicate is in the “terms” library. So the

following command must be executed first.

|?- use_module(library(terms)).

Unfortunately the CS machines at PSU don’t seem to have that library:

?- use_module(library(terms)). ERROR: source_sink `library(terms)' does not exist

### Chapter 2.3 Numeric computations

Binary operators

+, –, *, /, //, rem, mod, sin, cos, atan.

Unary operators

+, –, abs, ceiling, floor, float, truncate, round, exp, sqrt, log.

22 Prolog Experiments

Numeric Comparison. Numerical expressions can be compared with binary

comparison operators. The six operators are given as follows:

=:=, =\=, , ==.…

Test each of the numeric binary, unary, and comparison operations.

?- X is 5 + 2. X = 7 ?- X is 1 - 3. X = -2 ?- X is 3 * 4. X = 12 ?- X is 12 / 3. X = 4 ?- X is 10 / 3. X = 3.33333 ?- X is 10 // 3. X = 3 ?- X is 10 mod 3. X = 1 ?- X is 10 rem 3. X = 0.333333 ?- X is +5. X = 5 ?- X is -5. X = -5 ?- X is abs(-5). X = 5 ?- X is ceiling(5.2). X = 6 ?- X is floor(5.2). X = 5 ?- X is float(5.2). X = 5.2 ?- X is float(5). X = 5.0 ?- X is truncate(5.2). X = 5 ?- X is round(5.5). X = 6 ?- X is exp(1). X = 2.71828 ?- X is sqrt(4). X = 2 ?- X is sqrt(-1). ERROR: sqrt/1: Arithmetic: evaluation error: `undefined' ?- X is log(10). X = 2.30259 ?- X is log(exp(1)). X = 1

Interesting things to note: log() is base e, so it should have been called ln IMHO, sqrt() of negative numbers doesn’t work (what can you expect?), the ⁄⁄ operator does integer division and the ‘rem’ operator gives the fractional remainder part of division.

If we don’t want to type goals of the form “X is expression” we can define

a predicate to do the job. For example, a predicate to evaluate and print

a numeric expression can be defined as follows:

eval(X) :- A is X, write(A).

Try it out on several expressions. For example, try the goal

|?- eval(sin(5)*sin(5) + cos(5)*cos(5)).

?- [user]. |: eval(X) :- A is X, write(A). |: % user://1 compiled 0.00 sec, 492 bytes Yes ?- eval(1). 1 Yes ?- eval(floor(2.8)). 2 Yes ?- eval(sin(5)*sin(5) + cos(5)*cos(5)). 1 Yes

### Chapter 2.4 Type Checking

Prolog has these type checker predicates defined:

var, nonvar, integer, float, number, atom, atomic, compound.

We could define our own as well. The lab manual suggests defining nat(X) to mean that X is a natural number, that is, a nonnegative integer.

Test each of the type checker predicates.

?- float(25.0). Yes ?- float(25). No ?- var(X). X = _G157 ; No ?- var(D). D = _G157 Yes ?- var(2). No ?- nonvar(X). No ?- nonvar(2). Yes ?- integer(2). Yes ?- integer(2.5). No ?- number(2). Yes ?- number(2.5). Yes ?- number(X). No ?- atom(X). No ?- atom(p(a)). No ?- atom(p(X)). No ?- atom(1). No ?- atom(c). Yes ?- atom(_foo). No ?- atom(foo). Yes ?- atomic(1). Yes ?- atomic(X). No ?- compount(c). Correct to: compound(c)? yes No ?- compound(p). No ?- [user]. |: p(a) :- p(b);p(c). |: % user://2 compiled 0.01 sec, 260 bytes Yes ?- compound(p(a)). Yes

Construct a type checker for each of the following sets.

a. The non-negative numbers.

b. The even integers.

c. {0, 1, 2, 3,4, 5, 6, 7, 8}.

?- [user]. |: noneg(X) :- number(X), X >= 0. |: even-int(X):- integer(X), X mod 2 is 0. |: specialset(X) :- integer(X), X >= 0, X = 0, X =

I had more, but the PSU computer I was working on ate it. Grr.

## Leave a Reply