Assignment 4: Let There Be (Many) Variables

Part 1 Due: Wednesday, March 27, 11:59PM EST

Part 2 Due: Monday, April 8, 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.

This assignment consists of two parts. In Part 1 you must submit test programs written in the new Fraud+ language. In Part 2 you must implement Fraud+.

Part 1

For the first part of the assignment, you must write test programs in the Fraud+ language. These programs should be syntactically well-formed and must produce an answer when evaluated, i.e., these should be programs that either produce values or are expected to return ’err according to the Fraud semantics, but should not cause other errors. (The concept of an answer was introduced in Extort.)

You may write as many test programs as you like, but each program must be written in a separate file. You can put all of your files in one directory and compress ("zip") that directory to submit it. Each program should be formatted as usual for a standalone program, i.e., it should have the line #lang racket at the top and your program expression on a line below that.

Your submission will be graded by running each program on a set of Fraud+ compilers implemented by students in previous semesters, and your goal is to craft test programs that discover bugs in these implementations. Your programs will be run on many more compilers than you need to eliminate for a full score; this is so students do not all need to find the same bugs. Additionally, we do not know for certain that every compiler has a bug, so it may not be possible to eliminate all of them. (We randomly select some compilers that pass all of our tests so that students have the opportunity to write better tests than us. This has helped us find deficiencies in our compilers before.)

Part 2

For the second part of the assignment, you are given a fraud-plus.zip file on ELMS with a starter compiler similar to the Fraud language we studied in class.

Submitting

Submit a zip file containing your work to Gradescope. Use make submit.zip from within the fraud-plus directory to create a zip file with the proper structure.

We will not use your ast.rkt or parse.rkt files. Part of Assignment 3 was learning to design your own structures, but part of Assignment 4 is learning to work within the constraints of an existing design!

Testing

You can test your code in several ways:

• Using the command line raco test test/ from the fraud-plus directory to test everything.

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

Note that only a small number of tests are given to you, so you should write additional test cases. We recommend using your tests from Part 1!

Fraud+

The Fraud+ language extends the Fraud language we studied in class with some new features:

• The features added in Assignment 3, namely:

  • abs, -, and not

  • cond

  • case

• New primitives integer? and boolean?.

• An extended + that accepts any number of arguments.

• An extended let that can bind multiple variables at once.

• Back-referencing let* that can bind multiple variables at once.

From Dupe+ to Fraud+

Implement the abs, unary -, and not operations and the cond and case forms from Assignment 3 by modifying interp.rkt, interp-prim.rkt, compile.rkt, and compile-ops.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 the char? predicate that was covered in the lectures.

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.

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.

Back-Referencing Let

Similar to let, there is also let* that can also bind any number of expressions. The difference is that previous bindings are available in the right-hand sides of 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.

HINT: Think about what a lazy compiler writer would do.