CS计算机代考程序代写 prolog interpreter COMP 348 Principles of Programming Languages

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