Principles of
Programming Languages
Copyright By PowCoder代写 加微信 powcoder
• Recall: a query is one or more terms, separated by commas or semicolons
• Commas mean “and”, semicolons mean “or”
• president(M), has_pet(M,P), (cat(P); dog(P)).
• The solver looks for variable assignments that satisfy the query
• That is, what values result in statements that can be proven?
• Strategy: prove each term, from left to right
• If a we can’t prove a term, backtrack to the last choice point and make a different
• president(M), has_pet(M,P), (cat(P); dog(P)).
• Solve for president(M)
• M = chris; …1
• Solve for has_pet(chris, P)
• P = polly
• Solve for cat(polly); …2
• False, backtrack to …2
• Solve for dog(polly)
• False, backtrack to …1
president(chris).
president(jackie).
president(pat).
has_pet(chris, polly).
has_pet(pat, barksalot).
dog(barksalot).
• president(M), has_pet(M,P), (cat(P);
• Resume solving for president(M)
• M = jackie; …3
• Solve for has_pet(jackie, P)
• False, backtrack to …3
• Resume solving for president(M)
president(chris).
president(jackie).
president(pat).
has_pet(chris, polly).
has_pet(pat, barksalot).
dog(barksalot).
• president(M), has_pet(M,P), (cat(P); dog(P)).
• Solve for has_pet(pat, P)
• P = barksalot
• Solve for cat(barksalot); …4
• False, backtrack to …4
• Solve for dog(barksalot)
• Final solution: M = pat, P = barksalot
president(chris).
president(jackie).
president(pat).
has_pet(chris, polly).
has_pet(pat, barksalot).
dog(barksalot).
• Prolog’s solving strategy is depth-first, with backtracking
• Go as far as we can with a solution
• Retreat to the last decision if we cannot proceed
• Each time the solver makes a choice, it leaves a choice point describing the alternative
• When backtracking, it rewinds to the most recent choice point and goes the other way
• The solver uses a few tricks to avoid leaving choice points when no other solution is
• Sometimes, a choice point is left that won’t succeed; e.g., member(1, [1,2]).
Recall: Height of a Tree
• height/2 is a relation between a binary tree and
its height
• The “/2” means it takes two arguments
• We can use height/2 in several different ways
• Test whether a tree has a specific height
• Find the height of a tree
• Find trees with a particular height
height(tip, 0).
height(bin(L,_,R), H) :-
H #= 1 + max(LH,RH),
height(L, LH),
height(R, RH).
Case Study: Binary Search Trees
• A binary search tree is a binary tree where the value
at each node is greater than all values in its left
subtree and less than all values in its right subtree
• For simplicity, we will talk about BSTs containing
• How can we design bst/1?
• Direct translation of requirements
• Effective, but inefficient
bst(bin(L,X,R)) :-
all_under(X, L),
all_over(X, R),
all_under(B, tip).
all_under(B, bin(L,X,R)) :-
all_under(B, L),
all_under(B, R).
all_over(B, tip).
all_over(B, bin(L,X,R)) :-
all_over(B, L),
all_over(B, R).
Better bst/1
• Can we express our requirements differently?
• Consider this tree: bin(_,X,bin(L,Y,_))
• We need to require that every element in L is greater than X
and less than Y
• For interior nodes, we can use a helper predicate that combines
the BST condition with a range restriction
• If we further require the upper bound > the lower bound, we can
further reduce the number of comparisons
• Assuming the tree is finite, we will eventually compare every
node to its predecessor and successor (if any)
bst(_, tip, _).
bst(Lo, bin(L,X,R), Hi) :-
bst(Lo, L, X),
bst(X, R, Hi).
bst(Lo, tip, Hi) :-
bst(Lo, bin(L,X,R), Hi) :-
bst(Lo, L, X),
bst(X, R, Hi).
Stronger condition, fewer comparisons
Using bst/3 for bst/1
• How do we use bst/3 to define bst/1?
• We could make a few helper relations for the cases
where are bounded on one side
• But remember: Prolog variables start out
uninstantiated
• ?- bst(Lo, bin(bin(tip,1,tip),2,bin(tip,4,tip)), Hi).
Lo in inf..0, Hi in 5..sup.
• We don’t need to specify the bounds in advance!
bst(T) :- bst(_, T, _).
bst(Lo, tip, Hi) :-
bst(Lo, bin(L,X,R), Hi) :-
bst(Lo, L, X),
bst(X, R, Hi).
Trick: Testing Predicates
• Prolog does not give us a way to directly define constants
• When testing a relation, we might want to have a few sample values to test with that we do
not need to keep retyping
• We can write predicates that test specific inputs
• bstTest1 :- bst(bin(bin(tip,1,tip),2,bin(tip,3,tip))).
• ?- bstTest1.
• We can write predicates with fixed solutions
• bst1(bin(bin(tip,1,tip),2,bin(tip,3,tip))).
• ?- bst1(T), bst(T).
Logic Variables
• Haskell lets us pass computations to functions before evaluating them
• Prolog lets us use variables before assigning them values
• For some queries, we can get back answers that don’t assign values at all
• ?- member(X, [Y]).
• What are X and Y? Anything we can imagine, as long as they are the same
• Prolog is largely untyped
• We can say certain terms have certain types, but this is not enforced by
the language itself or checked by the compiler
• This is not necessarily a problem
• Relations are inherently partial, so we don’t need to say what to do for
inappropriate input
• e.g., height(apple, N) will just fail
Type Relations
• We can write relations that require their argument to
belong to some type
• E.g., tree(T) requires T to be a binary tree
• bst/1 also acts as kind of type requirement
tree(tip).
tree(bin(L,_,R)) :-
• Failure is not always the best choice for type errors — it can hide bugs
• Prolog provides exceptions for when we really want to fail
• Throwing an exception causes the entire query to fail, without backtracking
• There is also a mechanism to catch exceptions
• The CLP(FD) relations throw type error exceptions when given inappropriate
• Using exceptions correctly is subtle and involves tools we haven’t discussed yet
• We need to make sure we either succeed or throw the exception, but not both
Nontermination
• Ideally, we can just state requirements and let the solver find solutions
• But the solver’s strategy can result in missing some solutions
• Prolog’s depth-first strategy runs into problems if there are infinitely many
possibilities
• Consider:
• ?- T = bin(bin(tip,1,tip),x,tip), tree(T).
• ?- tree(T), T = bin(bin(tip,1,tip),x,tip).
• The first succeeds, the second does not terminate
Termination Terminology
• We say a query terminates existentially if it returns a result, or fails
• We say a query terminates universally if returns all results
• That is, Q terminates universally if Q, false terminates existentially
• When T is uninstantiated, tree(T) terminates existentially, but not
universally
• Existential termination can be sufficient, but universal termination is safer
Infinite Missing Trees
• Recall: ?- tree(T), T = bin(bin(tip,1,tip),x,tip).
• The solver produces:
T = bin(tip,_,tip);
T = bin(tip,_,bin(tip,_,tip));
T = bin(tip,_,bin(tip,_,bin(tip,_,tip)));
• Since tree(R) produces infinitely many trees, we never
backtrack to tree(L)
• There are infinitely many trees that never get produced
tree(tip).
tree(bin(L,_,R)) :-
Fixing tree/1
• tree/1 does not behave well when its argument is uninstantiated
• tree(T) produces infinitely many trees, but not all trees
• But tree/1 works fine if its argument is instantiated
• In fact, all we need is for the tree structure to be instantiated, the contents can be
uninstantiated
• One way to resolve this issue: only use tree/1 with instantiated arguments
• The “just don’t do that” approach
• In documentation, it is common to use mode annotations to describe the intended use
of a predicate
Mode Annotations
• Ideally, every argument to a relation could be instantiated or uninstantiated
• As we have seen, this does not always lead to good results
• Often, we need to state requirements for what sorts of arguments we can give — these are called
modes of the relation
• Modes are not part of Prolog itself; they are given in documentation as guidelines
• Common mode indicators:
• + for arguments that must be instantiated (inputs)
• ? for arguments that can be partially instantiated (input/output)
• – for arguments that can be partially instantiated (output)
Mode Annotations
• Thus, tree(+Tree), because the argument to tree/1 must be instantiated
• height(+Tree, ?Height), because the height can be specified or
unspecified, but the tree must be specified
• height/2 has a second mode, height(?Tree, +Height), since it terminates
universally if the height is specified
• square(?X, ?Y) because our definition of square terminates even when
neither argument is instantiated
Structural Instantiation
• Some predicates only require the structure of an argument to be instantiated
• length/2 and height/2 can compute the length or height of a list or tree,
even if the elements are uninstantiated
• ?- length([_,_,_],N) will be solved with N = 3
• label/1 applies to a list of variables, but the list itself must be known
• Other predicates may require an argument to be fully instantiated
— containing no unbound variables
• The range given to in/2 must be fully instantiated
Termination and Modes
• Modes are commonly used to describe how/when a predicate terminates
• We will also describe the required type of an argument
• length(+List, -Integer) is deterministic
• length(+List, +Integer) is semi-deterministic
• It fails if the integer is not the length of the list
• length(-List, +Integer) is deterministic
• The solver will find a list (with variable elements) of the requested length
Termination and Modes
• height(+Tree, -Integer) is deterministic
• height(-Tree, +Integer) terminates universally
• There are finitely many trees of a given height
• The solver will find all of them and then stop
• ?- height(T, 5), false. will terminate
• height(-Tree, -Integer) terminates existentially
• There are infinitely many solutions, so the solver will never run of of possible answers
• Any backtracking points prior to this goal are effectively lost
• Both ? and – mark arguments that can be partially instantiated
• This includes fully instantiated and uninstantiated arguments
• The difference between ? and – is intention, but it is subtle
• We can use — to mark arguments that must be uninstantiated
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com