Assignment 2, CSC430, Spring 2015

1 Guidelines

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.

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

Write a parser and interpreter for the EXCR2 language described below. The textbook can be of great assistance in this part of the assignment; it provides the beginnings of a parser, an abstract syntax datatype and an interpreter.

The EXCR2 language must include the following:

2.1 Binary arithmetic operators

In place of having separate rules for + and *, define a single syntactic rule for all binary arithmetic operators. Parse these into a binop datatype variant. Define a table that maps operator names (symbols) to actual functions (Racket procedures) that perform the corresponding operation. (This table may take the form of a function, a hash table, a list, or something else.) Having a single rule like this, accompanied by a table, makes your language easier to extend: once you have modified your parser and interpreter once to support binary operators, you won’t need to touch either one to add any number of new ones. To demonstrate this, define multiplication and division (using * and / to represent them in the language’s concrete syntax).

2.2 Functions with 0 or more arguments

Start with the interpreter with functions, and extend the implementation to support multiple or zero arguments to a function, and multiple or zero arguments in a function call.

For example,

{fn area {w h} {* w h}}

defines a function that takes two arguments, while

{fn five {} 5}

defines a function that takes zero arguments. Similarly,

{area 3 4}

calls the function area with two arguments, while

{five}

calls the function five with zero arguments.

Since you must change the ExprC datatype, and since different people may change it in different ways, you must update the parse function, which accepts an S-expression and produces an ExprC value. Also, you must update the parse-fundef function that takes one quoted define form and produces a FunDefC value.

Note: The fact that quoting an identifier produces a symbol instead of an s-exp is inconvenient, because it means that (parse 'x) doesn’t work. You could use (parse (symbol->s-exp 'x)), but a more readable trick is to use a backquote insted of a normal quote: (parse `x). A backquote always produces an s-exp. It also allows an escape back out of quoting, but we don’t need that feature, yet.

At run-time, a new error is now possible: function application with the wrong number of arguments. Your interp function should detect the mismatch and report an error that includes the words "wrong arity".

Some examples:

(test (interp (parse '{f 1 2})

(list (parse-fundef '{fn f {x y} {+ x y}})))

3)

(test (interp (parse '{+ {f} {f}})

(list (parse-fundef '{fn f {} 5})))

10)

(test/exn (interp (parse '{f 1})

(list (parse-fundef '{fn f {x y} {+ x y}})))

"wrong arity")

A function would be ill-defined if two of its argument names were the same. To prevent this problem, your parse-fundef function can optionally detect this problem and report a "bad syntax" error. For example, (parse-fundef '{fn f {x x} x}) could report a "bad syntax" error, while (parse-fundef '{fn f {x y} x}) might produce a FunDefC value.

Remember that plai-typed provides the following useful function:

• map – takes a function and a list, and applies the function to each element in the list, returning a list of results. For example, if sexps is a list of S-expressions to parse, (map parse sexps) produces a list of ExprCs by parsing each S-expression.

2.3 Conditionals

The language will support a simple ifleq0 construct, with a test, a then, and an else. All three must be present. The expression evaluates to the ‘then’ cause if the test value is less than or equal to zero, and the ‘else’ clause otherwise

So, for instance, here’s an if expression that returns (- x 1) unless x is already zero:

{ifleq0 x

x

{- x 1}}

2.4 A Nice Big Test Case

Does this language make sense to you? The very first piece of code you write should be a program in the EXCR2 language. how about one that rounds numbers to the nearest integer? You’ll probably want to do this by repeated subtraction. Notice that this language supports recursion without any extra effort on your part.

3 EBNF

The syntax of the EXCR2 language with these additional features can be captured using EBNF notation ([1]):

where an id is not +, - , *, /, or ifleq0. You should turn in a single Racket program containing all of the code needed to run your parser and interpreter. Implement the function parse, which consumes an expression in the language’s concrete syntax and returns the abstract syntax representation of that expression. Also implement the function interp , which consumes an abstract syntax expression (as returned by the parse function) and returns a racket number.

[1] The textbook introduced you to BNF. An extension of this notation, called EBNF (Extended Backus-Naur Form), provides three additional operators:

• ? means that one or more symbols to its left can appear zero or one times.

• ... means that one symbol to its left can be repeated zero or more times.

• + means that one symbol to its left can appear one or more times.

4 Interface

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

(define (top-eval [s : s-expression] [fun-sexps : (listof s-expression)])

: number

(interp (parse s) (map parse-fundef fun-sexps)))

5 Roadmap

This assignment can be broken down into a bunch of smaller steps–as I’m sure most of you know, this is called "incremental development," and it has many advantages over the implement-everything-all-at-once approach. You can do this assignment in any order you like, but I’ll specify one possible order that you might do it in.

Start with your Lab 2 code. Copy the given definition of top-eval, and write a few test cases for it.

The simplest new piece is the conditional, ifleq0. Add the form to the ExprC datatype, and then add a stub result to your evaluator that just signals an error. Then, add a test for your parser on this form. Make sure it fails, and then add the code to the parser to make it succeed. Then, add a test for top-eval that uses the new form. Finally, add code to the evaluator to make it succeed. Yay!

To tackle the binop piece: First, add a binop variant to the expression define-type. Make sure it includes all of the information necessary to interpret a binop. Add a case to your evaluator that just signals an "unimplemented" error if one of these appears. Then, change your parser so that it outputs binops rather than the existing plus and mult forms. Next, replace the "unimplemented" rule with one that works. Finally, eliminate the plus and mult forms from the set of expressions.

To tackle the function piece: First, add a FundefC define type. To start with, copy it directly from the book, so that it only accepts one argument. Next, write a parser that accepts fundef s-expressions and outputs FundefC’s. Then, add the (single-argument) application form to your expression define-type. Add an "unimplemented" rule to your evaluator. Add a parse rule to handle applications. Update your interpreter so that it passes a list of fundefs along on every recursive call. Then, paste the code from the book to allow interpretation of single-argument applications.

Multi-arg functions! Now, update your definition of FundefC so that it can handle multiple arguments. It’s probably easiest just to comment out your whole evaluator for the moment. Update your fundef parser so that it can handle zero or more arguments. Finally, uncomment your evaluator, and implement multi-arg functions.

6 Acknowledgments

Thanks to Matthew Flatt for large portions of this assignment!