banner

Prolog Weeks 3-4: Natural Language to Predicate Calculus

This project was designed and written by 173 alumnus and 2010 TA Karl Stratos (a.k.a. Jan Sung Lee), with some suggestions along the way from the other 2010 TAs and me. Thanks to all the TAs!. Re-edited Oct 16 2013. -- CB

Preparation and Grading

Read Chapter 9 (esp. 9.2 -- 9.5) of Clocksin Mellish 5th Edition (it's scanned into the e-reserves, listed as number 2, "Clocksin. Programming in Prolog").

2014: Code+Readme 60%, Writeup 40%. 2015: Code+Readme 50%, Writeup 50%.

We should be working toward the time when code is not the issue, but results are. That means the methods and results are well-enough documented and individual enough not to need checking over for correctness or duplication. In other words, the results (transcripts, test cases, outputs, individual bells and whistles added by author) should speak for themselves. However, the TAs may want to run your code.

In fact, Hassler Thurston in 2014 created these test cases and used them for grading. They are a first edition and heavy on relative clauses, so suggestions for improvement are welcome.

To Help Us Run Your Code

Your parsing predicate should be called parse(). By default it accepts a sentence in list form, either produced by you or by using the translation code referred to below. It produces the correct parse tree for a grammatical sentence. You might want to have a parameter that allows you to type a sentence to parse() interactively.

Similar thing for the translator predicate, which should be called translate().

Use these standard names for nonterminals in a parse tree (other terms may be used below, but these are for your program:
sentence, noun_phrase, verb_phrase, det, adj, noun, verb, be_verb, rel_cl, rel_pronoun.
Thus your output could contain ... noun_phrase(det(the),noun(boy)) .

Also in translations, standardize on
for all and there exists for quantifiers.

Motivation

Language processing is important in all areas of computer science - AI, systems, and theory. In particular, natural language processing (NLP) is one of the biggest research fields in AI. Here, you will employ the same parsing principles you used on arithmetic expressions to parse natural English sentences, thereby gaining a head start in your study of AI. You'll also confront a small and benign subset of the general problem of translating English into FOPC, which is a research issue (pursued hotly here at UR).

Parsing in Prolog is fun and not as messy as in C. First, you don't need a scanner (as long as you use the "read-in.txt" listification code found from a link in 'Walk Through and tutorial') section below.

Second, you don't need to get bogged down with compilation issues (like makefile, etc. - I had a nightmare dealing with them).

Third, you don't need to manipulate the control flow yourself (a point which is at the heart of logic programming), as opposed to in C where you had to tell the parser "if you find X, go here, if you find Y, go there,..." (For theoreticians: in other words, Prolog gives you an illusion of nondeterministic decisions---though it's clearly fake, since what Prolog uses to find an answer is a simple depth-first search, done behind the curtain.)

General Description

This project is analogous to the arithmetic parser you built in C. You will
  1. Parse a sentence of English,
  2. Build a parse tree while parsing, and
  3. Use the parse tree to translate the sentence into FOPC.

Parsing Basics
In the arithmetic parser, you used the parse tree of an arthmetic expression to evaluate it. In your natural language parser, you will use the parse tree of a sentence to 'evaluate' it to a logical form. That will involve issues like rules of logic and the scope of quantifiers and minimizing issues of word-sense or quanification ambiguity.

Word-sense: "I ran to the bank." (and jumped in? or withdrew $100?). Quantification: "A bird flies." could be a statement about all birds or could assert the existence of one. At first (at least), you should try to keep ambiguity to a minimum in your test set of sentences for translation.

Our sentences will be like:
"some boy likes Rochester", which with a simple grammar gives the parse tree

sentence(noun_phrase(determiner(some), noun(boy)),
         verb_phrase(verb(likes), noun_phrase(proper_noun(Rochester))).
The first-order logical form of this parse tree could be rendered in Prolog any number of ways, but I'll use
exists(x, boy(x) & like(x,Rochester)),
which I hope is clear: the sentence is an existentially quantified WFF, the AND of two atomic sentences, with x the variable.

The translation of a natural sentence into a logical formula is useful. You will write a program that translates your parse tree to its logical form.

We'll translate a tame, simple, specially-engineered subset of English to make the project feasible. The sentences we translate into logic will indeed sound like someone reading logic sentences aloud: for instance they will indicate quantification explicitly with words like 'all' and 'some'. Of course "A bird flies" is a pretty simple sentence: your parser will almost certainly handle a bigger range of sentences than we can accurately translate to logic, so your translation test-set will be a subset of the language accepted by your grammar.

What to do: Minimum Requirements

You will first write a parser that parses the input sentence and builds a parse tree accordingly. Keep in mind the distinction between the lexicon and the grammar. You need to build the lexicon for the words you will be parsing, and you need to write a grammar for the grammatical rules you will be using. Your lexicon should contain (at least)
Noun = {apple, boy, girl, government, watermelon}
Det = {a, the}
Verb = {conscript, like, run}
BeVerb = {is, are}
Adj = {evil}
Rel = {that, whom, who, which}.
Sample sentences of about the right complexity are:
List A
i. The boy runs.
ii. Girls like an apple.
iii. Any government that conscripts people is evil.
iv. The boy whom the girl likes likes a watermelon.
Notice that each represents an important grammatical structure of a sentence: (i) uses an intransitive verb (takes no object) run, (ii) uses a transitive verb (takes an object) like, (iii) contains a relative clause of the form VP (verb phrase) conscripts people and also a linking verb be, and (iv) contains a different instance of relative clause, the girl likes. We might like to enforce grammatical or lexical rules to disallow "The government conscripts" (force 'conscript' to be transitive, needing an object) or "The girl runs the boy" (only keeping the transitive 'run' as in 'runs across the street', not allowing 'runs the machine'). The ambiguity (polymorphism, in programming-language geek speak) of english is staggering and a rich source of problems as well as humor. You're more than welcome to pick one of these thornier issues, but I'd recommend to KISS when you're starting.

You first need to write a context-free grammar for the sentences you want to allow. Here is a minimal grammar you can use, but please feel free to expand it (in small stages!) if you want. Taking a grammar from the net is fine, just cite where it came from.

Here the nonterminals that terminate a search, like Noun and Verb, correspond to words from the lexicon.

S --> NP VP
NP --> Det Noun
   --> Det Noun RELCL
   --> Noun
VP --> Verb
   --> Verb NP
   --> BeVerb Adj
RELCL --> Rel VP
      --> Rel NP Verb
Let's agree that you should take care of number agreement, as covered in the parsing chapter of Clocksin and Mellish. This expands your grammar beyond a CFG, so congratulations! So your parser, while accepting (i),(ii), (iii), and (iv), should reject all the following sentences:
*The boy run.
*Girls likes an apple.
*A government that conscripts people are evil.
*The boy who the girl likes likes a watermelon.
*The boy which the girl likes likes a watermelon.
Recall that handling of agreement can be done easily in Prolog by keeping an extra parameter, as in the example below (for the first rule in the grammar):
sentence(X,sentence(NP, VP)) -->
	noun_phrase(X,NP), verb_phrase(X,VP), sentence_finisher.
Here, you are restricting noun_phrase and verb_phrase so that they share the same value on X, which can be your number agreement (e.g., {singular, plural}). (The last piece, sentence_finisher, just takes care of periods, exclamation points, and question marks in my code.) For detailed explanations, consult the textbook, or read the Walkthrough and Tutorial below.

You will next write a translator that translates the parse trees of your sentences (e.g. List B) into the corresponding FOL forms (e.g. List C).

List B
i. All boys run.
ii. All boys like all watermelons that contain some divine flavor.
iii. Some boy eats some apple.
iv. Some governments conscript some pacifist people.
v. All governments that conscript some pacifist people are evil.

List C
i. all(x1, boy(x1)=>run(x1))
ii. all(x6, boy(x6)=>like(x6, all(x7, watermelon(x7)&contain(x7, exists(x8, flavor(x8)&divine(x8))))))
iii. exists(x9, boy(x9), eat(x9, exists(x10, apple(x10))))
iv. exists(x11, government(x11), conscript(x11, exists(x12, people(x12)&pacifist(x12))))
v. all(x13, government(x13)&conscript(x13, exists(x14, people(x14)&pacifist(x14)))=>evil(x13))
For instance, I first obtained the parse tree T = sentence(noun_phrase(determiner(some), noun(boy)), verb_phrase(verb(eat), noun_phrase(determiner(some), noun(apple)))) from List B (iii) using my parser, and then fed this tree T to my translator to obtain List C (iii).

These are the actual results I obtained from my code.

Note that I avoided ambiguities of quantification mentioned above by using 'all' or 'some' in any place that requires quantification.

You can choose your own level of abstraction for your logical formulation. For instance, take time (tenses). Easiest are "timeless" statements (all present tense (or past, I guess)), but it's not that hard to come up with predicates that can be used to place events in simple temporal relations.

The following is a reasonable formulation of "The boy was hit by a girl" Because the English uses past tense, it invites us to have the idea of "now" and "before now", so we add a "when" argument to verbs like 'hit'.

exists(e, BEFORE(e,now),
 exists(x, boy(x),
  exists(y, girl(y),
   [[hit(y,x)]*e]))).

Warning: be careful with (A) the scope of a quantifier and (B) the logical connectives used with the universal and existential quantifiers.

Scope: I mean the variable used for a quantifier has a set range of domain where it can be used. You cannot assert, say,

exists(x9, boy(x9)) & eat(x9, exists(x10, apple(x10)))
because the domain of x9 is within exists(x9, boy(x9)), so it doesn't make sense to use x9 in the literal eat(x9, exists(x10, apple(x10))), which is outside the scope.

Connectives: I just decreed that for me, '=>' (implication) is only used with 'forall', and '&' (and) is only used with 'exists'. That avoids some "common translation mistakes" described in Logic texts (and our lectures). The universal quantifier only makes sense with the logical connective '=>'. You don't want to say

all(x1, boy(x1) & run(x1))
for the sentence "All boys run", because that's not what the sentence says. It says if any thing is a boy, then that thing runs, whereas the FOL formula says any thing is a boy and that thing runs (what a strong suggestion!). So the correct formulation is all(x1, boy(x1) => run(x1))

By the same token, the existential quantifier goes with the logical connective '&'. You don't want to say

exists(x1, boy(x1) => run(x1)
for the sentence "Some boy runs". The sentence means that there is a thing that is boy and that this thing runs, but the FOL formula is suggesting there is a something, and if that something is boy, it must run (weaker than the sentence's proposal). So the correct formulation is exists(x1, boy(x1) & run(x1).

A Detailed Walk-through and Tutorial

I prepared a little tutorial, with generally useful topics from the text and specific details of how I approached the project.

Exploiting This Work

This is a non-trivial project -- why not get more juice out of it. If you wanted use your project in another class, you might think of ambitious extensions like these.