Principles of
Programming Languages
Copyright By PowCoder代写 加微信 powcoder
Logic Programming
Preliminaries
• Programming Language Pragmatics, Chapter 12
• Canvas: Prolog References
• The Power of Prolog
• Recommended software: SWI-Prolog (swipl)
• Installed on iLab machines
• Or install locally
What are programs for?
• Programs tell a computer how to find the answer to some question
• Often a parameterized question, e.g., sqrt(x), where x = 25
• We can think of “question” and “answer” very broadly
• We could compute the answer to a math problem
• We could generate a report based on a data set
• We could decide what actions to perform in response to user input
Procedural Programming
• Compute answers by performing a sequence of actions
• Manipulate the state of an abstract machine
• Variables represent storage locations that can be read and updated
• Explicit control flow: procedure calls, loops, branches
to compute the length of a list L:
length <- 0
while L ≠ Nil:
length <- length + 1
L <- tail(L)
return length
Functional Programming
• Compute answers by evaluating functions
• Evaluate function application with substitution
• Variables represent values in a defined environment
• Higher-order: Functions can have function arguments and can return functions
• Instead of saying how to compute a correct answer, say what the answer is
the length of list L is:
if L = Nil, 0
otherwise, 1 + the length of tail(L)
Logic Programming
• Compute answer by solving logical queries
• Provide facts and inference rules
• Variables represent values, and may be bound or free
• A solver searches for variable assignments that satisfy the query
• Instead of saying what the correct answer is, describe what it means for an
answer to be correct
the length of Nil is 0.
the length of L is N, if the length of tail(L) is M and N = M + 1.
Comparison
Procedural Functional Logical
Specify the sequence
of steps needed to
compute an answer
Express the answer in
terms of the question
Declare what
conditions an answer
must satisfy
May require over-
specifying details
(e.g. sequence of
computation)
Only finds 1 solution;
maximizing efficiency
requires understanding
of the evaluator
May find too many
solutions; maximizing
efficiency requires
understanding of the
Logic Programming
• The goal of logic programming
• State facts
• Let computer answer queries based on those facts
• State facts in restricted first-order predicate calculus
• Answer some queries, time permitting
Example: Sorting
• List LS is a sorted version of List L, if
• LS is a permutation of L
• LS is in order
• Algorithm for finding LS, given L
• For each permutation LP of L,
• If LP is in order, then LS = LP
• How fast is this algorithm?
• Let n be the length of L
• There are n! possible permutations, and checking for order requires O(n) comparisons
• If L has 20 elements, the worst case is ≈4.8×1019 comparisons
What Computes?
• In functional programming, we describe the correct answer in terms of the
question parameters
• Actual computation is performed by an evaluator
• Sometimes, we need to understand how the evaluator works in order to achieve
good performance or avoid nontermination (divergence)
• In logic programming, we give rules that imply the correct answer(s)
• Actual computation is performed by a solver
• Sometimes, we need to understand how the solver works in order to achieve
good performance or avoid nontermination
• Ideally, we just state facts and then use them to answer queries
• Logic programs divide this into two parts
• A question-specific set of facts and rules
• A general-purpose solver
• The solver, or theorem prover, uses its own algorithms to answer queries based on the
• Methods: unification, backward chaining, backtracking
• Solvers can be simple and general (basic Prolog) or use sophisticated, domain-specific
tactics (advanced Prolog, SMT solvers)
Haskell’s Type System
• We have already seen logic programming hidden in Haskell’s type system
• An instance states a fact
• instance Eq Int where …
• Or a rule for inferring facts
• instance (Eq a) => Eq (Tree a) where …
• The type checker will use these to infer facts, such as Eq (Tree (Tree Int))
• Haskell’s class system is more constrained than a typical logic language, because the
solver needs to produce a unique witness (the implementation of the member functions)
• Abbreviation for programmation en logique (“programming in logic”)
• Created in France in the 1970s by AI researchers
• A program consists of fact and rule declarations and a particular query to
• Untyped: all values are terms
• Depth-first, backtracking solver
Using Prolog
• After loading a source file, we can ask a Prolog environment questions
?- 1 + 1 #= 2.
?- 1 + 1 #= X.
?- X + 1 #= 2.
?- X * X #= 4.
X in -2\/2.
?- X * X #= 4, X #> 0.
• A function is a mapping from a domain to a co-domain
• We compute a single output for each input
• A relation either holds or does not hold
• Relations do not have a “direction”: we can hold any parameter constant while
allowing others to vary
f(x) = x2 + 1
P(x, y) ≡ y < x2 + 1 ∃y . P(5,y) ∃x . P(x,26) • In Prolog, all variables begin with a capital letter or _ • Every variable is scoped over a clause • That is, a single fact, rule, or query • Variables are implicitly declared • Variables are initially free (not assigned to any value) • The solver will constrain variables • If the constraints become inconsistent, the query cannot be satisfied Syntax: Variables and Atoms • Everything in Prolog is a term • A term may be a variable, such as X or Sum or _127 • A term may be an atom (or symbol) • A word starting with a lower-case letter or digit: x, square, 17 • Text surrounded by single quotes: 'Jim', '#=', 'long atom' • Each atom is its own value (similar to strings) • The quotes are not part of the name: x and 'x' are the same Syntax: Terms with Arguments • A term may be an atom applied to arguments (sub-terms) • Usually written with parentheses and commas • square(X, 25), +(A,1), 'fancy insert'(2, [1,3,4], L) • Some atoms can be declared “infix” • E.g., X + 1 is the same as +(X,1) • Each infix atom has a precedence and associativity • These are not function calls! An atom applied to arguments is a tree • Note: it has to be an atom, not a variable; X(1,2) is not allowed Syntax: Lists • Lists in Prolog are just terms constructed with specific atoms • Traditionally, the empty list is '[]' and a non-empty list is '.' applied to two arguments • Instead of using those directly, we use square brackets • Empty list: [] • Non-empty lists separate elements with commas: [1, hello, 'how are you?', • The tail of the list can be given after |: [Head|Tail], [1,2|X] • [1,2,3] = [1,2|[3]], = [1|[2,3]] = [1|[2|[3]]] = [1|[2|[3|[]]]] • Don’t confuse Haskell list notation with Prolog list notation! Terms are Trees person(name('John', 'Smith'), date(1785,6,2), deceased) name date deceased Terms are Trees X + 1 = 2 * Y =(+(X,1), *(2,Y)) Terms are Trees '.'(a,'.'(b,'.'(X,Y))) Terms Are Not Functions • Do not be fooled by your experience with other programming languages! • A term with arguments is data, not a function call • Prolog uses terms to represent everything: facts, rules, queries • When you enter a term in the solver, it is treated as a query • When you load a file containing terms, they are added to the solver’s • Prolog files contain facts, rules, and directives • A fact is a term followed by a period • eats(jim, vegetables). • eats(jane, Anything). • Facts have no inherent meaning, beyond what we give to them • All Prolog cares about is “provable” vs “non-provable” • Any variables used are defined only for that fact • A rule is a fact written with :- • carnivore(X) :- eats(X, meat). • For all X, eats(X, meat) implies carnivore(X) • For all X, to prove carnivore(X), try proving eats(X, meat) • We can call the left the “head”, the “consequent”, or the “conclusion” • We can call the right the “tail”, the “antecedent”, or the “premise” • Supposedly, :- looks like ← Conjunction and Disjunction • To require proving multiple terms, separate them with commas • ?- eats(P,X), nondairy(X). • eats(jim, X) :- seafood(X), fresh(X). • Alternatives can be separated by semicolons • ?- (P = jim; P = jane), eats(P, X). • eats(bob, X) :- seafood(X), (fresh(X); preserved(X)). • Prolog’s solver is fairly simple • To solve some query G: • For each rule whose head unifies with G: • Attempt to solve the tail • If we can recursively solve all the subgoals, the query is satisfied • There may be multiple solutions! • This Prolog code defines four relations • The convention in Prolog is to refer to a relation by giving its name and the number of parameters (arity) • mouse/1, cat/1, dog/1, chases/2 • The name and the arity together identify the relation • If we defined dog/2, it would be unconnected to dog/1 mouse(jerry). cat(garfield). dog(odie). dog(scooby). chases(X, Y) :- cat(X), mouse(Y). chases(X, Y) :- dog(X), cat(Y). chases(garfield, odie). chases(ghosts, scooby). • Once we load this into a Prolog environment, we can ask questions • If a fact matching our question is present in the database, Prolog will answer true • ?- cat(garfield). • If the query contains variables, Prolog will try to unify it with its facts and report the unifier • ?- cat(X). X = garfield ; mouse(jerry). cat(garfield). dog(odie). dog(scooby). chases(X, Y) :- cat(X), mouse(Y). chases(X, Y) :- dog(X), cat(Y). chases(garfield, odie). chases(ghosts, scooby). • If no fact matches the query, Prolog returns false. • ?- cat(heathcliff). • If the query has multiple subterms, Prolog will try to find a consistent assignment of variables • ?- cat(X), dog(X). mouse(jerry). cat(garfield). dog(odie). dog(scooby). chases(X, Y) :- cat(X), mouse(Y). chases(X, Y) :- dog(X), cat(Y). chases(garfield, odie). chases(ghosts, scooby). • If the query matches the head of a rule, Prolog will add the tail as additional goals • ?- chases(odie, G). • Two rules unify with the query, so Prolog will try • Goal: cat(odie), mouse(G). • The first subgoal fails • Goal: dog(odie), cat(G). • Succeeds with G = garfield; G = tom mouse(jerry). cat(garfield). dog(odie). dog(scooby). chases(X, Y) :- cat(X), mouse(Y). chases(X, Y) :- dog(X), cat(Y). chases(garfield, odie). chases(ghosts, scooby). 程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com