1 Midterm 1

Due: Tues, March 10th, 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 midnight on Tuesday.

During the 72 hours of the exam period, you may only ask private questions on Piazza if you need assistance for the course staff. You may not communicate or collaborate with any one else about the content of this exam.

1.1 Short answer

Question 1

[10 points]

Assuming that the value in rax is 5 and the value in rbx is 10, briefly describe the difference, if any, between these two Asm instructions:

Question 2

[10 points]

Briefly describe the difference, if any, between these two Asm instructions (hint: offsets were first introduced in Fraud) :

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

Consider the following alternative design: #t is represented by the number 1, #f is represented by the number 0. All other numbers beside 0 and 1 are used to represent integers.

• Describe one way in which this design is worse that the tagging approach we have used in class.

• Describe on 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 Boolean connectives

Question 4

[25 points]

Consider the following interpreter from Extort: when errors exist.

; type Answer = Value | 'err

; Expr -> Answer

(define (interp e)

(match e

[(? integer? i) i]

[(? boolean? b) b]

[`(add1 ,e0)

(match (interp e0)

[(? integer? i) (add1 i)]

[_ 'err])]

[`(sub1 ,e0)

(match (interp e0)

[(? integer? i) (sub1 i)]

[_ 'err])]

[`(zero? ,e0)

(match (interp e0)

[(? integer? i) (zero? i)]

[_ 'err])]

[`(if ,e0 ,e1 ,e2)

(match (interp e0)

['err 'err]

[v

(if v

(interp e1)

(interp e2))])]))

Now extend the interpreter to include and and or connectives similar to those found in Racket.

The or form takes any number of subexpressions. The subexpressions are evaluated from left to right until a subexpression evaluates to a non-#f value, which is produced by the or. If no such subexpression exists, then #f is produced.

The and form is similar. It takes any number of subexpressions. The subexpressions are evaluated from left to right until a subexpression evaluates to a #f value, which is produced by and. Otherwise, and produces the value of the last subexpression. If there are no subexpressions, then #t is produced.

To make things interesting, you should not use Racket’s and and or in interp.

1.4 Compiling a new primitive operation

Question 5

[35 points]

Consider the following excerpt of a compiler that is able to compile the cons primitive and empty lists '(). The relevant representation information is given as is the function for compiling cons:

(define result-shift     3)

(define result-type-mask (sub1 (arithmetic-shift 1 result-shift)))

(define type-imm         0)

(define type-pair        2)

(define imm-shift        (+ 2 result-shift))

(define imm-type-empty   (arithmetic-shift 3 result-shift))

; Expr Expr CEnv -> Asm

(define (compile-cons e0 e1 c)

(let ((c0 (compile-e e0 c))

(c1 (compile-e e1 (cons #f c))))

`(,@c0

(mov (offset rsp ,(- (add1 (length c)))) rax)

,@c1

(mov (offset rdi 0) rax)

(mov rax (offset rsp ,(- (add1 (length c)))))

(mov (offset rdi 1) rax)

(mov rax rdi)

(or rax ,type-pair)

(add rdi 16))))

Now suppose a map-zero? operation is added to the language which takes a single argument, which must be a list of numbers. The operation determines, for each element of the list, whether the element is 0 or not and produces a list of the results. In other words, (map-zero? xs) should produce what (map zero? xs) produces in Racket.

Write a compile-map-zero? function that compiles an expression of the form (map-zero? e0):

; Expr CEnv -> Asm

(define (compile-map-zero? e0 c)

...)

You may use any of the x86 registers as scratch registers, with the exception of 'rsp and 'rdi which need to point to the stack and heap, respectively.