Homework 14a

MUST BE DONE WITH YOUR PARTNER

MUST USE CHECKED-SIGNATURES!

Due Date Tues at 9:00pm (Week 14)

Purpose Add set! and set-box! to StateLang.

Exercises

In this assignment, you will extend your language from 11A to include memory operations, set! and set-box!.

While this is essentially an extension, in order to make sure you are starting from the right place, we want you to start by fixing your existing solution and making sure it passes a suite of automated tests. This does mean you have to adapt to our data definitions, as follows, which may vary slightly from your own. Note that throughout the assignment we are using suffixes, as you will be extending them later (twice). You should submit all three versions of the code! But start by submitting once you finish Exercise 1 and ensure you pass all the automated tests before moving on.

(: op? (Any -> Boolean))

; determines whether argument is the symbol of an arithmetic operator

(define (op? s)

(member s '(+ - * /)))

(define Op (signature (predicate op?)))

(define-struct e-num [num])

(define-struct e-var [sym])

(define-struct e-op [op left right])

(define-struct e-lam [param body])

(define-struct e-app [fun arg])

(define ExprV1 (signature (mixed (ENumOf Number)

(EVarOf Symbol)

(EOpOf Op ExprV1 ExprV1)

(ELamOf Symbol ExprV1)

(EAppOf ExprV1 ExprV1))))

(define ValV1 (signature (mixed (ENumOf Number) (ELamOf Symbol ExprV1))))

Exercise 1 Rename your parse, subst, eval, and wf to parse-v1, subst-v1, eval-v1, and wf-v1. Ensure they pass all their tests. The signatures/headers that we expect are:

(: parse-v1 (S-Exp -> Expr))

(define (parse e) ...)

(: subst-v1 (Expr Expr Var -> Expr))

(define (subst-v1 e to from) ...)

(: eval-v1 (Expr -> Val))

(define (eval-v1 e) ...)

(: wf-v1 (Expr -> Expr))

(define (wf-v1 e) ...)

Note that we are providing automated tests for this problem (only), which you can use to make sure you have the correct starting point for the rest of the assignment.

Now, we want to start adding state. In order to do this, we are providing you with a library file which gives you access to a few features that aren’t in ISL+: hashtables and gensym. Please download the file lib.rkt, put it in the same directory as your code and add (require "lib.rkt") at the top of your file.

Hashtables we showed in class when we were using ASL: they are a key-value store that is much more efficient than using a list of pairs (but express the same thing). You can look at this documentation page for descriptions of the various functions we have provided.

We also provide a HashMapOf K V signature that, given signatures for Keys & Values will construct a signature for hashtables.

The other function, gensym, is a function that will return unique symbols. You pass it a symbol prefix, and it returns a unique symbol starting with that prefix (it adds a unique number after). We showed how to implement this in class using mutable state. This will be useful for your implementation.

Exercise 2 Your first task is to implement set!. First, add a struct and a new version of the Expr signatures (you can call these ExprV2 and ValV2). Like ASL, we will only allow variables as the first argument to set!.

(define-struct e-set! [id arg])

(define Var (signature (EVarOf Symbol)))

(define ExprV2 (signature ...

(ESet!Of Var Expr)

...))

If you don’t remember, please revisit how set! works in ASL.

NOTE: One difference, unlike in ASL, set! should return 0, rather than a void value (which we do not have in StateLang)

Exercise 3 Now, make an updated version of your parser (parse-v2). This should then allow you to write test cases for eval-v2 (which you haven’t implemented yet). You should update subst (subst-v2), for now just substituting in the second argument of the set! (we’ll come back to making this actually work, later). The last helper to update is wf (wf-v2): this should be a very simple change.

Exercise 4 Now the interesting part: updating eval. If you try to make a simple change (i.e., just add another branch of the cond), it won’t work. What goes wrong? Part of the problem is that state is not local, so if in one subexpression you mutate a variable, you need to communicate that change to subsequent uses of the variable. i.e., ((lambda (x) (+ (set! x 1) x)) 2) should return 1, not 2.

There are a couple approaches to this, the one we will use for this HW is based on a simplified model of memory that we’ll call a "Store". This will "store" values and unique identifiers ("locations") that map to them. Concretely, the store should be a hashtable that has symbols as keys (locations in the store) and Val’s as values.

We’ll do this in several steps.

First, you should add an argument to eval-v2 for your store. In addition to passing the store to calls to eval, it should be threaded back out of any intermediate calls: i.e., the output of one call has to be passed in to the next. This means you should define a Result struct & type as follows, and eval-v2 should return a Result.

(define-struct res [store val])

(define Result (signature (ResOf Store Val)))

Next, implement the argument threading: don’t change the store, just thread it through all recursive calls.

Now, we want to start using the store. First, add a new term in the expression grammar: a location that exists in the store.

(define-struct e-loc [sym])

(define Loc (signature (ELocOf Symbol)))

(define ExprV2 (signature ...

(ELocOf Symbol)

...))

Now, we’ve added this to our expressions, but we don’t actually want programmers to use these, so update wf-v2 to raise an error on these terms. Since wf-v2 is only called once, at the beginning, it is okay if these terms appear during evaluation.

You should next add case to eval-v2 that handles this new expression: it should look up the value of the location in the store. How are we going to use this? On function application, rather than just substituting the value for the occurrences of the variable, you first allocate a new entry in the store (use gensym to make a unique identifier for a key) and then substitute that for all occurrences of the variable.

That does mean that the signature of subst-v2 should change, since we are no longer substituting values, but ELocOf Symbols.

i.e., in the example above, ((lambda (x) (+ (set! x 1) x)) 2), once you evaluate the application, assuming you generated the location 'loc123 and put that, mapped to 2, in the store, you would substitute 'loc123 for occurrences of x, yielding something like: (+ (set! (loc 'loc123) 1) (loc 'loc123)).

Since you want to be able to write tests for subst-v2 and eval-v2, you should add support in parse-v2 for a syntax like the above. Note that, even though we are supporting it in our parser, we do not want programmers to write these location literals in their programs: we rule that out with wf-v2. They should only appear while the program is running). But since we want to test such intermediate points, it’s helpful to be able to parse them.

Now, you are finally ready to implement the case in eval-v2 for set!. One thing you may have noticed is that if you substituted for the first argument of set!, you violated the signature, as the signature said ESet!Of only had a Var as the first argument. Fix that by adding a signature for Loc and make the actual first argument to ESet!Of be a (mixed Var Loc). Initially (enforced by wf-v2) this will be a Var, but after subst-v2, it will be a Loc.

Since you can assume that wf-v2 has been run, this means there should not be any variables that are not substituted on application. Once you have evaluated the second argument, you should update what what the store contains for the given location with that value.

Make sure your tests pass!

Exercise 5 With set! implemented, its time to move on to set-box!.

NOTE: Like with set!, unlike in ASL, set-box! should return 0, rather than a void value (which we do not have in StateLang)

For this exercise, we want you to copy your implementations into parse-v3, subst-v3, wf-v3, eval-v3, etc. First, you need to extend your Expr and Val definitions to account for the new terms: box, unbox, and set-box!. You also need a value form for a boxed location: create the struct and extend the Val definition to account for this. Update parse-v3, subst-v3, and wf-v3. Use parse-v3 to write a bunch of tests for eval-v3 using these new definitions!

Exercise 6 Now, start by implementing box. This should evaluate the expression inside, allocate a new location, and put the value in the store at that location. It should evaluate to the boxed location (the new value form).

Exercise 7 Next, implement unbox. This should evaluate its argument, and assuming it is a boxed location, it should look the location up in the store and return the value that is stored there.

Exercise 8 Finally, implement set-box!. This should evaluate both arguments, and the first should be a boxed location. It should update the value in the store at the given location with the new value (what the second argument evaluated to).