For this programming assignment, once again you will be diagramming simple sentences. The sentence grammar is exactly the same as for Program 1.
For this assignment, your program must be written in Scheme. You will be programming in a "functional" style, as described in Chapter 15 of the text book. Since this program must be written in Scheme, appropriate use of functional language features is expected. Hence,
You must use recursion rather than iteration.
No assignment is permitted. Assignment is an imperative
concept,
based on the model of a stored memory machine, and it does not exist
in pure functional languages. Scheme does have some imperative
features, and those are the ones to avoid:
set!, setcar!, setcdr!, and all
other operations with named ending in "!" are not allowed.
Do not use global variables--bound names with values that change over the life of your program. In fact, none of your bound names, whether global or local, should change in value over time. Global constants, with a value that never changes, are fine. For local names, think of them as names for common subexpressions that you wish to use in more than one place.
The control structures you cannot use are do and
begin. That still leaves you with plenty of control
structures to work with, though.
Here are some suggestions:
For selection, use cond or if. The
if function is a special case of cond. If
you only use cond, you'll probably never miss
begin.
For iteration, use a named let. That
means using recursion in spirit whenever you need to repeat
a series of actions. Alternatively, you can define a separate
recursive function if you prefer.
For grouping a series of expressions into one sequence, use
let (instead of begin). This most
commonly arises if you
use an if instead of cond, which is one reason that
cond is often preferred.
Write your program as a Scheme function called
diagram-sentence. Your function should take a single
argument, which is a list of symbols that represents the input to be
diagrammed. It should then return the appropriate sentence diagram
as its result. For example, you might invoke your sentence diagrammer
with the following S-expression:
(diagram-sentence '(alice found mean green book))
This setup differs slightly from Program 1, in that you are no longer responsible for reading from standard input or splitting a line into individual tokens (words). Further, your solution will process just a single input that is provided as an argument, rather than looping to read all lines from standard input.
One way to organize your solution (but not the only way, and certainly not a requirement for this program) is to construct one procedure for each nonterminal that takes a list of strings as a parameter and breaks the list into a diagram for that nonterminal (if possible) and the remainder of the string. For example:
(define (adj list-of-symbols)
(cond
((null? list-of-symbols) ())
((equal? (car list-of-symbols) 'green)
(list 'green (cdr list-of-symbols)))
((equal? (car list-of-symbols) 'lean)
(list 'lean (cdr list-of-symbols)))
((equal? (car list-of-symbols) 'mean)
(list 'mean (cdr list-of-symbols)))
(else ())
)
)
The procedure adj
does the job for <adj>. This is just a
simple skeleton of an implementation--it may not handle all of the
necessary issues, including error checking.
A sample invocation of adj is
(adj '(green cow saw book))
which returns
(green (cow saw book))
You may need to adjust or adapt this approach, depending on the overall design you use for your Scheme solution--or you may ignore it altogether and develop your own strategy. Some Scheme procedures that you may find useful
and append car cdr cond
cons define equal? list map
not null? number? or symbol?
For purposes of our Scheme implementation, the "diagram" produced by your program will be an S-expression that represents the grammatical structure of the sentence. For example, consider the following sentence:
(mean cow saw carefully green alice with book)
The S-expression diagram for this sample should be:
(((mean) cow) (saw carefully) ((green) alice (with (book))))
Your diagram-sentence function should return such an
S-expression, or list structure, as its value for a sentence that
parses successfully, or return a string containing the appropriate
error message if the input is in error. The error message requirements
are exactly the same as in Program 1.
The requirements for where parentheses should appear in each diagram are the same as for Program 1. One difficulty with the output format described for the Program 1 assignment, however, is that exactly where parentheses should or should not be added in a diagram was not precisely defined.
To address this lack of clarity, we can employ another tool from the programming language field: denotational semantics. We can define a denotational semantic function D that gives the meaning of a parse tree for the Program 1 grammar as a diagram represented by a Scheme S-expression. In particular, the denotational semantic function D takes a subtree of the parse tree as argument and returns an S-expression.
D[[<sentence> --> <subject> <verb_phrase> <object>]]
= ( D[[<subject>]] D[[<verb_phrase>]] D[[<object>]] )
D[[<subject> --> <noun_phrase>]] = D[[<noun_phrase>]]
D[[<verb_phrase> --> <verb>]] = ( D[[<verb>]] )
D[[<verb_phrase> --> <verb> <adv>]] = ( D[[<verb>]] D[[<adv>]] )
D[[<object> --> <noun_phrase>]] = D[[<noun_phrase>]]
D[[<verb> --> terminal]] = terminal
D[[<adv> --> terminal]] = terminal
D[[<noun_phrase> --> <noun>]] = ( D[[<noun>]] )
D[[<noun_phrase> --> <adj_phrase> <noun>]] = ( D[[<adj_phrase>]] D[[<noun>]] )
D[[<noun_phrase> --> <noun> <prep_phrase>]] = ( D[[<noun>]] D[[<prep_phrase>]] )
D[[<noun_phrase> --> <adj_phrase> <noun> <prep_phrase>]]
= ( D[[<adj_phrase>]] D[[<noun>]] D[[<prep_phrase>]] )
D[[<noun> --> terminal]] = terminal
D[[<adj_phrase> --> <adj> <adj_phrase>]] = (cons D[[<adj>]] D[[<adj_phrase>]] )
D[[<adj_phrase> --> <adj>]] = ( D[[<adj>]] )
D[[<adj> --> terminal]] = terminal
D[[<prep_phrase> --> <prep> <noun_phrase>]] = ( D[[<prep>]] D[[<noun_phrase>]] )
D[[<prep> --> terminal]] = terminal
Some explanation of the denotational semantics is in order. While the argument to D is always a subtree of a parse tree, the definitions only give the meaning of the subtree in terms of its children. In particular, the argument of D on the left of a definition is the production used at the root of the subtree and the arguments to D on the right of a definition give the nonterminals that represent the immediate children of the subtree. For example, the definition
D[[<sentence> --> <subject> <verb_phrase> <object>]]
= ( D[[<subject>]] D[[<verb_phrase>]] D[[<object>]] )
covers the case of a parse tree having <sentence> as
the root, which has children <subject>,
<verb_phrase>, and <object>.
The production used is of course
<sentence> --> <subject> <verb_phrase> <object>
which is mentioned explicitly in the argument to D for clarity. The meaning attached to the parse tree is
( D[[<subject>]] D[[<verb_phrase>]] D[[<object>]] )
which is an S-expression (notice the parentheses) of length 3
having elements that are the meanings of the three subtrees
with roots <subject>, <verb_phrase>,
and <object>.
Note the use of the Scheme cons function in one of the
semantic definitions to indicate adding an element to the front of
an S-expression. Finally,
the terminal terminal is just meant to match
any of the appropriate terminals (words) from the grammar.
Now we can apply the denotational semantics above to an example to show how the resulting S-Expression is derived. Consider parsing this sentence:
(alice found mean green book)
The resulting output should be:
((alice) (found) ((mean green) book))
The denotational semantics for this sentence are derived below (each addition is highlighted in red):
D[[<sentence>]]
= ( D[[<subject>]] D[[<verb_phrase>]] D[[<object>]] )
= ( D[[<noun_phrase>]] D[[<verb_phrase>]] D[[<object>]] )
= (( D[[<noun>]] ) D[[<verb_phrase>]] D[[<object>]] )
= ((alice) D[[<verb_phrase>]] D[[<object>]] )
= ((alice) ( D[[<verb>]] ) D[[<object>]] )
= ((alice) (found) D[[<object>]] )
= ((alice) (found) D[[<noun_phrase>]] )
= ((alice) (found) ( D[[<adj_phrase>]] D[[<noun>]] ))
= ((alice) (found) ((cons D[[<adj>]] D[[<adj_phrase>]] ) D[[<noun>]] ))
= ((alice) (found) ((cons D[[<adj>]] ( D[[<adj>]] )) D[[<noun>]] ))
= ((alice) (found) ((cons mean ( D[[<adj>]] )) D[[<noun>]] ))
= ((alice) (found) ((cons mean (green)) D[[<noun>]] ))
= ((alice) (found) ((mean green) D[[<noun>]] ))
= ((alice) (found) ((mean green) book))
In addition to writing your program, you will also need to write a set of test cases that demonstrate that your program works correctly. The Curator-assessed portion of your program grade will depend on all three of these factors:
The correctness of your test cases (each test case must have the right expected output)
The thoroughness of your test cases (together, they must exercise all behaviors required by this assignment)
The correctness of your program (it must pass all your test cases)
Review the test case input guidelines to see the format for your test cases. The example above could be phrased as a test case like this:
//== (alice found mean green book) //-- ((alice) (found) ((mean green) book))
Here, the input section of the test case is the literal value to pass as an argument to your function (it will be quoted before being passed to your function, so no single quotes are needed in your test cases). The output section contains the expected result value that your function should produce. If the output result is a string, be sure to surround it with double-quotes in your expected output.
Combine all of your test cases into a single ASCII file to submit to the Curator along with your program. In addition, you can use the tddscm.pl tool to run test cases on your own machine.
Your Scheme implementation is to be organized in a single file. All documentation and identifying information should be placed in comments within the single source file. The comments at the beginning of the file should identify the assignment and give your full name. Every Scheme function should be preceded by comments explaining its purpose, the meaning of each parameter, and the general strategy of its implementation if applicable.
In addition to your Scheme source file, you will also need to submit a plain ASCII file containing your test cases.
Your program and test case file will be both be submitted electronically through the Web-CAT Curator for automatic grading. The Web-CAT Curator will grade one half of your program score (50 points), as well as assess any deductions based on the late policy described in the syllabus. The TA will assess the remaining 50 points based on the program grading criteria. There is no need to print or turn in a hard copy version of your program; the TA will mark up a PDF version of your program and e-mail it back to you.