AdministrativeThis exam was given in the Spring semester of 2010. Note that in this exam the “Type System” question is only about rules since in this semester we didn’t have the Picky language implementation. In addition, there is no continuation question since that part was extremely brief. |
| |||||||||||||||||||||||||
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.
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.
(define g123 (all-ints-between 1 3)) (test (g123) => 1) (test (list (g123) (g123)) => (list 2 3)) (test (g123) =error> "out of numbers") |
(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)) |
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:
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...).
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) |
(Note that the codec functions are applied to separate string chunks, but the idea would be similar even with something more complicated.)
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.
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:
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
|
Unless otherwise noted, choose the single best answer for each of the following.
(: twice : IO -> IO) ;; duplicates an IO description (define (twice io) (Begin2 io io)) |
(: twice : IO -> IO) (define (twice io) (Begin2 io io)) |
(: begin2 : (-> Void) (-> Void) -> (-> Void))
(define (begin2 thunk1 thunk2)
(lambda ()
(thunk1)
(thunk2))) |