1 Midterm 1

Due: Tuesday, March 9th 11:59PM

The exam consists of two parts: a written portion and a programmatic portion. Both will be handled through gradescope. You will see two gradescope assignments marked accordingly.

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.

Your submission must be submitted by 11:59 EDT on Tuesday, March 9th. For the programmatic fragment, you should submit a zip file containing only two files: the compile.rkt for the VariadicXor, and optimize.rkt for the Optimizer.

1.1 Short answer

Question 1 - Written

[10 points]

In the following questions, assume that the value in rax is 17 and the value in rsp is 2048.

What is the value of rax and rsp if we execute each of the following instructions or instruction sequences in that state?

• (Mov 'rax 42)

• (Mov 'rax 'rsp)

• (Mov 'rax (Offset 'rsp 0))

• (Push 'rax)

• (Mov 'rax 42)

  (Push 'rax)

Question 2 - written

[10 points]

Assume that the register rbx currently holds the value 1024. Write two sequences of instructions (in a86):

• One that stores the value of rax in location 1032 (= 1024 + 8).

• One that loads the value stored at location 1024 and stores it in rax.

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).

An alternative approach to disambiguate types at runtime would be to represent false (#f) as 0 (0), true (#t) as 1 (1), and any integer n as n+2, if n >= 0 and as n if n < 0.

Briefly answer the following questions:

• What is the range of integers that we can represent with this approach? How does it compare to the one in Dupe?

• Describe, at a high-level in English, how you could implement add1 using this design. How does it compare to the one in Dupe?

• How would you extend this approach to handle characters? How would you compare that to the way of generalizing Dupe to Dodger?

1.3 Interpreting the Xor Variadic Primitive - programmatic

Question 4

[25 points]

In the repo (https://github.com/cmsc430/Midterm1-prog), you will find a directory named "VariadicXor". That contains the Fraud language from the lectures, extended with a single additional primitive that takes an arbitrary number of arguments: bitwise-xor.

In racket, bitwise-xor performs the xor operation cumulatively at its arguments, at the bitlevel. For example:

; 0 is the neutral element for xor

(bitwise-xor) = 0

; xor with a single numeric argument yields the argument itself

(bitwise-xor 0) = 0

(bitwise-xor 1) = 1

; xor with a single non-numeric argument yields an error

(bitwise-xor #t) ; contract violation

; xor with two arguments is their bitwise xor

(bitwise-xor 1 2) = 3 ; Indeed: 1 = #b01, 2 = #b10

(bitwise-xor 1 3) = 2 ; Indeed: 1 = #b01, 3 = #b11, 2 = #b10

; xor with multiple arguments just performs the xor in sequence:

(bitwise-xor 1 2 3 4) = (bitwise-xor 1 (bitwise-xor 2 3 4)) = 4

Its AST representation and its interpretation are given below - it basically just applies the racket bitwise-xor function to the interpretation of all of its arguments (without doing any error handling, to keep things simple).

; AST

...

; Added compared to Fraud:

(struct BitwiseXor (es)  #:prefab)

; Expr Env -> Answer

(define (interp-env e r)

(match e

...

; Added compared to Fraud:

[(BitwiseXor es) (apply bitwise-xor (map (lambda (e) (interp-env e r)) es))]

...))

In the directory, you will find the ast.rkt, interp.rkt, and parse.rkt already implemented. Your task is to extend the compiler in compile.rkt to implement the same behavior.

Don’t worry about what happens if any of the arguments is not an integer or yields an 'err - the requirement is that the compiler evaluates the bitwise xor of its arguments, when these arguments evaluate to integers.

1.4 Writing a transformation over the AST - programmatic

Question 5

[35 points]

In the https://github.com/cmsc430/Midterm1-prog, you will find a directory named "Optimizer". That contains a simplification of the Fraud language from the lectures, that does not contain characters, conversions between characters and integers, begin or write-byte. What’s left is a simplified language with integers and booleans, arithmetic operations and tests, conditionals, let-bindings and read-byte. We provide the AST, interperter and parser.

Your task is to write an optimizer for this language (optimize.rkt) that transforms the AST of a given expression evaluating as much as possible. What does that mean? The majority of programs in this language contain constants (integer or boolean). These constants are known statically, which means that we can transform our programs to evaluate entire sub-expressions and replace them with the result. Note however, that some values are unknown until runtime (those that come from read-byte). Your optimizer should leave the behavior of programs containing read-byte unchanged, while still evaluating all fully-known sub-expressions.

Again, don’t worry about what happens in case for errors - you can assume all expressions are valid for this.

Let’s look at some examples:

1.4.1 Example 1 - Arithmetic Expressions

(+ 1 (- 43 2))

Would be transformed to a single integer:

42

1.4.2 Example 2 - Arithmetic with read-byte

(+ (read-byte) (+ 3 4))

Becomes:

(+ (read-byte) 7)

The second sub-expression (+ 3 4) can be replaced by its result (7) but read-byte must remain unchanged.

1.4.3 Example 3 - Conditionals

(if (zero? 17) (read-byte) 4)

Becomes a single integer again:

4

Because we know that (zero? 17) can evaluate to #f, we can simplify the entire if to its else branch.

1.4.4 Example 4 - Conditionals with read-byte

(if (zero? (read-byte)) 1 (zero? 0))

Becomes:

(if (zero? (read-byte)) 1 #t)

Since we don’t know the value of read-byte statically, we can’t simplify the conditional. However, we can simplify (zero? 0) to #t.

1.4.5 Example 5 - Let Bindings

(let ((x 7)) (+ x 8))

Becomes a single integer yet again:

15

The value that is bound to x is known statically and therefore we can use it in the body of the let.

1.4.6 Example 6 - Let Bindings with read-byte

(let ((x (+ (add1 2) (read-byte)))) (+ x (- 4 3)))

Becomes:

(let ((x (+ 3 (read-byte)))) (+ x 1))

This time the value bound to x is not statically known, so we can’t simplify the let-binding. However, we can simplify some sub-expressions (add1 2) and (- 4 3) to 3 and 1 respectively.

1.4.7 Example 7 - Don’t forget about nested expressions!

(+ (+ 1 2) (+ 3 4))

Becomes a single integer once more:

10

The two sub-expressions evaluate to 3 and 7, which then allows us to evaluate the outer addition to 10.

1.4.8 Example 8 - Nested Expressions with read-byte

(+ (+ 1 (read-byte)) (+ (read-byte) 4))

This expression remains unchanged.

No sub-expression can be fully evaluated and replaced with its result due to the presence of read-byte. In principle, one could use the commutativity of addition to try and add 1 and 4. Do not attempt to do that! That turns a slightly interesting but mostly straightforward midterm question to something that would probably be within scope for a final project! (Also it will throw off the autograder)

1.4.9 Submission and Grading

For this question, you must replace the placeholder implementation in optimize.rkt (which just returns the input expression), with your own optimizer. This question will be graded on two axes: correctness (15 points) and efficiency (20 points). Note that the placeholder solution gets all 15 correctness points - it is correct by definition! If you want to aim for the full score, you’ll have to implement various bits of functionality - but be careful: you risk losing correctness points otherwise!