Assignment 4, CSC430, Fall 2015
1 Goal
Extend the interpreter to handle mutable arrays.
2 Guidelines
2.1 Contracts & Test Cases
For this and all remaining assignments, every function you develop must come with the following things:
A commented purpose statement that expresses the result of the function in terms of its inputs, written in English. Be as precise as you can within the space of a line or two. The header lines must include input and output types.
Test cases. A function without test cases is incomplete. Write the test cases first, please.
2.2 Handling errors
Your parser and interpreter must detect errors and explicitly signal them by calling (error ...). We will consider an error raised internally by Racket to be a bug in your code.
For example, Racket signals a "divide by zero" error if you attempt to evaluate (/ 1 0). Since we use Racket’s division function to implement division in LOOI4, you may be tempted to leave it to Racket to signal division by zero errors for you. However, you must signal the error yourself by explicitly testing for division by zero before calling Racket’s division procedure.
2.3 Language Level & File Format
#lang plai-typed
Your solution should take the form of a single file. Solve each problem separately, and make sure that each solution appears in a separate part of the file, with comments separating each problem’s solution.
Hand in your solution using the handin server. For help with the handin server, please see the course web page.
3 The Assignment
For this assignment, you must implement mutable arrays, and mutable bindings.
As in previous assignments, the with form should just expand into an application.
3.1 New Forms
new-array: creates a fresh array of the given size, with all cells filled with the given value. So, for instance, {new-array 34 0.0} would create an array of 34 cells, all containing 0.0. It is illegal to create an array with fewer than one cell.
array: creates a fresh array containg the given values. So, for instance, {array 3 14 false 5} would create an array of length four whose second element is 14.
ref : returns an element of an array. So, for instance, {ref p [15]} would return the contents of cell 15 of the array named by p. If the array does not have that many elements, you must signal an error. The first element has index 0.
<- : the first set form is for arrays. So, for instance, {p [15] <- {f 6}} would set element 15 of the array named by p to be the result of calling f with 6. It must return the new value. The first element has index 0.
<- : the second set form is used to mutate bindings. So, for instance, {l <- 9} will change the binding of l to contain 9. It must return the new value. It is an error to mutate a variable that is not already bound.
begin : evaluates a sequence of expressions, returning the last one. So, for instance, {begin {f 9} p} would evaluate {f 9}, then return the value of p.
In order to allow mutable bindings and arrays, you’ll need to add a store, and rewrite your interpreter in store-passing style, as we did in class.
Note that arrays are not typed; it’s fine to have an array that mixes numbers and booleans.
3.2 Old Forms
In a language with mutation, programmers can observe the order of evaluation of binop arguments, and function call arguments. For this language, all of these must perform left-to-right evaluation.
Also, the eq? function must now accept arrays. It should return true for arrays only when its two arguments evaluate to the same array; that is, two arrays pointing to the same region of memory.
The serialize function must handle arrays. It should simply return the string "#<array>" for an array.
3.3 Syntax of lang-name
The concrete syntax of the lang-name language with these additional features can be captured with the following EBNF:
LOOI4 | = | num | ||
| | true | |||
| | false | |||
| | id | |||
| | {new-array LOOI4 LOOI4} | |||
| | {array LOOI4 ...} | |||
| | {ref LOOI4[LOOI4]} | |||
| | {LOOI4[LOOI4] <- LOOI4} | |||
| | {id <- LOOI4} | |||
| | {begin LOOI4 LOOI4 ...} | |||
| | {if LOOI4 LOOI4 LOOI4} | |||
| | {with {id = LOOI4} ... LOOI4} | |||
| | {func id ... LOOI4} | |||
| | {operator LOOI4 LOOI4} | |||
| | {LOOI4 LOOI4 ...} |
operator | = | + | ||
| | - | |||
| | * | |||
| | / | |||
| | eq? | |||
| | <= |
... where an id is not true, false, with, if, func, new-array, =, <-, begin or one of the operator names.
4 Suggested Implementation Strategy
Store-passing style is a bear. Here’s how I’d get started.
First thing, I’d strip down the language from assignment 3. Start in the parser, and comment out everything but binops and numbers. Comment out all of the test cases except those for binops. If you don’t have any tests that just use binops, write some, and make sure they work.
Next, I’d comment out the evaluation rules for everything but numbers and binops in the interpreter. Add an else clause that catches everything else and signals the error "unimplemented". At this point, your binop test cases should still work fine.
Time to add the store! Formulate the define-types and type aliases that you’ll need for stores (just like the book’s). Change the interp function so that it accepts a store, and returns a v*s. Update your test cases so that they pass a store in, and expect the v*s including the answer and the store. Rewrite the interp rules for numbers and binops so that they thread the store through the computation as they should.
With luck and some effort, you should be able to get those binop programs working again.
If this takes you a lot of time and effort, don’t worry: this might be the hardest part of the assignment. Once you get the hang of transforming code into store-passing style, it will get easier. Check to make sure that each store is used exactly once (with the exception of the mutation operations you’ll add later).
Next, I would add the mutation operations. Note that I’m advising you to add these before adding your other language forms (ids, funs, applications, if’s, and booleans) back in. First off, I think I’d add an allocate helper function that accepts a store, a number of locations to be allocated, and a value to place in all of them, and returns two things; the base location, and a new store.
Design your store so that the "next allocated" location is derived directly from the store. It could be a separate counter that’s part of a define-type, or it could be a function that just scans the store to find a new address. Don’t use the new-loc defined by the book; it makes testing quite painful.
Next, I would add a new arrayV value to the set of values. This will require a bunch of extra clauses in various places (serialize, for instance). Note that the representation of arrays is up to you, but it had probably better include a location and a length.
Following this, I would add the new-array operation to the set of expressions, to the interpreter, and to the parser. At this point, you should be able to create arrays, and the result of interpretation should include a store that contains lots of new allocated locations.
At this point, I would go back and add test cases that create arrays as subexpressions of the eq? binop; check that the allocations happen in the right order. As you go forward, you’ll want to use this technique to check order of evaluation for all of your forms.
At this point, it starts to make less difference what order you add language forms in. I think I would probably wait on applications, just because there will be lots of opportunities for mistakes.
5 Nice Big Test Cases
When you think you have everything working, develop a while function (that is, an LOOI4 program, using its concrete syntax) that accepts a guard procedure and a body procedure and keeps running the body until the guard returns false.
Then, use your while to develop the in-order function that accepts an array of numbers and its size and returns true if the array is in strictly increasing order.
5.1 Quicksort (optional)
This is not a good early test case, but you might want to see if you can write an in-place quicksort routine. You can model recursion as we did in class, by creating a box and then setting the box to contain the closure.
Good luck!
6 Interface
Make sure that you include the following functions, and that they match this interface:
procedure
(parse s) → ExprC
s : s-expression
procedure
(interp e env sto) → (Value * Store)
e : ExprC env : Environment sto : Store
procedure
(top-eval s) → string
s : s-expression
(define (top-eval [s : s-expression]) : string (serialize (fst (interp (parse s) empty-env empty-store))))
Your body can be different if you really want, but the types must match these.
value
while : s-expression?
value
in-order : s-expression?