Instructions

This years final is takehome, due at noon on April 24. Email the instructor 3 racket files as attachements, one per question. Make sure you have complete test coverage for each question. The exam is open book, you can use anything from the course web site (including textbooks) and the racket docs. The exam must be your work; you are not permitted to use generative AI. The usual UNB rules about plagiarism apply.

Scope

marks: 10

Consider a primitive {call-with {id v1} fex v2} which is equivalent to

{{let1 id v1 fex} v2}

except that the call is dynamically scoped with respect to id (and only id). Complete the callWith case of the given interp function so that given tests pass.

Continuations

marks: 15

Roughly speaking, the Continuation Passing Style (CPS) takes a function call like

(...stuff... (f ...args...) ...more-stuff...)

into

(f/k ...args...
     (lambda (<*>)
       (...stuff... <*> ...more-stuff...)))

In this question you will start with the syntactic continuation based interpreter from Lecture 17 and add two arithmetic operations to it.

Unary Decrement

To get started, let’s add support for a single argument decrement function. I’ve written it here as --, even though it doesn’t mutate like -- does in most languages.

In this “inside out” style, we need to call interp on the argument, with a last argument of “what to do next”. The function continue will then handle processing the evaluated argument.

Define an Exp variant minus1E, and parse -- to minus1E. You will need to add a stub to interp to get the code compiling and the following test passing
```
       (test (parse `{-- 2}) (minus1E (numE 2)))
```

Multiplication

The second part of the question is to define (binary) multiplication. Since there are two arguments, we need to add two continuation steps. Luckily this works almost exactly the same as Add, and Sub, so you can copy and modify one of those cases.

Tests

In this question you will implement a two space copying collector similar to the one discussed in Lecture 19. You are welcome to refer to that collector as a reference, but I cannot promise it will be easy to copy code from there. If you do use it directly, make sure to credit your sources.

A skeleton of two space garbage collector is provided. At the top of the file you can find definitions defining the heap structure. There are two slots for metadata, and the rest of the heap is divided into two spaces (conceptually). The first slot is the offset, which defines which space the system is currently allocating into, and the second slot defines where in the current space to next allocate. Doing allocation requires using both slots:

Swap spaces

Define a function swap-spaces! that swaps the from and to spaces. This function should not move any allocated records, just update the heap metadata. Your function should pass the following tests.

GC for flat items

Write an initial version of the function gc! that can handle “flat” items (e.g. numbers, booleans). Your initial function should pass the following test.

GC for cons pairs

Update your function gc! so that it can handle cons pairs. This will require moving the two records pointed to by the cons record.

For this part and the next you will need to modify the API of gc! and malloc to take one or more extra arguments for roots. It’s up to you how to manage this, but I suggest using rest arguments since that will allow leaving most of the calls to gc! as they are.

GC for closures

Update your function gc! that can handle closures. From a GC perspective clos records are like variable sized cons records, so the main difference from the previous part is figuring how many slots to copy. Your updated function should pass the following test.

Finishing up

Run some small mutator tests like fib.rkt. Include the mutator tests you run as block comments in your submission.