• Main
• Overview
• Resources
• Homeworks

Sample Final 1

Date: Thursday, April 18th

Remember: the correct answers are short. Also, questions that ask for a verbal answer rather than code should still be answered correctly and based on facts.

Question 1: Racket Programming

 20 pts 

In a plain (strict) language like Racket, we can view nullary functions as generators for various kinds of data. For example

(: rand-ints-between : ???)
(define (rand-ints-between lo hi)
  (lambda () (+ lo (random (+ (- hi lo) 1)))))

Write two new functions: all-ints-between and rand-lists-of.

• all-ints-between: has the same type signature as rand-ints-between, but it enumerates all of the integers in the specified range (which you can assume to be valid). When it reaches the end of the range, it simply throws an error. For example, here is a test that demonstrates how it should work:

  (define g123 (all-ints-between 1 3)) (test (g123) => 1) (test (list (g123) (g123)) => (list 2 3)) (test (g123) =error> "out of numbers")

  Remember to write a correct type (and a purpose statement) for this function (which would be the type of rand-ints-between too.)
• rand-lists-of: this function would consume a generator function (eg, something that one of the above functions return), and generates on each call a list of random length, with its elements drawn from the input generator. For example, here is two possible runs of this function (this is not a test, since the results would be random):

  (let ([r (rand-lists-of (rand-ints-between 1 30))]) (list (r) (r) (r))) --> ((28 14 18 12) (12) (14 7)) (let ([r (rand-lists-of (all-ints-between 1 30))]) (list (r) (r) (r))) --> ((1 2 3 4 5 6 7 8) () (9 10))

  Note that the second example could run out of numbers and throw an error. To create a list of random length, in each call you should use (zero? (random 4)) — if it’s true, then return null, otherwise, return a list with one element and the obvious recursive call. In other words — don’t make the code decide on the length first and then count up to it (because these lists can have arbitrary size). Again, remember to write a correct type declaration and a purpose statement.

Question 2: Language Extension: Extending Racket

 20 pts 

The tool that we implemented in the first question can be useful for automated testing. To make it easy, implement a run-tests macro that can be used to execute tests (usually randomized). Uses of the macro should look as follows:

(run-tests <numeric-expression> times
           <id> in <generator-expr>
  <test-expr>)

(run-tests 100 times
           x in (rand-lists-of (rand-ints-between 1 30))
  (let ([xx (append x x)])
    (= (* 2 (length x)) (length xx))))

Notes:

• times and in should be keywords that are required in the macro form. (This means that you need to use define-syntax with syntax-rules.)
• The first two expressions (the number of times and the generator) should be evaluated only once.
• The test expression should obviously be evaluated multiple times — and if any evaluation results in #f, it should throw some error.
• You should just grab values from the generator — ignoring the fact that it could throw an error if the generator is exhausted.

Hint: to simplify things, you can use the for macro that we’ve seen in class. For example: (for i = 1 to 100 do ...stuff...).

Question 3: Lazy Languages

 20 pts 

One of the nice things with the functional representation of I/O operations that we’ve used in a lazy language is that you can do more processing than the simple things that you can do with imperative operations. For example, in an imperative world, if you have some function foo that prints somthing, and you want to write a foo2 function that prints the same stuff twice, then you can write this:

(define (foo2) (foo) (foo))

(define-type IO
  [Print    String]
  [ReadLine (String -> IO)]
  [Begin2   IO IO])

(wrap-io io codec)

1. io is an I/O description (an instance of the IO type)
2. codec is a list holding two (String -> String) functions:
   1. the first is used to encode all outputs in the I/O value
   2. the second is used to decode all inputs read in the function

(Note that the codec functions are applied to separate string chunks, but the idea would be similar even with something more complicated.)

Question 4: Language Extension: Extending Toy

 20 pts 

