\documentclass{article}
\usepackage{fullpage}
\usepackage{epsfig}

\newcommand\problem[2]{\section{#1}\label{#2}}

% tightlist is stolen from Andre' DeHon, edited by Jeremy Brown & Jamie Morris
\newenvironment{tightlist}{
  \begin{list}{$\bullet$}{%
    \advance\partopsep by \topsep
    \setlength{\topsep}{0in}
    \setlength{\itemsep}{0in}
    \setlength{\parsep}{0em}
    \setlength{\leftmargin}{1.5em}
    \setlength{\rightmargin}{0in}
    \setlength{\itemindent}{0in}
    \def\tightlist@empty{}
  }
}
{\ifx\tightlist@empty\empty \item[$\circ$] None \fi \end{list}\vspace{1ex}}

\begin{document}


\begin{center}
{\huge Problem Set 3: Parsing and Frames}\\
{\em 6.034 Fall 2003}\\
{\tt http://www.ai.mit.edu/courses/6.034f/}\\
{\bf Due: Wednesday, October 29th, 2003 -- 11:59PM}
\end{center}

You will need to copy the following files to your ps3 directory: {\tt ps3.scm}, 
{\tt ps3-publictest.scm}, {\tt tester.scm}, {\tt stt.scm}.  These files can be downloaded off of the
webpage or from the 6.034 Athena locker ({\tt /mit/6.034/files/ps3}).

{\em
This problem set involves no Scheme coding in the sense of the previous problem sets. 
You will be asked to perform exercises, the answers to which should be placed in the 
appropriate places in the file {\tt ps3.scm}. Public test cases are provided that will
test only some parts of each question. These test cases are provided to give examples 
of correct form but a perfect score on the public test cases does not necessarily mean 
that your problem set is completely correct. As in previous problem sets, the test cases
can be run by executing the {\tt test-file} function from within Scheme.} In most cases,
questions of syntax or correct formation of solutions can be answered by looking at the 
public test cases or the documentation provided in {\tt stt.scm}.

\vspace{\baselineskip}

\input{story.tex}

\vspace{\baselineskip}
\noindent{\bf Problem 1: Semantic Transition Trees}

You are provided with an STT grammar for COUNTRIES that has three bugs.
{\bf Your task is to find and correct the three small bugs in the COUNTRIES STT grammar
and to write an STT grammar for WEAPONS.} 
We expect that you will be able to do most of what you need for the WEAPONS grammar
by copying and editing the COUNTRIES grammar.
See the top of {\tt stt.scm} for an explanation of how to format STT grammars.

\noindent {\bf Hint:} {\em The changes you will need to make to fix the COUNTRIES 
STT grammar are small. One of the bugs is causing infinite loops: you
will probably want to turn on verbose output and find that bug first.}

Your WEAPONS grammar should handle ``what'' and ``get'' questions like
the COUNTRIES grammar, and all of the vocabulary in the WEAPONS sample.

Here are samples from the COUNTRIES and WEAPONS databases.  

\begin{tabular}{|c|c|c|c|c|}
\hline
{\bf Country} & {\bf Military-Branch} & {\bf Size} & {\bf Morale} & 
{\bf Equipment-Quality} \\
\hline iraq & army & large & low & bad \\
\hline iraq & navy & tiny & low & bad \\
\hline us & army & large & medium & excellent \\
\hline us & navy & large & high & good \\
\hline us & airforce & large & high & excellent \\
\hline israel & army & small & high & good \\
\hline
\end{tabular}

\begin{tabular}{|c|c|c|c|c|}
\hline
{\bf Weapon} & {\bf Country} & {\bf Type} & {\bf Size} & {\bf Lethal} \\
\hline weapon & country & type & size & lethal \\
\hline m16 & us & gun & personal & yes \\
\hline uzi & israel & gun & personal & yes \\
\hline m60 & us & gun & squad & yes \\
\hline 80mm-howitzer & us & artillery & vehicle & yes \\
\hline stun-grenade & britain & grenade & personal & no \\
\hline
\end{tabular}

\vspace{\baselineskip}

And here are sample queries for the COUNTRIES database:

\begin{tightlist}
\item in database COUNTRIES get us army morale
\item in database COUNTRIES get the military sizes for iraq
\item in database COUNTRIES get the equipment quality for iraq
\item in database COUNTRIES what branches does the iraq military have
\item in database COUNTRIES what size is the israel navy
\end{tightlist}

\vspace{\baselineskip}

Pleased with his work, Milly brought Ben a new assignment. 
``It looks like you really know what you're doing. That's good,
because we're going to need you to do some more STT work, on
a more interesting part of the system.''

To Ben's inquiry, she went on, ``What you just did works, but
only for the simplest sorts of sentences. It doesn't know about
context, and it can't deal with most ambiguities. That's fine
when it's a human talking to a computer, but that's not what the
military's really interested in.''

``What they really want is to be able to understand what people
are saying to each other. Not complicated conversations, but
things like news stories. Our big contract is for a situational
awareness system that takes in stories from thousands of newspapers
all over the world, interprets them, and then acts like a 
research assistant for intelligence analysts. So if we want to know
about tensions in Bolivia, we can just ask it for stories about 
tensions in Bolivia and it'll give them to us.''

``Sounds like a good idea,'' said Ben, ``But what's so hard about that?
Can't you just look to see whether the word 'tension' is in a story?''

``Just looking at what words in a story turns out to give very little
information about the story. You either end up missing important stories
or getting back hundreds of irrelevant ones. Instead, we're trying to
build a system that actually understands the stories it reads. To do
that, it turns the story into several different representations used
by people and reasons collaboratively between them. Or at least that's
the plan --- it's rather hard to actually do.''

``So what's my role?'' asked Ben.

``You'', said Milly, ``are going to build an STT system that
translates between two different systems. The big new idea we have is
to use English as an intermediate representation. To translate from
one representation to another, we render the first representation into
simple English, then parse it into the second representation: it
simplifies the problem enormously and gives us human-readable output for
debugging. I need you to build an STT system for our transition
frame to trajectory frame connector.''

``First though, I'd better tell you about our two representations.''

Milly proceeded to explain transition frames and trajectory frames to
Ben, along with several examples to help him understand how they
worked.
\vspace{\baselineskip}

\noindent{\bf Problem 2: Transition Frames}

Transition frame representations take the form of ``ladder diagrams.''
Each column in the ladder corresponds to a step in time (every row of a
particular ladder should have the same number of time steps).  Each
row of the ladder corresponds to the transitions pertaining to a
particular relationship.

The specific syntax that we will be using in this problem set is the
following:

\begin{itemize}
\item The entire ladder is a {\tt transition-space}.  This object is a
list, the {\tt car} of which is the symbol {\tt transition-space} and
the {\tt cdr} of which is a list of {\tt transition-rows}.
\item Each {\tt transition-row} is a list, the first element of which is a 
{\tt transition-relation}, and the second 
element of which is a {\tt transition-sequence}.
\item Each {\tt transition-relation} is a list, the first element of which is 
a symbol representing the type 
of relationship being described, and subsequent 
elements of which are symbols representing the names of the things involved in the relation.
\item Each {\tt transition-sequence} is a list of symbols from the set of
possible transitions, shown in Table 1.
\end{itemize}

\begin{center}
\begin{table}[hbt]
\begin{center}
\begin{tabular}{|c|c|}
\hline
{\bf Transition type} & {\bf Symbol to use} \\ \hline
Change & {\tt cha} \\ \hline
Not Change & {\tt ncha} \\ \hline
Increase & {\tt inc} \\ \hline
Not Increase & {\tt ninc} \\ \hline
Decrease & {\tt dec} \\ \hline
Not Decrease & {\tt ndec} \\ \hline
Disappear & {\tt dis} \\ \hline
Not Disappear & {\tt ndis} \\ \hline
Appear & {\tt app} \\ \hline
Not Appear & {\tt napp} \\ \hline
\end{tabular}
\end{center}
\caption{Table of typical transitions and the corresponding symbols used in the code}
\end{table}
\end{center}

For example, an event such as, ``The distance between the ball and the
wall decreased and then disappeared while the speed of the ball did
not change and then disappeared'' would be represented in list
structure as the following:
\begin{quote}
\begin{verbatim}
'(transition-frame
  ((dist ball wall) (dec dis))
  ((speed ball) (ncha dis)))
\end{verbatim}
\end{quote}

{\bf For this question you are to represent sequences of events as a
transition frames using the syntax described above.}  For each of the
following three events, fill in the appropriate definition in {\tt
ps3.scm} so that the expression returns the {\tt transition-frame}
that you feel most accurately describes the given sequence of events.

Each object and relation type should be a symbol from the following list: {\tt us-army, 
us-airforce, iraqi-army, israeli-army, quality, morale, size, rank, speed, us-army-general,
distance, us-planes, altitude, us-army-equipment}.
\begin{description}
\item[Event A:] ~\\
The US Army grew larger before reaching a steady-state size. Meanwhile, the quality of the
US Army's equipment continually declined.
\item[Event B:] ~\\
Immediately after a sharp decrease in the morale of the US Army, a general of the US Army
was demoted.
\item[Event C:] ~\\
As the US Air Force approached the Iraqi Army, the US planes descended for a while and then
leveled out.
\end{description}
\vspace{\baselineskip}

\noindent{\bf Problem 3: Trajectory Frames}

For the purposes of this problem, we will be using a simplified
version of Jackendoff's {\em Lexical Conceptual Semantics}
representation for our trajectory frames. 

\begin{itemize}
\item Each event is described by one or more {\tt trajectory-frame} objects.
\item Each {\tt trajectory-frame} is a list, the first element of
which is the symbol {\tt trajectory-frame}, the second element of
which is a symbol representing the object that is moving along this
particular trajectory, and the subsequent elements of which are {\tt
trajectory-paths} defining the path(s) that the object moves along.
\item Each {\tt trajectory-path} is a list, the first element of which
is the symbol {\tt path}, the second element of which is a symbol
defining the type of path ({\tt to, toward, from, away-from}), 
and the third element of which is a {\tt trajectory-place}.
\item Each {\tt trajectory-place} is a list, the first element of
which is the symbol {\tt place}, the second element of which is a
symbol defining the type of place ({\tt at, on, under, above, in}), 
and the third element of which is a symbol representing
the particular object that is used to define the place.
\end{itemize}

For example, an event such as, ``The ball went from being on the table 
to being in the basket''
would be represented in list
structure as the following:
\begin{quote}
\begin{verbatim}
'(trajectory-frame
   ball
   (path from (place on table))
   (path to (place in basket))) 
\end{verbatim}
\end{quote}

{\bf For this question you are to represent sequences of events as 
trajectory frames using the syntax described above.} For each of the 
following three events, fill in the appropriate definition in {\tt ps3.scm}
so that the expression returns a list of one or more {\tt trajectory-frames} that you feel 
most accurately describe the sequence of events. Any symbol that may
be needed to define an object or place is in bold.

\begin{description}
\item[Event A:] ~\\
{\bf Sam} walked from his {\bf office} to the {\bf watercooler} and then over
toward the {\bf window}.
\item[Event B:] ~\\
The {\bf boy} moved further away from the {\bf spider} and crawled under the {\bf table}.  
\item[Event C:] ~\\
{\bf Sam}, after making his way over to the {\bf window}, stood and watched while
outside the {\bf birds} flew playfully from the {\bf windowsill} to the {\bf birdbath}.
\end{description}

\vspace{\baselineskip}

Once Milly had explained the representations, she gave Ben some
sample sentences to work with, and sent him off to work on his
parser. Ben quickly realized that this new problem wasn't very
different than before, and set to work coding up a tree to parse
English into trajectory frames. The top of the tree and all
the terminals of the tree were easy, but when Ben got to the
middle, he was stumped.

Panicked, he called Alyssa. ``You silly,'' she said, ``The
expressions don't have to be database queries. They can be any
arbitrary sort of expression you want.''

Sheepishly, Ben thanked Alyssa and went back to work, quickly
filling in the remaining parts of the problem.

\vspace{\baselineskip}

\noindent{\bf Problem 4: Semantic Transition Trees and Frames}

Ben's tree is supposed to take in English sentences and produce
trajectory frames.

{\bf Complete Ben's trajectory tree grammar.} You will need to fill in
expressions for the trees {\tt ?trajectory}, {\tt ?path}, {\tt
?path-element}, and {\tt ?place}.

\vspace{\baselineskip}

\noindent{\bf Problem 5: Topological Sorting}

Consider the four graphs shown below.  {\bf Using topological sorting,
provide a linearization of each hierarchy.}  Use alphabetical ordering
when the sub-before-super and left-before-right constraints are not enough to
determine the next element in your linearization.

For each hierarchy, fill in the appropriate definition in {\tt
ps3.scm}. Each definition should return a list, the elements of which
correspond to the letters of the nodes in the hierarchy (in proper
linearized order). If no linearization exists, an empty list should
be returned.

\begin{center}
\psfig{file=tree1.eps, scale=0.75} \hspace{1in}
\psfig{file=tree2.eps, scale=0.75}\\
\vspace{\baselineskip}
\vspace{\baselineskip}
\psfig{file=tree3.eps, scale=0.75} \hspace{1in}
\psfig{file=tree4.eps, scale=0.75}
\end{center}

\end{document}
