Assignment 2, CSC430, Winter 2019
1 Guidelines
1.1 Handling Errors
1.2 Mutation
2 Rudimentary Interpreter
2.1 Binary arithmetic operators
2.2 Functions with 0 or more arguments
2.3 Main
2.4 Conditionals
2.5 A Nice Big Test Case
3 EBNF
4 Interface
5 Roadmap
6 Acknowledgments
7.2.0.5

Assignment 2, CSC430, Winter 2019

1 Guidelines

For this and all remaining assignments, every function you develop must come with the following things:

For this assignment, you must develop your solutions using the typed/racket language. You might be interested in these Hints on Using Typed Racket in CSC 430.

Your test cases must use the check-equal?, check-=, or check-exn forms.

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.

1.1 Handling Errors

All of your error messages must start with the string "ZHRL: ". Essentially, this allows my test cases to distinguish errors correctly signaled by your implementation from errors in your implementation. To be more specific: any error message that doesn’t contain the string "ZHRL" will be considered to be an error in your implementation.

1.2 Mutation

There’s no need for mutation in any of the first three assignments in this class. Don’t mutate bindings, and don’t mutate structure fields. Yikes!

2 Rudimentary Interpreter

Write a parser and interpreter for the eager ZHRL2 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 ZHRL2 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. Your interpreter should use a lookup table (hash table or function) to map operator names to their meanings. Having a single rule like this 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,

{func {area w h} {* w h}}

defines a function that takes two arguments, while

{func {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 (Sexp) and produces an ExprC value. Also, you must update the parse-fundef function that takes one quoted define form and produces a FundefC value.

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.

Your language must be eager. That is, it must evaluate arguments to values before they are substituted into function bodies.

Your implementation should use substitution to replace arguments with values, as described in chapter 5. Do not use environments in this assignment. That will be the next one....

2.3 Main

Your programs must consist of a (bracketed) list of functions, where exactly one is named main, and it has no parameters. Evaluating a program means applying the main function.

Some examples:

(check-equal? (interp-fns
       (parse-prog '{{func {f x y} {+ x y}}
                     {func {main} {f 1 2}}}))
      3)
 (check-equal? (interp-fns
        (parse-prog '{{func {f} 5}
                      {func {main} {+ {f} {f}}}}))
       10)
 (check-exn #px"wrong arity"
            (λ ()
              (interp-fns
               (parse-prog '{{func {f x y} {+ x y}}
                             {func {main} {f 1}}}))))

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 '{func {f x x} x}) could report a "bad syntax" error, while (parse-fundef '{func {f x y} x}) might produce a FundefC value.

Remember that racket provides the following useful function:

2.4 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.5 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 ZHRL2 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 ZHRL2 language with these additional features can be captured using EBNF notation ([1]):

  ZHRL2 = num
  | {+ ZHRL2 ZHRL2}
  | {- ZHRL2 ZHRL2}
  | {* ZHRL2 ZHRL2}
  | {/ ZHRL2 ZHRL2}
  | {id ZHRL2 ...}
  | {ifleq0 ZHRL2 ZHRL2 ZHRL2}
  | id
  DEFN = {func {id id ...} ZHRL2}

where an id is not +, - , *, /, func, or ifleq0. You should turn in a single Racket program containing all of the code needed to run your parser and interpreter.

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

4 Interface

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

procedure

(parse s)  ExprC

  s : s-expression
Parses an expression.

procedure

(parse-fundef s)  FundefC

  s : s-expression
Parses a function definition.

procedure

(parse-prog s)  (listof FundefC)

  s : s-expression

procedure

(interp-fns funs)  Real

  funs : (listof FundefC)
Interprets the function named main from the fundefs.

procedure

(interp exp funs)  Real

  exp : ExprC
  funs : (listof FundefC)
Interprets the given expression, using the list of funs to resolve applications.

procedure

(top-interp fun-sexps)  Real

  fun-sexps : s-expression
Combines parsing and evaluation. Here’s the code you should probably use for this function:

(: top-interp (Sexp -> Real))
(define (top-interp fun-sexps)
  (interp-fns (parse-prog 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 3 code. Copy the given definition of top-interp, 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-interp 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 structure. 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!