CS代写 CSI2120/demoCode.html

Programming Paradigms

• Course overview •Introduction to programming
• Review: The object-oriented

Copyright By PowCoder代写 加微信 powcoder

paradigm in Java •Imperative and concurrent
programming paradigm: Go.
• Logic paradigm: Prolog.
• Functional paradigm: Scheme.

Announcement
• comprehensive assignment Go is due on March 7th. Accepted late with penalty till March 9th
• Late penalty waived
• Go assignment is posted. Due on March 14th, Accepted late till March 16th

Announcement
Labs is offered in-person and remote starting Feb 14th
Quiz 1-prolog is posted. Due Thursday March 10

Acknowledgment
The slides posted through the term are based of the slides offered by:
Prof. Jochen Lang
Demo code: https://www.site.uottawa.ca/~jl ang/CSI2120/demoCode.html

Logic Programming in Prolog
• BacktrackingwiththeCut – The “Cut”
– Coding the existence of a single solution • no other rules should be tried
• no backtracking across this point
– Abandoning a goal with cut and fail • Datastructures:Lists
– Basic list processing
– Appending a list to another – Reading into a list

The “Cut” !
• “cut” off some backtracking path
– Prolog will not try to re-satisfy certain goals.
• Reasons for using the cut
– faster execution
– more efficient use of memory (don’t have to keep track of as many backtrack points)
• Syntax:!
– goal that always succeeds and has a side effect (on the way backtracking works)

Cut-off concept
• The cut choice allows you to tell Prolog that you do not want to keep the choice points on hold
• Useful when there are mutual exclusive clauses * Ex: the following 2 rules
human(X):- male(X). human(X):- female(X).
* is written:
human(X):- male(X) ,!. human(X):- female(X) ,!.
If we already have demonstrated that X is a male,
there is no need to check if X is a female
2021-03-04

A Simple Example:
• Goal:Removingbranches(pruning)fromthesearchtree that are known not to produce a solution.
human (X): – male (X),!. human (X): – female (X),!.
– The cut commits Prolog to the facts established
• if the subgoal male(X) succeeds, the cut succeeds
and the cat rule in the first row succeeds. The backtracking path is now cut off and Prolog will not search to re-satisfy male(X) or human(X).

Effect of the Cut
• When a cut is encountered as a goal, the system becomes committed to all choices made since the parent goal was invoked.
– This means the choice of which clause, and all the choices in the “sibling” goals up to the cut are fixed.
• Therefore the Cut permits the elimination of branches in the search tree by
– eliminating other rules for the same goal – eliminating other choices for subgoals

 The cut! allows to eliminate all the choices not yet explored.
 The cut choice becomes active when demonstrated  Its effect going back to the point that it was
introduced
 The choices not explored before the introduction of the cut and after its demonstration remain available

 Rules and facts a,b,c,d,e,h arranged in a tree
h(X) :- d(X). h(X) :- X=e. d(X) :- X=a. d(X) :- X=b. d(X) :- X=c. a.
 Query initiating a tree traversal: ?- h(X).
 Produces the leave nodes (depth first search): abce

 Rules and facts a,b,c,d,e,h arranged in a tree
hX) :- d(X). h(X) :- X=e. d(X) :- X=a,!. d(X) :- X=b. d(X) :- X=c. a.
 Query initiating a tree traversal: ?- h(X).
When the cut is met, we can no longer prove otherwise.
 Produces only the leave nodes (depth first search): ae

p(X,Y):-q(X,Y),s(Y). p(a,a). q(X,Y):-v(X),w(Y). q(m,Y).
v(a). v(b). w(b). w(c). s(c).

?- p(X,Y). X=a,Y=c ; X=b,Y=c ; X = m, Y = c ; X = Y, Y = a.
v(X),w(Y),s(Y)
X=a v(a),w(Y),s(Y)
p(X,Y):-q(X,Y),s(Y). p(a,a). q(X,Y):-v(X),w(Y). q(m,Y).
p(X,Y) q(X,Y),s(Y)
q(m,Y),s(Y)
v(b),w(Y),s(Y) Y=b Y=c
v(a),w(b),s(b) v(a),w(c),s(c) v(b),w(b),s(b) v(b),w(c),s(c)
X=m,Y=c X=a,Y=c fail X=b,Y=c

