8 Intentional Behavior
Due date: Tuesday, April 15 at 11:59PM. No late work will be accepted: this assignment must be turned in on-time due to the grading deadline.
Upload your solutions to GradeScope here. You should upload a single file called code.rkt. Be sure to check that your uploaded solution is valid. You will receive 0 points if your solution does not run. There are two separate gradescope uploads for the two portions of this assignment.
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 for problem 1 here: here. For the extra credit problem here.
8.1 Implementing a CK Machine [100 Points]
In this problem we will implement a CK machine for a language with named exceptions:
(define-type IfLang (boolE [b : Boolean]) (ifE [g : IfLang] [thn : IfLang] [els : IfLang]) (tryE [e : IfLang] [handle-id : Symbol] [handler : IfLang]) (raiseE [id : Symbol]))
We will use the following frame and state datastructures for the machine:
(define-type Frame (handleF [id : Symbol] [h : IfLang]) (ifF [thn : IfLang] [els : IfLang])) (define-type State (state [C : IfLang] [K : (Listof Frame)]))
The state machine should have the following transitions that mirror the usual semantics we’ve seen several times for languages with named exceptions:
Current C
Current K
Guard
Next C
Next K
Final?
(ifE g thn els)
K
g
(cons (ifF thn els) K)
N
(tryE e id h)
K
e
(cons (handleF id h) K)
N
(boolE #t)
(cons (ifF thn els) K)
thn
K
N
(boolE #f)
(cons (ifF thn els) K)
els
K
N
(boolE b)
(cons (handleF id h) K)
(boolE b)
K
N
(boolE b)
K
K empty
(boolE b)
K
Y
(raiseE id1)
(cons (handleF id2 h) K)
id1=id2
h
K
N
(raiseE id1)
(cons (handleF id2 h) K)
id1 != id2
(raiseE id1)
K
N
Figure 3: A tabular representation of the CK machine for IfLang.
Your task is to implement the transition function according to the above transitions. For example, the folowing test should pass for your machine:
(test (run-machine-init (ifE (boolE #t) (boolE #f) (boolE #t))) (boolE #f)) (test (run-machine-init (tryE (raiseE 'x) 'x (boolE #t))) (boolE #t)) (test (run-machine-init (tryE (tryE (raiseE 'x) 'x (boolE #t)) 'x (boolE #f))) (boolE #t))
8.2 Runtime Safety for PairLang [50 Points Extra Credit]
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 | |
----------------------------------------------------------------------------------- |