Assignment 4: Diamondback:   Defining functions
1 The Diamondback Language
1.1 Concrete Syntax
1.2 Abstract Syntax
1.3 Semantics
1.4 Middle-End
1.5 Backend
2 Running main
3 List of Deliverables
4 Grading Standards
5 Submission
8.6

Assignment 4: Diamondback: Defining functions

Due: Sun 10/30 at 11:59pm

git clone

In this assignment, you’ll implement a compiler for a small language with local functions declarations and function calls, that can communicate with functions written in Rust. You’ll also add some static well-formedness checks to the compiler.

As for the project acronym, so far our greatest minds have come up with

Click here for scary snake picture!

1 The Diamondback Language

As usual, we have concrete and abstract syntaxes, along with a specification of semantics.

1.1 Concrete Syntax

The major addition to Diamondback are local function declarations. We have a new binding form, where we can def a series of mutually recursive functions in any expression.

‹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 | print | isbool | isnum ‹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›

The other addition is function applications, which are written IDENTIFIER(‹exprs›), for example f(1, 2, 3). This is the syntax for a call to a function.

1.2 Abstract Syntax

In this assignment, we add two new cases to our Exp AST, one for (mutually recursive sequences of) local function definitions and one for function calls. Since we will also need to use function definitions in our sequentialized code, we make a type FunDecl that is generic in the type of expressions.

pub struct FunDecl<E, Ann> {
    pub name: String,
    pub parameters: Vec<String>,
    pub body: E,
    pub ann: Ann,
}
pub enum Exp<Ann> {
    ... // previous cases
    FunDefs {
        decls: Vec<FunDecl<Exp<Ann>, Ann>>,
        body: Box<Exp<Ann>>,
        ann: Ann,
    },
    Call(String, Vec<Exp<Ann>>, Ann),
}

Our lambda lifting pass will separate the input program into two pieces: a sequence of top level definitions and a single main expression to be run. So our sequential form has calls, in which arguments are required to be immediate, but no local function definitions. Instead, we have a new type of sequential form programs SeqProg that packages the functions and main expression into a struct.

pub enum SeqExp<Ann> {
    ... // same as before
    Call(String, Vec<ImmExp>, Ann),
}

pub struct SeqProg<Ann> {
    pub funs: Vec<FunDecl<SeqExp<Ann>, Ann>>,
    pub main: SeqExp<Ann>,
    pub ann: Ann,
}

1.3 Semantics

There are several distinguishing features of Diamondback. The first is function applications. A function application should give the answer we’d get if we followed the rules for substituting argument values for parameter names. So, for example:

def f(x, y):
  x + y
in
f(1, 2)

should produce 3.

Logical operators && and || do not need to short-circuit; they should have the same behavior as you gave them in Assignment 3.

There are a number of new errors that can occur now that we have function declarations and calls. Your implementation should catch all of these cases statically; that is, at compile time before the program runs:

Again, these errors should stop the program from compiling, in your check_prog function, not happen at runtime.

1.4 Middle-End

Once the code passes the check_prog function, we need to do a few transformations before we’re ready for code generation.

For details on lambda lifting, see the corresponding lecture.

To help you get started, we’ve given you some stubs and code for plugging these passes together. As usual, you are free to change the types of any function you use internally, just don’t change the types of anything that is pub.

1.5 Backend

The file asm.rs gives you all the assembly instructions you should need, though you’re free to add your own new instructions if you want.

There are a few new pieces to the implementation:

When Diamondback functions call other Diamondback functions, you should use the snake calling convention as described in the lecture notes on function calls. For primitives like print, obviously, you’ll need to continue to follow the System V AMD ABI.

Stack alignment is trickier this time because we are calling our own functions as well and so incorrect alignment might cancel itself out to make some tests pass.

2 Running main

Running your own programs is the same as with Cobra, except you’ll give them the .diamond file extension.

3 List of Deliverables

Please ensure the your code builds properly. The autograder will give you a 0 on that portion of the grade if it cannot compile your code.

4 Grading Standards

For this assignment, you will be graded on

5 Submission

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

Please submit your homework to gradescope by the above deadline.