CS计算机代考程序代写 prolog Haskell CPSC 312 — Functional and Logic Programming

CPSC 312 — Functional and Logic Programming
Assignment 5 is available
Midterm #3 next week — more details on web site soon
“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 23 1 / 26
©D. Poole 2021

Since the midterm…
Done:
Syntax and semantics of propositional definite clauses
Model a simple domain using 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.
Syntax of Datalog: Predicate symbols, constants, variables, queries.
Semantics of Datalog: Interpretations, variable assignments, models, logical consequence.
CPSC 312 — Lecture 23 2 / 26
©D. Poole 2021

Semantics: General Idea
A semantics specifies the meaning of sentences in the language. An interpretation specifies:
what objects (individuals) are in the world
the correspondence between symbols in the computer and objects and relations in world
􏰌 constants denote individuals
􏰌 predicate symbols denote relations
CPSC 312 — Lecture 23 3 / 26
©D. Poole 2021

Formal Semantics
An interpretation is a triple I = ⟨D, φ, π⟩, where
D, the domain, is a nonempty set. Elements of D are
individuals.
φ is a mapping that assigns to each constant an element of D. Constant c denotes individual φ(c).
π is a mapping that assigns to each n-ary predicate symbol a relation: a function from D n into {TRUE, FALSE}.
CPSC 312 — Lecture 23 4 / 26
©D. Poole 2021

Clicker Question
Suppose we have an interpretation I with domain D = {􏰑, 􏰒, 􏰕, v, 􏰓}.
and φ(c) = v and φ(d) = v.
Which of the following is not true:
A Every statement that is true about d is true about c.
B c and d refer to two things with the same name
C There is one individual with two different names
D c could be replaced by d in all clauses and the same clauses would be true in I
©D. Poole 2021
CPSC 312 — Lecture 23 5 / 26

Clicker Question
Given a knowledge base KB, if an answer that is false in the intended interpretation is returned (given a sound and complete proof procedure). Which of the following is true
A One of the clauses in KB must be false in the intended interpretation
B There are too many irrelevant facts that confused the system
C The intended interpretation is a model of KB.
D None of the above.
©D. Poole 2021
CPSC 312 — Lecture 23 6 / 26

Clicker Question
Given a knowledge base KB, if g is true in the intended interpretation, and g is not given as an answer (assuming a sound and complete proof procedure that halts), which of the following is true
A One of the clauses in KB must be false in the intended interpretation
B g is false in another model of KB
C The intended interpretation is not a model of KB
D All of the above
E None of the above.
©D. Poole 2021
CPSC 312 — Lecture 23 7 / 26

Role of Semantics
in(kim,r123). part_of(r123,cs_building). in(X,Y) ←
kim r123 r023
part_of(Z,Y) ∧ in(X,Z).
cs_building
in( , ) part_of( , ) person( )
in(kim,cs_building) ©D. Poole 2021
CPSC 312 — Lecture 23 8 / 26

Variables
A variable assignment is a function from variables into the domain.
Given an interpretation and a variable assignment, each term denotes an individual and
each clause is either true or false.
A clause containing variables is true in an interpretation if it is true for all variable assignments.
This means variables are universally quantified in the scope of a clause.
CPSC 312 — Lecture 23 9 / 26
©D. Poole 2021

Queries and Answers
A query is a way to ask if a body is a logical consequence of the knowledge base:
?− b1, ···, bm. An answer is either
an instance of the query that is a logical consequence of the knowledge base KB (given by an assignment of values to variables in the query), or
no (or false) if no instance is a logical consequence of KB.
CPSC 312 — Lecture 23 10 / 26
©D. Poole 2021

Example Queries (simpvar.pl)
 in(kim,r123).
KB = in(X,Y) :- part of(Z,Y), in(X,Z).
 part of(r123,cs building).
Query Answer
?− part of (r 123, B ). part of (r 123, cs building ) ?− part of(r023,cs building). no
?− in(kim,r023). no
?− in(kim,B). in(kim,r123)
in(kim,cs building)
©D. Poole 2021
CPSC 312 — Lecture 23 11 / 26

Anonymous variable
In Prolog, is the anonymous variable.
It is a logical variable where all instances are a different variable.
in queries means we don’t care about the value of a variable
Singleton variables in a clause are often an error. Use instead.
CPSC 312 — Lecture 23 12 / 26
©D. Poole 2021

Electrical Environment
cb1
w5
outside power
circuit breaker
off
on switch
two-way switch
light
power outlet
s1
cb2
s2 w1 w2
s3
w3
w6
p2
p1
w0
w4
l1
l2
©D. Poole 2021
CPSC 312 — Lecture 23 13 / 26

Axiomatizing the Electrical Environment (elect reln.pl)
% light(L) is true if L is a light
light (l1 ). light (l2 ).
% down(S) is true if switch S is down down(s1). up(s2). up(s3).
% ok(D) is true if D is not broken ok(l1). ok(l2). ok(cb1). ok(cb2).
?− light(l1). =⇒ yes
?− light(l6). =⇒ no
?− up(X). =⇒ up(s2), up(s3)
©D. Poole 2021
CPSC 312 — Lecture 23 14 / 26

% connected to(X , Y ) is true if component X is connected to Y % so electricity will flow from Y to X
connected connected connected connected connected connected
to(w0, w1) :- up(s2). to(w0, w2) :- down(s2). to(w1, w3) :- up(s1). to(w2, w3) :- down(s1). to(w4, w3) :- up(s3). to(p1, w3).
?− connected to(w0, W ).
?− connected to(w1, W ).
?− connected to(Y,w3).
?−connectedto(X,W). =⇒ X=w0,W=w1,…
=⇒ W = w1
=⇒ no
=⇒ Y = w2, Y = w4, Y = p1
©D. Poole 2021
CPSC 312 — Lecture 23 15 / 26

