CS计算机代考程序代写 database ocaml prolog CS131: Programming Languages

CS131: Programming Languages
Boyan Ding DIS 1E Week 6 Winter 2021
1

TA: Boyan Ding
Email: dboyan@cs.ucla.edu
Office Hours:
Tuesday & Thursday 9:30–10:30am Zoom Link on CCLE
Discussion Section: 1E, Fridays 2:00 – 3:50pm
About TA
2

Course Announcement
• HW4 due: Next Friday, Feb. 19, 2021 11:55pm – Cutoff time one week later
• HomeworksshouldbesubmittedonCCLE,under“Assignments”
3

• Prolog
• Homework #4
Agenda
4

Prolog
5

Declarative Programming
• Describingwhatwewanttoachieve,nothowtodoit • Examples:SQL,regularexpressions,Prolog,…
6

Prolog
• Logicprogramminglanguage
• ProgramsdefinedusingFacts,RulesandQueries
• ThiscourseusesGNUProlog:http://www.gprolog.org
– Make sure you are not using SWI-Prolog, they have lots of differences – Command: gprolog, available on SEASnet servers
7

How to program in Prolog?
• FactsandRulesarewrittenintoafile,e.g.myrules.pl
• IninteractivePrologenvironment,consulttherulefile
– Command: [myrules].
– Or, use [user]. to directly input rule in interactive environment.
• Afterthat,youcanrunqueriesintheinteractiveenvironment.
8

Facts
• Factsdefinewhatistrueinourdatabase • Alwaysstartwithalowercaseletter
• Forexample:
Queries: ?- raining.
yes
?- john_is_cold.
yes
?- john_is_tired.
exception
Prolog file:
raining.
john_is_cold. john_forgot_his_raincoat.
9

Relations
• Factsconsistingofoneormoreterms • Closed-worldassumption
• Forexample:
Queries:
?- eats(fred, oranges).
yes
?- eats(fred, apples).
no
?- student(fred).
yes
Prolog file:
student(fred). eats(fred, oranges).
eats(fred, bananas). eats(tony, apples).
10

Variables and Unification
• Variables:stringsthatstartwithacapital letter (or an underscore)
– e,g, X, What, My_variable, …
• Unificationtriestofindawaytofillthe missing values
– Binding variables to atoms
Queries:
?- eats(fred, What). What = oranges ? a What = bananas
?- eats(Who, apples)
Who = tony
Prolog file:
eats(fred, oranges). eats(fred, bananas). eats(tony, apples).
11

Rules
• Rulesestablishesrelationshipofmultiplepredicates • Syntax:conclusion:-premises.
• Considerthestatement:“Allmenaremortal”:
Prolog file: mortal(X) :-
human(X). human(socrates)
Queries:
?- mortal(socrates).
yes
?- mortal(Who)
Who = socrates yes
12

Rules
• Usingmultiplepredicatesinthepremise
– Comma (,) is the AND operator, semi-colon (;) is the OR operator
red_car(X) :- red(X),
car(X).
red_or_blue_car(X) :- (red(X); blue(X)), car(X).
13

Equality in Prolog
• Threeequalityoperators:=,is,=:=
– “=” compares forms, does unification directly without evaluation – “is” does arithmetic evaluation on the right side and unifies
– “=:=” evalues both sides
?- 7 = 5 + 2.
no
?- A + B = 5 + 2.
A=5 B=2 yes
?- X is 5 + 2.
X=7 yes
?- 7 is 5 + 2
yes
?- 5 + 2 is 7.
no
?- 4 + 3 =:= 5 + 2.
yes
?- X =:= 4 + 3.
exception
?- X = 5, Y = 5, X =:= Y
X=5 Y=5 yes
14

Arithmetic comparisons
Mathematical Representation
Prolog
𝑥<𝑦 X= Y
𝑥>𝑦
X>Y
15

Lists
• Syntax:[val1,val2,val3,…,valn]
• Wecandounificationonlist
– [1,2,3,4]=[A|B]->Aisboundto1,Bisboundto[2,3,4] – [1,2,3,4]=[A,B|C]->A=1,B=2,C=[3,4]
– [1,2,3,4]=[A,B,C,D]->A=1,B=2,C=3,D=4
– Similar to pattern matching in OCaml
16

