On this page:
Con - More primitives
Con with Cond
Dupe+
Testing
Submitting
7.9

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.

Assignment repository:

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!

To do this, you should:
  • 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:

(if (zero? e0) e1 e2)

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:

image

image

Your task is to extend Con with this (restricted) form of cond.

To do this, you should:

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:

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!