CPSC 312 — Functional and Logic Programming
Midterm #3 on Monday! — more details on web site (yes, it’s like the others, only different questions)
Solution to assignment 5 availabale.
“Contrariwise,’ continued Tweedledee, ’if it was so, it might be; and if it were so, it would be; but as it isn’t, it ain’t. That’s logic.”
Lewis Carroll, Through the Looking-Glass
CPSC 312 — Lecture 25 1 / 10
©D. Poole 2021
Since the midterm…
Syntax and semantics of propositional definite clauses
Bottom-up proof procedure computes a consequence set using modus ponens.
Top-down proof procedure answers a query using resolution. The box model provides a way to procedurally understand the
top-down proof procedure with depth-first search.
Prolog Syntax: Predicate symbols, constants, variables, function symbols.
Prolog Semantics: Interpretations, variable assignments, models, logical consequence.
Functions applied to arguments refer to individuals. Individuals are described using clauses.
(Prolog’s function symbols are like Haskell constructors.) Special syntax for lists; internally a binary function ’[|]’.
Today: lists, trees…
CPSC 312 — Lecture 25 2 / 10
©D. Poole 2021
Writing a Prolog program
To write a Prolog program:
Have a clear intended interpretation – what all predicates, functions and constants mean
Don’t tell lies.
Make sure all clauses are true given your meaning for the constants, functions, predicates.
Make sure that the clauses cover all of the cases when a predicate is true.
Avoid cycles.
Design top-down, build bottom-up.
Debug all predicates as you write them.
To solve a complex problem break it into simpler problems.
CPSC 312 — Lecture 25 3 / 10
©D. Poole 2021
Lists examples (lists.pl)
Define sum(L,S) that is true when S is the sum of the elements of list L.
Define sum3(L,A,S) is true if S is A plus the sum of the elements of L
Define: reverse(L,R) is true if R has same elements as L in reverse order.
Define reverse 3(L, A, R ) is true if R consists of the elements of L reversed followed by the elements of A
CPSC 312 — Lecture 25 4 / 10
©D. Poole 2021
Lists examples (lists.pl)
Compare
% append(L,A,R) is true if list R contains the
% elements of list L followed by the elements of list A
append([],R,R).
append([H|T],A,[H|R]) :-
append(T,A,R).
% reverse3(L,A,R) is true if R contains the
% elements of L reversed followed by the elements of A
reverse3([],R,R).
reverse3([H|T],A,R) :-
reverse3(T,[H|A],R).
©D. Poole 2021
CPSC 312 — Lecture 25 5 / 10
Clicker Question
% append(L,A,R) is true if R contains the
% elements of L followed by the elements of A
append([],L,L).
append([H|T],A,[H|R]) :-
append(T,A,R).
What is the answer to query
?- append([a,b,c],X,Y).
A B C D B
There are no proofs
Y=[a,b,c|X] X=[],Y=[a,b,c] X=Y=[a,b,c] Y=[a,b,c,X]
©D. Poole 2021
CPSC 312 — Lecture 25 6 / 10
Clicker Question
% reverse3(L,A,R) is true if list R consists of
% the elements of list L reversed
% followed by the elements of list A
reverse3([],R,R).
reverse3([H|T],A,R) :-
reverse3(T,[H|A],R).
What is the answer to query
?- reverse3([a,b,c],X,Y).
A B C D E
There are no proofs
Y=[c,b,a|X] Y=[c,b,a],X=[] Y=X=[c,b,a] Y=[c,b,a,X]
©D. Poole 2021
CPSC 312 — Lecture 25 7 / 10
Clicker Question
revapp([],R,R).
revapp([H|T],A,[H|R]) :-
revapp(T,[H|A],R).
What is the answer to query
?- revapp([a,b,c],X,Y).
A B C D E
There are no proofs
Y=[c,b,a,c,b,a|X] Y=[a,b,c,a,b,c|X] Y=[c,b,a,a,b,c|X] Y=[a,b,c,c,b,a|X]
©D. Poole 2021
CPSC 312 — Lecture 25 8 / 10
Trees (bstree.pl)
A binary search tree can be used as a representation for dictionaries.
A binary search tree is either
empty or
bnode(Key,Val,T0,T1) where Key has value Val and T0 is
the tree of keys less than Key and T1 is the tree of keys greater than Key
Define val(K,V,T) is true if key K has value V in tree T
Define insert(K,V,T0,T1) true if T1 is the result of inserting K = V into tree T0
CPSC 312 — Lecture 25 9 / 10
©D. Poole 2021
Trees (bstreec.pl)
In Prolog, when X < Y is called, both X and Y must be ground (variable free) numbers
There are constraint solvers that let Prolog act more logically. X #< Y specifies the constraint that X < Y .
Eg, consider the query
val(K,V,bnode(2,22, bnode(1,57,empty,empty),
bnode(5,105,empty,empty))).
< is much faster as it can be evaluated immediately.
#< requires more sophisticated reasoning.
?- val(K,V,bnode(2,22, bnode(1,57,empty,empty),
bnode(5,105,empty,empty))), V #< 99.
?- V #< 99, val(K,V,bnode(2,22,
bnode(1,57,empty,empty),
bnode(5,105,empty,empty))).
CPSC 312 — Lecture 25 10 / 10
©D. Poole 2021