Assignment 2: Control Flow🔗

Due: Fri 02/14 at 11:59pm

git clone

In this assignment, we extend our previous compiler with additional mechanisms for complex control flow: conditional statements, and a limited form of functions that can only be invoked by a tail call.

1 The Boa Language🔗

1.1 Concrete Syntax🔗

‹prog›: def main ( IDENTIFIER ) : ‹expr› ‹expr›: | let ‹bindings› in ‹expr› | if ‹expr› : ‹expr› else: ‹expr› | ‹decls› in ‹expr› | ‹binop-expr› ‹binop-expr›: | IDENTIFIER | NUMBER | true | false | ! ‹binop-expr› | ‹prim1› ( ‹expr› ) | ‹expr› ‹prim2› ‹expr› | IDENTIFIER ( ‹exprs› ) | IDENTIFIER ( ) | ( ‹expr› ) ‹prim1›: | add1 | sub1 ‹prim2›: | + | - | * | < | > | <= | >= | == | && | || ‹decls›: | ‹decls› and ‹decl› | ‹decl› ‹decl›: | def IDENTIFIER ( ‹ids› ) : ‹expr› | def IDENTIFIER ( ) : ‹expr› ‹ids›: | IDENTIFIER | IDENTIFIER , ‹ids› ‹exprs›: | ‹expr› | ‹expr› , ‹exprs› ‹bindings›: | IDENTIFIER = ‹expr› | IDENTIFIER = ‹expr› , ‹bindings›

1.2 Semantics🔗

The semantics of functions and if expressions are as discussed in class and implemented in the provided interpreters. If you have questions about the semantics, ask for clarification on Piazza.

The semantics of boolean constants is that true is an alias for 1 and false is an alias for 0. All non-zero integers are considered to represent the boolean true while only 0 represents false. The logical operators of negation (!), conjunction (&&) and disjunction (||) are all allowed to take arbitrary integers as inputs, but always return either 0 or 1.

Comparison operations should treat inputs as integers and produce boolean balues (1 or 0).

2 Compiler Passes🔗

For this compiler you will extend the three passes from before to account for the new control-flow mechanisms.

• frontend.rs: Extend your scope checking to new forms and check that functions are used correctly.

• middle_end.rs: Extend your lowering pass to handle boolean values, new operators, conditionals and function definitions

• backend.rs: Extend your code generation to handle sub-blocks, branching and coercions.

2.1 Well-formedness checking🔗

We extend our previous notion of scope with a new mechanism for defining variables: local function definitions.

This adds several new types of compile-time errors with functions:

• A function being called that was not declared

• Mutually recursively defined functions with the same name

• A function having multiple parameters with the same name

• A function being called with the wrong number of arguments

• A function being called in a non-tail position.

2.2 Lowering To SSA🔗

The new SSA form has full support for parameterized blocks as well as operations for implementing integer to boolean coercions and logical and comparison operations. We include primitives for bitwise and and, or and xor, as well as a coercion from integers to booleans which is useful for correctly implementing logical operators.

Additionally, we have updated the Continuation type to be an enum: either a block of code with an input variable, or a Return. The Return continuation indicates the continuation is trivial, and therefore the expression is in tail position. If you have correctly ruled out non-tail calls in frontend.rs, you should never have a call with a non Return continuation. Additionally, if a conditional has a Return continuation, you need not generate a join point for it.

2.3 Code Generation🔗

Most of the work is in compiling to SSA, but there are a few things to keep in mind for code generation:

• As discussed in February 3 lecture, make sure that branch with arguments don’t overwrite temporaries.

• The setcc operation uses 8-bit registers, these are added in asm.rs as Reg8.

3 Starter Code🔗

You are provided with starter code as before that provides a runner script, a parser, printing for assembly code, as well as type definitions for the ASTs, SSA form and Assembly code.

Much of your implementation from assignment 1 will still be useful for assignment 2, but will need to be refactored and extended accordingly with new features. You are free to use your solution for assignment 1 as a starting point, but we also provide a reference solution for assignment 1 on the gitlab. You should have received an invitation to a private gitlab group that gives you access to this reference solution.

4 List of Deliverables🔗

For this assignment you will submit your updated versions of three files:

• src/frontend.rs

• src/middle_end.rs

• src/backend.rs

These are the only files that you can change in your submission, your code will be linked with reference versions of the other files.

We’ve included a script mk_submission.sh in the starter code repo that should make zip file with just those three files and your testing files that you should upload to gradescope. The testing files are included for us to get some idea of how students are testing their code, they are not graded.

5 Grading Standards🔗

For this assignment, you will be autograded on whether your code implements the specification (functional correctness). We encourage you to test but your test coverage is not graded.

6 Submission🔗

Wait! Please read the assignment again and verify that you have not forgotten anything!

Please submit your homework on gradescope by the above deadline.