2 Midterm 2

Due: Tuesday, April 13th 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 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, April 13th. For the programmatic fragment, you should submit a zip file containing two files: the BoxIncr/compile.rkt for Question 4, and CallByName/interp.rkt for Question 5.

2.1 Short answer

Question 1

[10 points]

• On the random generation lecture on Tuesday (a recording can be found on ELMS!), we wrote random generators for testing the Con and Dupe languages. When going from Con to Dupe, we modified the generators to take an additional argument representing the type of the expression we want to generate. Why?

• Why did we need to introduce the Lea assembly instruction when implementing Knock?

Question 2

[10 points]

Is it possible for fib1 to run out of memory? Justify your answer.

(define (fib1 i)

(match i

[0 1]

[1 1]

[_ (+ (fib1 (- i 1)) (fib1 (- i 2)))]))

How about fib2? Again, justify your answer.

(define (fib2-aux i fib-1 fib-2)

(if (zero? i) fib-1

(fib2-aux (sub1 i) (+ fib-1 fib-2) fib-1)))

(define (fib2 i)

(match i

[0 1]

[1 1]

[_ (fib2-aux (sub1 i) 1 1)]))

Hint: consider Jig.

Question 3

[10 points]

For each of the following expressions, which subexpressions are in tail position? Assume that the top-level expression is in tail position.

• (sub1 e0)

• (begin e0 e1)

• (let ((x a)) e)

• (if b (box e1) e2)

• (match e [p1 e1] [_ e2])

2.2 Code generation

Question 4

[25 points]

In the repo (https://github.com/cmsc430/Midterm2-prog), you will find a directory named "BoxIncr". That contains the Hustle language from the lectures, partially extended with two additional primitives: incr-box! and an decr-box!.

An (incr-box! e) expression evaluates e. The result of e should be a boxed integer (otherwise an error is signalled). The box is updated (mutated) to increment its value by 1. Similarly, (decr-box! e) should decrement the boxed integer by 1. The result of the operation should be void.

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

(let ((b (box 41)))

(let ((v (incr-box! b)))

(unbox b)))

The ast, parser, and interpreter have already been updated for you to implement this functionality. Your job is to implement the compiler.

2.3 Call by Name

Question 5

[45 points]

In the https://github.com/cmsc430/Midterm2-prog, you will find a stripped down version of the Iniquity: function definitions and calls language: just the interpreter. Iniquity introduces the notion of function definitions and function calls. The way we evaluate function calls (as in racket) is known as "call-by-value": the arguments to a function call are evaluated before the body of the function is evaluated.

An alternative evaluation strategy is "call-by-name". In call-by-name, the arguments to a function call are substituted in the function body, left to be evaluated as they appear: if an argument is unused, it will never be evaluated; if an argument is used multiple times, it will be evaluated multiple times.

Consider the following example:

(begin

(define (f x) 42)

(f (read-byte)))

In standard call-by-value, this will read a byte from standard input, and proceed to call f with that read value, ignore it, and return 42. In call-by-name, this program will not read any value from the standard input - the read-byte will never be evaluated, as the body of f does not make use of x.

On the other hand, consider the following program:

(begin

(define (f x) (+ x x))

(f (read-byte)))

Again, in standard call-by-value, this will read a byte from standard input, and proceed to call f with that read value, doubling it. In call-by-name, this program will result to two different calls to read-byte, whose results will then be added together: when calling (f (read-byte)), the argument will be substituted into the body of f, yielding (+ (read-byte) (read-byte)).

An interesting point is how call-by-value interacts with let-bindings. For this assignment, we will keep let-bindings strict, just like in the current interpreter, that is the argument to the let will be evaluated before the body is executed.

To fully understand the interactions between let and function calls, consider the following examples:

(begin

(define (f x y) (+ (+ x x) (+ y y)))

(let ((z (read-byte))) (f z (read-byte))))

This program has the effect of first evaluating read-byte (for example, say 42), and then substituting its value for z in the body of the let. Then it will evaluate the call (f z (read-byte)). This will have the effect of substituting the value of z (which has already been evaluated), and the expression (read-byte) for x and y in the body of f. In turn, that means that there will be two new calls to read-byte, for each occurence of y in the body of f.

(begin

(define (f x) (+ x y))

(let ((y 42)) (f y)))

This program should yield an error - we’re still using static scoping!

(begin

(define (f x) (let ((y 42)) x))

(let ((y 17)) (f y)))

This program should yield 17, in both evaluation methods.

(begin

(define (f x) (let ((x 42)) x))

(f 17))

This example should yield 42, the let in the body of f shadows the argument.

(begin

(define (loop x) (loop x))

(define (f x) 42)

(f (loop 0)))

In call-by-name, this program terminates as the argument (loop 0) is never evaluated!

(begin

(define (f x) 42)

(f (+ #t #f)))

In call-by-name, this program also terminates: the error-producing argument (+ #t #f) is again never evaluated!

Your task is to modify the interpreter to implement this style of evaluation. The easiest way to do that is to re-implement let-bindings and function calls using substitution instead of the environment to pass arguments. While an implementation using environments is possible, it can be very tricky to get right; you have been warned!

Question Call-by-need: Extra Credit

[20 points]

An alternative to call-by-name is call-by-need. In call-by-need, the arguments to a function are not evaluated at call time (just like in call-by-name), but the evaluation of the argument is memoized - it’s going to only be evaluated the first time it’s needed and future occurences will reuse that evaluation’s result.

You’re on your own on this one and there will be no autograder, so reach out to set out a time to talk about your solution if you try to tackle this!

2.3.1 Submission and Grading

We will only use two files for grading: BoxIncr/compile.rkt and CallByName/interp.rkt. You should be able to submit a zip from inside the cloned repo to Gradescope, but we will only be using these two files for grading, so restrict your work in those.