Assignment 4: Diamondback: Defining functions

8.7

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

Designing an
Intel Architecture
MOstly dynamic
Nested-expression
(Diamondback supports recursion)
Boolean-tagged
Arithmetic-supporting
Compiler.
...K?

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:

A function application with the wrong number of arguments should signal an FunctionCalledWrongArity error
If you apply a function f but there is a local variable named f, you should signal a ValueUsedAsFunction
A function application of a non-existent function f that is not a locally defined variable should signal an UndefinedFunction error.
An identifier x used in a value position with no corresponding let declaration and no function declaration should report an UnboundVariable error
An identifier x used in a value position with no corresponding let declaration but where there is a function declaration defining x should report a FunctionUsedAsValue error
A let binding with duplicate names should report a DuplicateBinding error
A function declaration with duplicate names in the argument list should report a DuplicateArgName error
If there are mutually recursive function definitions with the same name and arity, report a DuplicateFunName error. You can support overloading if you wish, but it probably won’t be allowed in future assignments
If a numeric constant is too large, report an Overflow error

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.

First, rename all functions and variables with unique names, to simplify later passes
Then, add all captured free variables as extra arguments and lift function definitions to the top-level
Finally, sequentialize the main expression and all function definitions

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

your compile.rs and asm.rs
the other src/*.rs files in the starter code
any additional modules you saw fit to write
your runtime/stub.rs
the Cargo.toml
integration tests (tests/examples.rs)
your test input programs (examples/*.cobra files)

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

Whether your code implements the specification (functional correctness),
the clarity and cleanliness of your code, and

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.

1	The Diamondback Language
2	Running main
3	List of Deliverables
4	Grading Standards
5	Submission