Transcript Powerpoint Slides

Prolog for Linguists
Symbolic Systems 139P/239P
John Dowding
Week 7, November 12, 2001
[email protected]
Office Hours
We have reserved 4 workstations in the Unix Cluster in
Meyer library, fables 1-4
No office hours this week or next week
Contact me to make other arrangements
Course Schedule
1.
2.
3.
4.
5.
6.
7.
8.
Oct. 8
Oct. 15
Oct. 22
Oct. 29
Nov. 5 (double up)
Nov. 12
Nov. 26 (double up) – Iterative Deepening and Logic
Dec. 3
No class on Nov. 19
Dynamic predicates and assert
Add or remove clauses from a dynamic predicate at run time.
To specify that a predicate is dynamic, add
:- dynamic predicate/Arity.
to your program.
assert/1, asserta/1, assertz/1 adds a new clause for the predicate
retract/1 removes one or more clauses
retractall/1 removes all clauses for the predicate
abolish/1 removes all information about a predicate
Can’t modify compiled predicates at run time
Modifying a program while it is running is dangerous
Aggregation: findall/3.
findall/3 is a meta-predicate that collects values from
multiple solutions to a Goal:
findall(Value, Goal, Values)
findall(Child, parent(james, Child), Children)
Prolog has other aggregation predicates setof/3 and
bagof/3, but we’ll ignore them for now.
Built-in: current_op/3
current_op/3 gives the precedence and associativity of all
current operators.
current_op(Precedence, Associativity, Operator)
where Precedence in an integer 1-1200
and Associativity is of
 fx or fy for prefix operators
 xf or yf for postfix operators
 xfx, xfy, yfx, yfy for infix operators
Associativity
These atoms: fx, fy, xf, yf, xfx, xfy, yfx, yfy draw a
“picture” of the associativity of the operator:
 The location of the f tells if the operator is prefix, infix,
or postfix.
 x means that the argument must be of lower precedence
 y means that the argument must be of equal or lower
precedence.
 A y on the left means the operator is left associative
 A y on the right means the operator is right associative
yfy is not in Sicstus Prolog, or Quintus Prolog
Creating new operators
Built-in op/3 creates new operators
op(+Precedence, +Associativity, +Operator)
:- op(700, xfx, equals).
:- op(650, fx, $).
:- op(650, xf, cents).
$Dollars equals Cents cents :Cents is 100 * Dollars.
Declarations
The syntax
:- Goal.
indicates to execute Goal when consulting the file
We’ve seen a few of these so far:
:- dynamic known_prime/1.
:- op(700, xfx, equals).
Consult
The operation for reading in a file of Prolog clauses and
treating them as a program is traditional known as
“consulting” the file.
We will write a simple consult/1 predicate, and build on it
over time.
We will write similar
Parsing, grammars, and language theory
The development of Prolog (by Colmeraur at Marseilles)
was motivated in part by a desire to study logic and
language.
Grammars are formal specifications of languages
Prolog takes these specifications and treats them as logical
theories about language, and as computations
Grammar  Proof  Computation
Pereira and Warren, Parsing as Deduction, 1984.
Ideas from Prolog/Logic Programming, particularly
unification, are found in modern Linguistics.
Difference lists as indicies
Traditional parsing uses indicies to keep track of phrase
boundaries
the man likes the dog
0 1
2
3 4 5
“the man” is an NP spanning 0-2
“likes the dog” is a VP spanning 2-5
We’ll use difference lists to indicate spans,
“the dog” is an NP spanning [the,dog]-[]
“the man” is an NP spanning [the,man,likes,the,dog][likes,the,dog]
Difference list grammar rule translation
s  np, vp.
Translates to:
s(S0, SN) :- np(S0, S1), vp(S1, SN).
Instead of one variable, we have two, for the start and end
points of the phrase,
And the phrases are linked so that the end of one phrase is
the same as the start of the adjacent phrase.
Ruling out ungrammatical phrases
We’ve got a little grammar, but it accepts a lot of
ungrammatical sentences
First, let’s deal with number agreement between subject
NP and the verb:
Conventional to indicate ungrammatical sentences with a *
The man sleeps.
*The man sleep.
Features
But, this leads to duplicating a lot of rules
What if we want to eliminate other ungrammatical
sentences:
 Number agreement between determiner and noun
 Transitive and Intransitive verbs
