Assignment 6, CSC430, Winter 2014

1 Goal

Extend the Assignment 4 evaluator to include strings, rec, and a type system.

2 Guidelines

2.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. The header lines must include input and output types.

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

2.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.

2.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.

3 The Assignment

This assignment will build on Assignment 4, with a few features from Assignment 5. As always, you are welcome to use my solution to the previous assignment as the basis for your work.

3.1 Strings

You must add strings to the language, as you did for Assignment 5. In fact, I strongly suggest that you simply copy your implementation of strings from Assignment 5.

Here’s the specification from Assignment 5, in case it’s useful:

Add strings to the language. This will require a new form of AST for string literals, a new form of string value, and a rule that evaluates string literals into string values.

In addition, you will need to extend the eq? function to work correctly on strings. Specifically, eq? must return true for two strings containing the same sequence of characters.

3.2 Recursion

Add recursion, using a rec form.

This one is not like Assignment 5. In particular, the desugaring strategy we used for Assignment 5 won’t play nicely with type-checking.

Instead, add a new expression form, and a new evaluation rule. The evaluation rule should follow these steps:

• Allocate a new location.

• Place a dummy value in that location (you could use the string "UNDEFINED").

• Bind the given name to the new location to make a new environment.

• Use the new environment to evaluate the expression in the rec.

• Put the new value into the new location.

• Return that new value.

Here’s a simple example of a use of rec :

{with {[f : {-> Num Num}] =

{rec [loop : {-> Num Num}]

{fun {[n : Num]} {if {<= 0 n} {loop {- n 1}} 34}}}}

{f 9}}

This will count from 9 down to 0, and then return 34.

3.3 Type Checking

Implement a type checker for your language. Note that since functions must now come annotated with types for arguments, you will need to have a type parser that parses types. For Heaven’s sake, don’t make this part of your expression parser. Note that the types of functions are extended to handle multiple arguments. So, for instance, the type {-> Num String Bool} refers to a function that accepts two arguments, a number and a string, and returns a boolean.

All type rules are standard. The rules for type-checking arrays should follow directly from the rules that we gave in class today for lists.

As in the book, arrays will be homogeneous; you cannot put a different type of thing into an array. In a similar way, you cannot mutate a variable to contain a different type.

3.3.1 Binops

Type-checking binops is more or less as you might expect. For instance, a + should receive two numbers, and will produce a number. The <= operator will take two numbers, and return a boolean.

The eq? operator is a bit different. In order to match its behavior in earlier assignments, the eq? operator should allow arguments of any type at all, and produce a boolean.

4 Suggested Implementation Strategy

Copy your string implementation from A5.

Copy your ’rec’ test cases from A5.

Add ’rec’ as an actual language form.

(Add ’rec’ to the set of keywords.)

Add a data definition for Types.

Add a parser for the language of types.

(Add ’->’ to the set of keywords.)

Add a definition for Type Environments

Add bogus type parameters to funs.

Add a type checker. Write your test cases first!

Add your type checker to top-eval. Type checking should happen after parsing and before evaluation.

5 Syntax of MAFL

A MAFL program consists of a single expression.

The concrete syntax of the MAFL expressions with these additional features can be captured with the following EBNFs.

... where an id is not true, false, with, if, fun, array, set, =, begin, rec, or one of the operator names.

6 Support Code

In order to allow me to test your code, you’ll need a top-level parse-evaluate-serialize function. Here’s one:

(define (top-eval [prog : s-expression]) : string

(local [(define ast (parse prog))]

(begin (type-check ast empty-tenv)

(serialize (v*s-v (interp ast empty-env empty-store))))))

Your body can be different if necessary, but the types must match these.