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 Laziness?
3.2 Recursive Functions
3.3 Removing List Primitives
3.4 Objects
4 Syntax of OCFAE
5 Support Code

Assignment 5, 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 an OCFAE, 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 recursive first-class functions, and structures.

3.1 Laziness?

This assignment’s interpreter should not be lazy. Make it eager again, and make sure that all of your old test cases pass before beginning the rest of the assignment.

3.2 Recursive Functions

For this assignment, you must implement recursive functions using the withrec form. It binds a (possibly recursive) function in the environment, and then evaluates the body. Here’s a simple example:

  {withrec {countDown {fun {x} {switch x [0 => 0] [else {countDown {- x 1}}]}}}
    {countDown 13}}

As in lecture, the environment contained in the newly formed closure must contain the binding for the closure itself. You may use a box (as discussed in class) to represent this circular binding.

Note that you are not required to extend the withrec form to handle multiple bindings. You might like to think about how this might work....

3.3 Removing List Primitives

The pair and related forms are now redundant, as they can be implemented using objects. Remove all of them, including all of the related operators.

3.4 Objects

The assignment requires you to implement objects much as we did in class. Specifically, you must implement the new form and pattern-matching in parameters, along with a simple is-a? form that allows you to check the kind of an object.

Here are some examples:

  {new pair
    {new name "Herbert" "Simon"}
    {new book "The Sciences of the Artificial"
       {new name "Herbert" "Simon"}
       {+ 2 1994}}}

The pair and name objects have two fields, the book object has three.

When a function uses a structure pattern as a parameter, the names in the pattern are bound to the corresponding pieces of the object. So, if this function

  {fun {{book title auth date}} {someOtherFunction auth}}

... were called with the book described earlier, the body would be evaluated in an environment that bound title to the book’s first field, auth to the book’s second field, and date to the book’s third field. This function then calls someOtherFunction with the author. This assumes that somewhere else the function someOtherFunction is defined.

Your with form should also support patterns. This code can re-use the parsing code you develop for the fun parser.

Finally, you must support an is-a? form–much like Java’s–that determines whether an object is of a given "type"; more precisely, whether its name field matches the one specified in the form. So, for instance, the expression

  {is-a? book {new book "Harry Potter and the Beacon of Urgwurt"
                {new author "Julius K." "Growling"}
                2009}}

... should return true, whereas

  {is-a? book {new pair 3 4}}

... would return false.

4 Syntax of OCFAE

The syntax of the OCFAE language with these additional features can be captured with the following EBNF:

  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}

with

  Pattern = id
  | {id Pattern *}

and

  operator = +
  | -
  | *
  | /
  | and
  | or
  | equal?
  | <=
  | not
  | number?
  | string?

where an id is not true, false, with, switch, else, fun, withrec, is-a?, new, 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

Your code 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?)])
  
  ; 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?))])
  
  ; parse-exp : s-exp -> OCFAE?
  ;  consumes an s-expression and produces the corresponding
  ;  expression.
  (define (parse-exp sexp)
    ...)
  
  ;  This procedure interprets the given OCFAE and produces a result
  ;  in the form of an OCFAE-Value
  ;  interp : OCFAE? hash? -> OCFAE-Value?
  (define (interp expr env)
    ...)