COMP 348 Principles of Programming Languages
COMP 348
PRINCIPLES OF
PROGRAMMING
LANGUAGES
LECTURE 11 – PROLOG APPLICATIONS
Fall 2021Dept. of Computer Science and Software Engineering, Concordia University
Logical Programming with PROLOG
[Deterministic] Finite State Machines (FSMs)
2
• The following materials are the original lecture note from
the Course Pack “COMP 348 Principles of Programming
Languages” written and developed by:
Dr. Constantinos Constantinides, P.Eng.
Department of Computer Science and Software Engineering
Concordia University, Montreal, Quebec, Canada
.ca
https://users.encs.concordia.ca/~cc/
3
Acknowledgement and Copyright Notice
mailto: .ca
https://users.encs.concordia.ca/~cc/
Formalities of a Deterministic FSM AKA DFA
4
( )FqQM ,,,, 0=
Q
0q
F
: States (a finite set of states)
: Alphabet (a finite set of input symbols)
: Transition function (δ: QxΣ→Q)
: Initial state (an element of Q)
: Final states (a subset of Q)
Example
5
0q 1q 2q 3q 4q
a b b a
5q
a a bb
ba,
ba,
Input Alphabet
6
0q 1q 2q 3q 4q
a b b a
5q
a a bb
ba,
ba,=
ba,
Set of States
7
0q 1q 2q 3q 4q
a b b a
5q
a a bb
ba,
543210 ,,,,, qqqqqqQ =
ba,
Initial State
8
0q
1q 2q 3q 4q
a b b a
5q
a a bb
ba,
ba,
0q
Final State(s)
9
0q 1q 2q 3qa b b a
5q
a a bb
ba,
4qF =
ba,
4q
Transition Function
10
0q 1q 2q 3q 4q
a b b a
5q
a a bb
ba,
QQ →:
ba,
( ) 10 , qaq =
2q 3q 4q
a b b a
5q
a a bb
ba,
ba,
0q 1q
Transition Function
11
( ) 50 , qbq =
1q 2q 3q 4q
a b b a
5q
a a bb
ba,
ba,
0q
Transition Function
12
0q 1q 2q 3q 4q
a b b a
5q
a a bb
ba,
ba,
( ) 32 , qbq =
Transition Function
13
Transition Function
14
0q 1q 2q 3q 4q
a b b a
5q
a a bb
ba,
a b
0q
1q
2q
3q
4q
5q
1q 5q
5q 2q
5q 3q
4q 5q
ba,
5q5q
5q5q
Languages Accepted by DFAs
The language includes all strings (over the
alphabet) accepted by
= { strings that drive to a final state}
15
( )ML
M
M( )ML
Example
16
0q 1q 2q 3q 4q
a b b a
5q
a a bb
ba,
ba,
( ) abbaML = M
accept
• Consider the following FSM:
17
Implementing FSMs in Prolog
• We can represent the transition function in the following table:
18
Implementing FSMs in Prolog
• We can represent an FMS by facts:
start(state).
transition(currentState, condition, nextState).
final(state).
• Example:
start (q0) .
final(q3) .
transition(q0, a, q1).
transition(q0, b, q0).
transition(q1, a, q2).
transition(q1, b, q0).
transition(q2, a, q2).
transition(q2, b, q3).
transition(q3, a, q1).
transition(q3, b, q0).
19
FMS Representation
• We can use a predicate i.e. accept/1 as in the following:
accept(Xs) :- start(Q), path(Q, Xs).
• The second goal above needs to be defined as a new rule:
path(Q, [XIXs]) :- transition(Q, X, Ql), path(Ql, Xs).
• If our input string is valid, we will eventually reach the final
state, having exhausted all symbols in the string:
path(Q, []) :- final(Q) . .
20
Building and Interpreter
• Given all the facts (start/1, final/1, and transition/3) and the
three rules (accept/1, and path/2), we can now execute the
interpreter program:
?- accept([a,a,b]).
Yes
?- accept([a,a,b,a,b,a,a,b]).
Yes
?- accept([]).
No
?- accept([b, a, a]).
No
21
Putting all together
Logical Programming with PROLOG
Boolean Algebra and Digital Gates
22
• Conjunction, AKA AND, denoted by ‘X’, ‘Λ’, or ‘.’,
e.g. p x q, also in short pq.
true if both p and q are true.
• Disjunction, AKA OR, denoted by ‘+’, ‘V’,
e.g. p + q.
true if either p or q are true, otherwise false.
• Inverse, AKA NOT, negation, whose truth value is the reverse
truth value of its operand, denoted by ‘’’, ‘~’, or ‘┐’,
e.g. ┐ p. some others use p.
23
Boolean Operations
_
• The truth table of the three Boolean operations are illustrated
in the following table:
24
Boolean Operations
_
• Any Boolean expression / clause can be written using the
three Boolean / logical gates, however, other gate are also
used in logic. See also:
– NAND
– NOR
– XOR
25
Boolean Operations
• We can define procedures to represent logical connectives in
Boolean algebra and consequently digital gates which are
the building blocks of digital circuits.
• we will follow the convention operation (in, out) to denote an
operation whose input is in and whose output is out, e.g:
– inv(0, 1). “The inverse of 0 is 1”
– inv(1, 0). “The inverse of 1 is 0”
– or(0, 0, 0).
– or(0, 1, 1). “The disjunction of 0 and 1 is 1”
– or(1, 0, 1).
– or(1, 1, 1).
26
Boolean Operations
• We can define procedures to represent logical connectives in
Boolean algebra and consequently digital gates which are
the building blocks of digital circuits.
• we will follow the convention operation (in, out) to denote an
operation whose input is in and whose output is out, e.g:
– and(0, 0, 0).
– and(0, 1, 0).
– and(1, 0, 0).
– and(1, 1, 1).
– nand(1, 0, 1).
– nand(0, 1, 1).
– nand(0, 0, 1).
– nand(1, 1, 0).
27
Boolean Operations
• We can define procedures to represent logical connectives in
Boolean algebra and consequently digital gates which are
the building blocks of digital circuits.
• we will follow the convention operation (in, out) to denote an
operation whose input is in and whose output is out, e.g:
– nor(1, 0, 0).
– nor(0, 1, 0).
– nor(0, 0, 1).
– nor(1, 1, 0).
– xor(1, 0, 1).
– xor(0, 1, 1).
– xor(0, 0, 0).
– xor(1, 1, 0).
28
Boolean Operations
• Digital circuits are made using the logical gates, as specified.
Below is an example of a digital Circuit:
29
Digital Circuits
• We can define a rule to represent the Boolean expression
(and consequently the digital circuit) as follows:
circuit(X, Y, Out) :-
inv(Y, Tmp1),
and(X, Tmp1, Tmp2),
or(Tmp2, Y, Out).
30
Digital Circuits
31
Digital Circuits
• We can now test the digital circuit by executing queries:
?- circuit(1, 1, Out)
Out = 1.
?- circuit(1, 0, Out)
Out = 1.
32
Digital Circuits
• We can also ask questions that correspond to ground and
non-ground queries, i.e. “Is it indeed the case that for X = 1
and for Y = 1, the output is 1?”
?- circuit(1, 1, 1)
true
“For what input values, if any, is the output 0?”
?- circuit(X, Y, 0)
X = 0,
Y = 0 ;
false
33
Digital Circuits
• We can also simulate the digital circuit by executing the
program as follows:
?- circuit(X, Y, OUT)
X = 0,
Y = 0,
OUT = 0 ;
X = 1,
Y = 0,
OUT = 1 ;
X = 1,
Y = 1,
OUT = 1 ;
X = 0,
Y = 1,
OUT = 1 ;
false.
Logical Programming with PROLOG
Complex Structures
34
• Prolog uses same unification process for complex structures.
owns(adam, car(bmw, black)).
owns(adam, car(porsche, red)).
owns(adam, car(jeep, green)).
?- owns(adam, X)
X = car(bmw, black) ;
X = car(porsche, red) ;
X = car(jeep, green) ;
false
35
Complex structures
• Prolog uses same unification process for complex structures.
owns(adam, car(bmw, black)).
owns(adam, car(porsche, red)).
owns(adam, car(jeep, green)).
?- owns(adam, car(X,_))
X = bmw ;
X = porsche ;
X = jeep ;
false
36
Complex structures
• Prolog uses same unification process for complex structures.
owns(adam, car(bmw, black)).
owns(adam, car(porsche, red)).
owns(adam, car(jeep, green)).
?- findall(X, owns(adam, X), Cars)
Cars = [car(bmw, black), car(porsche, red), car(jeep, green)]
?- findall(X, owns(adam, car(_,X)), L)
L = [black, red, green]
37
Complex structures
• Consider the following example, an structure with a list of
belongings:
owns(adam, [car(bmw, black), car(porsche, red), car(jeep, green)]).
• How to find all adam’s belongings?
?- owns(adam, Belongings)
Belongings = [car(bmw, black), car(porsche, red), car(jeep, green)]
• What if adam has other belongings?
38
Complex structures
• Consider the following example, an structure with a list of
belongings:
owns(adam, [car(bmw, black), car(porsche, red), car(jeep, green)]).
• How to find all cars that belong to adam?
?- owns(adam, Belongings),
findall(X, member(car(X, _), Belongings), Cars)
Belongings = [car(bmw, black), car(porsche, red), car(jeep, green)],
Cars = [bmw, porsche, jeep]
39
Complex structures
• A date example:
date(‘sep’, 1, 2015).
?- date(M, D, Y)
M = sep,
D = 1,
Y = 2015.
Note the use of quote in ‘Sep’.
40
Complex structures
date(‘Sep’, 1, 2015).
?- date(M, D, Y)
M = ‘Sep’,
D = 1,
Y = 2015.
• Expression trees are another example of complex structure:
plus( minus(num(3), num(1)), star(num(4), num(2))
41
Expression Trees
adapted from lecture notes of COMP348 by Dr. Nora Houari
• Expression trees are another example of complex structure:
plus( minus(num(3), num(1)), star(num(4), num(2))
may be unified with
plus( minus(num(3), num(X)), star(num(Y), num(2))
42
Expression Trees
adapted from lecture notes of COMP348 by Dr. Nora Houari
• Lets consider the following binary tree:
One way of representing the above tree would be using the
following facts:
node(5,3,6). leaf(1).
node(3,1,4). leaf(4).
leaf(6).
43
Binary Trees
adapted from lecture notes of COMP348 by Dr. Nora Houari
5
3
1 4
6
• Lets consider the following binary tree:
The preorder traverse of the tree (NLR) is as follows:
– Display the data part of the root (or current node).
– Traverse the left subtree by recursively calling the pre-order
function.
– Traverse the right subtree by recursively calling the pre-order
function.
44
Tree Traversal
adapted from lecture notes of COMP348 by Dr. Nora Houari
5
3
1 4
6
• Lets consider the following binary tree:
The preorder traverse of the tree (NLR) is as follows:
– For instance the preorder traverse of the above tree is:
5, 3, 1, 4, 6
45
Tree Traversal
adapted from lecture notes of COMP348 by Dr. Nora Houari
5
3
1 4
6
• Lets consider the following binary tree:
One of the applications of The preorder traversal is to get the polish
notation of a given expression, i.e.
+ * 1 3 7
46
Tree Traversal
adapted from lecture notes of COMP348 by Dr. Nora Houari
+
*
1 3
7
node(5,3,6).
node(3,1,4).
leaf(1).
leaf(4).
leaf(6).
Consider the following prolog program
preorder(Root, [Root]) :- leaf(Root).
preorder(Root, [Root | L]) :- node(Root, Child1, Child2),
preorder(Child1, L1),
preorder(Child2, L2),
append(L1, L2, L).
47
Tree Traversal
adapted from lecture notes of COMP348 by Dr. Nora Houari
5
3
1 4
6
?- preorder(5, L)
L = [5, 3, 1, 4, 6].
Logical Programming with PROLOG
More examples
48
• Example: how to find maximum of two numbers?
• max(X, Y, X) :- X > Y.
• max(X, Y, Y) :- X < Y. • max(X, X, X). ?- max(9, 5, X). X = 9; No ?- max(5, 9, X). X = 9; No Question: What is the output for max(5, 5, X)? 49 Relational and Logical Operators Alternatively, conditions maybe written using -> operator.
Example:
max(X, Y, Z) :- (X < Y -> Z = Y ; Z = X).
?- max(1, 5, M)
M = 5.
50
Conditional Operator
An example of the factorial function using conditional operator:
factorial(N, F) :-
(N > 0 ->
N1 is N – 1, factorial(N1, F1), F is N * F1;
F = 1).
?- factorial(12, X)
X = 479001600.
51
Conditional Operator
Unlike the cut operator, the fail operator causes fail and
therefore backtracking.
The Example below prints all members of a given list:
printall(L) :-
member(X, L),
write(X),
nl,
fail.
What if we replace fail with the cut operator?
52
Using fail
?- printall([1, 4, 7, 10])
1
4
7
10
false
• The built-in append/3 procedure may be used to append two
lists.
• The following is a sample implementation of such append
rule:
append(X,[],X).
append([],X,X).
append([H|T],Y,[H|T2]) :- append(T, Y, T2).
• Examples:
?- append([1, 2, 3], [4, 5, 6], X)
X = [1, 2, 3, 4, 5, 6].
53
Example: Appending two lists
• You may test whether two lists construct a third list or not:
?- append([1, 2, 3], [4, 5, 6], [1, 2, 3, 4, 5, 6])
true
?- append([1, 3], [4, 5], [1, 2])
false
• Similarly, the append procedure may also be used to obtain a
sub-list from a given list:
?- append(X, _, [1, 2, 3, 4, 5, 6]), length(X, L), L = 3.
L = 3,
X = [1, 2, 3].
54
Example: Append and Sub-lists
• The following obtains all sub-lists of at least length 2, starting
from the beginning:
?- append(X, _, [1, 2, 3, 4, 5, 6]), X = [_,_|_].
X = [1, 2] ;
X = [1, 2, 3] ;
X = [1, 2, 3, 4] ;
X = [1, 2, 3, 4, 5] ;
X = [1, 2, 3, 4, 5, 6] ;
false
55
Example: Append and Sub-lists / cont.
• The following obtains all sub-lists of at least length 2, starting
from any position:
sublist2ormore(L,X) :-
append(_,B,L),append(X,_,B),length(X,N),N>=2.
?- sublist2ormore([1, 2, 3, 4, 5],X)
X = [1, 2] ;
X = [1, 2, 3] ;
X = [1, 2, 3, 4] ;
X = [1, 2, 3, 4, 5] ;
X = [2, 3] ;
X = [2, 3, 4] ;
X = [2, 3, 4, 5] ;
X = [3, 4] ;
X = [3, 4, 5] ;
X = [4, 5] ;
false
56
Example: Append and Sub-lists / cont.
• Support a list contains 0s and 1. The following provide
Boolean ‘and’ on the elements of a list:
and([0, _],0) :- !.
and([1, X],X) :- !.
and([0|T], 0) :- and(T, _), !.
and([1|T], X) :- and(T, X).
?- and([1, 1, 0, 1, 0],X)
X = 0
?- and([1, 1],X)
X = 1
?- and([1],X)
false
?- and(1,X)
false
57
Example: Boolean Functions and Lists
• The following provide Boolean ‘or’ on the elements of a list:
or([1, _],1) :- !.
or([0, X],X) :- !.
or([1|T],1) :- or(T, _), !.
or([0|T],X) :- or(T, X).
?- or([1, 1, 0, 1, 0],X)
X = 1
?- or([1, 1],X)
X = 1
?- or([0, 0, 0],X)
X = 0
58
Example: Boolean Functions and Lists / cont.
• The following provide Boolean ‘xor’ on the elements of a list:
xor([0, X], X) :- !.
xor([1, X], Y) :- Y is 1 – X, !.
xor([0|T], X) :- xor(T, X).
xor([1|T], X) :- xor(T, Y), X is 1 – Y.
?- xor([1, 1, 0, 1, 0], X)
X = 1
?- xor([1, 1], X)
X = 0
?- xor([0, 0, 0], X)
X = 0
59
Example: Boolean Functions and Lists / cont.
• Consider a rule reverse/2 to calculate the reverse of a given
list. To implement this, we use an auxiliary reverse/3, as
follows:
reverse(List, X) :- reverse(List, X, []).
reverse([], X, X).
reverse([H|T], X, Acc) :- reverse(T, X, [H|Acc]).
• Example:
?- reverse([a, b, c],X).
X = [c, b, a].
In the above rules, the third argument accumulates the reverse of the list in
during the recursion.
60
Example: Reversing a List