A man sleeps.
*A men sleep.
The men like the cat.
*The men like.
The men sleep.
*The men sleep the cat.
Features
We can add features on rules to express these constraints
concisely.
s(Number)  np(Number), vp(Number).
np(Number)  det(Number), n(Number).
vp(Number)  v(Number, intranitive).
vp(Number)  v(Number, transitive), np(_).
det(singular)  [a].
det(_)  [the].
n(singular)  [man].
n(plural)  [men].
v(singular, transitive)  [likes].
v(singular, intransitive)  [sleeps].
Improved Consult
consult_term((NT --> Rule)):!,
grammar_rule_body(Rule, Body, Start, End),
make_nonterminal(NT, Start, End, Goal),
assertz((Goal :- Body)).
make_nonterminal(NT, Start, End, Goal):NT =.. List,
append(List, [Start,End], FullList),
Goal =.. FullList.
Improved Consult (cont)
grammar_rule_body((Rule1, Rule2),(Body1, Body2), Start, End):!,
grammar_rule_body(Rule1, Body1, Start, Next),
grammar_rule_body(Rule2, Body2, Next, End).
grammar_rule_body(List, true, Start, End):is_list(List),
!,
append(List, End, Start).
grammar_rule_body(NT, Goal, Start, End):make_nonterminal(NT, Start, End, Goal).
Using Features to return results: Parse trees
In addition to just judging grammatical and ungrammatical
sentences, we can also use the grammar to build up results
to pass back.
One example: building a parse tree.
This doesn’t require any changes to consult
Parse tree as a Prolog term
S
VP
NP
DET
the
N
man
V
NP
likes
DET
the
N
cats
s(np(det(the),n(man)),vp(v(likes),np(det(the),n(cats)))
Grammar1
s(s(NP, VP)) --> np(Number, NP),
vp(Number, VP).
np(Number, np(DET, N)) -->
det(Number, DET), n(Number, N).
vp(Number, vp(V)) --> v(Number,
intransitive, V).
vp(Number, vp(V, NP)) --> v(Number,
transitive, V), np(_, NP).
det(_, det(the)) --> [the].
det(singular, det(a)) --> [a]
n(singular, n(man)) --> [man].
n(plural, n(men)) --> [men].
n(singular, n(woman)) --> [woman].
n(plural, n(women)) --> [women].
n(singular, n(cat)) --> [cat].
n(plural, n(cats)) --> [cats].
n(singular, n(dog)) --> [dog].
n(plural, n(dogs)) --> [dogs].
v(singular, transitive, v(likes)) -->
[likes].
v(plural, transitive, v(like)) --> [like].
v(singular, intransitive, v(sleeps)) -->
[sleeps].
v(plural, intransitive, v(sleep)) -->
[sleep].
Utility to type in and parse sentences
parse_sentences :repeat,
write('Type in a sentence to parse:'),
nl,
read_line(Line),
tokenize(Line, Tokens),
s(Result, Tokens, []),
write('Parse tree: '), nl,
write(Result), nl,
at_end_of_stream(user_input).
read_line([Char|RestLine]):get_code(Char),
Char \== 0'\n,
!,
read_line(RestLine).
read_line([]).
One more extension
Our consult_file/1 is almost all the way to handling full
Definite Clause Grammars. (DCGs)
It’s common practice to separate out the grammar from the
lexicon. This can make the grammar more concise.
Read Ch. 9 of Clocksin and Mellish for more about DCGs
Grammar 2
s(s(NP, VP)) -->
np(Number, NP),
vp(Number, VP).
np(Number, np(DET, N)) -->
det(Number, DET),
n(Number, N).
vp(Number, vp(V)) -->
v(Number, intransitive, V).
vp(Number, vp(V, NP)) -->
v(Number, transitive, V),
np(_, NP).
det(Number, det(Det)) -->
[Det],
{det(Det, Number)}.
n(Number, n(Noun)) -->
[Noun],
{n(Noun,Number)}.
v(Number, Transitivity, v(Verb)) -->
[Verb],
{v(Verb, Number, Transitivity)}.
Lexicon
det(the, _).
det(a, singular).
v(likes, singular, transitive).
v(like, plural, transitive).
v(sleeps, singular, intransitive).
v(sleep, plural, intransitive).
n(man, singular).
n(men, plural).
n(woman, singular).
n(women, plural).
n(cat, singular).
n(cats, plural).
n(dog, singular).
n(dogs, plural).
Consult modified to allow {Goal}
{Goal} allows a regular Prolog Goal to be called, without
treating it as a nonterminal
grammar_rule_body({Body}, call(Body), Start, Start):!.
Example: Syntactic Gaps
Questions and relative clauses are often missing a phrase
that would normally be required:
Who likes cats?
The man who likes cats sleeps.
The man who cats like sleeps.
Syntactic elements like wh-words (who, what, where,
when, how) and relative pronouns (who, that) introduce
gaps.
Example: Syntactic Gaps (cont)
The gapped elements are linked to the source
The man who likes cats sleeps
The man who cats like sleeps
*The man who like cats sleeps.
Handling gaps
We will use difference lists to pass information through the
parser to handle gaps



Gap introduction rules
Gap discharging rules
Gap threading rules
We’ll just worry about the relative clause case…
Gap Introduction Rules
np(GapsIn, GapsOut, Number, np(DET, N, RC)) -->
det(Number, DET),
n(Number, N),
relative_clause(GapsIn, GapsOut, Number, RC).
relative_clause(GapsIn, GapsOut, Number, rc(Rel, S)) -->
rel_pronoun(Rel),
s([np_gap(Number)|GapsIn], GapsOut, S).
Gap Discharging
np([np_gap(Number)|RestGaps], RestGaps, Number, Gap) -->
[].
Gap Threading
Any category that the gap might pass through will have to
allow for gaps:
s(GapsIn, GapsOut, s(NP, VP)) -->
np(GapsIn, GapsNext, Number, NP),
vp(GapsNext, GapsOut, Number, VP).
Example: Quasi-Logical Forms (QLFs)
To really make use of a grammar, we will need more
semantically useful representations.
We can augment our DCGs to produce various kinds of
semantic/logical representations
Quasi-Logical Forms because it doesn’t deal with
quantifier scoping.
This is meant as an example only…
Examples:
The man likes the cats
qterm(the, X, man(X)), qterm(the,Y,cat(Y)), likes(X, Y)
The man that likes the cats sleeps
qterm(the,X,man(X), qterm(the,Y,cat(X)), likes(X,Y), sleeps(X)
The man that the cats like sleeps
qterm(the,X, man(X)), qterm(the,Y, cat(Y)), likes(Y,X), sleeps(X)
QLF bits
qterm(Quantifier, Variable, Predicate)
1-place predicates for nouns:
cat(X)
man(X)
1- and 2- place predicates for verbs
likes(X,Y)
sleeps(X)
Noun Phrases
Two new argument positions for the QLF and the semantic variable:
np(Gaps, Gaps, Number, QLF, Var) -->
det(Number, QLF, Pred, Var),
n(Number, Pred, Var).
det(Number, QLF, Pred, Var) -->
[Det],
{det(Det, Number, QLF, Pred, Var)}.
n(Number, Pred, Var) -->
[Noun],
{n(Noun,Number, Pred, Var)}.
Noun Phrase Lexical Items
det(the, _, qterm(the, X, Pred), Pred, X).
det(a, singular, qterm(a, X, Pred), Pred, X).
n(man, singular, man(X), X).
n(men, plural, man(X), X).
Verb Phrase Rules
The semantic variable from the subject is passed into the verb phrase:
vp(Gaps, Gaps, Number, SubjVar, Pred) -->
[Verb],
{v(Verb, Number, intransitive, SubjVar^Pred)}.
vp(GapsIn, GapsOut, Number, SubjVar, (ObjQLF,Pred)) -->
[Verb],
{v(Verb, Number, transitive, SubjVar^ObjVar^Pred)},
np(GapsIn, GapsOut, _, ObjQLF, ObjVar).
Verb Phrase Lexical Items
Using ^ as an infix operator like lambda
v(sleeps, singular, intransitive, X^sleeps(X)).
v(sleep, plural, intransitive, X^sleeps(X)).
v(likes, singular, transitive, X^Y^likes(X,Y)).
v(like, plural, transitive, X^Y^likes(X,Y)).
Possible Class Projects
Should demonstrate competence in Prolog programming
Expect problems with solutions in 5-20 pages of code
range.
Talk/email with me about your project
What to cover in remaining weeks
We’ve got 4 more “sessions”, I have these plans:
 Another session on DCGs
 A session on iterative deepening
 Some time on logical foundations/theorem proving
Any thoughts on other things you’ld like to cover?
More review?
Help with class projects?
Assignment:
Definite Clause Grammars
I expect it will take 2-4 hours effort
Due on Nov. 19th (no class that day!)