Assignment 3, CSC430, Spring 2015

1 Goal

Implement an interpreter for a higher-order language including booleans and local variable bindings.

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 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 class, 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.

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 Extended Interpreter

Write a parser and interpreter for the language we’ve discussed in class including higher-order functions and environments, extended with the language features described below. Your interpreter should have eager application semantics and use environments. Call the new language EXCR3 .

3.1 Syntax of EXCR3

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

... where an id is not true, false, with, if, fn or one of the operator names.

3.2 Syntax Notes:

Note that the last rule is the one for applications. Also, note that all of the ‘...’s are to be read as *zero* or more. That is, zero is legal in these cases.

4 Getting it working

Before adding booleans, conditionals, or with, you need to adapt your base evaluator so that it works with environments and higher-order functions, and has a serialize function that renders values as strings.

What follows is my recommended iterative development strategy; in the following, I try to keep the evaluator and its test cases working at every step, so that you don’t spend too much time wandering in the wilderness of broken code.

First, define the type of environments, then add it to the list of arguments to interp, then adapt varrefs so they perform lookup. Finally, alter the rule for applications so that it adds things to the environment rather than performing substitution. The code should work on a consistent set of test cases all through this transition. Finally, you can remove subst.

4.1 Booleans and comparisons

Next, we’re going to add new kinds of values to the language, and we can begin by adding booleans. Once again, iterative development is your friend. First, add a Value define-type, initially including only numbers and booleans. Then adapt the evaluator so that it returns a Value rather than a number. Note that you’ll have to update your binops so that they can deal with Values returned by interp rather than simple numbers (the textbook covers this).

Next, you’ll need true and false constants in the expr definition, along with parse rules and eval rules (that just evaluate to the corresponding booleans).

In order to make our real boolean conditionals useful, we want some way to compare numbers. The simplest useful operation is <= (using it, we can model all of the other numeric comparison operators). Add the <= operator to your set of binops.

In addition, let’s add an eq? operator. This operator should return true if given two booleans with the same value, or two numbers with the same value. If the operands are different kinds of value or if they’re both function values, this operator should return false (this is not an error, it just returns false).

4.2 Conditionals

Now that we have booleans, we can change the icky awful ifleq0 into a nice clean if.

First, rewrite your test cases so that they use the new boolean-producing operators, and then modify your expression definition to change ifleq0 into if, updating the parser and the evaluator (slightly). The if expression should signal an error if its test expression does not produce a boolean value.

4.3 Function Values (closures)

Next, add closures to the set of values. This is pretty much straight out of the book.

At this point, you can add the serialize function. It should map values to strings, and will be critical for *me*, to run my tests on your code. It should turn the value representing the number 14 into the string "14", using to-string. For every function value, it should simply return the string "#<procedure>". Note that while this is (probably) sufficient to allow me to test your code, you should *not* write all of your test cases using serialize; it throws out a lot of data, and makes debugging a lot harder.

Once you’ve got this working, you can try sticking some function values into the initial environment passed to the evaluator. Then, update the exprC definition so that the first position in an application is an arbitrary expression (exprC) rather than a symbol, and update the evaluation rule for application so that the first position is interpreted, rather than just being looked up. At this point, your test cases with function definitions will be ignoring the list of functions, and just looking in the environment for their definitions. Those definitions will all have to be supplied manually by your test cases, though, because you don’t have any way of defining them in the code. Now, you can yank the top-level funs argument to the interpreter, because it’s not being used.

Next, you need to make it possible to define functions in the program; do this by adding a function literal form (the lamC form of the book), and the accompanying parser and interpretation rules. At this point, you should be able to specify test cases that include literal functions, and apply them to arguments.

5 With

As you know, local variable definitions are incredibly useful. As Shriram points out, though, you can get them "for free", by desugaring them into applications. Specifically, you can change

{with {z = {+ 9 14}}

{y = 98}

{+ z y}}

into

{{fn {z y} {+ z y}}

{+ 9 14}

98}

You must add this with syntax to your parser. it will make your test cases read much more nicely.

5.1 Error-checking in Parse

Your parser should detect all terms that fail to match the EBNF, and signal an error. For instance, a function definition with a parameter named ’+’ should cause an error. Also, for this assignment, you must signal errors for functions where more than one parameter has the same name.

5.2 Error-checking in Interp

Your interpreter must signal an error for "type-like" errors; application of a non-closure, calling an arithmetic primitive with a non-number, applying a function to the wrong number of arguments, using a conditional with a non-boolean test.

6 Interface

Make sure that you include the following functions, and that they match this interface:

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

(serialize (interp (parse s) empty-env)))

Your body can be different if you really want, but the types must match these.