1 Guidelines
1.1 Contracts & Test Cases
1.2 Handling errors
1.3 Language Level & File Format
2 Pair Programming
3 The Assignment
3.1 Boxes
3.2 Sequencing
3.3 No Racket Boxes
3.4 NOTE FOR HANDING IN!
3.5 Using Monadic abstractions sanely
3.6 Order of Evaluation
4 Syntax of OCFAE
5 Support Code

Assignment 6, CSC430, Winter 2011

1 Guidelines

1.1 Contracts & Test Cases

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

1.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 CFWAE, 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.

Note that you may assume that your contracts are respected. That is, if your interp function’s contract indicates that it expects a MOCFAE, you do not need to worry about miscreants that call it with a number or a string or another surprising value.

1.3 Language Level & File Format

For this assignment, you must develop your solutions using the
  #lang plai
language level. Your test cases must use the (test ...) or the (test/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 Pair Programming

This assignment is a pair programming assignment. This means that you may work with at most one other person. You are not required to do so, but I strongly encourage it; if you don’t feel that you need the help, then work with someone who does.

To declare partners, both you and your partner must send me e-mail indicating this fact, at least three days before the assignment is due. In order to submit a pair programming assignment, use the string formed by joining your individual ids with a "+" in between. So, if my login is "clements" and my partner’s is "wilson", then we would submit as "clements+wilson". Don’t submit by yourself if you’re planning to work with a partner; an individual submission will prevent a later pair submission.

3 The Assignment

This assignment requires you to implement mutation of boxes, and expression sequencing.

3.1 Boxes

This assignment adds three new primitive functions: makebox, openbox, and changebox!. It adds one new kind of value, the boxV. These primitive functions behave precisely as in class.

3.2 Sequencing

Once we have mutation, we may wish to sequence expressions, as we might do in Racket using begin or as we might do in Java using semicolons. The seq expression must act similarly: it should evaluate all of its subexpressions, and evaluate to the value of the last one. So, for instance, this program:

  {with {{b = {makebox 14}}}
     {seq {changebox! b 15}
          {changebox! b 16}
          {openbox b}}}

... would evaluate to 16.

The seq expression must have at least one subexpression.

3.3 No Racket Boxes

Well, to be honest, you are allowed to use boxes in this assignment, just not for mutable structure fields. That is, your prior use of boxes–in the construction of recursive bindings–can continue to use boxes. However, you must implement mutable fields without using a mutable store.

Since you’re not allowed to use Racket’s boxes to represent the target language boxes, you’ll need to use the store monad. This means that functions like interp will have to produce OCFAE-Value computations, rather than plain OCFAE-Values. Your stores will be elements of the Store define-type, containing an immutable hash representing memory and a number representing the next unallocated store location.

You are absolutely not required to reclaim unused memory locations. In fact, don’t even think about it.

For this assignment, I am providing a support file contaning definitions. Save this file to the same directory as your project, and name it "p6-support.rkt". Then, in your project, add the line

  (require "p6-support.rkt")

This should allow you to use all of the definitions in this file.

Note that you must use the monadic forms, though you may choose whether or not to use the sdo abbreviation form.

As an example, here are two versions of the same piece of code; one uses sdo, and the other uses bind directly. Note the goofy indentation in the second example.

  (sdo [a <- (boggle-woggle)]
       [b <- (fub-fub a)]
       (brotz (+ b a))
       (lift (glognar (+ 9 a))))

  (bind (boggle-woggle) (lambda (a)
  (bind (fub-fub a) (lambda (b)
  (bind (brotz (+ b a)) (lambda (dontcare)
  (lift (glognar (+ 9 a)))))))))

3.4 NOTE FOR HANDING IN!

When you’re handing in, you’re going to have to replace

  (require "p6-support.rkt")

with

  (require p6/p6-support)

3.5 Using Monadic abstractions sanely

To use the monadic abstractions correctly, you have to "play by the rules." In particular:

3.6 Order of Evaluation

Order of evaluation is now observable. Order of evaluation should be first-to-last in applications and sequences, and the expressions should be evaluated as needed for switch expressions.

4 Syntax of OCFAE

The syntax of the OCFAE language with these additional features differs from that of the prior assignment only in that it has the new seq form and the three new primitives:

  OCFAE = num
  | string
  | true
  | false
  | {operator OCFAE *}
  | id
  | {switch CFWAE [CFWAE => CFWAE] * [else CFWAE]}
  | {with {{Pattern = OCFAE}*} OCFAE}
  | {withrec {id OCFAE} OCFAE}
  | {fun {Pattern *} OCFAE}
  | {OCFAE OCFAE *}
  | {new id OCFAE *}
  | {is-a? id OCFAE}
  | {seq OCFAE OCFAE *}

with

  Pattern = id
  | {id Pattern *}

and

  operator = +
  | -
  | *
  | /
  | and
  | or
  | equal?
  | <=
  | not
  | number?
  | string?
  | makebox
  | openbox
  | changebox!

where an id is not true, false, with, switch, else, fun, withrec, is-a?, new, seq, or one of the operator names

and num is a number.

If a fun or a with expression has duplicate identifiers, we consider it a syntax error. Therefore, such errors must be detected in parse-exp. For example, parsing the following expressions must signal errors:

  {with {{x 10} {x 20}} 50}
  
  {fun {x x} 10}
  
  {fun {weight {zebra name weight}} {equal? weight weight}}

...

5 Support Code

The monadic helper functions appear in the supporting file.

In addition to this, the functions you implement must adhere to the following template, without any changes.

  ; represents an expression
  (define-type OCFAE
    [num (n number?)]
    [bool (b boolean?)]
    [str (s string?)]
    [unop (op symbol?) (arg OCFAE?)]
    [binop (op symbol?) (lhs OCFAE?) (rhs OCFAE?)]
    [varref (name symbol?)]
    [switch (val OCFAE?) (clauses (listof SClause?)) (elseval OCFAE?)]
    [fun (params (listof Pattern?)) (body OCFAE?)]
    [withrec (name symbol?) (rhs OCFAE?) (body OCFAE?)]
    [app (f OCFAE?) (args (listof OCFAE?))]
    [newexp (name symbol?) (fields (listof OCFAE?))]
    [is-a (name symbol?) (arg OCFAE?)]
    [seq (exps (listof OCFAE?))])
  
  ; represents a 'switch' clause
  (define-type SClause
    [clause (patval OCFAE?) (result OCFAE?)])
  
  ; represents a pattern
  (define-type Pattern
    [idPat (name symbol?)]
    [objPat (name symbol?) (subPats (listof Pattern?))])
  
  ; represents a possible result of evaluation
  (define-type OCFAE-Value
    [numV (n number?)]
    [boolV (b boolean?)]
    [strV (s string?)]
    [closureV (params (listof Pattern?))
              (body OCFAE?)
              (env hash?)]
    [objectV (name symbol?)
             (fields (listof OCFAE-Value?))]
    [boxV (loc number?)])
  
  ; An environment is represented as a hash mapping symbols
  ;  to (racket) boxes containing OCFAE-Values
  
  ; represents a store containing a hash and the next unused address
  (define-type Store
    [sto (memory (and/c immutable? hash?)) (next-loc number?)])
  
  ; parse-exp : s-exp -> OCFAE
  ; Consumes an s-expression and generates the corresponding OCFAE
  (define (parse-exp sexp)
    ...)
  
  ;  This procedure interprets the given OCFAE and produces a result
  ;  in the form of a function that accepts a Store and produces
  ;  a OCFAE-Value. paired with a new store.
  ;  interp : OCFAE? hash? -> (OCFAE-Value? computation)
  (define (interp expr env)
    ...)