Principles of
Programming Languages
Copyright By PowCoder代写 加微信 powcoder
Recap: Logic Programming
• Answer questions based on stated facts and implications
• Prolog uses terms to represent facts/implications and queries
• A query is one or more terms, possibly containing variables
• A query is provable if it unifies with a fact, or it unifies with the head of a
rule and the tail is provable
• Idea: We ask whether some assignment of values to variables makes the
query provable; if so, which one(s)?
Facts/Queries/Statements/Terms
• Prolog only knows about terms (atoms, variables, atoms applied to arguments)
• We use terms to model the actual things we want to talk about
• parent(joel, ellie). “Joel is the parent of Ellie”
• square(5, X). “X is the square of 5”
• length([1,2,3], 5). “the length of [1,2,3] is 5”
• bst(bin(tip, 4, bin(tip, 6, tip))). “bin(tip, 4, bin(tip, 6, tip)) is a binary
search tree”
• We can always tell whether a term is being used as a query, fact, or part of an implication,
but any meaning beyond that is outside the scope of Prolog
• In Prolog source code, a term followed by a period states a fact:
• age(john, 37).
• Prolog queries can be entered into the Prolog environment:
• age(john, 37). “Is John’s age 37?”
• age(john, X). “What is X, such that John’s age is X?”
• age(X, 37). “What is X, such that X’s age is 37?”
• age(X, Y). “What are X and Y, such that X’s age is Y?”
Rules/Implications
• A rule says how infer facts from other facts
• Or, what other facts must be proven in order to prove some fact
• eligable(X) :- age(X, Y), Y #> 35.
• The head, eligible(X), says what this rule can prove
• The tail says what needs to be proven in order to prove the head
• “X is eligible if the age of X is Y, and Y > 35.”
• “For all X, X is eligible if, for some Y, the age of X is Y and Y > 35.”
Variable Scope
• All variables in Prolog are scoped over a single clause
• A sequence of terms separated by commas/semicolons and terminated by a period
• Variable names can be re-used in different clauses, but they are unrelated
• We can always rename a variable to avoid confusion
• Variables are initially uninstantiated, but may become constrained or instantiated as a
result of unification
• Variables in facts and rule heads are effectively universally quantified
• Variables in queries or only used in rule tails are effectively existentially quantified
• To use a fact or rule to prove a query, we unify the query with the fact or rule
• We find substitutions that will make the terms equal
• Example: using eligible(X) :- age(X, Y), Y #> 25. to prove
eligible(john)
• Unify eligible(X) with eligible(john) — succeeds with X = john
• Apply substitution to rule tail: age(john, Y), Y #> 25.
• Prove each of these terms
Constraints
• Originally, Prolog variables were either instantiated or uninstantiated
• That is, they had a specific value (bound), or could take on any value (free)
• Most Prologs now support constrained variables, which are limited to a subset of all
possible values
• This allows the solver to answer queries such as dif(X,Y), X = Y. in finite time
• Contraint Logic Programming (CLP) is a general framework for expressing these
constraints
• If a Prolog environment offers CLP(X), it means we can constrain variables to fall
within X (e.g., finite sets of integers, integers, real numbers, etc.)
Using dif/2
• \=/2 is true if its arguments cannot be unified, based
on previous substitutions
• Its meaning is tied to the solving process
• Its meaning is not purely logical
• dif/2 constrains its argument to be non-equal
• Its meaning is independent of how Prolog’s solver
• \= can only react to the past, but dif can
constrain the future
?- member(X, [1,2,3]), X \= 1.
?- X \= 1, member(X, [1,2,3]).
?- member(X, [1,2,3]), dif(X,1).
?- dif(X,1), member(X, [1,2,3]).
Integer Arithmetic
• Prolog has a standard set of terms for working with numbers
• …but they aren’t great, so we will use CLP instead
• CLP(FD) or CLP(Z) let us set constraints for integer-valued variables
• :- use_module(library(clpfd)). % in a Prolog file
• A #= B asserts that A and B are equal, if interpreted as arithmetic
expressions
• A = B means that A and B are unifiable
• Can be made equal by substituting variables
• 1 + 1 = 2. — false: +(1,1) and 2 are distinct terms
• A #= B means that A and B are numerically equal
• Can be made equal by substituting variables and performing arithmetic
• 1 + 1 #= 2. — true, because we can simplify +(1,1) to 2
• You may see is and =:= in textbooks/tutorials; use #= instead
Numeric Operations
• We can form arithmetic expressions with the usual operators
• +, – (binary and unary), *, ^ (exponent)
• //, rem (integer division/remainder using truncation)
• div, mod (integer division/remainder using floor)
• abs, min, max
• Relations: #=, #\=, #<, #>, #=<, #>=
• Note #\= for not equal, and #=< for less-than-or-equal • CLP(FD) can solve most statements involving finite sets of integers, but can struggle with infinite sets • ?- X #< 5, X #> 5.
• ?- X #< Y, X #> Y.
Y #=< X + -1, X #=< Y + -1. • CLP(FD) isn’t quite strong enough to realize these constraints are unsatisfiable, but it can if we assert a finite domain • ?- X #< Y, X #> Y, Y in 0..1000.
• We can set the domain of a variable using in/2
• X in 0..20. 0 ≤ X ≤ 20
• Domains are:
• A single integer
• A range, Lower..Upper, where the bounds may be integers, inf (–∞), or sup (+∞)
• A union, D1\/D2, where D1 and D2 are domains
• Domains may not contain uninstantiated variables
• E.g., X in -10 .. -1 \/ 1 .. 10.
#\= vs dif
• What is the difference between dif(X,0) and X #\= 0?
• They may seem equivalent: X ≠ 0
• But #\= also constrains X to be an integer
• dif(X,0), X = good. — provable
• X #\= 0, X = good. — error!
• Operationally, dif and #\= use different parts of the solver that don’t
necessarily communicate (may miss some opportunities to simplify)
Example: Cryptarithmetic
• A cryptarithmetic puzzle presents an arithmetic puzzle where letters stand for digits
• An answer is correct if each letter is assigned to a different digit
• Substitution results in a correct statement
• No letter used in the most significant digit of a number is 0
• E.g., EAT + PIE = MORE
• 350 + 893 = 1243
• 420 + 954 = 1374
Solving Cryptarithmetic
• How could we solve SEND + MORE = MONEY?
• A naïve approach: try every assignment of digits to letters, and test each
one until we find a correct one
• Problem: there are 10 digits and 8 letters in the puzzle: 100,000,000
possible solutions
• We can reduce it to 10!/(10-8)! = 1,814,400 possible solutions if we only
generate cases where the assignments are distinct
• Alternative: express more constraints before generating possible solutions
Cryptarithmetic Constraints
• Puzzle: SEND + MORE = MONEY
• We can use in to constrain our variables to the range 0..9, or ins to restrict a list of variables
• [S,E,N,D,M,O,R,Y] ins 0..9, S #\= 0, M #\= 0
• We can use all_different/1 to require that every variable in a list be different from every
other variable
• all_different([S,E,N,D,M,O,R,Y])
• Finally, the equality itself
• S * 1000 + E * 100 + N * 10 + D + M * 1000 + O * 100 + R * 10 + E
#= M * 10000 + O * 1000 + N * 100 + E * 10 + Y
Resolving the Puzzle
• We added Vars = [S,E,N,D,M,O,R,Y] to avoid repeating the list of variables
• Thus, all_different(Vars), Vars ins 0..9
• We can use indomain/1, label/1, or labeling/2 to force the solver to look for specific
• indomain instantiates a single variable, label instantiates a list of variables, and labeling
has an additional argument that specifies a strategy
• e.g., label(Vars)
• But this only works if Vars is already instantiated with a list of variables, each of which is
constrained to a finite domain — more non-logical aspects!
?- Vars = [S,E,N,D,M,O,R,Y], all_different(Vars), Vars ins 0..9, S #\=
0, M #\= 0, S*1000 + E*100 + N*10 + D + M*1000 + O*100 + R*10 + E #=
M*10000 + O*1000 + N*100 + E*10 + Y.
Vars = [9, E, N, D, 1, 0, R, Y],
E in 4..7,
all_different([9, E, N, D, 1, 0, R, Y]),
91*E+D+10*R#=90*N+Y,
N in 5..8,
D in 2..8,
R in 2..8,
Y in 2..8.
SWI-Prolog’s implementation of CLP(FD) can’t tell whether this has a unique instantiation,
so it leaves the constraints unresolved
?- Vars = [S,E,N,D,M,O,R,Y], all_different(Vars), Vars ins 0..9, S #\=
0, M #\= 0, S*1000 + E*100 + N*10 + D + M*1000 + O*100 + R*10 + E #=
M*10000 + O*1000 + N*100 + E*10 + Y, label(Vars).
Vars = [9, 5, 6, 7, 1, 0, 8, 2],
Using label/2 tells SWI-Prolog to start trying instantiations
?- Vars = [S,E,N,D,M,O,R,Y], all_different(Vars), Vars ins 0..9, S #\=
0, M #\= 0, label(Vars), S*1000 + E*100 + N*10 + D + M*1000 + O*100 +
R*10 + E #= M*10000 + O*1000 + N*100 + E*10 + Y.
Vars = [9, 5, 6, 7, 1, 0, 8, 2],
Putting label/2 earlier results in generating millions of instantiations and rejecting all but one of them
On my laptop, this takes 37 seconds to produce the first answer;
the version on the previous slide takes 0.001 seconds.
Data Structures
• We use terms to build data structures
• Lists have a special syntax that creates nested terms
• [1,2,3] is actually [1|[2|[3|[]]]]
• We can define our own data structures by using terms as constructors
• e.g., tip/0 and bin/3 for binary trees
• There is no type system to prevent mistakes, but we can just fail for
non-examples
Height of a Tree
• What is the height of a tree?
• height/2 is a relation between a binary tree and an integer
• height(tip, 0).
• The height of the empty tree is 0
• height(bin(L,_,R), N) :-
N #= 1 + max(LH, RH), height(L,LH), height(R,RH).
• The height of a non-empty tree is one more than the height of its taller child
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com