Assignment 4, CSC430, Fall 2019
1 Goal
2 Guidelines
2.1 Handling Errors
2.2 Progress Toward Goal comment
2.3 Using Monads
3 The Assignment
3.1 Top-Level environment
3.2 New Values
3.3 New Forms
3.4 Order of Evaluation
3.5 Array Values
3.6 Syntax of RGME4
4 Suggested Implementation Strategy
4.1 Store-passing style
5 Nice Big Test Cases
5.1 Quicksort (optional)
6 Interface
7.5.0.16

Assignment 4, CSC430, Fall 2019

1 Goal

Extend the interpreter to handle mutable arrays.

2 Guidelines

For this and all remaining assignments, every function you develop must come with the following things:

For this assignment, you must develop your solutions using the typed/racket language. If you haven’t seen them, you might be interested in these Hints on Using Typed Racket in CPE 430.

Your test cases must use the check-equal?, check-=, or check-exn forms.

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.

2.1 Handling Errors

All of your error messages must start with the string "RGME: ". Essentially, this allows my test cases to distinguish errors correctly signaled by your implementation from errors in your implementation. To be more specific: any error message that doesn’t contain the string "RGME" will be considered to be an error in your implementation.

2.2 Progress Toward Goal comment

Graders are happier when they know what to expect. Your final submission should start with a short one- or two-line comment indicating how far you got through the project. Ideally, this would just be: “Full project implemented.” But if you only implemented, say, squazz and blotz, and didn’t get to frob or dringo, please indicate this in the comment, so that we don’t spend all our time searching for bits that aren’t there.

2.3 Using Monads

Want to use the store monad? Here’s some sample code:

monad-example.rkt

3 The Assignment

For this assignment, you must extend Assignment 3 by implementing mutable arrays. These arrays are instead of boxes. Just as the previous assignments asked you to generalize the book’s solution from one argument to many arguments, this assignment generalizes from a single box to an array.

In addition, we’ll be adding strings and a simple substring operation.

As we’ve discussed in class, this code will use no side effects in its implementation; that is, it’s implementing state without using it. The key technology here is SPS, Store Passing Style.

3.1 Top-Level environment

This assignment makes us pay in sweat and tears for every form in the language.

Fortunately, we simplified the language significantly in Assignment 3, when we removed binops from the language. Also, we represented true and false as variable references. All of these simplify the language.

Best of all, we implemented var as syntactic sugar; that means that we won’t need to make any changes to it, either. Yay!

3.2 New Values

Add a value that represents the null value. It will be used as the result of mutation operations. The serialize function should produce "null" when called with a null value. The null value should be equal to itself, but not to any other value.

The array value is also a new kind of value, but I’m going to delay discussing it for a few paragraphs.

3.3 New Forms

Implement these new forms as primitive bindings in a top-level environment. For details on this transformation, see the roadmap below.

There’s one more form, and this one can’t be implemented as a primitive function:

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 contains a mixture of numbers and booleans.

In order to allow mutable bindings, you will have to change the type of the environment; rather than mapping names to values, it will map names to locations. That is, "every" binding will be a reference to the store.

3.4 Order of Evaluation

In a language with mutation, programmers can observe the order of evaluation of function call arguments. For this language, all forms must perform left-to-right evaluation.

3.5 Array Values

The equal? 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.6 Syntax of RGME4

The concrete syntax of the RGME4 language with these additional features is captured by the following EBNF:

  expr = number
  | string
  | id
  | {id <- expr}
  | {if expr expr expr}
  | {var {id = expr} ... expr}
  | {lam {id ...} expr}
  | {expr expr ...}

  top-level-constants = true
  | false
  | null

  top-level-functions = +
  | -
  | *
  | /
  | equal?
  | <=
  | array
  | new-array
  | aref
  | aset!
  | begin
  | substring

... where an id is not var, if, lam, <- or =.

4 Suggested Implementation Strategy

4.1 Store-passing style

Store-passing style is a bear. Here’s how I’d get started.

First thing, strip down the language. In the interp function, comment out everything except the evaluation of numbers and applications of primitive functions. Add an other rule that signals an "unimplemented" error for all other forms. Make sure that your test cases for binops still work.

Time to add the store! Formulate the define-types and type aliases that you’ll need for stores (just like the book’s, or use hash tables if you prefer). Change the Env type to map names to locations. Choose a representation for a Value-combined-with-store, and change the type of the interp function so that it accepts a store and returns a Value-combined-with-store. Update your test cases so that they pass a store in, and expect the A*S including the answer and the store. Rewrite the interp rules for numbers and primitive applications 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 identifiers and functions; these are both one-line changes. Now you can re-enable your tests involving these items.

Next, I would add the mutation operations. Note that I’m advising you to add these before adding your other language forms (if, application of closures) 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 an extended 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. 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 equal? 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 RGME4 program, using its concrete syntax) that accepts a guard procedure and a body procedure and keeps running the body until the guard returns false. This function will have to be recursive; build a recursive function using mutation. Here’s an example of a factorial function written in this way:

{var {fact = "bogus"}
 {begin {fact <- {lam {n} {if {<= n 0} 1 {* n {fact {- n 1}}}}}}
   {fact 12}}}

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 by using the technique that Shriram describes in the next chapter.

Did I mention that this is optional?

6 Interface

Make sure that you include the following functions, and that they match this interface–actually, I’m giving you a couple of choices: you can return a Result, as Shriram describes, or an A*S, from interp. Your definition of top-interp will depend on which of these you choose. In fact, if you use a monadic style, your eval will look different from both of these. So these are really just suggestions.

procedure

(parse s)  ExprC

  s : s-expression
Parses an expression.

procedure

(interp e env sto)  Result

  e : ExprC
  env : Environment
  sto : Store
Interprets an expression, with a given environment. The Result may be any type you design.

procedure

(top-interp s)  string

  s : s-expression
Combines parsing and evaluation. You should probably use this definition for this function:

(define (top-interp [s : s-expression]) : string
  (serialize (value-part (interp (parse s) initial-env initial-store))))

Note that I’m assuming the existence of some value-part function that discards the store and returns only the value.

value

while : s-expression?

an s-expression representing the while function, described above, implemented in RGME4 .

value

in-order : s-expression?

an s-expression representing the in-order function, described above, implemented in RGME4 . It’s okay for this s-expression to assume that while is already bound.