Assignment 4: Let there be (Many) Variables

Due: Tuesday, Oct 19th at 11:59PM EST

The goal of this assignment is to extend a compiler with binding forms and primitives that can take any number of arguments.

You are given a zip file on ELMS with a starter compiler similar to the Fraud language we studied in class. You are tasked with:

• incorporating the language 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

• adding a let*-binding form to the language to allow back-references.

From Dupe+ to Fraud+

Implement the abs, unary -, and not operations and the cond and case forms 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.

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.

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 interpreter and compiler to behave similarly.

The following file have already been updated for you:

• ast.rkt

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

The following file have already been updated for you:

• ast.rkt

• parse.rkt

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.

The following file have already been updated for you:

• ast.rkt

• parse.rkt

HINT: what would a lazy compiler writer do?

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.

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 compile.rkt, interp.rkt, and interp-prim.rkt files for grading, so make sure all your work is contained there! Note the lack of ast.rkt, parse.rkt, etc. - 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!