First-order Functions, CSC430, Fall 2024🔗

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 "AAQZ". 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 "AAQZ" 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 (actually 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 AAQZ3 language described below. The textbook provides a starting point for this work, along with the parser you assembled as part of lab 3.

The AAQZ3 language must include the features described by the following subsections.

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 0 or more arguments🔗

Start with the book’s interpreter for single-parameter 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,

{def area {(w h) => {* w h}}}

defines a function that takes two arguments, while

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

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

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 no parameters. Evaluating a program means applying the main function.

Some examples:

(check-equal? (interp-fns

(parse-prog '{{def f {(x y) => {+ x y}}}

{def main {() => {f 1 2}}}}))

3)

(check-equal? (interp-fns

(parse-prog '{{def f {() => 5}}

{def main {() => {+ {f} {f}}}}}))

10)

(check-exn #px"wrong arity"

(λ ()

(interp-fns

(parse-prog '{{def f {(x y) => {+ x y}}}

{def 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 must detect this problem and report a “bad syntax” error. For example, (parse-fundef '{def f {(x x) => x}}) could report a “bad syntax” error, while (parse-fundef '{def f {(x y) => x}}) might produce a FundefC value.

Remember that in Racket, you can transform elements of a list using the built-in map function, or by using the for/list form, as e.g.

(for/list : (Listof ExprC) ([sexp list-of-sexps])

(parse sexp))

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 decrements x, but only if it is positive.

{ifleq0? x

x

{- x 1}}

4 EBNF🔗

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

where an id is not +, - , *, /, def, ifleq0?, or =>. 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, that accepts an s-expression and returns an ExrpC.

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.

Ready for the next part?

Now, extend the data definition for your application (function call) expression, so that it can contain multiple arguments.

Update your interpreter so that (for now) it just signals an error if it encounters an application that doesn’t have exactly one argument.

Then, update your parser to handle zero or more arguments for a function call. Remember to start with the test cases. Also, note that the application form can now "collide" with the other forms, in that an application can look a lot like a binop or a conditional; you’ll have to resolve these conflicts.

I think the next step would be to update your function definition AST node to allow multiple parameters.

Next, update your interpreter as before to simply signal an error when it encounters a function that doesn’t have exactly one parameter.

Then, as before, update your function parser to correctly handle multiple parameters. Again, start with the test cases!

Finally, it’s time to tackle the interpreter. All of the interesting updates will occur in the application rule, and in various helper functions. Proceed slowly, and make sure you know what a helper function is supposed to do (that is, write tests first!) before implementing it.