Assignment 2, CSC430, Winter 2014

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 MAFL language ([1]) we discussed in class. 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.

Once you’ve written and tested the parser and interpreter for MAFL, extend the language with these features:

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,

{define {area w h} {* w h}}

defines a function that takes two arguments, while

{define {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 '{define {f x y} {+ x y}})))

3)

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

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

10)

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

(list (parse-fundef '{define {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 '{define {f x x} x}) could report a "bad syntax" error, while (parse-fundef '{define {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.

3 EBNF

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

where an id is not +, - , *, or /. 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 or more symbols to its left can be repeated zero or more times.

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

4 Acknowledgments

Thanks to Matthew Flatt for large portions of this assignment!