% lit(L) is true if the light L is lit lit(L) :- light(L), ok(L), live(L).
% live(C) is true if there is power coming into C live(Y) :-
connected to(Y,Z),
live(Z). live (outside ).
This is a recursive definition of live.
©D. Poole 2021
CPSC 312 — Lecture 23 16 / 26

Recursion and Mathematical Induction
above(X,Y) :- on(X,Y).
above(X,Y) :- on(X,Z), above(Z,Y). This can be seen as:
Recursive definition of above: prove above in terms of a base case (on) or a simpler instance of itself; or
Way to prove above by mathematical induction: the base case is when there are no blocks between X and Y , and if you can prove above when there are n blocks between them, you can prove it when there are n + 1 blocks.
CPSC 312 — Lecture 23 17 / 26
©D. Poole 2021

Function Symbols
Often we want to refer to individuals in terms of components. Examples: 4:55 p.m. English sentences. A classlist.
We extend the notion of term. So that a term can be
􏰌 a variable
􏰌 a constant
􏰌 of form f(t1,…,tn) where f is a function symbol and the ti
are terms.
CPSC 312 — Lecture 23 18 / 26
©D. Poole 2021

Semantics: General Idea
A semantics specifies the meaning of sentences in the language. An interpretation specifies:
what objects (individuals) are in the world
the correspondence between symbols in the computer and objects and relations in world
􏰌 constants denote individuals (specified by φ)
􏰌 predicate symbols denote relations (specified by π)
􏰌 in an interpretation and with a variable assignment, term
f(t1,…,tn) denotes an individual in the domain. Also specified by φ (constant is just a special case).
The semantics is otherwise unchanged.
Prolog functions are like Haskell constructors (defined with data in Haskell).
CPSC 312 — Lecture 23 19 / 26
©D. Poole 2021

Example: dates (dates.pl)
Suppose we want to refer to dates, e.g., December 25, 1971 Use ce(Y,M,D) where Y is the year, M is the month and D
is the day of the month. (ce is for “common era”). ce(·) can only be used as part of an atom:
% born(Person,Date) is true if Person was born on Date
born(justin,ce(1971,dec,25)).
born(pierre,ce(1919,oct,18)).
born(ella_mai,ce(1994,nov,3)).
born(shawn_mendez, ce(1998,aug,8)).
Define before(D1,D2) which is true when date D1 is before date D2. (You may use infix predicate < where X < Y is true if X is less than Y). Add bce(y, m, d) for before common era, e,g,. bce(55, mar, 15) is the ides of March, 55BCE. Given born(Person, Date) information, write older(P1, P2). CPSC 312 — Lecture 23 20 / 26 ©D. Poole 2021 Clicker Question foo(a,X,X) A must be an atom B must be a term C Prolog cannot tell if it is a term or atom D Prologcantellifitisatermoranatombywhereit appears in a clause. ©D. Poole 2021 CPSC 312 — Lecture 23 21 / 26 Clicker Question If foo(a,X,X) appears as foo(a,X,X) :- bar(X). For an interpretation I A foo(a,X,X) denotes an individual in I B foo(a,X,X) is true or false in I C foo(a,X,X) denotes an individual in I only given a variable assignment D foo(a,X,X) is true or false in I only given a variable assignment ©D. Poole 2021 CPSC 312 — Lecture 23 22 / 26 Clicker Question If foo(a,X,X) appears as noon(foo(a,X,X),17) :- bar(X). For an interpretation I A foo(a,X,X) denotes an individual in I B foo(a,X,X) is true or false in I C foo(a,X,X) denotes an individual in I only given a variable assignment D foo(a,X,X) is true or false in I only given a variable assignment ©D. Poole 2021 CPSC 312 — Lecture 23 23 / 26 Working with terms (myis.pl) Prolog has a predicate ’is’, so that is(N,E) usually written N is E is true when expression E evaluates to number N. E must not contain variables when called. Prolog has predicate number(N) that is true if N is a number. Define myis(N,E) that is true if arithmetic expression E has value the number N. ’myis’ can be made into an infix operator by declaring: :- op(700, xfx, myis). CPSC 312 — Lecture 23 24 / 26 ©D. Poole 2021 Lists (mylist.pl) A list is an ordered sequence of elements. Let’s use 􏰌 the constant empty to denote the empty list, and 􏰌 the function cons(H,T) to denote the list with first element H and rest-of-list T. These are not built-in. The list containing jan, feb and mar is cons(jan, cons(feb, cons(mar, empty))) member(E,L) is true if E is and element of list L. append(X,Y,Z) is true if list Z contains the elements of list X followed by the elements of list Y . append(empty,Z,Z). append(cons(A,X),Y,cons(A,Z)) :- append(X,Y,Z). CPSC 312 — Lecture 23 25 / 26 ©D. Poole 2021 Syntactic Sugar for Lists (lists.pl) The empty list is [ ] The list with first element H and the rest of the list T is [H | T]. [···a··· | []] written as [···a···]. [···a··· | [···b···]] written as [···a··· ,···b···]. Examples member(X,L) is true if X is an element of list L append(A,B,C) is true if C contains the elements of A followed by the elements of B numeq(X,L,N) is true if N is the number of instances of X in L. sum(L,N) is true if N is the sum of the elements of L reverse(L,R) is true if R is the reverse of list L. CPSC 312 — Lecture 23 26 / 26 ©D. Poole 2021