CS131: Programming Languages
Zhaowei Tan
Discussion 1B Week 6, Winter 2022
Copyright By PowCoder代写 加微信 powcoder
• Homework #4
• Logic programming language
• Programs defined using Facts, Rules, and Queries
• Declarative Programming: Describing what we want to achieve, not how todoit
• This course uses GNU Prolog: http://www.gprolog.org
– Make sure you are not using SWI-Prolog, they have lots of differences
– Command: gprolog, available on SEASnet servers
How to program in Prolog?
• Building blocks: facts, rules, and queries
• Facts and Rules are written into a file, e.g., myrules.pl • In interactive Prolog environment, consult the rule file
– Command: [myrules].
– Or use [user]. to directly input rule in interactive environment
• Finish typing with Ctrl-D
• After that, you can run queries in the interactive environment
• Facts define what is true in our database
• Always start with a lowercase letter • For example:
Queries: ?- raining.
?- john_is_cold.
?- john_is_tired.
Prolog file:
john_is_cold. john_forgot_his_raincoat.
• Facts consisting of one or more terms
• Closed-world assumption • For example:
?- eats(fred, oranges).
?- eats(fred, apples).
?- student(fred).
Prolog file:
student(fred). eats(fred, oranges). eats(fred, bananas). eats(tony, apples).
Variables and Unification
• Variables: strings that start with a capital letter (or an underscore)
– E.g., X, What, My_variable, …
• Unification tries to find a way to fill the missing values
?- eats(fred, What). What = oranges ? a What = bananas
?- eats(Who, apples)
Who = tony
– Binding variables to atoms
Prolog file:
eats(fred, oranges). eats(fred, bananas). eats(tony, apples).
• Note:pressatoseeallresults; press ‘;’ to see the next result
• Rules establishes relationship of multiple predicates
• Syntax: conclusion :- premises.
• Consider the statement: “All men are mortal”:
Prolog file: mortal(X) :-
human(X). human(socrates).
?- mortal(socrates).
?- mortal(Who)
Who = socrates yes
• Using multiple predicates in the premise
– Comma (,) is the AND operator, semi-colon (;) is the OR operator
red_car(X) :- red(X),
red_or_blue_car(X) :-
(red(X); blue(X)), car(X).
Equality in Prolog
• Three equality operators: =, is, =:=
– “=” compares forms, does unification directly without evaluation – “is” does arithmetic evaluation on the right side and unifies
– “=:=” evaluates both sides
?- 7 = 5 + 2.
?- A + B = 5 + 2.
A=5 B=2 yes
?- X is 5 + 2.
?- 7 is 5 + 2
?- 5 + 2 is 7.
?- 4 + 3 =:= 5 + 2.
?- X =:= 4 + 3.
?- X = 5, Y = 5, X =:= Y
X=5 Y=5 yes
Arithmetic comparisons
Mathematical Representation
• We can do unification on list
– [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
• Syntax: [val1, val2, val3, …, valn]
List: Examples
• Consider the following relation:
p([H | T], H, T).
• What is the result of the following queries?
1) p([a, b, c], a, [b, c]). 2) p([a, b, c], X, Y).
3) p([a], X, Y). 4) p([], X, Y).
List: Searching
• How can we check if a specific element is in a list?
• Write a rule exists(X, List), which is true when X is in List
exists(X, [X | _]). exists(X, [_ | T]) :-
exists(X, T).
?- exists(a, [a, b, c]).
?- exists(a, [x, y, z]).
?- exists(X, [1, 2, 3]).
X=1?a X=2 X=3
Tracing in Prolog.
• trace. shows all the calls (use notrace. to turn off)
exists(X, [X | _]). exists(X, [_ | T]) :-
exists(X, T).
Prolog’s List library
• Some “functions” we will cover:
– member (the same as “exists” above) – permutation
List: member
• From the manual: “member(Element, List) succeeds if Element 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]).
?- member(X, [1, 2, 3]).
List: permutation
• From the manual: “permutation(List1, List2) succeeds if List2 is a permutation of the elements of List1.”
?- permutation([3,2,1],[1,2,3]).
?- 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] ? ;
List: permutation
• Note: You should have known elements in the first argument:
?- 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)
List: length
• From the manual: “length(List1, Length) succeeds if Length is the length of List.”
?- length([1,2,3,4], 4).
?- length([1,2,3,4], Len).
Len = 4 yes
?- length(List, 5).
List = [_,_,_,_,_] yes
• From the manual: “nth(N, List, Element) succeeds if the Nth 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).
?- nth(3, L, 5).
List = [_,_,5|_] yes
List: maplist
• From the manual: “maplist(Goal, List) succeeds if Goal can successfully be applied on all elements of List.”
?- maplist(>(5), [1,2,3]).
?-maplist(=(1), [1,2,3]).
Generating a List with Constraints
• Problem: Generate a list of length N where each element is a unique integer between 1…N
• Approach: implement unique_list(List, N), that succeeds when List satisfies the constraint above
• Start by outlining what we need:
unique_list(List, N) :- length(List, N),
elements_between(List, 1, N), all_unique(List).
Provided by only has between(Min, Max, X) Not provided by prolog
• Implementation
Generating a List with Constraints
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).
! prevents backtracking (cut)
!, fail is a combination to cause failure of current attempt and prevents backtracking
Finite Domain Solver
• Previous solution: enumerate all possibilities to find answer • Finite Domain Solver works in another way
– 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
• Often lead to more optimized solution with less code
Finite Domain Solver
• Let’s solve the earlier problem with FD solver:
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).
FD Constraints
• FD constraints are written in different ways than ordinary ones
• Arithmetic constraints example: – 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
• See official documentation for more built-in constraints – http://www.gprolog.org/manual/html_node/gprolog054.html
FD Constraints
• Note: constraints do not find a solution, they just limit the options – 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
Homework #4
Homework #4: Ken *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
Homework #4: Ken *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
Homework #4
• Write Prolog code to solve KenKen puzzle
• Two implementations: one with FD solver, the other without (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, design a proper API for no-op KenKen
– 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 the solver)
Constraint Representation
• e.g., the “11+” in the upper-left corner – +(11, [1|1],[2|1])
• The whole constraint set:
Invoking your solution
• Refer to “Example” sections of the course website • A sample call
• Properly describe the properties of solution
• The solution outline should probably look like
– TisanNxNmatrix
– All values are between 1, 2, ... N.
– Every row/column is different (or a permutation of [1,2,...,N])
Common for FD and plain
FD: directly leverage primitives, simple plain: implement logic by hand
– Satisfies all constraints
FD and plain should be similar, but with slightly different operators
Simplified problem
• Consider a 1-D “line” problem
– A line of 6 cells, their values are all within 1, 2, ... 6, and each cell contain different value.
– A set of constraints
• +(S,A,B):CellA+CellBequalstoS
• -(D, A, B): abs(Cell A - Cell B) equals to D
• 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).
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
Prolog Resources
• GNU Prolog manual: http://www.gprolog.org/manual/gprolog.html
• : https://en.wikibooks.org/wiki/Prolog
• Prolog Visualizer: http://www.cdglabs.org/prolog/#/
• When looking for resources, first make sure that they are for GNU Prolog, not SWI-Prolog.
Questions?
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com