Prolog/Math, Functions and Equality
This section explains how to use math in prolog, using functions and equality.
Numbers in Prolog Edit
Prolog, like any other programming language, has a representation for numbers. Numbers are used like constants, and represented like they are anywhere on the computer, the following are valid ways of dealing with numbers in a predicate:
a(12, 345). a(A) :- b(A, 234.3). a(345.3409857) :- b(23476.923804).
To perform mathematical operations on numbers, we will need functions. To store the result of a mathematical operation in a variable, we will need to look more closely at equality.
Until now, predicates have always represented a simple true or false. Predicate a(A, B) is true or false, depending on the values of A and B. Functions are predicates that represent a value. The sin() predicate, for instance, is a function. sin(0) represents the value 0 and sin(1) represents the value 0.841471. Functions can be used anywhere a number or constant can be used, in queries, predicates and rules. For instance, if the fact p(0). is in your program, the query ?- p(sin(0)). will unify with it.
The following common mathematical functions are built in to most Prolog implementations:
|+||2 + 3||5|
|-||36 - 5||31|
|*||4 * 3||12|
|^||4 ^ 2||16|
(table to be completed)
Note that functions themselves cannot be evaluated. the query ?- sin(3). will fail because sin() is implemented as function and not as a predicate.
One difference between functions and predicates is that the meaning (or definition) of a predicate is usually defined by you, in your program. When you use functions like sin(), they've already been defined in your prolog implementation. In other words, prolog will not find the definition in your program, but in it's library of built-in predicates. It is possible to create your own functions, but that's something you will usually not need.
There are several kinds of equality, with slightly different meanings. Here we will just look at the = operator and the is operator. First, look at:
?- A is 36/5.
This query assigns the result of mathematical operation 36/5 to the variable A. So Prolog will answer:
A = 7.2
This idea may be familiar from other programming languages. The = operator, however, is very different. It doesn't solve the right-hand side, but instead keeps it as a formula. So you get this:
?- A = 36/5. A = 36/5
Instead of assigning the result of the operation to the variable A, prolog assigns the operation to A, without evaluating it.
You can see the same thing with queries. If you ask
?- (31 is (36-5)).
You'll get "Yes", because the (36-5) is evaluated (solved). But if you ask
?- (31 = (36-5)).
You'll get "No", because Prolog will compare a number (31) to a formula (36-5), rather than to the result of solving the formula.
The is operator is meant specifically for mathematical functions. The left argument has to be a variable and the right argument has to be a mathematical function with all variables instantiated. The = operator is used for unification of variables and can be used with any two arguments (although it will fail if the two arguments aren't the same and can't be made the same by instantiating variables a certain way).
Prolog knows many other ways of comparing two terms or instantiating variables, but for now, these two will suffice. When working with functions, we will almost always use the is operator.
Now that we know about functions and equality, we can start programming with math.
plus(A, B, C) :- C is A + B.
This predicate adds two numbers (A and B), and unifies the result with C. The following program is somewhat more complex.
fac(0,1). fac(A,B) :- A > 0, Ax is A - 1, fac(Ax,Bx), B is A * Bx.
This program calculates the factorial of A (A! in math notation).
It works recursively. The first rule states that the factorial of 0 is 1. The second states that the factorial of a number A greater than 0 is the factorial of A-1 times A.
(1) What will prolog answer to the following queries (on an empty database)? Try to think of the answer yourself, and then use a prolog compiler to verify it.
- ?- X = 1 + 2 + 3.
- ?- X is 100/10.
- ?- X is (14 + 16)/3, X + 3 = Y.
- ?- X = 1000/100 + 5, Y is X.
(2) Write a predicate called sigma, such that sigma(A,B,N) is true when N=A+(A+1)+(A+2)+...+(B-2)+(B-1)+B. In other words, . You may assume that A and B are integers with B>A. Test your predicate with queries such as:
?- sigma(4,9,X). X = 39 ; fail. ?- sigma(-7,-2,X). X = -27 ; fail. ?- sigma(-5,5,X). X = 0 ; fail.
(3) The factorial program shown at the end of this chapter sins against one of the guidelines of using recursive rules. In the second rule:
fac(A,B) :- A > 0, Ax is A - 1, fac(Ax,Bx), B is A * Bx.
The recursive part is not the last predicate in the rule.
- Show how prolog evaluates the query ?- fac(3, X). and explain why the program is set up like this.
- Explain why the line A > 0 is necessary. What would prolog do after it had found an answer, if the line was missing?
Answers to Exercises Edit
(1) ?- X = 1 + 2 + 3.
X = 1 + 2 + 3. ?- X is 100/10. X = 10.
?- X is (14 + 16)/3, X + 3 = Y. X = 10. Y = 10 + 3.
?- X = 1000/100 + 5, Y is X. X = Y, Y = 15.
(2) As usual, there is more than one way to solve this problem. Here's one way which uses recursion in a similar way to the factorial predicate.
sigma(A,A,A). sigma(A,B,N) :- B>A, %What do you think would happen if you removed this line? Try it. Why does this happen? A1 is A+1, sigma(A1,B,N1), N is A+N1.
Tail Recursive way: sigma(A,B,N):- add_1(A,B, A, N).
B > A, A1 is A + 1, Count1 is Count + A1, add_1(A1, B, Count1, N).