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
𝑥>𝑦
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