So, there’s good news and there’s bad news. The good news is that your programming language (Turbo Toy, of course) was chosen by NASA to run on the next generation of remote-controlled exploration robots on other planets. (With the exception of one remote-controlled street cleaner that will be sent to the moon.)

The bad news is that this means that it is absolutely crucial that computations are reliable — and that to achieve this, you need to extend the Turbo Toy implementation with a new form: safe. The semantics of this new form should be that {safe E} evaluates E twice and aborts with a “panic” error if the two evaluations don’t return identical results. (The plan is to eventually have a third machine, and use a majority vote, but for now you’re implementing a first prototype system.)

(Note: obviously, speed is important too, so the NASA people would prefer a compiler. But somehow they get the feeling that you didn’t really read through the relevant homework back when you were in school, so instead of requiring a compiler, they offer a 5-point bonus if extend the compiler instead of the interpreter. So, you need to choose whether you want to start with the interpreter (see the solution to Homework #11) or the compiler (Homework #12). (This bonus applies to anyone that does it, not only to master students.))

First, the BNF (and the parser) is extended with the safe form:

<TOY> ::= ...same...
        | { safe <TOY> }

(define-type TOY
  ...same...
  [Safe TOY])

Now that you have this, people started using it too often — and soon enough they ran into a major problem. If there is a safe nested in the dynamic scope of another safe, then the inner one’s expression will get evaluated four times. If it happens in a loop, then the number goes up exponentially.

To solve this, you could add an argument to eval (or to compiled functions, if you’re doing that) that tracks whether you’re currently in a safe expression or not. But a more convenient (and less desirable (this is just a quick prototype...)) way to achieve this is to add a flag that will keep track of this:

(: in-safe : —«fill-in»—)
(define in-safe —«fill-in»—)

Add the missing bits, and change your code so that if safe is encountered while evaluating safe, then the inner one is just ignored and will be evaluated once, as usual (since the whole thing will be done twice anyway). Note: your answer should have only this version of the evaluation fragment, no need to keep around the previous one.

Question 5: Type System

 20 pts 

We wish to extend the Picky language definition with rules for floating point numbers. First, begin with the language as we’ve seen, except that all occurrences of Number are changed to Integer to avoid confusion. (The revised definition is at the bottom of this question, but you don’t need to copy it, you only need to write the new rules.)

The idea of the extended language is that it can coerce integers into floating point numbers. Note that this could just as well be the case with the previous system — but we didn’t have any rules about them: we only knew that adding two numbers returns a number, and that < comparisons work among any two numbers. The extended definition will specify the types that we expect for all such operations.

But first we need to also add a new terminal to the BNF <fpnum> for floating point literals, and change <num> to <int> for the integer literals. (Both of these changes are done below.) One trivial extension here is the axiom for floating point literal numbers that comes in addition to the one for integers. (Again, this is already done below.)

Now your job is to revise the two numeric rules – the one for + and the one for <. The rules should reflect the following behavior:

• When + is given two integers, it returns an integer,
• when it is given two floats, it returns a float,
• when given one of each, it will coerce the integer to a float,
• < is done in an analogous way, except that the return value is always Boolean.

You need to write exactly two new rules: one for a + with two floating point inputs, and one for < with two floats. (Note: the existing rules for integers stay the same.) You should not write a rule for these operations with mixed-type inputs. Instead, write a new single coercion rule, that can be used when a float is needed but an integer is given.

(Note: each application of this coercion rule will correspond to the code in the implementation that does this coersion.)

<PICKY> ::= <int>
          | <fpnum>
          | <id>
          | { fun { <id> : <TYPE> } : <TYPE> <PICKY> }
          | { with { <id> : <TYPE> <PICKY> } <PICKY> }
          | { rec  { <id> : <TYPE> <PICKY> } <PICKY> }
          | { + <PICKY> <PICKY> }
          | { < <PICKY> <PICKY> }
          | { call <PICKY> <PICKY> }
          | { if <PICKY> <PICKY> <PICKY> }

<TYPE>  ::= Integer
          | Float
          | Boolean
          | ( <TYPE> -> <TYPE> )

Γ ⊢ i : Integer            ; <--- i is for all literal integers

Γ ⊢ fp : Float             ; <--- fp is for floating point numbers

Γ ⊢ x : Γ(x)

Γ ⊢ a : Integer   Γ ⊢ b : Integer
                                 
      Γ ⊢ {+ a b} : Integer

Γ ⊢ a : Integer   Γ ⊢ b : Integer
                                 
      Γ ⊢ {< a b} : Boolean

        Γ[x:=τ1] ⊢ E : τ2
                                  
Γ ⊢ {fun {x : τ1} : τ2 E} : (τ1 -> τ2)

Γ ⊢ f : (τ1 -> τ2)  Γ ⊢ v : τ1
                            
    Γ ⊢ {call f v} : τ2

Γ ⊢ c : Boolean   Γ ⊢ t : τ   Γ ⊢ e : τ
                                       
         Γ ⊢ {if c t e} : τ

Γ ⊢ v : τ1   Γ[x:=τ1] ⊢ E : τ2
                            
Γ ⊢ {with {x : τ1 v} E} : τ2

Γ[x:=τx] ⊢ E : τ   Γ[x:=τx] ⊢ v : τx
                                 
   Γ ⊢ {rec {x : τx v} E} : τ

Question 6: Language Features

 20 pts 

Unless otherwise noted, choose the single best answer for each of the following.

1. In a Racket-like language (sqrt (sqrt "2") 3) throws an arity error for sqrt when evaluated. What interesting feature does it have?
   1. It is dynamically scoped.
   2. It does not have first-class continuations.
   3. It is lazy.
   4. It evaluates its arguments from the right-to-left.
   5. It evaluates its arguments from the left-to-right.
   6. It is a parallel language.
2. Question 1 suffered from a major problem: if any of the sub sequences terminates, the whole generator is aborted. For example, if we use it as in Question 2, we cannot predict when this will happen. It would be much better to just make it possible to test a certain test for all values in some range and exactly that value. How could this be done?
   In this question you need to list all of the answers that are valid. That is, the answer is a subset of {a, b, c}.
   1. We can add a new “end of sequence” value, and make any higher-order generator (like rand-lists-of) detect such values and terminate itself accordingly.
   2. If we had a way to catch exceptions, we could end-of-generator catch exceptions in the higher order generator and have it terminate instead.
   3. We could thread the computation differently: instead of generators that return values, we could have them get a receiver function that will be applied on values of the generator.
3. In Question 3 we’ve seen how we can deal with I/O representations as if they are plain values. There is, however, a subtle problem with this that is demonstrated by this code:

   (: twice : IO -> IO) ;; duplicates an IO description (define (twice io) (Begin2 io io))

   What is this problem?
   1. There is a type error in this definition.
   2. There is a memory leak that we’ll see if we try to execute the result and its input was an infinite IO description.
   3. The dynamic scope rules of dealing with IO will “leak” from the first use of io to the second.
   4. When the io values are passed to Begin2, they need to be wrapped in a thunk.
4. Trying to mimic the description language of IO values in a strict language using thunks, we could say that this function from IO representations to IO representations:

   (: twice : IO -> IO) (define (twice io) (Begin2 io io))

   is equivalent to which of the following functions when we use thunks instead, where Begin2 is defined as this combinator on thunks:

   (: begin2 : (-> Void) (-> Void) -> (-> Void)) (define (begin2 thunk1 thunk2) (lambda () (thunk1) (thunk2)))

   Choose one of these, all with the a proper type of ((-> Void) -> (-> Void)):
   1. (define (twice io) (begin2 io io))
   2. (define (twice io) (let ([io* (io)]) (begin2 io* io*)))
   3. Both work fine
   4. Neither is is the same as the above twice.