List: Examples • Considerthefollowingrelation:
p([H | T], H, T).
• Whatistheresultofthefollowingqueries?
1) p([a, b, c], a, [b, c]). 2) p([a, b, c], X, Y).
3) p([a], X, Y).
4) p([], X, Y).
17

List: searching
• Howcanwecheckifaspecificelementisinalist?
• Writearuleexists(X,List),withistruewhenXininList
exists(X, [X | _]). exists(X, [_ | T]) :-
exists(X, T).
Queries:
?- exists(a, [a, b, c]).
yes
?- exists(a, [x, y, z]).
no
?- exists(X, [1, 2, 3]).
X=1?a X=2 X=3
18

Tracing in Prolog.
• trace. shows all the calls (use notrace. to turn off)
exists(X, [X | _]). exists(X, [_ | T]) :-
exists(X, T).
19

Prolog’s List library
• Some“functions”wewillcover:
– member (actually the same as “exists” above) – permutation
– length
– nth
– maplist
20

List: member
• Fromthemanual:“member(Element,List)succeedsifElement belongs to the List. This predicate is re-executable on backtracking and can thus be used to enumerate the elements of List.”
?- member(3, [1, 2, 3, 4, 5]).
true
?- member(X, [1, 2, 3]). X=1?a
X=2
X=3
21

List: permutation
• Fromthemanual:“permutation(List1,List2)succeedsifList2isa permutation of the elements of List1.”
?- permutation([3,2,1],[1,2,3]).
true
?- permutation([1,2,3], X).
X = [1,2,3] ? ; X = [1,3,2] ? ; X = [2,1,3] ? ; X = [2,3,1] ? ; X = [3,1,2] ? ; X = [3,2,1] ? ;
22

List: permutation
• Note:Youshouldhaveknownelementsinthefirstargument:
?- permutation(X, [1,2,3]).
X = [1,2,3] ? a
Fatal Error: global stack overflow (size: 32768 Kb, reached: 32765 Kb, environment variable used: GLOBALSZ)
23

List: length
• Fromthemanual:“length(List1,Length)succeedsifLengthis the length of List.”
?- length([1,2,3,4], 4).
yes
?- length([1,2,3,4], Len).
Len = 4 yes
?- length(List, 5).
List = [_,_,_,_,_] yes
24

List: nth
• Fromthemanual:“nth(N,List,Element)succeedsiftheNth argument of List is Element.”
?- nth(5, [1,2,3,4,5,6], Element).
Element = 5 yes
?- nth(N, [1,2,3,4,5,6], 3).
N=3? yes
?- nth(3, L, 5).
List = [_,_,5|_] yes
25

List: maplist
• Fromthemanual:“maplist(Goal,List)succeedsifGoalcan successfully be applied on all elements of List.”
?- maplist(>(5), [1,2,3]).
yes
?-maplist(=(1), [1,2,3]).
no
26

Generating a List with Constraints
• Problem:GeneratealistoflengthNwhereeachelementisa unique integer between 1…N
• Approach:implementunique_list(List,N),thatsucceedswhenList satisfies the constraint above
• Startbyoutliningwhatweneed:
unique_list(List, N) :-
length(List, N), elements_between(List, 1, N), all_unique(List).
Provided by Prolog
Prolog only has between(Min, Max, X) Not provided by prolog
27

Generating a List with Constraints • Implementation
unique_list(List, N) :-
length(List, N), elements_between(List, 1, N), all_unique(List).
elements_between(List, Min, Max) :- maplist(between(Min, Max), List).
all_unique([ ]). all_unique([H|T]) :-
member(H, T), !, fail all_unique([H|T]) :- all_unique(T).
!, fail is a combination to cause failure of current attempt and prevents backtracking
28

Finite Domain Solver
• Previoussolution:enumerateallpossiblepossibilitytofindanswer
• FiniteDomainSolverworksinanotherway
– Variable values are limited to a finite domain (non-negative integers) – Symbolic constraints are added to limit solution space
– Solution is obtained by going through the final constrained space
• Oftenleadtomoreoptimizedsolutionwithlesscode
29

