7 Intentional Behavior
Upload your solutions to GradeScope.
Your programs will be evaluated on the fraction of tests that they pass. We will show you some tests, but not all tests. You should test your code thoroughly. After the submission deadline, we will reveal the hidden tests.
Starter code here.
7.1 Runtime Safety for PairLang
This will count for extra credit for the assignment category. You cannot get more than 100% for this category.
In this problem we will be adding pairs to the SafeRefLang we saw in this lecture. We will use the following abstract syntax:
(define-type PairLang (letE [id : Symbol] [e1 : PairLang] [e2 : PairLang]) (identE [id : Symbol]) (pairE [e1 : PairLang] [e2 : PairLang]) (fstE [e : PairLang]) (sndE [e : PairLang]) (boxE [e : PairLang]) (unboxE [e : PairLang]) (numE [n : Number]) (addE [e1 : PairLang] [e2 : PairLang]) (locE [l : Number]))
We have given you a number of helper functions for running your abstract machine and have included the relevant frame and state machine definitions for you. This language has the usual semantics for a language with pairs, let bindings, and references. Here are some example tests that illustrate the desired semantics:
(test (run-machine-init (fstE (pairE (numE 1) (numE 2)))) (numE 1)) (test (run-machine-init (fstE (unboxE (boxE (pairE (numE 1) (numE 2)))))) (numE 1)) (test (run-machine-init (fstE (fstE (pairE (pairE (numE 1) (numE 2)) (numE 3))))) (numE 1)) (test/exn (run-machine-init (letE 'x (boxE (numE 10)) (fstE (unboxE (identE 'x))))) "runtime") (test/exn (run-machine-init (letE 'x (boxE (numE 10)) (fstE (unboxE (identE 'x))))) "runtime")
Your task is to implement the function transition of type (State -> State) that implements the CESK machine for this language. Your implementation should raise a 'runtime error if an illegal operation, such as calling fst on a non-pair – is attempted. You should not modify the state of the abstract machine in any way, but you will need to come up with your own tags for data.
Big hint: You will need to use a tagging scheme for pairs in the store so that you know their type when you unbox them. Here is a suggested strategy that we recommend you follow. Add an additional pair-tag that designates a value in the store as a pair. Then, the next two heap cells should contain pointers to the left and right element of the pair.
For example, suppose we evaluate the following program:
(boxE (pairE (numE 1) (numE 2)))
Then, the store should look like this after the program runs, and the program should evaluate to (locE 0):
locations 0 1 2 3 4 5 6 |
------------------------------------------------ |
| pair-tag | 3 | 5 | int-tag | 1 | int-tag | 2 |
----------------------------------------------- |
Notice how store location 1 is a pointer to the first element of the pair at location 3.
The reason we add these extra pointers is to handle pairs of pairs: we don’t necessarily know, just by looking at the tag, how much memory each component of the pair will need. For example, after we run the program:
(boxE (pairE (pairE (numE 1) (numE 2)) (numE 3)))
the store should look like:
locations 0 1 2 3 4 5 6 7 8 9 10 11 |
----------------------------------------------------------------------------------- |
| pair-tag | 3 | 10 | pair-tag | 6 | 8 | int-tag | 1 | int-tag | 2 | int-tag | 3 | |
----------------------------------------------------------------------------------- |