CSI2120 Programming Paradigms Jochen Lang
jlang@uottawa.ca
Faculté de génie | Faculty of Engineering
Jochen Lang, EECS jlang@uOttawa.ca
Arithmetic Expressions and I/O
• Arithmetic Expressions
– Built-in operators
– Unification with numbers – Recursive calculations
– Looping with repeat
– Generator
• Input and output: Streams
– Reading and writing to console – Reading and writing to file
– Character i/o
Jochen Lang, EECS jlang@uOttawa.ca
Numbers in Prolog
• Prolog recognizes numbers
– integers and floating point
• Number constants
5 1.75 0 1.345e-10 -27 -3.4 42
• Rules about arithmetic expressions use – number constants
– arithmetic operators
– arithmetic variables
Jochen Lang, EECS jlang@uOttawa.ca
Arithmetic Expressions
• Prolog supports common operators as built-ins including
X+Y
X-Y
X*Y
X/Y
X // Y %integer division
X mod Y
• Mathematical functions, e.g.,
abs(X)
ln(X)
sqrt(X)
Jochen Lang, EECS jlang@uOttawa.ca
Evaluating Arithmetic Expressions
• Special predicate “is” in order to treat variables and operators as relating to mathematical operations
?- 1+2 = 1+2.
true.
?- 3 = 1+2.
false.
?- 1+2 = 2+1.
false.
?- 3 is 1+2.
true.
?- X is 1+2, X is 2+1.
X = 3.
Jochen Lang, EECS jlang@uOttawa.ca
Unification with Arithmetic Expressions
• Careful with expressions and unification – Unification of 1+2 and 3 fails.
• 3 is a number, while 1+2 is a term.
– Evaluation of arithmetic expression is not part of the regular unification algorithm and does not happen automatically
Jochen Lang, EECS jlang@uOttawa.ca
Infix Comparison Operators
• Comparisons
X=:=Y %XequalsY X=\=Y %XnotequalsY X
X >= Y
• The operators are applied after calculations, e.g.,
?- 1+2 =:= 2+1.
true.
Jochen Lang, EECS jlang@uOttawa.ca
Example: Min Predicate
min(X,Y,X) :- X
• What queries can we ask?
?- min(5,7,X).
?- min(5,X,7). % false
?- min(X,5,7). % false
?- min(X,Y,7). % error – why?
Jochen Lang, EECS jlang@uOttawa.ca
Predicates using Recursion: power
• Positive Powers
– boundary case for power to 1
pow( X, 1, X ).
– recursion to calculate the product
pow( X, Y, Z ) :- Y > 1,
Y1 is Y – 1,
pow( X, Y1, Z1 ), Z is X * Z1.
Jochen Lang, EECS jlang@uOttawa.ca
Predicates using Recursion: gcd
• Greatest common divisor – Boundary condition
• gcd of 0 and any number is the number itself
gcd(U,0,U).
– Recursive clause based on Euclid’s algorithm
• modulo divisions until remainder is 0 at which point we found a divisor for all intermediate divisors and the original number
gcd(U,V,W) :- V>0, R is U mod V, gcd(V,R,W).
• Alternative implementation of Euclid’s algorithm
gcd(A,A,A).
gcd(A,B,GCD):- A
Jochen Lang, EECS jlang@uOttawa.ca
Animation of Euclid’s Algorithm
gcd(1071,462,W) :-
462>0, 147 is 1071 mod 462,
gcd(462,147,W) :-
147>0, 21 is 462 mod 147,
gcd(147,21,W) :-
21>0, 0 is 147 mod 21,
gcd(21,0,W).
W = 21.
Image source: Wikimedia Commons, CC 3.0, Author: Proteins
Jochen Lang, EECS jlang@uOttawa.ca
Predicates using Recursion: fibonacci
• Fibonacci numbers
– aseriesofnumbers1123581321…
– Recursive clause based on Fibonacci’s algorithm • fib(N) = fib(N-1) + fib(N-2)
fib(N,F):- N>1,
N1 is N-1,
N2 is N-2,
fib(N1,F1),
fib(N2,F2),
F is F1+F2.
– Two boundary conditions are needed.
fib(0,1).
fib(1,1).
Jochen Lang, EECS jlang@uOttawa.ca
Example with Crossed Recursions
Predicate to test if a positive number is even
even(0).
odd(N) :- N>0,
M is N-1,
even(M). even(N):- N>0,
M is N-1,
odd(M).
Jochen Lang, EECS jlang@uOttawa.ca
A Last Example
• Interval test to see if X is in the interval between L and H
intervalTest(X,L,H):- X>=L, X=