CPSC 312 — Functional and Logic Programming
Project #2 – get started!
But what is truly distinctive and valuable about human natural language is its semantic or representational capacities — the features of language responsible for how words carry meaning, and how words can be combined into sentences to make an indefinite number of distinct, meaningful assertions about the world.
Kevin deLaplante “All the Formal Logic You Need to Know for Critical Thinking” https://criticalthinkeracademy.com/courses/2514/ lectures/751606
CPSC 312 — Lecture 26 1 / 18
©D. Poole 2021
Today
lists (cont.)
definite clause grammars
natural language interfaces to databases
CPSC 312 — Lecture 26 2 / 18
©D. Poole 2021
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],L,[H|R]) :-
append(T,L,R).
What is the answer to query
?- append([a,b,c],R,L).
A There are no proofs
B L=[a,b,c|R]
C L=[a ,b, c], R=[]
D L=[a,b,c], R=[a,b,c]
©D. Poole 2021
CPSC 312 — Lecture 26 3 / 18
Clicker Question
What is the answer to query
?- append([a,b,c],R,L), append([1,2,3],S,R).
A B C D E
There are no proofs
R=[1,2,3|S],L=[1,2,3,a,b,c|S]. R=[1,2,3|S],L=R. R=[1,2,3|S],L=[a,b,c,1,2,3|S]. R=L,L=[a,b,c,1,2,3|S].
©D. Poole 2021
CPSC 312 — Lecture 26 4 / 18
Natural Language Understanding
We want to communicate with computers using natural language (spoken and written).
unstructured natural language — allow any statements, but make mistakes or failure.
controlled natural language — only allow unambiguous statements that have fixed meanings (e.g., in supermarkets or for doctors).
There is a vast amount of information in natural language.
Understanding language to answer questions is more difficult than getting extracting gestalt properties such as topic, or choosing a web page.
CPSC 312 — Lecture 26 5 / 18
©D. Poole 2021
Syntax, Semantics, Pragmatics
Syntax describes the form of language (using a grammar). Semantics provides the meaning of language.
Pragmatics explains the purpose or the use of language (how utterances relate to the world).
Examples:
This lecture is about natural language. The green frogs sleep soundly. Colorless green ideas sleep furiously. Furiously sleep ideas green colorless.
CPSC 312 — Lecture 26
6 / 18
©D. Poole 2021
Understanding needs parsing
A person with a big hairy cat drank the cold milk.
Who or what drank the milk?
Simple parse tree:
s
np
a person pp drank np
the
a big hairy cat
vp
with np
cold milk
CPSC 312 — Lecture 26 7 / 18
©D. Poole 2021
Context-free grammar
A terminal symbol is a word (perhaps including punctuation). A non-terminal symbol can be rewritten as a sequence of terminal and non-terminal symbols, e.g.,
sentence −→ noun phrase, verb phrase verb phrase −→ verb, noun phrase verb −→ [drank]
Can be written as a logic program, where a sentence is a sequence of words:
sentence(S) :- noun phrase(N), verb phrase(P), append(N, P, S). verb phrase(P) :- verb(V ), noun phrase(N), append(V , N, P).
To say word “drank” is a verb:
verb([drank]).
CPSC 312 — Lecture 26 8 / 18
©D. Poole 2021
Difference Lists
Non-terminal symbol s becomes a predicate with two arguments, s(T1, T2), meaning:
T2 is an ending of the list T1
all of the words in T1 before T2 form a sequence of words of
the category s.
Lists T1 and T2 together form a difference list. “the student” is a noun phrase:
noun phrase([the, student, passed, the, course], [passed , the , course ])
The words “drank” and “passed” are verbs: verb([drank | W ], W ).
verb([passed | W ], W ).
CPSC 312 — Lecture 26
9 / 18
©D. Poole 2021
Definite clause grammar
The grammar rule
sentence −→ noun phrase, verb phrase
means that there is a sentence between T0 and T2 if there is a noun phrase between T0 and T1 and a verb phrase between T1 and T2:
sentence(T0, T2) :-
noun phrase(T0, T1),
verb phrase(T1, T2). sentence
T0 T1 T2
noun phrase verb phrase
©D. Poole 2021
CPSC 312 — Lecture 26 10 / 18
Definite clause grammar rules
The rewriting rule
h −→ b1,b2,…,bn
says that h is b1 followed by b2, . . . , followed by bn:
h(T0,Tn) :- b1(T0, T1), b2(T1, T2),
.
bn(Tn−1, Tn). using the interpretation
h
T0 T1 T2 ···Tn−1 Tn
b1 b2 bn
©D. Poole 2021
CPSC 312 — Lecture 26 11 / 18
Terminal Symbols
Non-terminal h gets mapped to the terminal symbols, t1, …, tn: h([t1,···,tn |T],T)
using the interpretation
h
t1,··· ,tn T
Thus, h(T1, T2) is true if T1 = [t1, …, tn | T2].
©D. Poole 2021
CPSC 312 — Lecture 26 12 / 18
Context Free Grammar Example
see
https://www.cs.ubc.ca/~poole/cs312/2021/prolog/cfg_
simple.pl
What will the following query return?
noun phrase([the,student,passed,the,course,with,a,computer],R). How many answers does the following query have? sentence([the,computer,science,course,with,a,computer],R).
©D. Poole 2021
CPSC 312 — Lecture 26 13 / 18
Example
% a noun phrase is a determiner followed by adjectives
% followed by a noun followed by a prepositional phrase.
noun_phrase(L0,L4) :-
det(L0,L1),
adjectives(L1,L2),
noun(L2,L3),
pp(L3,L4).
% dictionary for determiners
det(L,L).
det([a|L],L).
det([the|L],L).
% adjectives is a sequence of adjectives
adjectives(L,L).
adjectives(L0,L2) :-
adj(L0,L1),
adjectives(L1,L2).
©D. Poole 2021
CPSC 312 — Lecture 26 14 / 18
Clicker Question
If the query for the grammar rule
noun_phrase([the,cat,on,the,mat,sat,on,the,hat], R). returns with substitution R=[sat,on,the,hat]
What is the noun-phrase it found? A the cat
B the mat
C the cat on the mat
D sat on the hat
E either “the cat”, “the mat” or “the hat”, we can’t tell
©D. Poole 2021
CPSC 312 — Lecture 26 15 / 18
Clicker Question
If the query for the grammar rule
noun_phrase([the,cat,on,the,mat,sat,on,the,hat], R). returns with substitution R=[on,the,mat,sat,on,the,hat]
What is the noun-phrase it found? A the cat
B the mat
C the cat on the mat
D sat on the hat
E either “the cat”, “the mat” or “the hat”, we can’t tell
©D. Poole 2021
CPSC 312 — Lecture 26 16 / 18
Question-answering
How can we get from natural language directly to the answer?
Goal: map natural language to a query that is asked of a knowledge base.
Add arguments representing the individual noun phrase(T0,T1,O)
means
T0 − T1 is a difference list forming a noun phrase. The noun phrase refers to the individual O.
Can be implemented by the parser directly calling the knowledge base.
CPSC 312 — Lecture 26
17 / 18
©D. Poole 2021
Example natural language to query
see
https:
//www.cs.ubc.ca/~poole/cs312/2021/prolog/geography.pl
©D. Poole 2021
CPSC 312 — Lecture 26 18 / 18