Take-Home Final Examination

Due: 5 p.m., Friday, 16 December 2011. This is an absolute, College-imposed, deadline.

• Preliminaries
  • Exam Format
  • Academic Honesty
  • Presenting Your Work
  • Grading
• Problems
  • Problem 1: A New Control Structure
  • Problem 2: Translating Restricted Conditionals
  • Problem 3: Evaluating Booleans
  • Problem 4: Attributes, Revisited

Preliminaries

Exam Format

This is a take-home examination. You may use any time or times you deem appropriate to complete the exam, provided you return it to me by the due date.

There are four problems on this examination. Each problem is worth the same amount. However, problems are not necessarily of equal difficulty.

I expect that someone who has mastered the material should be able to complete this examination in about six hours. However, you may take as little or as long as you would like to do this examination.

Academic Honesty

This examination is open book, open notes, open mind, open computer, open Web. However, it is closed person. That means you should not talk to other people about the exam. Other than as restricted by that limitation, you should feel free to use all reasonable resources available to you.

As always, you are expected to turn in your own work. If you find ideas in a book or on the Web, be sure to cite them appropriately. If you use code that you wrote for a previous lab or homework, cite that lab or homework and the other members of your group. If you use code that you found on the course Web site, be sure to cite that code. However, you need not cite the code provided in the body of the examination or explicitly linked from the examination.

Although you may use the Web for this exam, you may not post your answers to this examination on the Web. And, in case it's not clear, you may not ask others (in person, via email, via IM, by posting a please help message, or in any other way) to put answers on the Web.

Because different students may be taking the exam at different times, you are not permitted to discuss the exam with anyone until after I have returned it. If you must say something about the exam, you are allowed to say This is among the hardest exams I have ever taken. If you don't start it early, you will have no chance of finishing the exam. You may also summarize these policies. You may not tell other students which problems you've finished. You may not tell other students how long you've spent on the exam.

You must include both of the following statements on the cover sheet of the examination.

1. I have neither received nor given inappropriate assistance on this examination.
2. I am not aware of any other students who have given or received inappropriate assistance on this examination.