Finite Domain Solver
• Let’ssolvetheearlierproblemwithFDsolver:
Create a list of length N with no bound values
Define all values in List to be between 1 and N Define all values in List to be different
Find a solution
unique_list2(List, N) :- length(List, N), fd_domain(List, 1, N), fd_all_different(List), fd_labeling(List).
30

FD Constraints
• FDconstraintsarewrittenindifferentwaysthanordinaryones
• Arithmeticconstraintsexample:
– FdExpr1 #= FdExpr2: equality
– FdExpr1 #\= FdExpr2: inequality
– FdExpr1 #< FdExpr2: less than – FdExpr1 #=< FdExpr2: less than or equal – FdExpr1 #> FdExpr2: greater than
– FdExpr1 #>= FdExpr2: greater than or equal
• Seeofficialdocumentationformorebuilt-inconstraints
– http://www.gprolog.org/manual/html_node/gprolog054.html
31

FD Constraints
• Note:constraintsdonotfindasolution,theyjustlimittheoptions – Solution is found with fd_labeling
?- X #= Y.
X = _#0(0..268435455) Y = _#0(0..268435455)
?- X #< 5. X = _#2(0..4) ?- X #< 5, fd_labeling(X). X=0?a X=1 X=2 X=3 X=4 32 Homework #4 33 Homework #4: KenKen N*N square filled with numbers 1..N, values not repeated in any row/column A set of constraints on one or more contiguous cells Sum/Product is a certain value (A pair of cells’) difference / quotient is a certain value 34 Homework #4 • WritePrologcodetosolveKenKenpuzzle • Twoimplementations:onewithFDsolver,theotherwithout(only using plain Prolog primitives) – Provide comparison of performance – Note: non-FD solver probably won’t work well with larger grids, might try 4x4 • Additionally,designaproperAPIforno-opKenKen – Constraints only come with numbers, with the operators erased. They needed to be figured out during the solution process – Give a sample invocation (no need to implement). 35 Constraint Representation • e.g.,the“11+”intheupper-leftcorner – +(11, [1|1],[2|1]) • Thewholeconstraintset: 36 Invoking your solution • Referto“Example”sectionsofthecoursewebsite • Asamplecall 37 Hints • Properlydescribethepropertiesofsolution • Thesolutionoutlineshouldprobablylooklike – T is an NxN matrix – All values are between 1, 2, ... N. – Every row/column is different (or a permutation of [1,2,...,N]) – Satisfies all constraints Common for FD and plain FD: directly leverage primitives, simple plain: implement logic by hand FD and plain should be similar, but with slightly different operators 38 Simplified problem • Considera1-D“line”problem – A line of 6 cells, their values are all within 1, 2, ... 6, and each pair of cells cells contain different value. – A set of constraints • +(S,A,B):CellA+CellBequalstoS • -(D, A, B): abs(Cell A - Cell B) equals to S +10 +7 -4 -1 39 • Solution Simplified problem fd_line_constraint(L, +(S, A, B)) :- nth(A, L, X), nth(B, L, Y), S #= X + Y. fd_line_constraint(L, -(D, A, B)) :- nth(A, L, X), nth(B, L, Y), (D #= X - Y; D #= Y - X). fd_line(C, L) :- length(L, 6), fd_domain(L, 1, 6), fd_all_different(L), maplist(fd_line_constraint(L), C), fd_labeling(L). 40 line_constraint(L, +(S, A, B)) :- nth(A, L, X), nth(B, L, Y), S is X + Y. line_constraint(L, -(D, A, B)) :- nth(A, L, X), nth(B, L, Y), (D is X - Y; D is Y - X). line(C, L) :- permutation([1,2,3,4,5,6], L), maplist(line_constraint(L), C). Homework #4: Statistics SinceStart = cpu time used since gprolog started SinceLast = cpu time used since statistics was last called 41 Prolog Resources • GNUPrologmanual:http://www.gprolog.org/manual/gprolog.html • PrologWikibook:https://en.wikibooks.org/wiki/Prolog • PrologVisualizer:http://www.cdglabs.org/prolog/#/ • Whenlookingforresources,firstmakesurethattheyareforGNU Prolog, not SWI-Prolog. 42 Questions? 43