1. Assignment 2 (10 points total)
Answer Set Prolog may be unlike any other programming language you have used until now.
You should try to develop ASP code as logic definitions. This will be frustrating at first, but when
you finally get the hang of it, you will find that you can write understandable code that is
surprisingly compact.
The logic needed for the first two questions was reviewed, and the ASP needed for the
programming question introduced previously. For the ASP programming part, you will be
modifying a file that will be made available to you (it is an extended version of the code we
looked at in class). You may be able to test your code using: https://potassco.org/clingo/run/ ,
but you will probably find it more convenient to install clingo on your own machine. The tutors
and your piazza community should be able to help with this.
It is an important part of learning to be a developer or computer scientist to be able to find the
domain knowledge that you need to complete your tasks. You are not expected to already know
the small amount of domain knowledge in biology and linguistics that this assignment requires,
but you are expected to be able to find it on the internet. If you’re really stuck with the domain
knowledge (like “what’s a past participle?”) you may ask about, and share answers about,
ONLY the linguistic or biology domain knowledge on Piazza. You may not share or ask for help
with the non-programming questions on Piazza, or in any other way. Similarly, you may not
share information about how to complete the knowledge representation or programming parts of
the task on Piazza or in any other way.
.
1.1 Propositional Logic Problem (2 marks)
DNA is made up of the four nucleotide bases Adenine (A), Thymine (T), Cytosine (C) and Guanine
(G). Adenine and Guanine are purines. Cytosine and thymine are pyrimidines. Pyrimidines always
pair with purines.
An example of expressing a constraint in this domain in propositional calculus is:
Constraint: If A is a base, it is either a purine or a pyrimidine, but not both.
Propositional calculus representation: base_A ⇒ purine_A ∨ pyrimidine_A ∧ ¬ ( purine_A ∧
pyrimidine_A)
Express the following constraints in propositional logic [1 mark altogether]
● If T is a base, it is either a purine or a pyrimidine, but not both; similarly for C and G.
[three formulas]
● If A bonds with C (A_bondswith_C), it does not bond with T or G. Similarly for the other
bases [four formulas]
● A does not bond with A; similarly C, T or G do not bond with themselves [four formulas]
● If A bonds with T, it is the case that A is a base and that T is a base, and it is either the
case that A is a purine and T a pyrimidine, or vice versa. Similarly with other pairs of
● bases. [four formulas]
An important feature of formulas in propositional logic is whether they are satisfiable or not.
That is, whether there is an assignment of the truth values {true, false} to the propositions
above (e.g., base_a, purine_T or A_bondswith_C) such that the entire formula evaluates to
true. Choose such an assignment to the propositions in the example and your 15
formulas and show that they each evaluate to true using a truth table [one mark]. It
might be helpful to use the facts of biology as a guide to choosing which propositions are true
and which are false in your choice of a satisfying assignment (also known as a model),
although a satisfying assignment that does not agree with biology would be acceptable if you
can find one; basic information about the biology of DNA and RNA is widely available on the
Internet. For example, to agree with biology, your predicates for “A bonds with T” and for “G
bonds to C” should be true. Satisfiability is also fundamental to the way ASP works, so doing
this problem may help with your programming.
1.2. Predicate Logic Problem (2 marks)
Adding the following constraint to those in the previous question (1.1) “If f A bonds with T, then T
bonds with A, and similarly for all other pairs”, write a general version of the bonds-with relation,
bondsWith(Base1,Base2), in predicate calculus only using standard quantifiers, connectives, the
unary not (¬), equality (=) and the predicates:
● base(X)
● pyrimidine(X); purine(X)
And the constants:
● adenine, thymine, cytosine and guanine
1.3. ASP (Answer Set Prolog) Problem (6 Marks)
In this part, you will combine what you have learned about logic, ASP programming, and
knowledge representation to extend an ASP program to add to its parsing abilities, and then to
connect it to frame semantics. The base program, COMPSCI367_2021S2_Assignment2.lp will
be made available at the same time as this Assignment. You should keep your additions in a
separate file, which we will concatenate with our version of the base program and some test
cases during grading.
1.3.1 Extend irregular plurals to cover Māori [1 mark]
The base program handles irregular plurals in English. Māori also has irregular plurals, but they
do not act in the same way as in English.
The plural of “tamaiti” (child) is “tamariki” (children), so “te tamaiti” but “ngā tamariki”.
The plural of “tangata” is “tāngata”, of “wahine”, “wāhine” and of “matua”, “mātua”.
You may also have to tell your program that some of these are nouns if it doesn’t already know
that. You should test your program to make sure that it can construct the plurals of these
words, and others, correctly after modification. And you should test that it still works for English
too.
1.3.2 Add Adjectives to the parser [2 marks]
Both English and Māori have adjectives, but the base code doesn’t handle them. Adjectives
modify nouns. Using the unary predicate, adjective/1 you should add the Māori adjectives “nui”
(big), “reka” (sweet) and “pai” (good) to your code. You should also add the English adjectives
“big” (nui), “sweet” (reke) and “good” (pai). You will need to extend the noun phrase definitions
to allow adjectives to be used, and verify that you can parse entire sentences including
adjectives, in both English and Māori.
Example noun phrases with Adjectives: “the good children”, “the big bird”, “he whare nui”, “nga
āporo reka”, “the sweet banana”, “a big canoe”. Note that you may also need to add a noun or
two if you want to test with these sentences.
1.3.3 Recognise and fill in FrameNet-Style Frame [3 marks]
Suppose we have a frame, sitting_somewhere, which has the role describing frame elements
sitter and location, and is complete if both of those roles are filled. In the sentence, “the sheep
is sitting in the canoe”, the sitter is “the sheep” and the location is “in the canoe”. In “the cat is
sitting on the mat in the box” the sitter would be “the cat” and the location is “on the mat in the
box”.
You should create a predicate frame_match/4 with four arguments, a frame, a sentence it
matches, a role name, and a phrase (something defined using the function the_phrase() in the
base code that fills that role. A single frame will have frame_match for each role in the frame.
For example, the sentence above involving the sheep should produce both
frame_match(sitting_somewhere, sentence(6), sitter, the_phrase(np,en(“the”),
the_phrase(np,en(“sheep”)))) and another frame_match for the role location.
You may write frame specific code for this, but your frame_match code may be tested with any
sentence that matches the frame, and some of those sentences may include adjectives. You
may share test sentences with one another on Piazza as you test your code.
2. Submission Information
1. What to submit
You need to submit a zip archive, yourUpi.zip (e.g., mbar098.zip) containing 2 files:
LogicProblems.pdf, and parsing.lp. The first file has the answers for questions 1.1 and 1.2. The
second one is the linguistic analysis ASP code. Your parsing.lp should include only the new code
you have written, and should work when concatenated onto the end of the base code that you
have been given.
2. When and where to submit
You need to submit this to Canvas by 6 Oct 2021 23:59 NZ Time. You will be informed when
Canvas is ready to receive submissions.
3. Marking Rubric
1. Written answer marking
The marking for the propositional and predicate logic modelling questions is
straightforward.
2. Protein sequence Prolog question
We will grade your ASP prorams by adding sentences in the same format as the example to them,
and seeing whether they are parsed correctly by your program, or whether they recognise that the
frame applies, and correctly fill out the frame, given the sentences we input. Your ASP program
for this question MUST produce whole sentence parses and recognise and fill frames on its own.
You will get a zero for this question, if an answer is hard coded into the ASP code. For some
cases, this will not be possible, anyway, since we will use new sentences.
3. FINAL Reminder.
You may be tempted to just use someone else’s code, DON’T!!!! The assignment you submit
MUST BE your own work!! You can talk about it the domain knowledge and about how ASP works
with others and we recommend that you do, but if we detect that you copied any of the assignment
from another source, you will get a ZERO for the ENTIRE ASSIGNMENT!! This should not come
as news for you; it just recapitulates basic standards of academic integrity, with which you will be
thoroughly familiar by now. Please take a moment to remind yourself now that you have agree to
follow the standards of integrity expect at Waipapa Taumata Rau, the University of Auckland.
Appendix COMPSCI367_2021S2_Assignment2.lp
%prepositions
preposition(en(“in”); en(“on”); en(“with”)).
%verb
infinitive(en(“be”);en(“run”);en(“eat”); en(“go”); en(“cook”);).
irregular_verb(en(“be”); en(“go”)).
regular_third_person_sing(en(“eat”), en(“eats”)).
regular_third_person_sing(en(“cook”), en(“cooks”)).
participle(en(“cook”),present_tense,en(“cooking”)).
participle(en(“cook”),past_tense,en(“cooked”)).
participle(en(“eat”),present_tense,en(“eating”)).
participle(en(“eat”),past_tense,en(“eaten”)).
participle(en(“sit”),present_tense,en(“sitting”)).
participle(en(“sit”),past_tense,en(“sat”)).
infinitive(en(W)):- participle(en(W),_,_).
verb_form(1,en(“be”),first_person,singular_number,present_tense,simple_aspect,indicitive_mood,en(“am”)).
verb_form(1,en(“be”),second_person,singular_number,present_tense,simple_aspect,indicitive_mood,en(“are”)).
verb_form(1,en(“be”),third_person,singular_number,present_tense,simple_aspect,indicitive_mood,en(“is”)).
verb_form(1,en(“be”),first_person,plural_number,present_tense,simple_aspect,indicitive_mood,en(“are”)).
verb_form(1,en(“be”),second_person,plural_number,present_tense,simple_aspect,indicitive_mood,en(“are”)).
verb_form(1,en(“be”),third_person,plural_number,present_tense,simple_aspect,indicitive_mood,en(“are”)).
verb_form(1,en(“be”),first_person,singular_number,past_tense,simple_aspect,indicitive_mood,en(“was”)).
verb_form(1,en(“be”),second_person,singular_number,past_tense,simple_aspect,indicitive_mood,en(“were”)).
verb_form(1,en(“be”),third_person,singular_number,past_tense,simple_aspect,indicitive_mood,en(“was”)).
verb_form(1,en(“be”),first_person,plural_number,past_tense,simple_aspect,indicitive_mood,en(“were”)).
verb_form(1,en(“be”),second_person,plural_number,past_tense,simple_aspect,indicitive_mood,en(“were”)).
verb_form(1,en(“be”),third_person,plural_number,past_tense,simple_aspect,indicitive_mood,en(“were “)).
%% look for more compact syntax for this
verb_form(1,en(V),first_person,singular_number,present_tense,simple_aspect,indicitive_mood,en(V)) :-
infinitive(en(V)), not irregular_verb(en(V)) .
verb_form(1,en(V),second_person,singular_number,present_tense,simple_aspect,indicitive_mood,en(V)) :-
infinitive(en(V)), not irregular_verb(en(V)) .
verb_form(1,en(V),third_person,singular_number,present_tense,simple_aspect,indicitive_mood,en(TS)) :-
regular_third_person_sing(en(V),en(TS)), not irregular_verb(en(V)) .
verb_form(1,en(V),first_person,plural_number,present_tense,simple_aspect,indicitive_mood,en(V)) :-
infinitive(en(V)), not irregular_verb(en(V)).
verb_form(1,en(V),second_person,plural_number,present_tense,simple_aspect,indicitive_mood,en(V)) :-
infinitive(en(V)), not irregular_verb(en(V)).
verb_form(1,en(V),third_person,plural_number,present_tense,simple_aspect,indicitive_mood,en(V)) :-
infinitive(en(V)), not irregular_verb(en(V)) .
%multi word verb forms (in this case, simple progressive (not perfective)) formed with form of be, and present
participle
verb_form(2,en(I),PER,NUM,TENSE,progressive_aspect,indicitive_mood,en(B),en(PP)) :-
infinitive(en(I)), not irregular_verb(en(I)),
verb_form(1,en(“be”),PER,NUM,TENSE,simple_aspect,indicitive_mood,en(B)),
participle(en(I),present_tense,en(PP)).
%todo clean up active and passive voice in En and make consistent in Mi
tense_particle(mi(“kua”); mi(“i”); mi(“e”); mi(“ka”); mi(“me”)).
verb_active(mi(“tunu”); mi(“kite”); mi(“tuhituhi”); mi(“noho”); mi(“aroha”)).
verb_passive(mi(“tunua”); mi(“kitea”); mi(“tuhituhia”); mi(“tuhia”); mi(“nohoia”); mi(“arohaina”)).
verb(V):- verb_active(V).
verb(V):- verb_passive(V).
%single and multiple term verb forms are verbs
verb(V) :- verb_form(1,I,_,_,_,_,_,V),infinitive(I).
verb2(V,V2) :- verb_form(2,I,_,_,_,_,_,V,V2),infinitive(I).
%Articles
%Māori articles
indefinite_article( mi(“he”)).
definite_article(mi(“ngā”);mi(“te”)).
singular_number(mi(“te”);mi(“he”)).
plural_number(mi(“he”);mi(“ngā”)).
%English articles and determiners
indefinite_article( en(“a”); en(“an”)).
definite_article(en(“the”)).
singular_number(en(“a”);en(“an”);en(“the”)).
plural_number(en(“the”)).
determiner(en(“some”); en(“any”)).
%Both languages
article(W):- indefinite_article(W).
article(W):- definite_article(W).
determiner(W) :- article(W).
%This is very important – if you don’t add a word class here, the program won’t work.
word(W) :- determiner(W).
word(W) :- noun(W).
word(W) :- preposition(W).
word(W) :- verb(W).
word(W1) :- verb2(W1,W2).
word(W2) :- verb2(W1,W2).
word(W) :- pronoun(W).
word(W) :- tense_particle(W).
string(X) :- word(mi(X)).
string(X) :- word(en(X)).
word_position(S,word_number(P),mi(WS)) :- string_position(S,string_number(P),WS), word(mi(WS)).
word_position(S,word_number(P),en(WS)) :- string_position(S,string_number(P),WS), word(en(WS)).
%English & Māori nouns are NPs
phrase_span(S,P1,P1,np,the_phrase(np,N)) :- word_position(S,P1,N),noun(N).
%English & Māori pronouns are NPs
phrase_span(S,P1,P1,np,the_phrase(np,PN)) :- word_position(S,P1,PN),pronoun(PN).
%English & Māori determiners followed by nouns are NPs if they agree in number
phrase_span(S,word_number(P1),word_number(P3),np,the_phrase(np,D,N)) :-
word_position(S,word_number(P1),D),
determiner(D),
phrase_span(S,word_number(P2),word_number(P3),np,N),
P2=P1+1.
%similar for PP
phrase_span(S,word_number(P1),word_number(P3),prepp,the_phrase(prepp,P,N)) :-
word_position(S,word_number(P1),P),preposition(P),
phrase_span(S,word_number(P2),word_number(P3),np,N),
P2=P1+1.
% NP PP is NP
phrase_span(S,word_number(P1),word_number(P4),np,the_phrase(np,NP,PP)) :-
phrase_span(S,word_number(P1),word_number(P2),np,NP),
phrase_span(S,word_number(P3),word_number(P4),prepp,PP),
P3=P2+1.
% V NP is VP in English
phrase_span(S,word_number(P1),word_number(P3),vp,the_phrase(vp,V,NP)) :-
word_position(S,word_number(P1),V),verb(V),
phrase_span(S,word_number(P2),word_number(P3),np,NP),
P2=P1+1.
% V can be VP in English (as in “I cook” or “I am cooking”
phrase_span(S,word_number(P1),word_number(P1),vp,the_phrase(vp,V)) :-
word_position(S,word_number(P1),V),verb(V).
% The “I am cooking” case
phrase_span(S,word_number(P1),word_number(P2),vp,the_phrase(vp,V,V2)) :-
word_position(S,word_number(P1),V),
word_position(S,word_number(P2),V2),
verb2(V,V2).
%Tense_particle V is VP in Māori
phrase_span(S,word_number(P1),word_number(P2),vp,the_phrase(vp,TP,V)) :-
word_position(S,word_number(P1),TP), tense_particle(TP),
word_position(S,word_number(P2),V),verb(V),
P2=P1+1.
% VP PP is VP in En
phrase_span(S,word_number(P1),word_number(P4),vp,the_phrase(vp,VP,PP)) :-
phrase_span(S,word_number(P1),word_number(P2),vp,VP),
phrase_span(S,word_number(P3),word_number(P4),prepp,PP),
P3=P2+1.
% NP VP is S in En
clause_span(S,word_number(P1),word_number(P4),sent,the_clause(sent,NP,VP)) :-
phrase_span(S,word_number(P1),word_number(P2),np,NP),
phrase_span(S,word_number(P3),word_number(P4),vp,VP),
P3=P2+1.
% VP NP is S in Mi
clause_span(S,word_number(P1),word_number(P4),sent,the_clause(sent,VP,NP)) :-
phrase_span(S,word_number(P1),word_number(P2),vp,VP),
phrase_span(S,word_number(P3),word_number(P4),np,NP),
P3=P2+1.
%These are essentially diagnostic prints for non-trivial phrases and clauses
l_noun_phrase(S,P, P1,P2):- phrase_span(S,P1,P2,np,P), P1<>P2.
l_prep_phrase(S,P, P1,P2):- phrase_span(S,P1,P2,prepp,P), P1<>P2.
l_verb_phrase(S,P, P1,P2):- phrase_span(S,P1,P2,vp,P), P1<>P2.
%A sentence is a sentence clause that has a length > 1
sentence(S,C, P1,P2):- clause_span(S,P1,P2,sent,C), P1<>P2, active(S).
%it’s a full parse if it’s a sentence and it starts at the first word of the sentence and the sentence has no
words past the span it covers
full_parse(S,C) :- sentence(S,C,P1,P2), P1=word_number(1), not word_position(S,word_number(NXT),_),
P2=word_number(THIS), NXT=THIS+1.
%Data
%English Sentence
string_position(sentence(1),string_number(1),”the”).
string_position(sentence(1),string_number(2),”girl”).
string_position(sentence(1),string_number(3),”is”).
string_position(sentence(1),string_number(4),”in”).
string_position(sentence(1),string_number(5),”the”).
string_position(sentence(1),string_number(6),”canoe”).
%active(sentence(1)).
string_position(sentence(2),string_number(1),”the”).
string_position(sentence(2),string_number(2),”girl”).
string_position(sentence(2),string_number(3),”in”).
string_position(sentence(2),string_number(4),”the”).
string_position(sentence(2),string_number(5),”canoe”).
string_position(sentence(2),string_number(6),”is”).
string_position(sentence(2),string_number(7),”sitting”).
%active(sentence(2)).
string_position(sentence(4), string_number(1),”I”).
string_position(sentence(4), string_number(2),”cook”).
%active(sentence(4)).
string_position(sentence(5), string_number(1),”I”).
string_position(sentence(5), string_number(2),”was”).
string_position(sentence(5), string_number(3),”cooking”).
%active(sentence(5)).
string_position(sentence(6),string_number(1),”the”).
string_position(sentence(6),string_number(2),”sheep”).
string_position(sentence(6),string_number(3),”is”).
string_position(sentence(6),string_number(4),”sitting”).
string_position(sentence(6),string_number(5),”in”).
string_position(sentence(6),string_number(6),”the”).
string_position(sentence(6),string_number(7),”canoe”).
%active(sentence(6)).
string_position(sentence(7),string_number(1),”I”).
string_position(sentence(7),string_number(2),”sit”).
string_position(sentence(7),string_number(3),”in”).
string_position(sentence(7),string_number(4),”the”).
string_position(sentence(7),string_number(5),”canoe”).
%active(sentence(7)).
string_position(sentence(8),string_number(1),”I”).
string_position(sentence(8),string_number(2),”sit”).
%active(sentence(8)).
string_position(sentence(9),string_number(1),”the”).
string_position(sentence(9),string_number(2),”sheep”).
string_position(sentence(9),string_number(3),”is”).
string_position(sentence(9),string_number(4),”sitting”).
string_position(sentence(9),string_number(5),”on”).
string_position(sentence(9),string_number(6),”the”).
string_position(sentence(9),string_number(7),”mat”).
string_position(sentence(9),string_number(8),”in”).
string_position(sentence(9),string_number(9),”the”).
string_position(sentence(9),string_number(10),”canoe”).
active(sentence(9)).
%Māori Sentence
string_position(sentence(3),string_number(1),”ka”).
string_position(sentence(3),string_number(2),”tunu”).
string_position(sentence(3),string_number(3),”ahau”).
%active(sentence(3)).
%diag(D,S,P1,P2) :- verb(D), word_position(S,word_number(P1),D), P2=P1+1.
%#hide.
#show full_parse/2.
%#show mydiag/1. %word_position/3.
%#show participle/3.
%#show verb2/2.
%#show sentence/4.
%#show verb_form/7.
%—-