Please sign and date each statement. Note that the statements must be true; if you are unable to sign either statement, please talk to me at your earliest convenience. You need not reveal the particulars of the dishonesty, simply that it happened. Note also that inappropriate assistance is assistance from (or to) anyone other than Professor Rebelsky (that's me).

Since not all students will be taking this examination at the same time, I would appreciate it if you did not discuss the exam with anyone until I return the exam.

Presenting Your Work

You must present your exam to me in two forms, physically and electronically. That is, you must write all of your answers using the computer, print them out, number the pages, put your name on the top of every page, and hand me the printed copy. You must also submit an electronic copy of your exam. You should create the electronic version by making a tarball of any relevant code and submitting that tarball on Pioneerweb. If you fail to name and number the printed pages, you may suffer a penalty. If you fail to turn in both versions, you may suffer to a much worse penalty. If you fail to turn in a legible version of the exam, you are also likely to suffer some sort of penalty.

If your answer relies on provided files but you have not modified the files, you should include them in the tarball but should not include them in the printed copy of the exam. If you have made only minor changes to a file, it is appropriate to provide just the changes in the printed copy of the exam. For example, you could provide a diff of the two files.

In many problems, I ask you to write code. Unless I specify otherwise in a problem, you should write working code and include examples that show that you've tested the code. You should do your best to format that code to GNU coding standards.

You should always document the procedures you write. You need not use six-P format. However, you should provide clear documentation.

Just as you should be careful and precise when you write code and documentation, so should you be careful and precise when you write prose. Please take the time to check your spelling and grammar.

Grading

A student who provides correct or nearly-correct answers to all four of these questions will earn an A. A student who provides correct or nearly-correct answers to three of these questions will earn a B. A student who provides correct or nearly-correct answers to two of these questions will earn a C. A student who provides a correct or nearly-correct answer to one of these questions will earn a D. A student who provides no correct or nearly-correct answers to these questions will earn an F. A student who fails to turn in this examination will receive no credit for the examination.

I may give partial credit for partially correct answers. I am best able to give such partial credit if you include a clear set of work that shows how you derived your answer. You ensure the best possible grade for yourself by clearly indicating what part of your answer is work and what part is your final answer.

A student who takes both the in-class and take-home final examinations will receive the higher of the two grades as the grade for the final examination.

Problems

Problem 1: A New Control Structure

Your class has been tasked with designing a new programming language. Your colleague, Khan Ditional, knows that Boolean variables are just represented as integers. Khan therefore suggests that your language should have something that Khan calls an choice statement, which is a kind of integer if.

choose_statement
  : _CHOOSE exp statement_list optional_default
  ;

statement_list
  : statement
  | statement _SEMI statement_list

optional_default
  : /* epsilon */
  | _DEFAULT statement
  ;

Khan says,

Here's how choose works. We evaluate the expression. If the value is 0, we execute element 0 of the statement list. If the value is 1, we execute element 1 of the statement list. If the value is 2, we execute element 2 of the statement list. And so on and so forth. If the value is negative or too large, we use the default statement. If there is no default statement, we issue a warning but do not terminate the program.

Another colleague, Andi Gewus, notes that the grammar has some potential problems. In particular, Andi notes that there may be multiple parse trees for some choose statements. To make the explanation simpler, Andi adds just one other kind of statement to the language.

statement
  : choose_statement
  | _ID
  ;

Andi then asks you to consider the input of

choose x choose y a; b; c

Andi says,

There are at least three ways to parse this simple statement. Clearly, the inner choose statement is choice 0 for the outer choose statement. Similarly, the a is choice 0 for the outer choose statement. However, the b could be choice 1 for the inner choose statement or choice 1 for the outer choose statement. And, if b is choice 1 for the inner choose statement, the c could be choice 2 for the inner choose statement or choice 1 for the outer choice statement.

Andi also demonstrates this using Flex and Bison, building a simple parser for a language with basic statements, choose statements, and compound statements.

program
  : statement
  ;

statement
  : /* epsilon */
  | basic_statement
  | choose_statement
  | compound_statement
  ;

basic_statement
  : _IDENTIFIER
  ;

choose_statement
  : _CHOOSE exp statement_list optional_default
  ;

optional_default
  : /* epsilon */
  | _DEFAULT statement
  ;

compound_statement
  : _BEGIN statement_list _END
  ;

statement_list
  : statement statement_list_tail
  ;

statement_list_tail
  : /* epsilon */
  | _SEMI statement statement_list_tail
  ;

exp
  : _INTEGER
  ;

(You can find Andi's simple parser in Examples/Final/Problem_1.)

When we run Bison, we get shift-reduce conflicts.

$ bison --report=all  language.y
language.y: conflicts: 3 shift/reduce

Andi has a simple solution: Require the default option. But Khan refuses to budge. Khan says

It's obvious what to do. We always associate the choices with the innermost choose. If a programmer wants to associate a choice with an outer choose, she can just enclose the inner choose in a begin/end. And I don't care about the shift-reduce conflict. Bison does the right thing, anyway.

At first glance, Khan seems to be right. When we run Andi's program, we see the appropriate binding.

$ ./print-tree
choose 1 choose 1 a; b; c
choose_statement/3
   1 iconstant/0 [ivalue:1]
   2 statement_list/1
       1 choose_statement/3
           1 iconstant/0 [ivalue:1]
           2 statement_list/3
               1 basic_statement/0 [name:'a']
               2 basic_statement/0 [name:'b']
               3 basic_statement/0 [name:'c']
           3 default/0
   3 default/0
$ ./print-tree
choose 1 a; choose 1 b; c 
choose_statement/3
   1 iconstant/0 [ivalue:1]
   2 statement_list/2
       1 basic_statement/0 [name:'a']
       2 choose_statement/3
           1 iconstant/0 [ivalue:1]
           2 statement_list/2
               1 basic_statement/0 [name:'b']
               2 basic_statement/0 [name:'c']
           3 default/0
   3 default/0

But, those shift-reduce conflicts still bother us. Will there be a time in which something unexpected happens because of the conflicts? We don't know.

In addition, as you might expect, your colleague, Theo Retision, is unsatisfied. Theo insists that the class needs an unambiguous grammar that meets Khan's criterion (match choices with innermost choose statement) and that still gives the appropriate parse tree. (That is, the tree should still have the same form as given by the original grammar.)

Repair the grammar so that it is unambiguous but matches the same language. You may simply write a new grammar. However, if you have a more experimental bent, you might modify the language.y file. In the latter case, you should try to create the trees similar to those as implied by the original grammar.

Problem 2: Translating Restricted Conditionals

Although you have succeeded in writing an unambiguous grammar, your classmates have decided that it would be simpler to just modify Khan's language to remove the ambiguity. (So what if the programmer has to type a few extra things.) They make one main changesw they require the default clause (rather than making it optional).

They are now starting to experiment with implementation. They don't want to bother with stack frames, so they are going to use registers for most of their variables. They've decided that the Andi's basic statements can be implemented with output the identifier. They've decided that every expression has an address and generates code. And they've even implemented those decisions. You can find the implementation in Examples/Final/Problem_2.

You'll note that they have not implemented the choose statement.

$ ./li -p
choose 1 a; b default c
   0 IMOV %r0 1 
   1 SWRITE "a" 
   2 WRITELN 
   3 SWRITE "b" 
   4 WRITELN 
   5 SWRITE "c" 
   6 WRITELN 
   7 EXIT 0 
a
b
c

Implement the choose statement.

Problem 3: Evaluating Booleans

You may recall that we began our exploration of Bison with a simple program that evaluated integer expressions. In Examples/Final/Problem_3, you will find the start of a Bison program that provides a simple evaluator for Boolean expressions. The program supports two kinds of lines: Boolean expressions, which should be evaluated and printed, and assignment statements, in which the expression should be evaluated and then stored.

For example,

$ ./bool
true
=> true
true and false
=> false
x = true
*** assigned true to x ***
x and not x
=> false
x and y
*** y is not defined ***

Finish the program.

Problem 4: Attributes, Revisited

After nearly a semester with my quick AttributeSet hack, I have heard a number of comments about the hack. While you have found it useful, you have also noted some flaws. These include:

• It doesn't make sense that we need to specify the size of the set in advance. The set should grow as we need it.
• It's very strange that we do not have the type of an attribute associated with the attribute.
• It's very hard to clean up an attribute set, since pointer attributes don't have a cleanup mechanism.

Given those criticisms, it seems reasonable to re-implement attribute sets to match a more general API, which you can find in Examples/Final/Problem_4/attributes.h.

Finish the implementation.

I've put some useful files in Examples/Final/Problem_4/. You will note there is a preliminary unit test in that directory. You will find a more extensive set of unit tests in the coming days.