Assignment 3: Conditional forms and parsing
Due: Thu, Feb 25, 11:59PM
The goal of this assignment is to extend the parser, interpreter, and compiler with some simple unary numeric and boolean operations and conditional expressions.
You are given a repository with two starter compilers, one for the Con and one for the Dupe language we studied in class. You are tasked with extending each language in a number of ways:
Con - More primitives
Add the following forms of expression to the Con language:
There are many ways to implement these at the assembly level. You should try implementing these using the limited a86 instruction set.
Hint: Use subtraction!
Study ast.rkt and the new forms of expression (i.e. new AST nodes) then update the comment at the top describing what the grammmar should look like.
Study parse.rkt and add support for parsing these expressions.
Update interp-prim.rkt and interp.rkt to correctly interpret these expressions.
Update compile.rkt to correctly compile these expressions.
Con with Cond
The Con language we studied added a simple form of performing conditional evaluation of sub-expressions:
However, in the original paper on Lisp, Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I, John McCarthy introduced a generalization of if called “conditional expressions,” which we could add to our language with the following syntax:
(cond [(zero? e-p1) e-a1] ... [else e-an])
A cond expression has any number of clauses [(zero? e-pi) e-ai] ..., followed by an “else” clause [else en]. (We are using zero? here to avoid having to introduce booleans as a distinct data type; a restriction we will remove later.)
The meaning of a cond expression is computed by evaluating each (zero? e-pi) in order until the first one that is true is found, in which case, the corresponding e-ai is evaluated and its value is the value of the cond expression. If no such e-pi exists, e-an’s value is the value of the cond.
The formal semantics can be defined as:
Your task is to extend Con with this (restricted) form of cond.
To do this, you should:
Study ast.rkt to add Cond and Clause AST nodes.
Extend parse.rkt to parse such expressions.
Update interp-prim.rkt and interp.rkt to correctly interpret cond expressions.
Update compile.rkt to correctly compile cond expressions.
The subset of x86 needed to compile this extension of Con should not require anything more than what was used for Con without cond.
Dupe+
The last part of this assignment is to port these extensions over to Dupe and add one more unary primitive, this time one that operates on booleans.
(not e): compute the boolean negation of e
a86 Hint: While you can implement this with a jump, it is possible to implement using only a single a86 instruction :)
In addition to not, you should also add the primitives you implemented for Con (absolute value and negation), as well as conditionals.
Conditionals can now be properly unrestricted: the checks no longer need to be zero? predicates, but can be arbitrary expressions that evaluate to a boolean.
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 with exactly the same structure that the stub contains (a con-plus and a dupe-plus folder). We will only use the parse.rkt, ast.rkt, compile.rkt, interp.rkt, and interp-prim.rkt files for grading, so make sure all your work is contained there!