Assignment 3, CSC430, Spring 2014

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

3.1 Syntax of BOZOR3

The concrete syntax of the BOZOR3 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 each of 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. You can start with your solution to assignment 2, or my sample solution.

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.

Next, you need to get rid of separate top-level fundefs. Once again, iterative development is your friend. First, add a Value define-type, including both numbers and function values. 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).

At this point, 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. (In fact, you now have a turing-complete language, for the first time in the class.)

5 Booleans and Conditionals

In order to make our language more useful, we want to add booleans and conditionals.

Quite frankly, this will probably be way less work than the earlier part. Add a boolean value to the set of Values and extend serialize to handle it, returing "true" and "false" respectively. Then, add a boolean literal expression to the exprC definition, and an evaluator rule that just changes literal expressions into literal values. Finally, add a rule to the parser so that the identifier true gets parsed as the boolean literal corresponding to true, and do likewise for false.

Next, let’s add conditionals. A simple if will suffice. First, add it to the exprC definition, then add a rule for evaluation. Finally, add a rule for it to the parser, following the concrete syntax specified by the EBNF below.

6 Comparison

In order to make our 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.

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

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

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

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