代写代考

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