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

CPSC 312 — Functional and Logic Programming
Project #2 – should be underway
“In Prolog, as in most halfway decent programming languages, there is no tension between writing a beautiful program an writing an efficient program. If your Prolog code is ugly, the chances are that you either don’t understand your problem or don’t understand your programming language, and in neither case does your code stand much chance of being efficient. In order to ensure your program is efficient, you need to know what it is doing, and if your code is ugly, you will find it hard to analyse.”
Richard A. O’Keefe, “The Craft of Prolog”, 1990.
CPSC 312 — Lecture 28 1 / 8
©D. Poole 2021

Plan
Last time difference lists
definite clause grammars
natural language interfaces to databases Future
computer algebra and calculus Knowledge graphs
Semantic web
Negation as failure
Proofs
CPSC 312 — Lecture 28
2 / 8
©D. Poole 2021

Building a list of constraints on the entity (geographyq.pl)
Nouns and adjectives provide constraints:
adj([large | L],L,Entity, [large(Entity)|C],C).
adj([Lang,speaking | L],L,Entity,
[speaks(Entity,Lang)|C],C).
noun([country | L],L,Entity, [country(Entity)|C],C).
noun([city | L],L,Entity, [city(Entity)|C],C).
Verbs and propositions provide relations reln(T0,T1,Subject,Object,C0,C1)
􏰌 T 0 − T 1 is a verb or preposition that provides relations in
C 0 − C 1 that is true between individuals Subject and Object
reln([borders | L],L,O1,O2,[borders(O1,O2)|C],C).
reln([the,capital,of | L],L,O1,O2,
[capital(O2,O1)|C],C).
reln([next,to | L],L,O1,O2, [borders(O1,O2)|C],C).
CPSC 312 — Lecture 28 3 / 8
©D. Poole 2021

Clicker Question
If the query for the grammar rule
noun_phrase([the,cat,on,the,mat,sat,on,the,hat],
R, Ent, C0, C1).
returns with substitution R=[sat,on,the,hat] What do we hope the value of C0 and C1 is:
A C0 = [the,cat,on,the,mat|C1]
B C0 = [cat(Ent),on(Ent,A),mat(A)|C1] C C0 = felix,C1 = fluffy
D C0=C1
E we would hope this would fail
©D. Poole 2021
CPSC 312 — Lecture 28 4 / 8

Clicker Question
Which specifies that sat is a verb, than indicates the relation sat: A
reln([sat | L], L, Sub, Obj, [sat(Sub,Obj) | C], C).
B reln([sat | L], L, Sub, Obj, [sat | C], C).
C reln([sat | L], L, Sub, Obj, sat(Sub,C), C).
D reln([sat | L], L, Sub, Obj, sat(Sub,Obj), C).
E It can’t be done
©D. Poole 2021
CPSC 312 — Lecture 28 5 / 8

Real-world queries
Want a tokenizer: mapping from strings to sequence of words. readln provides a simple one.
What should the system do with ungrammatical sentences?
What should the system do with new words?
What about pronoun references?
The student took many courses. Two computer science courses and one mathematics course were particularly dif- ficult. The mathematics course. . .
Other tricky and subtle aspects of English? — program them
— learn them
We need a lexicon. Wordnet is a large lexical database of English https://wordnet.princeton.edu. It comes in a Prolog version and one that is complicated to use. It has 212558 “words”.
CPSC 312 — Lecture 28 6 / 8
©D. Poole 2021

NLP requires Understanding (Winograd Schemas)
The city councilmen refused the demonstrators a permit because they feared violence. Who feared violence?
The city councilmen refused the demonstrators a permit because they advocated violence. Who advocated violence? Steve follows Fred’s example in everything. He [admires/influences] him hugely. Who [admires/influences] whom?
The table won’t fit through the doorway because it is too [wide/narrow]. What is too [wide/narrow]?
Grace was happy to trade me her sweater for my jacket. She thinks it looks [great/dowdy] on her. What looks [great/dowdy] on Grace?
Bill thinks that calling attention to himself was rude [to/of]
Bert. Who called attention to himself?
In a recent competition, the best algorithm got 58% correct!
https://cs.nyu.edu/faculty/davise/papers/WinogradSchemas/WS.html
CPSC 312 — Lecture 28 7 / 8
©D. Poole 2021

Computer Algebra (algebra.pl)
Because Prolog does not evaluate expressions, an algebraic expression can be manipulated. E.g., as in Assignment 5.
Algebraic variables can be treated as Prolog constants. (Remember Prolog variables mean “for all”).
Derivatives can be defined using
deriv(E,X,DE) is true if DE is the derivative of E with respect to X
Expressions can be simplified: To simplify A ∗ B: first simplify A and B, then check for multiplication by 0 or 1 or when both simplify to numbers.
More sophisticated simplification is possible (but difficult). Multivariate differentiation just works.
Integration is more difficult (finding when to apply rules is more complicated)
CPSC 312 — Lecture 28 8 / 8
©D. Poole 2021