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

• Designing an

• Intel Architecture

• MOstly dynamic

• Nested-expression

• (Diamondback supports recursion)

• Boolean-tagged

• Arithmetic-supporting

• Compiler.

• ...K?

### 1The Diamondback Language

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

#### 1.1Concrete 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.2Abstract 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.3Semantics

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.4Middle-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.5Backend

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.

### 2Running main

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

### 3List 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)