2 Midterm 2

Due: Thurs, Oct 14, 11:59PM

The repository contains a single markdown file m2.md, which you can edit to submit your answers to the following questions. Your submision must be pushed by midnight on Thursday.

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.

2.1 Short answer

Question 1

[12 points]

Using only cons, '(), symbols, and literal numbers, strings, booleans, or characters, write expressions that are equivalent to each of the following:

• '((1) x 2)

• '((1) x . 2)

• '(1 . (2 . (3)))

• '(quote (x 2))

• `(1 ,(add1 2))

• `(1 ,@'(2 3) x)

For example, '(1 2 3) is equivalent to (cons 1 (cons 2 (cons 3 '()))).

Question 2

[10 points]

Will the following program run forever using only a constant amount of memory, or will it eventually consume all memory and crash? Briefly justify your answer.

(begin (define (flip x)

(flop (add1 x)))

(define (flop y)

(flip (sub1 y)))

(flip 5))

How about this one? Again, justify your answer.

(begin (define (flip x)

(flip (flop (add1 x))))

(define (flop y)

(flop (flip (sub1 y))))

(flip 5))

Question 3

[8 points]

Which of the following subexpressions are in tail position?

• (if e0 e1 e2)

• (match e0 [p1 e1] [p2 e2])

• ((λ (x y) e0) e1 e2)

• (eq? e0 e1)

2.2 Code generation

Question 4

[20 points]

Suppose we wanted to add a set-box! operation to our language.

A (set-box! e0 e1) expression evaluates e0 and e1. The result of e0 should be a box (otherwise an error is signalled). The box is updated (mutated) to contain the value of e1. Racket’s set-box! returns a special value called void, but your compiler may have the expression return any value.

Here’s an example (note: let is used for sequencing here):

Examples

> (let ((b (box 10)))     (let ((i1 (set-box! b 2)))       (unbox b)))

2

Implement the following function in the compiler. (You may assume this code will be added to the Loot compiler and may use any functions given to you.)

; LExpr LExpr CEnv -> Asm

; Compiler for (set-box! e0 e1)

(define (compile-set-box! e0 e1 c) ...)

2.3 Defunctionalizing

Question 5

[20 points]

Here is a program we wrote for computing the product of a binary tree of numbers.

It is clever in that it never multiplies if there is a zero in the tree; it immediately returns 0. It does this without using exception handlers, but instead by being written in a continuation-passing style.

; BT -> Number

(define (prod bt)

(prod/k bt (λ (x) x)))

; BT (Number -> Number) -> Number

(define (prod/k bt k)

(match bt

['leaf (k 1)]

[`(node ,v ,l ,r)

(if (zero? v)

0

(prod/k l (λ (pl)

(prod/k r (λ (pr)

(k (* v (* pl pr))))))))]))

Use defunctionalization to derive an equivalent definition of prod that does not use λ-expressions or higher-order values (i.e. no functions consume or produce other others).

The resulting program should consist of three mutually-recursive, first-order functions where every call to one of these functions is a tail-call.

For full credit, be sure to include a type definition for the type of defunctionalized λ-expressions in this program and type signatures for all three functions.

2.4 Pattern matching

Question 6

[30 points]

When we studied how to transform away pattern-matching expressions, we considered the following grammar of patterns:

; type Pat =

; | #t

; | #f

; | Integer

; | String

; | Variable

; | ‘_

; | ‘'()

; | ‘(quote ,Symbol)

; | ‘(cons ,Pat ,Pat)

; | ‘(list ,Pat ...)

; | ‘(? ,Expr ,Pat ...)

The pattern (list p ...) is a pattern that matches a list of any length, so long as every element of the list matches the subpattern p. Note that the elipsis here is literally part of the syntax!

If the pattern matches, it matches any pattern variables within p to the list of things that match in the elements of the list.

Some examples:

Examples

> (match (list 1 2 3)     [(list xs ...) (reverse xs)])

'(3 2 1)

> (match (list 'x 'y 'z)     [(list (? symbol? xs) ...) xs])

'(x y z)

> (match (list)     [(list (? symbol? xs) ...) xs])

'()

> (match (list 'x 3 'z)     [(list (? symbol? xs) ...) xs]     [_ '()])

'()

> (match '((x 1) (y 2) (z 3))     [(list (list xs ys) ...) (list xs ys)])

'((x y z) (1 2 3))

Extend the definitions of pat-match and pat-bind which wrote when implementing pattern matching to include this new kind of pattern.

; Pat Variable -> Expr

; Produces an expression determining if p matches v

(define (pat-match p v)

(match p

[(list 'list p1 '...)

; your solution here

'todo]

; omitted code that was previously given))

; Pat Variable Expr -> Expr

; Produce an expression that deconstructs v and binds pattern variables

; of p in scope of e.

; ASSUME: v matches p

(define (pat-bind p v e)

(match p

[(list 'list p1 '...)

; your solution here

'todo]

; omitted code that was previously given))

You do not have to transcribe the complete function, just give the code that goes in two occurrences of 'todo to complete the definition.

If you need to rely on any helper functions, you must give their complete definition and type signatures.