Courses/CS 332L/Introduction to Prolog

From CSWiki

Prolog is especially useful for symbolic computation. Look at this program for symbolic differentiation. (This is more sophisticated than you will be able to understand right now, but it's a good illustration of the power of Prolog.) Try the following.

• Copy the program into a file called symbolicDifferentiation.pl. (The Prolog extension is .pl.)
• Start SWI-Prolog.
• Within SWI-Prolog, load symbolicDifferentiation.pl. (File > Consult then browse for symbolicDifferentiation.pl.)
• At the ?- prompt enter:

?-  differentiate(x^2 + 3*x + 5, x, Answer).

Answer = 2*x+3

This says that the derivative of x^2 + 3*x + 5 with respect to x is 2*x+3.

But the simplifier built into the program is quite primitive. Try the following.

?- differentiate(4*x^2 + 3*x + 5, x, Answer).

Answer = 4* (2*x)+3

The system did not simplify 4*(2*x)+3 to be 8*x+3. It got a correct answer, but not in the simplest form.

Note a number of conventions.

• Numbers represent themselves.
• Alphanumeric identifiers that begin with lower case letters are used for predicates (as in differentiate) and atoms (as in x). In Prolog, the word predicate is used for what would normally be called a function, or method, or subprogram in other languages.
• Alphanumerics identifiers that begin with upper case letters are used for variables (as in R).

Here are some more things to notice.

• In Prolog programs, separate statement-like components are separated by , .
• On the ?- line, inputs must be terminated with . .
• Values are always returned through parameters. Predicates are not functions. They don't return values in the traditional way.
• Prolog has no control structures. To get the effect of an if statement, one writes multiple clauses. Notice that deriv/3 and simplfy/2 both have multiple clauses. (Note also the notation for referring to predicates: name/arity.

[edit] member/2

member(A, [A|_]).
member(A, [_|B]) :- member(A, B).

This program determines whether an element is in a list.

Try adding it to your program.

Then try

?- member(X, [a, b, c]).

X = a

This asks whether the variables X is a member of the list [a, b, c]. The answer is that X = a is such a member.

Note that Prolog notation for lists is square brackets around a list of elements.

Note also that Prolog does pattern matching. The first clause succeeds since X, which starts out as an undefined variable, can be set to a, the first element in the list. This is a very powerful capability called unification.

?- member(a, [a, b, c]).

Yes
?- member(b, [a, b, c]).

Yes
?- member(c, [a, b, c]).

Yes
?- member(d, [a, b, c]).

No

The preceding ask whether a, b, c, and d are members of [a, b, c]. The answers are Yes for all but d.

Let's trace through how Prolog answers these questions.

1. The first one, member(a, [a, b, c]) is answered by the first clause.
2. The second one, member(b, [a, b, c]) is answered by the second clauses, which calls the first clause with member(b, [b, c]).
3. The third one member(c, [a, b, c]) is answered like the second one but with two recursive calls.
4. The fourth one member(d, [a, b, c]) makes repeated recursive calls until it gets to member(d, []). There is no clause that matches that call, which is why the system returns No.

To see how this runs, you can trace through it.

 ?- trace, member(d, [a, b, c]).
   Call: (9) member(d, [a, b, c]) ? creep
   Call: (10) member(d, [b, c]) ? creep
   Call: (11) member(d, [c]) ? creep
   Call: (12) member(d, []) ? creep
   Fail: (12) member(d, []) ? creep
   Fail: (11) member(d, [c]) ? creep
   Fail: (10) member(d, [b, c]) ? creep
   Fail: (9) member(d, [a, b, c]) ? creep

No

To take a single step (creep) hit "c" or the Enter key.

?- member(X, [a, b, c]).

X = a ;

X = b ;

X = c ;

No

This asks again for a value to be assigned to X which is a member of [a, b, c]. After getting each answer, we type ; to ask Prolog to backtrack and look for additional answers. It finds all possible answers until there are no more.