%% =========================
%%  CMPU-181, Spring 2013
%%  More Grammars in Prolog
%%  April 22, 2013
%% =========================
%%   Note:  To use this file:
%%          -- Download it to your CS account.
%%               For the purposes of this example, I'll assume you
%%               have put it into a directory called "grammars".
%%          -- Open up a terminal window and "CD" into the "grammars"
%%               directory:   cd grammars
%%          -- Start up the SWIPL program by typing:  swipl
%%          -- At the SWIPL prompt, type:  ['apr22.pl'].
%%               (That loads the contents of this file into SWIPL.)
%%          -- Enter queries at the SWIPL prompt, for example:
%%               nSent([a,a,a,b,b,c]).
%%          -- When SWIPL gives an answer, it then waits for further
%%               instructions.  Type either a semi-colon (to ask for
%%               more answers to the same query) or a period (to return
%%               to the SWIPL prompt for the next query).
%%          -- To exit SWIPL, type:  halt.

%% -------------------------------------------------------
%%  Previously seen grammar for the language a*b*c*.
%% -------------------------------------------------------
%%  sent(Xs) is a "wrapper predicate" that holds if Xs is a sentence
%%  contained in the language a*b*c* (i.e., if Xs is a list containing
%%  zero or more a_s, followed by zero or more b_s, followed by zero 
%%  or more c_s).

sent(Xs) :- s(Xs/[]).

%%  The following rules are written using the somewhat-ugly
%%  "difference list" notation.

s(As/Xs) :- a(As/Bs), b(Bs/Cs), c(Cs/Xs).  

a(Xs/Xs).  
a([a|Xs]/Ys) :- a(Xs/Ys).

b(Xs/Xs).
b([b|Xs]/Ys) :- b(Xs/Ys).

c(Xs/Xs).
c([c|Xs]/Ys) :- c(Xs/Ys).

%%   Try the following queries at the Prolog prompt:
%%         sent([a,a,b,c]).
%%         sent([a,X,c]).
%%         sent([X,X,X,X]).
%%         sent([X,Y,Z]).

%% ================================================
%%  An easier way to get the same grammar
%% ================================================

%%  nSent is a "wrapper predicate" that hides the use of "difference lists".

nSent(Listy) :- nS(Listy, []).

%%  The following rules use Prolog's DCG syntax.
%%  (DCG stands for "Definite Clause Grammar".)

%%  Each of the predicates used below have two "hidden inputs"
%%  that hide the use of "difference lists".

%%  A sentence can be built out of zero or more As, followed by
%%  zero or more Bs, followed by zero or more Cs.

nS --> nA, nB, nC.

%%  Zero or more A_s can be gotten:
%%    ** by having an empty list (i.e., zero A_s)
%%    ** or by having one A, followed by zero or more additional A_s.

nA --> [].
nA --> [a], nA.

%%  Similar rules for zero or more B_s and zero or more C_s.

nB --> [].
nB --> [b], nB.

nC --> [].
nC --> [c], nC.

%%  Try the following queries at the Prolog prompt:
%%        nSent(Listy).
%%        nSent([X,Y,Z]).

%%  To see that there "really are" hidden inputs, try these queries:
%%   nA([a,a,a,a],[]).    <-- TRUE because [a,a,a,a] - [] has all a_s 
%%   nA([a,a,x,x],[x,x]). <-- TRUE because [a,a,x,x] - [x,x] has all a_s
%%   nB([b,b,x,y],[x,y]). <-- TRUE because [b,b,x,y] - [x,y] has all b_s
%%   nB([b,b,x,y],[]).    <-- FALSE because [b,b,x,y] - [] is not all b_s
%%     etc.

%% =============================
%%   DCG for English grammar
%% =============================

%%  Wrapper predicate (to facilitate making queries)
%%    rSenty has the following EXPLICIT inputs:
%%       Tense -- the tense of the sentence (e.g., present, past, future)
%%       Num   -- the number of the subject and verb (which must match)
%%       Tree  -- a parse tree for the sentence
%%       Listy -- the list of words in the sentence
%%  The following is a standard prolog rule (using :- ); thus, it
%%  shows all arguments (no hidden inputs).  Thus, rS shows both
%%  Listy and [].

rSenty(Tense,Num,Tree,Listy) :- rS(Tense,Num,Tree,Listy,[]).

%%  The following use the special DCG syntax.
%%  Thus, each predicate does NOT show its TWO HIDDEN INPUTS.
%%  Instead, each predicate only shows its EXPLICIT INPUTS.
%%  The HIDDEN INPUTS take care of splitting the desired list of
%%  words into sub-lists that will be given to the predicates on
%%  the righthand side of the double arrow.
%%  Thus, the first rule holds if LISTY is a list of words that
%%  can be split into two sub-lists, LISTY-ONE and LISTY-TWO, such
%%  that LISTY-ONE satisfies the rNP predicate, and LISTY-TWO satisfies
%%  the rVP predicate.  We don't have to worry about how that splitting
%%  of lists into sub-lists is done!  Thanks, DCG!

%%  rS -- One way a list of words can form a SENTENCE is if
%%        it can be split into a noun phrase (NP) and a verb phrase (VP)
%%            Note that the Number of the NP and VP must be the same!
%%            Note that the parse tree for the sentence is constructed
%%              out of the parse trees for the NP and VP!

