Distributed: 10:00 a.m., Monday, 10 April 2006
Due: 10:00 a.m., Friday, 21 April 2006
No extensions.
This page may be found online at
.
Contents
There are five problems on the exam. Some problems have subproblems.
Each problem is worth twenty (20) points. The point value associated
with a problem does not necessarily correspond to the complexity
of the problem or the time required to solve the problem.
Experience shows that different people find different problems
complex. Hence, if you get stuck on an early problem, try moving
on to another problem and let your subconscious work on the early
problem. (You'll also get a better sense of accomplishment if you
can find at least one problem that you can solve early.)
This examination is open book, open notes, open mind, open computer,
open Web. However, it is closed person. That means you may 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.
Although you may use the Web for this exam, you may not post your answers
to this examination on the Web (at least not until after I return exams
to you). 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.
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. Experience from the first exam suggests that you should begin
this exam early, or at least look at the problems early.
I expect that someone who has mastered the material and works at
a moderate rate should have little trouble completing the exam in a
reasonable amount of time. In particular, this exam is likely to take
you about eight hours, depending on how well you've learned topics
and how fast you work. You should not work more than twelve hours
on this exam. Stop at twelve hours and write There's more to life
than CS
and you will earn at least 75 points on this exam.
I would also appreciate it if you would write down the amount of time
each problem takes. Each person who does so will earn two points of
extra credit. Since I worry about the amount of time my exams take,
I will give two points of extra credit to the first two people who
honestly report that they've spent at least eight hours on the exam or
completed the exam. These people should also let me know what work
they have done. (At that point, I may then change the exam.)
You must include both of the following statements on the cover sheet of the
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).
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.
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 both answer all of your questions electronically and turn in a
printed version of your exam. That is, you must write all of your answers
on the computer, print them out, number the pages, put your name on every
page, and hand me the printed copy. You must also email me a copy of
your exam by copying the various parts of your exam and pasting it into
an email message. Put your answers in the same order as the problems.
Please write your name at the top of each sheet of the printed copy.
Failing to do so will lead to a penalty of two points.
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. Unless I specify otherwise, you should
document your code.
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 check your spelling and grammar. Since I should be equally
careful, the whole class will receive one point of extra credit for each
error in spelling or grammar you identify on this exam. I will limit
that form of extra credit to five points.
I will give partial credit for partially correct answers. You ensure
the best possible grade for yourself by emphasizing your answer and
including a clear set of work that you used to derive the
answer.
I may not be available at the time you take the exam. If you feel that
a question is badly worded or impossible to answer, note the problem you
have observed and attempt to reword the question in such a way that it
is answerable. If it's a reasonable hour (before 10 p.m. and after 8
a.m.), feel free to try to call me in the office (269-4410) or at home
(236-7445). I also respond well to email questions.
I will also reserve time at the start of classes next week
to discuss any general questions you have on the exam.
In homework assignment 2, you implemented a denotational semantics
for a very simple imperative language. In this problem, you will
extend the language and, therefore, the semantics.
In some languages (such as C and its descendants) it is possible to use
an assignment statement as an expression, as in
if (x := x+1) then ... fi
What changes would we have to make to the D semantics to incorporate
assignment expressions?
Note that you need not describe changes to the concrete syntax,
but just to the abstract syntax, semantic domains, and semantic functions.
One of the regular comments about continuations is (approximately)
continuations are useful because they support coroutining
.
In this problem, you will explore coroutining with continuations.
The traditional coroutining example is that of producers and consumers.
The producer (or producers) and consumer (or consumers) share a
common buffer. Producers add values to the buffer and consumers
remove values from the buffer.
In Scheme, we might model a buffer as an object.
Here is a generalized consumer.
Here is a generalized producer.
Using continuations, implement the suspend operation. This operation
should, presumably, save the current continuation, get the continuation
of the coroutine (or a coroutine), and resume that coroutine.
Test your solution.
a. Write a method (and any helper methods you need),
String buildAbstractClass(String className), that, given
the name of a class, returns the text code for an abstract class that
corresponds to the original class. The abstract class should
* extend any classes the original class extended,
* implement any interfaces the original class implemented,
* include any fields the original class included, and
* declare method prototypes for any object method the original class
declared.
b. As you learned in the early writings on language design, some
pundits consider aliasing a problem. Aliasing occurs
when you have two or more referents to the same memory location.
In Java, we might say that aliasing occurs if
* (a) two or more variables refer to the same object,
* (b) two or more objects contain a reference to the same object, or
* (c) a variable refers to an object that is also contained as a reference within another object.
Write a method, aliases(Object[] variables), that,
given a list of all the objects referred to by variables, determines
whether there are any aliases and reports on those aliases. You
may choose how to report aliases.
In neither of these problems do you need to handle parameterized
types.
In our exploration of types and typing, we observed a variety of kinds
of type combinations, including product (records), sequences (arrays),
ranges, and functions. In discussing assignability and equivalence,
we focused primarily on products. Let us turn to another of the core
mechanisms for combining types, the function. Consider the following
types:
type small = range(int): 0..9
type f0 = function (int x int) -> int
type f1 = function (int x int) -> int
type f2 = function (int x int) -> small
type f3 = function (int x small) -> int
type f4 = function (int x small) -> small
type f5 = function (int x int x int) -> int
type f6 = alias type f1
type f7 = alias type f2
type f8 = alias type f1
type f9 = alias type f8
Assume we have variables v0 ... v9, with each variable belonging to the corresponding type (e.g., v4 is of type f4).
Describe four notions of assignability and, for each, explain what
happens in three interesting
cases and why. I would recommend
that three of your four notions correspond to: declaration equivalence,
name equivalence, and structural equivalence.
Write and answer a problem that covers some topic we've explored in
CSC302. You will be graded on both the quality of the question and the
quality of the answer. The problem should be of the same approximate
complexity as the other problems on this examination.
Note: I know many of you are frustrated by problems of this form.
However, at this stage of your career, you should be able to demonstrate
your knowledge through more open-ended problems.
These are some of the questions students have asked about the
exam and my answers to those questions.
- Since you didn't give us a concrete syntax for D, why did you tell us not to worry about it?
- My experience when giving a similar assignment before is that students worry about the ambiguity associated with assignment. You do not need to worry about resolving that ambiguity. However, you do need to worry about changes to the abstract syntax (which I wrote) and to the semantics (which you wrote).
- Under structural equivalence, are aliases given the types that they ultimately resolve to?
- Yes.
Here you will find errors of spelling, grammar, and design that
students have noted. Remember, each error found corresponds to a
point of extra credit for everyone. I limit such extra credit to
six points.
Early April 2006 [Samuel A. Rebelsky]
* Designed problems.
Sunday, 9 April 2006 [Samuel A. Rebelsky]
* Wrote exam.
Monday, 10 April 2006 [Samuel A. Rebelsky]
* Cleanup.
* Released.