程序代写

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