rS(Tense, Num, s(NPTree,VPTree)) --> rNP(Num,NPTree), rVP(Tense,Num,VPTree).

%%  rNP -- One way a list of words can be a noun phrase (NP) is if
%%         it is a proper noun (PN).  Notice that the Number of the
%%         NP and PN must match.

rNP(Num,np(PNTree)) --> rPN(Num,PNTree).

%%  Sample proper nouns:
%%    LUKE is a SINGULAR proper noun.
%%    AMERICANS is a PLURAL proper noun.

rPN(sing,pn(luke)) --> [luke].
rPN(plural,pn(americans)) --> [americans].

%%  rNP -- Another way a list of words can form a noun phrase (NP) is
%%         if it can be split into a Determiner (Det) followed by a
%%         noun (Noun).  Notice that the Number of the Det, Noun and NP
%%         must be the same.  Notice that the parse tree for the NP
%%         is constructed out of the parse trees for the Det and Noun.

rNP(Num,np(DetTree,NounTree)) --> rDet(Num,DetTree), rNoun(Num,NounTree).

%%  Sample determiners (singular and plural).

rDet(sing,d(a)) --> [a].
rDet(sing,d(the)) --> [the].
rDet(plural,d(the)) --> [the].

%%  Sample nouns:  singular and plural.

rNoun(sing,n(dog)) --> [dog].
rNoun(plural,n(dogs)) --> [dogs].
rNoun(sing,n(cat)) --> [cat].
rNoun(plural,n(cats)) --> [cats].

%%  rVP -- One way a list of words can be a verb phrase (VP) is if
%%          it consists of an intransitive verb (IV).  Notice that
%%          both the Tense and Number of the VP and IV must match.

rVP(Tense,Num,vp(IVTree)) --> rIV(Tense,Num,IVTree).

%%  Sample intransitive verbs (i.e., verbs that need NOT take a
%%   direct object).  (Actually, RUN *can* take a direct object in
%%   some contexts; e.g., "I run the machine."  But it doesn't have to.)

rIV(past,sing,iv(ran)) --> [ran].
rIV(past,plural,iv(ran)) --> [ran].
rIV(present,sing,iv(runs)) --> [runs].
rIV(present,plural,iv(runs)) --> [runs].

%%  rVP --  Another way a list of words can form a verb phrase is
%%          if it can be split into an intransitive verb (IV) followed
%%          by a prepositional phrase (e.g., "to the store") (PP).
%%          Notice that the parse tree for the VP is built out of the
%%          parse trees for the IV and PP.

rVP(Tense,Num,vp(IVTree,PPTree)) --> rIV(Tense,Num,IVTree), rPP(PPTree).

%%  rPP -- A list of words can make a prepositional phrase if it
%%         consists of a preposition (Prep) followed by a noun phrase (NP).

rPP(pp(PrepTree,NPTree)) --> rPrep(PrepTree), rNP(_,NPTree).

%%  Sample prepositions:

rPrep(p(to)) --> [to].
rPrep(p(from)) --> [from].

%%  rVP -- Another way a list of words can form a verb phrase (VP)
%%         is if it consists of a transitive verb (TV) followed by
%%         a noun phrase (NP).  (The noun phrase is the "direct object"
%%         of the transitive verb.  For example:  "threw the ball".)

rVP(Tense,Num,vp(TVTree,NPTree)) --> rTV(Tense,Num,TVTree), rNP(_,NPTree).

%%  Sample transitive verbs.
%%    Notice that each verb has a tense and a number:

rTV(present,sing,tv(chases)) --> [chases].
rTV(present,plural,tv(chase)) --> [chase].
rTV(past,sing,tv(chased)) --> [chased].
rTV(past,plural,tv(chased)) --> [chased].

%%  rS -- Another way a list of words can form a sentence is if
%%        it consists of a noun phrase with an adjective (NPAdj)
%%        followed by a verb phrase (VP).
%%        NOTE:  This is probably not the best way to arrange things.

rS(Tense, Num, s(NPTree,VPTree))
  --> rNPAdj(Num,NPTree), rVP(Tense,Num,VPTree).

%%  rNPAdj -- A list of words forms a noun phrase with an adjective
%%            if it consists of a determiner (Det), followed by an
%%            adjective (Adj), followed by a noun (Noun).

rNPAdj(Num,np(DetTree,AdjTree,NounTree))
  --> rDet(Num,DetTree), rAdj(AdjTree), rNoun(Num,NounTree).

%%  Some sample adjectives:

rAdj(adj(blue)) --> [blue].
rAdj(adj(happy)) --> [happy].
rAdj(adj(busy)) --> [busy].

%%  Try the following queries:
%%    rSenty(Tense,Num,Tree,[the,busy,dog,chased,luke]).
%%    rSenty(Tense,Num,Tree,[the,busy,dog,X,Y]).
%%    rSenty(past,sing,Tree,[X,Y,Z]).
%%    rSenty(Tense,Num,Tree,[the,X,dog,ran]).


%%  To see that hidden arguments are really there,
%%  run some queries using the predicates rS, rNP, rVP, etc.
%%  For example:
%%       rNP(sing,Tree,Listy,[]).
%%       rAdj(Tree,[busy],[]).
%%       rAdj(Tree,[busy,as,a,bear],[as,a,bear]).
%%           This last one is true because [busy,as,a,bear] - [as,a,bear]
%%           (i.e., the list [busy]) consists solely of an adjective!