Assignment 3: Case
Due: Thursday, June 11, 11:59PM
Starter code: extort-plus.zip
The goal of this assignment is to extend the language developed in Extort: when errors exist to add a new form of control flow expressions, case-expressions, and to bring the features developed in Dupe+ to Extort.
Note: you will need to carry forward all of the changes you implemented for Dupe+ and adapt them to the setting of Extort.
Extort+
The Extort+ language extends Extort: when errors exist in the follow ways:
Case expressions
The following new case form is included in Extort+:
(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 Extort means integer, boolean, and character literals.
As a convenience, case expressions can omit the else clause, but the parser will insert a final else clause that evaluates to (void), so both the interpreter and compiler may always assume the presence of an else-clause. (The same convenience has been extended to cond by the parser.)
Implementing Extort+
You must extend the interpreter and compiler to implement Extort+. Use the starter code in extort-plus.zip, which is based on the Extort: when errors exist language we studied in class.
You may use any a86 instructions you’d like.
Parsing Extort+
The AST type and parser for Extort+ are given to you.
Here’s the AST definition for the added primitives, cond, and case:
; type Expr = ... ; | (Cond [Listof Expr] [Listof Expr] Expr) ; | (Case Expr [Listof [Listof Datum]] [Listof Expr] Expr) ; type Datum = Integer | Boolean | Character ; type Op = ; ... ; | 'abs | '- | 'not (struct Cond (cs es el) #:prefab) (struct Case (e ds cs el) #:prefab)
There are two new kinds of expression constructors: Case and Cond. The Cond form is unchanged from Dupe+. A Case AST node contains four 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 lists of datums, an equal length list of expressions, and an else-clause expression. A datum is either an integer, a boolean, or a character, i.e. it includes all of the literals allowed in Extort.
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 (list 4)) (list (Lit 1)) (Lit 2)),
(case 4 [(4 5 6) 1] [else 2]) parses as (Case (Lit 4) (list (list 4 5 6)) (list (Lit 1)) (Lit 2)), and
(case 4 [(4 5 6) 1] [(#t #f) 7] [else 2]) parses as (Case (Lit 4) (list (list 4 5 6) (list #t #f)) (list (Lit 1) (Lit 7)) (Lit 2)).
Implementing case
Implement the case expression form as described earlier. To do this, you should:
Study syntax/ast.rkt to understand how this new form of expression is represented.
Add test cases to test/define-tests.rkt. These will be tested with both the interpreter and compiler.
Update interpreter/interp.rkt to correctly interpret case expressions.
Bring forward all of the changes you made to the interpreter from Dupe+.
Test your interpreter with raco test test/run-interp-tests.rkt.
Make examples of case-expressions and potential translations of them to assembly.
Update compiler/compile.rkt to correctly compile case expressions based on your examples.
Bring forward all of the changes you made to the compiler from Dupe+.
Test your interpreter with raco test test/run-compile-tests.rkt.
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 extort-plus directory to create a zip file containing your work and submit it to Gradescope.