p(X,Y):-q(X,Y),!,s(Y). p(a,a). q(X,Y):-v(X),w(Y). q(m,Y).
v(a). v(b). w(b). w(c). s(c).

?- p(X,Y). false.
The cut is demonstrated here
v(X),w(Y),!,s(Y) X=b
v(a),w(c),s(c) v(b),w(b),s(b) v(b),w(c),s(c) X=a,Y=c fail X=b,Y=c
Introduction the cut
q(m,Y),s(Y)
v(a),w(Y),!,s(Y) v(b),w(Y),s(Y)
q(X,Y),!,s(Y) X=m
p(a,a) X=a,Y=a
p(X,Y):-q(X,Y),!,s(Y). p(a,a). q(X,Y):-v(X),w(Y). q(m,Y).
Y=b Y=c
v(a),w(b),!,s(b)

p(X,Y):-q(X,Y),s(Y). p(a,a). q(X,Y):-v(X),!,w(Y). q(m,Y).
v(a). v(b). w(b). w(c). s(c).

?- p(X,Y).
X = a, Y = c ; X = Y, Y = a.
Introducing the cut
The cut is demonstrated here
v(X),!,w(Y),s(Y) X=a X=b
X=a,Y=c fail X=b,Y=c
q(X,Y),s(Y)
q(m,Y),s(Y)
v(a),!,w(Y),s(Y)
v(b),w(Y),s(Y)
Y=c Y=b Y=c v(a),w(b),s(b) v(a),w(c),s(c) v(a),w(b),s(b) v(a),w(c),s(c)

?- p(X,Y).
X = a, Y = c ; X = Y, Y = a.
Introducing the cut
p(X,Y):-q(X,Y),s(Y). p(a,a). q(X,Y):-v(X),!,w(Y). q(m,Y).
v(a). v(b). w(b). w(c). s(c).
The cut is demonstrated here
v(X),!,w(Y),s(Y) X=a X=b
Y=c Y=b Y=c v(a),w(b),s(b) v(a),w(c),s(c) v(a),w(b),s(b) v(a),w(c),s(c)
X=a,Y=c fail X=b,Y=c
q(X,Y),s(Y)
q(m,Y),s(Y)
v(a),!,w(Y),s(Y)
v(b),w(Y),s(Y)

An Arithmetic Example: roots
• Anaivewaytocalculatetheintegerrootofanumberis to use a generator for integer numbers and see if the result succeeds.
• Generator
int(N) :- int(N1), N is N1+1.
• Rootpredicate
root(N,R) :- int(K), K*K>N,!, R is K-1.
– Cut ensure that once 𝐾2 > 𝑁, backtracking of the generator stops (int). As the generation of integers has no end.

– change the solution space (see the previous root example).
• GreenCuts
– remove choices that wouldn’t work anyway – efficiency gain
– reduced memory footprint

Summary: Utility of the Cut
• Delete branches that will not lead to a solution
• Removemutuallyexclusivecasesinrules
• Reducethenumberofsolutionsproduced
• Makesurethatcertainprograms(recursion)terminate • Controloftheproofprocedure

leave(friday). weather(friday, fine). weather(saturday, fine). weather(sunday, fine). weekend(saturday). weekend(sunday).
The request:
? – picnic (J).
The results:
D = saturday; D = sunday; D = friday.
% The rules:
picnic(J):- weather(J, fine), weekend(J). picnic(J):- leave(J).

leave(friday). weather(friday, fine). weather(saturday, fine). weather(sunday, fine). weekend(saturday). weekend(sunday).
The rules:
The request:
? – picnic (J).
The results:
picnic (J): – weather (J, fine),!, weekend (J). picnic (J): – leave (J).

leave(friday). weather(friday, fine). weather(saturday, fine). weather(sunday, fine). weekend(saturday). weekend(sunday).
The rules:
picnic (J): – weather (J, fine), weekend (J),!. picnic (J): – leave (J).
The request:
? – picnic (J).
The results:
D = Saturday.

