Assignment 4: Case
Due: Thursday, October 2, 11:59PM
The goal of this assignment is to extend the language developed in Dupe+ with another new form of control flow expressions: case-expressions.
Note: you will need to carry forward all of the changes you implemented for Dupe+.
Dupe++
The Dupe++ language extends Dupe+ in the follow ways:
adding case.
Case expressions
The following new case form is included in Dupe++:
(case ev [(d1 ...) e1] ... [else en])
The case expression form is a mechanism for dispatching between a number of possible expressions based on a value, much like C’s notion of a switch-statement.
The meaning of a case expression is computed by evaluating the expression ev and then proceeding in order through each clause until one is found that has a datum di equal to ev’s value. Once such a clause is found, the corresponding expression ei is evaluated and its value is the value of the case expression. If no such clause exists, expression en is evaluated and its value is the value of the case expression.
Note that each clause consists of a parenthesized list of datums, which in the setting of Dupe means either integer or boolean literals.
For the purposes of this assignment, we will assume every case expression ends in an else clause, even though this is not true in general for Racket. The parser will reject any case-expression that does not end in else.
Implementing Dupe++
You must extend the interpreter and compiler to implement Dupe++. You are given a file dupe-plus-plus.zip on ELMS with a starter compiler based on the Dupe: a duplicity of types language we studied in class.
You may use any a86 instructions you’d like, however it is possible to complete the assignment using Cmp, Je, Jg, Jmp, Label, Mov, and Sub.
Parsing Dupe++
In the past, designing the AST type and structure definitions has given students some grief. Getting stuck at this point means you can’t make any progress on the assignment and making a mistake at this level can cause real trouble down the line for your compiler.
For that reason, let us give you a strong hint for a potential design of the ASTs and examples of how parsing could work. You are not required to follow this design, but you certainly may.
Here’s a potential AST definition for the added primitives, cond, and case:
; type Expr = ; ... ; | (Case Expr [Listof CaseClause] Expr) ; type CaseClause = (Clause [Listof Datum] Expr) ; type Datum = Integer | Boolean (struct Case (e cs el) #:prefab)
There is one new kind of expression constructor: Case. A Case AST node contains three things: an expression that is the subject of the dispatch (i.e. the expression that is evaluated to determine which clause should be taken), a list of case-clauses (not to be confused with cond-clauses), and an else-clause expression. Each case-clause, like a cond-clause, consists of two things. Hence we re-use the Clause structure, but with different types of elements. The first element is a list of datums, each being either an integer or a boolean.
Here are some examples of how concrete expressions are parsed into ASTs using this representation:
(case (add1 3) [else 2]) parses as (Case (Prim1 'add1 (Lit 3)) '() (Lit 2)).
(case 4 [(4) 1] [else 2]) parses as (Case (Lit 4) (list (Clause (list 4) (Lit 1))) (Lit 2)),
(case 4 [(4 5 6) 1] [else 2]) parses as (Case (Lit 4) (list (Clause (list 4 5 6) (Lit 1))) (Lit 2)), and
(case 4 [(4 5 6) 1] [(#t #f) 7] [else 2]) parses as (Case (Lit 4) (list (Clause (list 4 5 6) (Lit 1)) (Clause (list #t #f) (Lit 7))) (Lit 2)).
Implementing case
Implement the case expression form as described earlier. To do this, you should:
Study ast.rkt to understand how this new form of expression is represented.
Update interp.rkt to correctly interpret case expressions.
Make examples of case-expressions and potential translations of them to assembly.
Update compile.rkt to correctly compile case expressions based on your examples.
Bring forward all the changes you made for Dupe+.
Check your implementation by running the tests in test/all.rkt.
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
To submit, use make from within the dupe-plus-plus directory to create a zip file containing your work and submit it to Gradescope.