Principles of
Programming Languages
Copyright By PowCoder代写 加微信 powcoder
Recap: Logic Programming
• State facts and rules for deriving new facts
• Answer queries about those facts
• Prolog program consists of facts, rules, and query
• Prolog solver uses facts and rules to answer query
• We write the program; the solver is implicit
Recap: Terms
• Everything in Prolog is represented using terms
• Data and code; Prolog uses the same structure for both
• Simple terms:
• Variables start with _ or a capital letter
• Atoms are words starting with lower-case letter, or numbers, or single-quoted
text, or certain punctuation marks (+, *, #=, etc.)
• Compound terms: an atom applied to one or more arguments
• Usually arguments enclosed with parentheses and separated by commas
• Facts are stated in a Prolog file (eg., lec24.pl)
• A compound term followed by a period
• food(meat).
• eats(alice, cheese).
• connect_(manhattan, brooklyn, bridge).
• A fact can have variables, meaning it can be proven for any possible argument
• eats(eve, Anything). % i.e., “eve eats anything”
• Note that you may get a “singleton variable” warning for this, to avoid, use eats(eve, _).
http://lec24.pl
• A rule describes how to deduce a new fact from known facts
• eats(eve, F) :- food(F). % eve eats F, if F is food
• Form: consequent :- antecedents.
• Or, goal :- subgoals.
• Or, head :- tail.
• We can provide multiple rules with the same head
• The tail is one or more terms separated by commas (and/or semicolons)
• Facts are just rules with an empty tail.
• Both facts and rules define relations
• Relations in Prolog are identified by name and arity (number of arguments)
• Relations with the same name but different arities are independent
• We can provide facts and/or rules to define a relation
• Each fact or rule is called a clause
• food(cheese).
• food(pie(Filling)) :- food(Filling).
• Queries are one or more terms separated by
commas and/or semicolons, terminated with a
• eats(alice, pie(poison)).
• eats(eve, F), food(F).
• The solver will attempt to prove/disprove your
query, using the known facts and rules
• If the query has variables, it will try to find every
assignment that satisfies the query
food(meat).
food(cheese).
food(apple).
food(banana).
food(poison).
food(pie(F)) :- food(F).
eats(alice, meat).
eats(alice, cheese).
eats(alice, pie(_)).
eats(bob, apple).
eats(bob, banana).
eats(bob, pie(apple)).
eats(bob, pie(banana)).
eats(eve, _).
Terms Are Not Function Calls
• Relations can involve any term, including compound terms
• eats(alice, pie(F)) :- savory(F).
• This means that eats/2 applies to alice and any term pie(F), where
savory/1 applies to F
• In other words, we are using pie to construct values
• Similarly, we can think of savory(F) as meaning “try to prove that F is
savory”, but it is really just data that describes a subgoal
• The line between code and data is blurry in Prolog
• How does the Prolog solver answer our queries?
• Consider a simple query: eats(alice, pie(meat)).
• Look for any facts or rules that match the query
• If a fact matches the query, report true
• If a rule head matches the query, recursively try to prove the tail
• Continue with the next fact or rule that matches the query
• Queries that have no variables are either true (provable) or false (not provable)
• Queries that have variables may be provable in different ways
• Formally, a query matches a fact or rule head if they unify
• Similar to pattern matching in Haskell, but more powerful
• Two terms unify if there is an assignment of variables that makes them equal
• Meaning, the same term structure with the same atoms and variables
• So, pie(apple) and pie(F) unify, because we can make F = apple
• pie(meat) and cheese do not unify
• pie(meat) and pie(cheese) do not unify
• When are two terms considered equal?
• Atoms are equal to themselves (ignoring some syntax; e.g., x = ‘x’)
• Variables are equal to themselves
• Compound terms are equal if they have the same functor, the same
number of arguments, and the corresponding arguments are equal
• For the most part, equal terms look identical
• Exceptions: quotes around atoms, infix vs prefix terms
Substitutions
• Recall: a substitution is a mapping of variable names to values
• Applying a substitution to a term replaces variables with their corresponding values
• Applying a substitution to a term produces an instance of that term
• Applying {X = pie, Y = Z} to eats(Y, X) produces eats(Z, pie)
• Two terms unify if at least one term is an instance of both
• That term is called a unifier
• eats(alice, pie) is the unifier of eats(X, pie) and eats(alice, Y)
• To attempt to solve a goal G
• For each rule head F:
• If G and F unify, apply the same substitution to the tail of F and add its
contents as sub-goals
• Recursively prove all sub-goals
• Remember: all variables in Prolog are local to a single clause
• To avoid confusion/capture, replace all the variables in a rule with unused
names before unifying
• Query: parent(X, gerald).
• Try each clause defining parent/2
• Succeed with X = eve
• Succeed again with X = frank
parent(alice, eve).
parent(bob, eve).
parent(carol, frank).
parent(dan, frank).
parent(eve, gerald).
parent(frank, gerald).
grandparent(X, Z) :-
parent(X, Y),
parent(Y, Z).
• Query: grandparent(bob, X).
• One relevant rule
• Rename variables to avoid capture
• grandparent(_1,_2) :- parent(_1,_3),
parent(_3,_2).
• Unify with { _1 = bob, _2 = X }
• Introduce subgoals
• parent(bob,_3), parent(_3,X)
parent(alice, eve).
parent(bob, eve).
parent(carol, frank).
parent(dan, frank).
parent(eve, gerald).
parent(frank, gerald).
grandparent(X, Z) :-
parent(X, Y),
parent(Y, Z).
• Goals: parent(bob,_3), parent(_3,X)
• Try to prove first goal
• Succeeds with { _3 = eve }
• Substitute with remaining goal: parent(eve, X)
• Try to prove last goal
• Succeeds with { X = gerald }
• Report X = gerald
parent(alice, eve).
parent(bob, eve).
parent(carol, frank).
parent(dan, frank).
parent(eve, gerald).
parent(frank, gerald).
grandparent(X, Z) :-
parent(X, Y),
parent(Y, Z).
• Query: grandparent(Y, gerald).
• One relevant rule, rename vars to avoid capture
• grandparent(_1,_2) :- parent(_1,_3),
parent(_3,_2).
• Unify succeeds: { _1 = Y, _2 = gerald }
• Goals: parent(Y, _3), parent(_3,
parent(alice, eve).
parent(bob, eve).
parent(carol, frank).
parent(dan, frank).
parent(eve, gerald).
parent(frank, gerald).
grandparent(X, Z) :-
parent(X, Y),
parent(Y, Z).
• Goals: parent(Y, _3), parent(_3,
• First solution: { Y = alice, _3 = eve }
• Goal: parent(eve, gerald)
• Proven, with Y = alice
• If we ask for more answers, the solver will backtrack
to the previous goal and find { Y = bob, _3 = eve }
parent(alice, eve).
parent(bob, eve).
parent(carol, frank).
parent(dan, frank).
parent(eve, gerald).
parent(frank, gerald).
grandparent(X, Z) :-
parent(X, Y),
parent(Y, Z).
Meaning vs Procedure
• Ideally, we want to think about what our rules mean
• E.g., X is the grandparent of Z if there is some Y such that X is the parent of Y and
Y is the parent of Z
• The specific process used by the solver should not be important
• …except that certain ways of expressing rules may cause the solver to waste time
• …or get stuck trying infinitely many subgoals
• So we must dirty our hands with process, from time to time
• Prolog’s solver is relatively simple, so it’s easier to see where it gets stuck
Non-Termination
• We can generalize parent/2 and grandparent/2 to
create ancestor/2
• Logically, , so switching the order of
the antecedents should not matter
• …but Prolog’s solver always attempts goals from
left to right
• The solver will get stuck if someone has no
(known) parent
A ∧ B = B ∧ A
ancestor(X, Z) :-
parent(X, Z).
ancestor(X, Z) :-
parent(X, Y),
ancestor(Y, Z).
ancestor(X, Z) :-
parent(X, Z).
ancestor(X, Z) :-
ancestor(Y, Z),
parent(X, Y).
Performance
• We can expand ancestor(A, B) to see the solving
• parent(A, B); parent(A, C), ancestor(C, B)
• If A or B are unbound, we end up searching for
parents twice
• We can rephrase slightly, using ;
• Logically the same, but may have better
performance
ancestor(X, Z) :-
parent(X, Z).
ancestor(X, Z) :-
parent(X, Y),
ancestor(Y, Z).
ancestor(X, Z) :-
parent(X, Y),
ancestor(Y, Z)).
Working with Data
• How do I add up all the elements in a list?
• Wrong question!
• What relation exists between lists and their sums?
• sum([], 0). % the sum of the empty list is 0
• sum([X|Tail], Sum) :- sum(Tail, S), Sum #= X + S.
• X is the first element of the list, Tail is the rest of the list
• Sum is the sum of the whole list, S is the sum of the tail
Relations Are Flexible
• ?- sum([1,2,3], 6).
• ?- sum([1,2,3], X).
• ?- sum([1,X,3], 6).
• ?- sum([1,X,3], Y).
Y #= X + 4. % or something that simplifies to this
• ?- sum(L, 6).
L = [6] % and infinitely many other solutions…
List Membership
• How can I tell whether X is part of some list L?
• member(X, [X|_]).
• X is part of a list if the first element of the list is X
• Unlike in Haskell, variables can occur multiple times in a Prolog pattern
• member(X, [_|T]) :- member(X, T).
• X is part of a list if X is part of the tail of the list
Backtracking
• ?- member(2, [1,2,3]).
• What happened?
• The solver tries every possibility
• When we tried to solve member(2, [2,3]), both rules match
• We know only the first will succeed, but the solver doesn’t, so it offers to try again
• In this context, false means no additional answers
member(X, [X|_]).
member(X, [_|T]) :- member(X, T).
Backtracking
• ?- member(1, [1,1,2]).
• What happened?
• Again, the solver tries every possibility, and here two of them lead to success
• From a theoretical standpoint, this is not a problem
• From a practical standpoint, this may slow down solving of larger goals
member(X, [X|_]).
member(X, [_|T]) :- member(X, T).
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com