Assignment 4: Let there be (Many) Variables

Due: Tuesday, March 23rd at 11:59PM EST

The goal of this assignment is to extend a compiler with binding forms.

You are given a repository with a starter compiler similar to the Fraud language we studied in class. You are tasked with:

• incorporating the Con+ features you added in Assignment 3,

• extending the addition primitive to handle an arbitrary number of arguments,

• extending the let-binding form of the language to bind any number of variables, and

• extending the let-binding form of the language to allow back-references (let*).

From Con+ and Dupe+ to Fraud+

Implement the abs, unary - and not operations and the cond form from Assignment 3.

Unlike Assignment 3, the AST struct definitions and parsing code are provided. Study the relevant parts in ast.rkt and parse.rkt, understand what is different (if anything) from your own implementation and implement the relevant functionality in interp.rkt, interp-prim.rkt, and compile.rkt. You can start from your previous code, but you will need to update it to work for the structures provided. What’s essentially left for you to do is to make sure to correctly signal an error ('err) when these constructs are applied to the wrong type of argument.

While you’re at it, implement the predicates integer? and boolean? for checking the type of an argument, modeled by char? which was covered in the lectures.

In case it’s helpful, the formal semantics of cond are defined as:

You do not necessarily need to change all of these files depending on your design choices, but you shouldn’t alter any other files for Gradescope to work. If you feel that modifying a different file leads to a more natural/intuitive design - reach out! We’ll be happy to see a different approach and possibly extend our infrastructure to handle that.

From Binary to Variadic Addition

In Fraud, we implemented a binary operation for addition. However, Racket supports an arbitrary number of arguments for +. Your job is to extend the parser, interpreter, and compiler to behave similarly.

The following file have already been updated for you:

• ast.rkt

Generalizing Let

The Fraud language has a let form that binds a single variable in the scope of some expression. This is a restriction of the more general form of let that binds any number of expressions. So for example,

(let ((x 1) (y 2) (z 3))

e)

simultaneously binds x, y, and z in the scope of e.

The syntax of a let expression allows any number of binders to occur, so (let () e) is valid syntax and is equivalent to e.

The binding of each variable is only in scope in the body, not in the right-hand-sides of any of the let.

To capture that behavior, you need to implement:

• well-formed? ; Expr -> Boolean in parse.rkt, which consumes an expression and determines if it is a well-formed expression, i.e. it must be an instance of an Expr and each let expression must bind a distinct set of variables, while the bodies of the let-bindings only reference variables that are available in the context prior to the let. We have provided a new struct in ast.rkt, IllFormedError that is raised by the parser when the expression read fails the well-formed check.

• The parser, interpeter, and compiler functionality to correctly handle the generalized form of let. The compiler may assume the input is a well-formed expression.

Back-Referencing Let

Similar to let there is also let* that also binds any number of expressions. The difference is that previous bindings are available to subsequent bindings. For example,

(let* ((x 1) (y 2) (z (add1 y)))

e)

binds x to 1, y to 2, and z to 3 in the scope of e.

The syntax of a let* expression allows any number of binders to occur, so (let* () e) is valid syntax and is equivalent to e.

Update the parser, interpreter, and compiler to implement this different form of let-binding.

Testing

You can test your code in several ways:

• Using the command line raco test . from the directory containing the repository to test everything.

• Using the command line raco test <file> to test only <file>.

Note that only a small number of tests are given to you, so you should write additional test cases.

We provide a random-exprs.rkt module which provides exprs, a list of 500 randomly-generated closed expressions. You can use them freely to test various properties of your interpreter or compiler.

Submitting

You should submit on Gradescope. You should submit a zip file that has exactly the same structure that the stub contains. We will only use the parse.rkt, compile.rkt, interp.rkt, types.rkt and interp-prim.rkt files for grading, so make sure all your work is contained there! Note the lack of ast.rkt - part of assignment 3 was learning to design your own structures, part of assignment 4 is learning to work within the constraints of an existing design!