1 Midterm 1
Due: Tuesday, October 13th 11:59PM
The repository contains a single plaintext file m1.txt, which you can edit to submit your answers to the following questions. Your submission must be pushed by 11:59 EDT on Tuesday, October 13th.
During the 72 hours of the exam period, you may only ask private questions to the staff (via email, discord, etc.) if you need clarification. You may not communicate or collaborate with any one else about the content of this exam.
Questions that are deemed applicable to the entire class will be shared, along with their responses, with the rest of the class.
1.1 Short answer
Question 1
[10 points]
Assuming that the value in rax is 42 and the value in rsp is 1024, briefly describe the difference, if any, between these two Asm instructions. Ensure that you mention what the value residing in rax would be after executing each of these.
(mov rax rsp) |
(mov rax (offset rsp 0)) |
Question 2
[10 points]
Assume that the register rbx currently holds the value 2048. Please write two sequences of instructions. The first should load the value stored at address 2048 in memory, and place that value in rax. The second should store the value 42 at address 2048.
1.2 Representation
Question 3
[20 points]
When studying the Dupe: a duplicity of types language, we used the least significant bit of a 64-bit integer to indicate whether the value being represented was an integer (tagged with #b0) or a boolean (tagged with #b1).
What is one alternative approach to disambiguating types at runtime (i.e. not a static type system)? It can be a completely new design of your own if you’d like.
One way to consider the possibilities is to think about how you would implement the logic we use in main.c to determine how to print the value returned by running the code that was generated by our compiler.
Once you’ve described your chosen alternative approach, do the following:
Describe one way in which this design is worse that the tagging approach we have used in class.
Describe one way in which this design is better than the tagging approach used in class.
Describe, at a high-level in English, how you could implement add1 using this design.
1.3 Interpreting Variadic Primitive
Question 4
[25 points]
Consider the following interpreter from Extort: when errors exist.
; type Answer = Value | 'err ; Expr -> Answer (define (interp e) (match e [(int-e i) i] [(bool-e b) b] [(add1-e e0) (match (interp e0) [(? integer? i) (add1 i)] [_ 'err])] [(sub1-e e0) (match (interp e0) [(? integer? i) (sub1 i)] [_ 'err])] [(zero?-e e0) (match (interp e0) [(? integer? i) (zero? i)] [_ 'err])] [(if-e e0 e1 e2) (match (interp e0) ['err 'err] [v (if v (interp e1) (interp e2))])]))
Now extend the interpreter to include + and * functions similar to those found in Racket.
Unlike our language Grift, both of these forms can take any number of subexpressions. The subexpressions are evaluated from left to right, but should halt when one of the subexpressions results in an error, or if one of the subexpressions is not an integer. The resulting error should be propagated up, as it is in the interpreter above. Aside from the possible error conditions, the resulting value should be the sum and product (for + and *, respectively) of the subexpressions. If there are no subexpressions, the result should be the identity element for the given operation (see the examples below).
For example:
; The following would result in 26 (+ 5 6 7 8) ; The following would result in 0 (+) ; The following would result in 1680 (* 5 6 7 8) ; The following would result in 1 (*) ; Both of the following would result in 'err (+ 5 6 #t 8) (* 5 (zero? #t) 7 8)
To make things interesting, you should not use Racket’s variadic + and * in interp (but you can use them as binary operators, e.g. (+ a b) is okay but (+ a b c) is not).
You can assume two new AST nodes sum-e and prod-e that each have one field, which is a list of expressions.
1.4 Writing a transformation over the AST
Question 5
[35 points]
In our language Grift: binary operations, we briefly discussed the notion of Administrative Normal Form (ANF). We will take inspiration from ANF and make the following restriction on our ASTs for Grift: all primitive operations (i.e. anything of the form prim-e p es can only have variables and literals as subexpressions (i.e. var-e, int-e, and bool-e).
Restrictions like this are popular in compilers because they make certain analyses and optimizations more straightforward, but no one would want to program with these restrictions. So compiler writers transform their programs into this form.
Your task is to write a compiler transformation, to-restricted that takes ASTs without this restriction and produces ASTs that abide by this restriction. You will do this by recursively ‘lifting out’ complex expressions and binding them to a new variable with a let (use gensym for creating new variable names, just make sure you keep track!).
Things that may make your life easier:
If you’d like, you can use the generalized let-e from Assignment \#4.
Redundant let-e’s are fine, as long as the restriction described above is maintained.
Below we have provided all of the uninteresting bits of the traversal. You will need to fill in the rest. I urge you to define helper functions and explain your reasoning with comments. If you document your thought process well, you are more likely to get partial credit.
; Expr -> Expr (define (to-restricted e) (match e [(int-e i) e] [(bool-e b) e] [(var-e v) e] [(if-e e t f) (if-e (to-restricted e) (to-restricted t) (to-restricted f))] [(let-e bs b) (let-e (restrict-binds bs) (to-restricted b))] [(prim-e p es) (error "TODO")])) (define (restrict-binds bnds) (match bnds ['() '()] [(cons (binding v e) bnds) (cons (binding v (to-restricted e)) (restrict-binds bnds))]))
1.4.1 Example 1
(prim-e '+ (list (var-e 'x) (var-e 'y)))
Would be unchanged.
1.4.2 Example 2
(prim-e '+ (list (prim-e 'sub1 (list (int-e 5))) (prim-e 'add1 (list (int-e 5)))))
Becomes:
(let-e (list (binding 'g348 (prim-e 'sub1 (list (int-e 5)))) (binding 'g347 (prim-e 'add1 (list (int-e 5))))) (prim-e '+ (list (var-e 'g348) (var-e 'g347))))
1.4.3 Example 3
Don’t forget about nested expressions!
(prim-e '+ (list (prim-e 'sub1 (list (prim-e 'sub1 (list (int-e 6))))) (prim-e 'add1 (list (int-e 5)))))
Becomes:
(let-e (list (binding 'g352 (let-e (list (binding 'g353 (prim-e 'sub1 (list (int-e 6))))) (prim-e 'sub1 (list (var-e 'g353))))) (binding 'g351 (prim-e 'add1 (list (int-e 5))))) (prim-e '+ (list (var-e 'g352) (var-e 'g351))))