Assignment 3, CSC430, Fall 2023

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.

• A type declaration (possibly inline), specifying the input and output types.

• Test cases. A function without test cases is incomplete. Write the test cases first, please.

For this assignment, you must develop your solutions using the typed/racket language. If you haven’t seen them, you might be interested in these Hints on Using Typed Racket in CPE 430.

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

Your solution should take the form of a single file.

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 contain the string "PAIG". 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 "PAIG" will be considered to be an error in your implementation.

Additionally, your error messages should be actually helpful. Since you are the primary consumer of your own error messages, making these error messages good in the first place should reduce your overall development time. There are two parts to this: first, the error message should include text that actually indicates what the programmer did wrong. Second, include the text of the user’s program, so they (actualy you) can figure out how to fix it. See lab 3 for an example of how to do this. (Apologies in advance if I renumber the labs and fail to update this paragraph....)

1.2 Progress Toward Goal comment

Graders are happier when they know what to expect. Your final submission should start with a short one- or two-line comment indicating how far you got through the project. Ideally, this would just be: “Full project implemented.” But if you only implemented, say, squazz and blotz, and didn’t get to frob or dringo, please indicate this in the comment, so that we don’t spend all our time searching for bits that aren’t there.

2 Mutation

There’s no need for mutation in any of the first five assignments in this class. Don’t mutate bindings, and don’t mutate structure fields. You don’t have to use hash tables at all, but if you do use hash tables use immutable hash tables only; no hash-set!.

3 Rudimentary Interpreter

Write a parser and interpreter for the eager PAIG3 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 PAIG3 language must include the following:

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

3.2 Functions with exactly one argument

For this assignment, your interpreter should support functions and applications with exactly one argument.

For example,

{fun {addone (x)} {+ x 1}}

defines the function that adds one to a number, while

{addone (23)}

calls that function with 23.

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 in the future....

3.3 Main

Your programs must consist of a (bracketed) list of functions, where no two have the same name, where one is named main, and it has exactly one parameters named init. Evaluating a program means applying the main function to the argument 0

A simple example:

(check-equal? (interp-fns

(parse-prog '{{fun {f (x)} {+ x 14}}

{fun {main (init)} {f (2)}}}))

16)

3.4 Conditionals

The language will support a simple ifleq0? construct ("if less or equal to zero"), 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 leq0? expression that returns (- x 1) unless x is already zero:

{ifleq0? x :

x

else:

{- x 1}}

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

4 EBNF

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

where an id is not +, - , *, /, fun, ifleq0?, :, or else:. 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:

• ? 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.1 Extra Parens

Like Racket (and Scheme and other "parenthesized" languages), parentheses are never used "just for grouping" in this assignment or any of the other language implementation assignments; they always change the meaning of the program. Just as in Racket, the expression x is a totally different expression from (x). As a result, your parser should never just discard parentheses.

5 Interface

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

procedure (parse-prog s) → (listof FundefC)

s : s-expression

(: top-interp (Sexp -> Real))

(define (top-interp fun-sexps)

(interp-fns (parse-prog fun-sexps)))

6 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. Take out the ExprS, you won’t need it for this assignment. Update your parse function to target ExprC directly.

Write a parser for expressions. You should probably use the match patterns that you practiced in Lab 3. it should map Sexps to the ExprC definition of section 5. It should signal an error, by calling error, when the input is not formed. Make sure the error output is useful to programmers: you are the programmer!

Next, bring in the interpreter from the textbook translation.

Then, 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. You should be able to copy it from the text, more or less. Next, write a parser that accepts fundef s-expressions and outputs FundefC’s. Then, add the 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.

7 Acknowledgments

Thanks to Matthew Flatt for large portions of this assignment!