First-order Functions, CSC430, Winter 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 "IKEU". 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 "IKEU" will be considered to be an error in your implementation.

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

Extend your parser and interpreter from the previous assignment to handle multiple arguments to function calls.

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

3.1 Functions with 0 or more arguments

Start with the interpreter with 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,

{fundef area {w h} : {* w h}}

defines a function that takes two arguments, while

{fundef 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.2 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 '{{fundef f {x y} : {+ x y}}

{fundef main {} : {f 1 2}}}))

3)

(check-equal? (interp-fns

(parse-prog '{{fundef f {} : 5}

{fundef main {} : {+ {f} {f}}}}))

10)

(check-exn #px"wrong arity"

(λ ()

(interp-fns

(parse-prog '{{fundef f {x y} : {+ x y}}

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

Remember that in Rcaket, 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))

4 EBNF

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

where an id is not +, - , *, /, fn, leq0?, then, else, 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

As always, this sequence of steps is just one possible way of getting things done.

Here’s what I think might work.

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