Assignment 5, CSC430, Spring 2008

1 Guidelines

1.1 Contracts & Test Cases

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

• A commented header line 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.

• A commented contract line that gives the types of the inputs and the output. The contract should have the form <in-type> ... -> <out-type>. So, for instance, a numerical square function might have the contract line:

    ; number -> number

• Test cases. A function without test cases is incomplete. Write the test cases first, please.

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 Scheme to be a bug in your code.

For example, Scheme signals a "divide by zero" error if you attempt to evaluate (/ 1 0). Since we use Scheme’s division function to implement division in CFWAE, you may be tempted to leave it to Scheme to signal division by zero errors for you. However, you must signal the error yourself by explicitly testing for division by zero before calling Scheme’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 CFWAE, 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

NOTE: For this assignment, you must develop your solutions using the Programming Languages: Application and Interpretation: Pretty Big PLAI Scheme language level. Your test cases must use the (test ...) or (test/exn ...) form.

Your solution should take the form of a single file. Solve each problem separately, ands 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 with mutation.

3.1 Laziness?

This assignment’s interpreter can’t be lazy. Laziness doesn’t play nice with mutation. 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 recfun form. It binds a (possibly recursive) function in the environment, and then evaluates the body. Here’s a simple example:

{recfun {countDown {x} {if {= x 0} 0 {countDown {- x 1}}}}

{countDown 13}}

This form combines the rec form with the fun form. As in lecture, the environment contained in the newly formed closure must contain the binding for the closure itself. Initially, you may use a box (as discussed in class) to represent this circular binding.

Before handing in the assignment, though, you’ll have to adapt the implementation to use locations rather than a box. This won’t make sense until you’ve done the rest of the assignment, so you can revisit these instructions later.

3.3 Objects

The assignment requires you to implement objects as we did in class. Specifically, you must implement the new form and pattern-matching in parameters. Here are some examples:

{new name "Herbert" "Simon"}

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

The first of these has two fields, the second has three (title, author, year of publication). Note: It’s true, your language doesn’t have strings. But the examples are easier to read and write if we temporarily imagine that it does. You are not required to add strings to your language.

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.

3.4 Mutation

Whoa, this is where everything gets crazy. You’ll have to make the following changes: environments will now bind names to locations in the store (numbers), and the fields of objects will all be locations in the store. Also, the interpreter will now have to return a new store along with a value as the result of evaluating every expression. We’ll bind these two together as a Value*Store.

There’s also a new form, set, for mutation, and another form, seq, for sequencing (like a semicolon in C or Java). This allows you to mutate the nth field of an object (using zero-based indexing), like this:

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

{seq {set book myBook 2 1997}

{with {{book a b c} myBook}

c}}}

This will evaluate to 1997, because the date was altered by the use of set.

Note that the grammar specified above requires that a sequence contains at least one subexpression.

Adding mutation to the language will require you to thread the store through the computation, as described in the book and in lecture.

Finally, note that you will need to evaluate all subexpressions left-to-right. So, for instance, in the application {{f 6} {g 5}}, you must evaluate the {f 6} term before the {g 6} term. Before we had mutation, there was no way to observe this difference. Now, there is.

4 Syntax of MOCFAE

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

MOCFAE		=		num
		|		true
		|		false
		|		{+ MOCFAE MOCFAE}
		|		{- MOCFAE MOCFAE}
		|		{* MOCFAE MOCFAE}
		|		{/ MOCFAE MOCFAE}
		|		{and MOCFAE MOCFAE}
		|		{or MOCFAE MOCFAE}
		|		{not MOCFAE}
		|		{= MOCFAE MOCFAE}
		|		id
		|		{if MOCFAE MOCFAE MOCFAE}
		|		{with {{Param MOCFAE}*} MOCFAE}
		|		{recfun {id {Param *} MOCFAE} MOCFAE}
		|		{fun {Param *} MOCFAE}
		|		{MOCFAE MOCFAE *}
		|		{new name MOCFAE *}
		|		{set name MOCFAE num MOCFAE}
		|		{seq MOCFAE MOCFAE *}

with

Param		=		id
		|		{name Param *}

... where an id is not true, false, +, -, *, /, and, or, not, =, with, if, fun, recfun, new, set, or seq

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. For example, parsing the following expressions must signal errors:

{with {{x 10} {x 20}} 50}

{fun {x x} 10}

...

5 Support Code

Your code must adhere to the following template, without any changes.

Note that for this assignment, you probably won’t want to just drop this block into your code. Instead, make changes incrementally. Don’t use this code verbatim until you’re adding mutation.

; represents an expression

(define-type MOCFAE

[num (n number?)]

[bool (b boolean?)]

[binop (op procedure?) (lhs MOCFAE?) (rhs MOCFAE?)]

[id (name symbol?)]

[ifexp (tst MOCFAE?) (then MOCFAE?) (els MOCFAE?)]

[fun (params (listof Pattern?)) (body MOCFAE?)]

[recfun (name symbol?) (params (listof Pattern?)) (funbody MOCFAE?) (body MOCFAE?)]

[app (f MOCFAE?) (args (listof MOCFAE?))]

[newexp (name symbol?) (fields (listof MOCFAE?))]

[set (name symbol?) (target MOCFAE?) (index number?) (new-val MOCFAE?)]

[seq (exprs (listof MOCFAE?))])

; represents a pattern

(define-type Pattern

[idPat (name symbol?)]

[objPat (name symbol?) (subPats (listof Pattern?))])

; represents an environment during evaluation

(define-type Env

[mtEnv]

[anEnv (name symbol?) (location number?) (env Env?)])

; represents a possible result of evaluation

(define-type MOCFAE-Value

[numV (n number?)]

[boolV (b boolean?)]

[closureV (params (listof Pattern))

(body MOCFAE?)

(env Env?)]

[objectV (name symbol?)

(locations (listof number?))])

; represents a store mapping locations to values

(define-type Store

[mtSto]

[aSto (location number?) (value MOCFAE-Value?) (store Store?)])

; represent a value and a store paired

(define-type Value*Store

[v*s (value MOCFAE-Value?) (store Store?)])

; parse : s-exp -> MOCFAE

; Consumes an s-expression and generates the corresponding MOCFAE

(define (parse sexp)

...)

; This procedure interprets the given MOCFAE and produces a result

; in the form of a MOCFAE-Value (either a boolV, a closureV, a numV, or an objectV)

; and a store

; interp/inner : MOCFAE-Value? Env? Store? -> Value*Store?

(define (interp expr env store)

...)