Vagabond Shark

Ideas, Bikes, Art, Design, Architecture, Politics, Tech, Software

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).

  1. X=a (obviously).
  2. X=a, Z=f(Y), Y=Y
  3. X=b, Y=a, Z=Y=a
  4. X= f(a,b), V=f(Y,a), Z=Y
  5. 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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: