1 Midterm 1

Due: Tues, Oct 8, 11:59PM

The repository contains a single plaintext file m1.txt, which you can edit to submit your answers to the following questions. Your submision must be pushed by midnight on Tuesday.

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

1.1 Short answer

Question 1

[10 points]

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:

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

Cosider the following alternative design: #t is represented by the number 0, #f is represented by the number 1. 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.

• Describe on way in which this design is better.

• 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 produces 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-add1 operation is added to the language which takes a single argument, which must be a list of numbers. The operation adds one to each element of the list and produces a list of the results. In other words, (map-add1 xs) should produce what (map add1 xs) produces in Racket.

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

; Expr CEnv -> Asm

(define (compile-map-add1 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.