Assignment 4, 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:

• 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 CFAE, 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

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 make several changes to your solution for Program 3.

First, you must move from first-order to higher-order functions. This means that fun is now an expression, and that closureV is now a value. Correspondingly, there’s no separate ’parse-fun’ anymore, and that there’s no separate ’FunDef’ type.

Next, you must remove the with expression from the abstract syntax definition, as we did in class. Note that you must still support programs that use the with form; it’s just that your parser will now parse these into applications.

Thirdly, your interpreter must evaluate programs lazily.

Fourthly (and totally uninterestingly), I’m going to require the use of symbols in binops; it’s just easier to test.

3.1 Laziness

As we discussed in class, laziness does not change the meaning of programs–very much. In particular, things that evaluated to numbers in the eager interpreter will still evaluate to the same number, things that evaluated to functions should still evaluate to functions that "mean" the same thing, though they may appear a bit different. However, the lazy evaluator may produce answers for programs on which the eager evaluator ran forever or produced errors.

4 Concrete Syntax

Note the differences in the last two rules: functions are expressions, and the first position of an application does not need to be an identifier.

CFWAE		=		num
		|		string
		|		true
		|		false
		|		null
		|		{operator CFWAE *}
		|		id
		|		{switch CFWAE [CFWAE => CFWAE] * [else CFWAE]}
		|		{with {{id = CFWAE} *} CFWAE}
		|		{fun {id *} CFWAE}
		|		{CFWAE CFWAE *}

operator		=		+
		|		-
		|		*
		|		/
		|		and
		|		or
		|		equal?
		|		<=
		|		pair
		|		not
		|		number?
		|		pair?
		|		string?
		|		null?
		|		first
		|		rest

... where an id is not true, false, with, switch, else, fun, or one of the operator names.

5 Support Code

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

; represents a 'switch' clause

(define-type SClause

[clause (patval CFAE?) (result CFAE?)])

; represents an expression

(define-type CFAE

[num (n number?)]

[bool (b boolean?)]

[str (s string?)]

[mt]

[unop (op symbol?) (arg CFAE?)]

[binop (op symbol?) (lhs CFAE?) (rhs CFAE?)]

[varref (name symbol?)]

[switch (val CFAE?) (clauses (listof SClause?)) (elseval CFAE?)]

[fun (params (listof symbol?)) (body CFAE?)]

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

; environments are represented as immutable hash tables.

; represents a possible result of evaluation

(define-type CFAE/L-Value

[numV (n number?)]

[boolV (b boolean?)]

[strV (s string?)]

[mtV]

[pairV (first CFAE/L-Value?) (rest CFAE/L-Value?)]

[closureV (params (listof symbol?))

(body CFAE?)

(env hash?)]

[exprV (expr CFAE?)

(env hash?)

(cached box?)])

; parse-exp : expression -> CFAE

; This procedure parses an expression into a CFAE

(define (parse-exp sexp)

...)

; interp : CFAE hash? -> CFAE/L-Value?

; This procedure interprets the given CFAE and produces a result

; in the form of a CFAE/L-Value.

(define (interp expr env)

...)

; strict : CFAE/L-Value? -> CFAE/L-Value?

; This procedure accepts a value and returns a value that has the

; same meaning but is guaranteed not to be an exprV.

(define (strict val)

...)

6 Acknowledgments

Thanks to Shriram Krishnamurthi and Greg Cooper for these assignments.