Programming Languages (CS302 2006S)

Post-Mid-Semester Examination

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 http://www.cs.grinnell.edu/~rebelsky/Courses/CS302/2006S//Exams/midsem.html.

Contents

Preliminaries

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.

Problems

Problem One: Extending the Denotational Semantics of D

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.

Problem Two: Continuations and Coroutines

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.



(define make-buffer
  (lambda (capacity)
    (let ((contents (make-vector capacity))
          (front 0)
          (back 0)
          (capacity capacity)
          (size 0))
      (lambda (command . params)
        (cond 
          ((eq? command ':empty?)
           (<= size 0))
          ((eq? command ':full?)
           (>= size capacity))
          ((eq? command ':get!)
           (let ((tmp (vector-ref contents front)))
              (set! front (modulo (+ front 1) capacity))
              (set! size (- size 1))
              tmp))
          ((eq? command ':put!)
           (vector-set! contents back (car params))
           (set! back (modulo (+ back 1) capacity))
           (set! size (+ size 1)))
          ((eq? command ':dump)
           (display "capacity: ") (display capacity) (newline)
           (display "size: ") (display size) (newline)
           (display "front: ") (display front) (newline)
           (display "back: ") (display back) (newline)
           (display "contents: ") (display contents) (newline))
          (else
            (error "Undefined command")))))))
>

Here is a generalized consumer.


(define consumer 
  (lambda (buffer DONE? SUSPEND CONSUMEVALUE)
    (let kernel ((count 0))
       (cond 
         ((DONE?))
         ((buffer ':empty?) 
          (SUSPEND) 
          (kernel count))
         (else 
          (CONSUMEVALUE (buffer ':get!) count)
          (kernel (+ count 1)))))))


Here is a generalized producer.


(define producer
  (lambda (buffer DONE? SUSPEND CREATEVALUE)
    (let kernel ((count 0))
       (cond 
         ((DONE?))
         ((buffer ':full?) 
          (SUSPEND) 
          (kernel count))
         (else 
          (buffer ':put! (CREATEVALUE count)) 
          (kernel (+ count 1)))))))


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.

Problem Three: Reflection

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

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

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.

Problem Four: Typing Functions

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.

Problem Five: Roll Your Own

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.

Some Questions and Answers

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.

Errors

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.

 

History

Early April 2006 [Samuel A. Rebelsky]

Sunday, 9 April 2006 [Samuel A. Rebelsky]

Monday, 10 April 2006 [Samuel A. Rebelsky]

 

Disclaimer: I usually create these pages on the fly, which means that I rarely proofread them and they may contain bad grammar and incorrect details. It also means that I tend to update them regularly (see the history for more details). Feel free to contact me with any suggestions for changes.

This document was generated by Siteweaver on Wed May 10 09:02:19 2006.
The source to the document was last modified on Thu Apr 13 10:16:04 2006.
This document may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS302/2006S/Exams/midsem.html.

You may wish to validate this document's HTML ; Valid CSS! ; Check with Bobby

Samuel A. Rebelsky, rebelsky@grinnell.edu