Assignment 3: Primitives, conditionals
Due: Thursday, September 25, 11:59PM
The goal of this assignment is to extend the language developed in Dupe: a duplicity of types with some simple unary numeric and boolean operations and a new form of control flow expressions: cond-expressions.
Dupe+
The Dupe+ language extends Dupe in the follow ways:
adding new primitive operations,
adding cond.
Primitives
The following new primitves are included in Dupe+:
Conditional expressions
The following new conditional form is included in Dupe+:
(cond [e-p1 e-a1] ... [else e-an])
A cond expression has any number of clauses [e-pi e-ai] ..., followed by an “else” clause [else e-an]. For the purposes of this assignment, we will assume every cond expression ends in an else clause, even though this is not true in general for Racket. The parser will reject any cond-expression that does not end in else.
The meaning of a cond expression is computed by evaluating each expression e-pi in order until the first one that does not evaluate to #f is found, in which case, the corresponding expression e-ai is evaluated and its value is the value of the cond expression. If no such e-pi exists, the expression e-an’s value is the value of the cond.
Implementing Dupe+
You must extend the interpreter and compiler to implement Dupe+. (The parser for Dupe+ is given to you.) You are given a file dupe-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+
The AST type and parser for Dupe+ are given to you.
Here’s the AST definition for the added primitives and cond:
; type Expr = ; ... ; | (Cond [Listof Expr] [Listof Expr] Expr) ; type Op = ; ... ; | 'abs | '- | 'not (struct Cond (cs es el) #:prefab)
There is one new kind of expression constructor: Cond. A Cond AST node contains three parts: two equal length lists of expression and an expression. The two lists represent the clauses, where the first list contains all of the left-hand-side parts of the clauses and the other contains all of the right-hand-side parts.
Here are some examples of how concrete expressions are parsed into ASTs using this representation:
(abs 1) parses as (Prim1 'abs (Lit 1)),
(not #t) parses as (Prim1 'not (Lit #t)),
(cond [(not #t) 3] [else 5]) parses as (Cond (list (Prim1 'not (Lit #t))) (list (Lit 3)) (Lit 5)),
(cond [(not #t) 3] [7 4] [else 5]) parses as (Cond (list (Prim1 'not (Lit #t)) (Lit 7)) (list (Lit 3) (Lit 4)) (Lit 5)),
Implementing primitives
Implement the primitives as described earlier.
There are many ways to implement these at the assembly level. You should try implementing these using the limited a86 instruction set.
Study ast.rkt to understand how these new forms of expression are represented.
Study parse.rkt and add support for parsing these expressions. (See Parsing Dupe+ for guidance.)
Update interp-prim.rkt and interp.rkt to correctly interpret these expressions.
Make examples of these primitives and potential translations of them to assembly.
Update compile.rkt to correctly compile these expressions.
Check your implementation by running the tests in test/all.rkt.
Implementing cond
Implement the cond expression form as described earlier. To do this, you should:
Study ast.rkt to add appropriate AST nodes.
Update interp-prim.rkt and interp.rkt to correctly interpret cond expressions.
Make examples of cond-expressions and potential translations of them to assembly.
Update compile.rkt to correctly compile cond expressions based on your examples.
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 directory to create a zip file containing your work and submit it to Gradescope.