%Facts: The request: leave(friday). ? – picnic (J). weather(friday, fine). weather(saturday, fine). weather(sunday, fine). weekend(saturday). weekend(sunday).
The rules:
picnic (J): – !, weather (J, fine), weekend (J). picnic (J): – leave (J).
http://www.cse.unsw.edu.au/~billw/dictionaries/prolog/cut.html
The results:
D = Saturday; D = Sunday.

p(X, Y):-q(X), r(X, Y). p(c, c1).
r(a, a1). r(a, a2). r(b, b1). r(b, b2). r(b, b3).
6 solutions

p (X, Y):- q (X), r (X, Y),!. p (c, c1).
1 solution
p (X, Y):- q (X),!, r (X, Y). p (c, c1).
2 solutions
p (X,Y):- !, q (X), r (X,Y). p (c, c1).
5 solutions
p(X, Y):- q(X), r(X, Y). p(c, c1).
q(a). q(b). r(a, a1). r(a, a2). r(b, b1). r(b, b2). r(b, b3).

If-then-else
• Max function returning the larger of two numbers
max(X,Y,X) :- X >= Y.
max(_,Y,Y).
• This will produce surprising results, consider
?- max(7,5,X).
Call: (6) max(7, 5, _G1326) ? creep Call: (7) 7>=5 ? creep
Exit: (7) 7>=5 ? creep
Exit: (6) max(7, 5, 7) ? creep
Redo: (6) max(7, 5, _G1326) ? creep Exit: (6) max(7, 5, 5) ? creep

If-then-else with the Cut
• Solution: Use an explicit test
max(X,Y,X) :- X >= Y.
max(X,Y,Y) :- X < Y. • Solution: Use the Cut for efficiency max(X,Y,X) :- X >= Y, !.
max(_,Y,Y).
?- max(7,5,X).
Call: (6) max(7, 5, _G1326) ? creep Call: (7) 7>=5 ? creep
Exit: (7) 7>=5 ? creep
Exit: (6) max(7, 5, 7) ? creep

max (X, Y, Y): – X<=Y. max (X, Y, X): - X>Y.
max (X, Y, Y): – X<=Y,!. max (X, Y, X). max (X, Y, Y): - X<= Y,!. max (X, Y, X): - X>Y.
max (X,Y, Z): – X<=Y,!,Y= Z. max (X, Y, X). Predicate fail • Thefailpredicatealwaysfails. • CombinedwiththeCutwegetnegation is_false(P) :- P, !, fail. is_false(P). • TheclausePiseithertruethenthegoalis_falsefails. – Subgoal P is true, Cut is true cutting backtracking off, fail succeeds making the goal is_false(P) fail. – If subgoal P fails, the second rule succeeds. • Thecombinationiscalledcut-fail. Simple Example with Negation single_student(X):- not(married(X)), student(X). student(joe). married(jean). ? – single_student (joe). true ? – single_student (jean). false ? - single _student (X). Negation: not or \+ • Thenegationpredicatenot(F)withFatermcanalso be written with the operator \+F – Associative prefix operator • Negationbyfailure – Prolog proofs the success of a goal not(F) by showing that it can not satisfy F. • Remember that Prolog may also fail to proof F for trivial reasons, e.g., it may simply missing facts in its database. – Prolog’s proof strategy is referred to as closed world assumption. Negation: not or \+ ?- \+ (2 = 4). true. ?- not(2 = 4). true. http://www.cse.unsw.edu.au/~billw/prologdict.html#negation The cut-fail canEnterPolice (P): - aAcriminalFolder (P),!, fail. Used when demonstrating a condition invalidates all others 2021-03-04 Not Equals or Difference • Wehaveseentheoperatornotequalsbefore. • Binarydifferenceoperatoristheoppositeofa successful unification of its’ arguments. – This operator is equivalent to the following definition X =\= Y :- not(X = Y). – expressed with cut- fail X =\= X :- !,fail. X =\= Y. Interval Predicate Again • Recall previous definition of a test for an interval and a separate definition of a generator for interval intervalTest(X,L,H):- X>=L,X==L, X=CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com