►Assignment 5: Diamondback:   Defining functions
Assignment 5: Diamondback:   Defining functions
1 The Diamondback Language
1.1 Concrete Syntax
1.2 Abstract Syntax
1.3 Semantics
1.4 Implementation
1.4.1 A new structure for ANF
1.4.2 A new is_  well_  formed function
1.4.3 The AProgram structure
1.4.4 locate_  bindings
1.5 Tail calls
1.6 Extra credit:   Printing stack traces
1.7 Testing
2 Running main
3 List of Deliverables
4 Grading Standards
5 Submission
8.14

Assignment 5: Diamondback: Defining functions🔗

Due: Tue 02/20 at 8:59pm

git clone

In this assignment, you’ll implement a compiler for a small language with functions declarations and function calls, that can communicate with functions written in C. 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

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 function declarations. Our programs are now a sequence of zero or more function declarations, followed by a single main expression.

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

Diamondback also supports line comments, beginning with a # and continuing to the end of the line.

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. Note that primops and function calls are whitespace-sensitive: there can be no space before the left parenthesis. (This is a workaround for a grammatical ambiguity in the language. You can see a remnant of that ambiguity by the "1 shift/reduce conflict" warning produced by ocamlyacc in the provided code.)

1.2 Abstract Syntax🔗

In this assignment, we distinguish between the surface syntax that the parser produces (expr) from the ANF expression forms (aexpr). All these types are given in exprs.ml; below we show a simplified, undecorated form:

type prim1 =
  | Add1
  | Sub1
  | Not
  | Print
  | IsNum
  | IsBool

type prim2 =
  | Plus
  | Minus
  | Times
  | And
  | Or
  | Greater
  | GreaterEq
  | Less
  | LessEq
  | Eq

(* Surface expressions *)
type bind = (string * expr)

type expr =
  | ELet of bind list * expr
  | EPrim1 of prim1 * expr
  | EPrim2 of prim2 * expr * expr
  | EApp of string * expr list
  | EIf of expr * expr * expr
  | ENumber of int
  | EBool of bool
  | EId of string

type decl =
  | DFun of string * string list * expr

type program =
  | Program of decl list * expr


(* Internal ANF expressions *)
type immexpr =
  | ImmNumber of int
  | ImmBool of bool
  | ImmId of string

and cexpr =
  | CPrim1 of prim1 * immexpr
  | CPrim2 of prim2 * immexpr * immexpr
  | CApp of string * immexpr list
  | CIf of immexpr * aexpr * aexpr
  | CImmExpr of immexpr

and aexpr =
  | ALet of string * cexpr * aexpr
  | ACExpr of cexpr

and adecl =
  | ADFun of string * string list * aexpr

and aprogram =
  | AProgram of adecl list * aexpr

The EApp and CApp constructors correspond to function applications, and the decl and adecl types respresent function declarations. A program is a list of decls (surface) or adecls (ANF), with a main expression.

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

f(1, 2)

should produce 3.

Logical operators && and || should short-circuit: they should have the same behavior as you gave them in Assignment 4.

Since our Diamondback functions only call other Diamondback functions, rather than arbitrary functions in C, you can use a simpler calling convention than the full x64 calling convention: you can simply push all the arguments onto the stack and pop them all back off again. For primitives like print, obviously, you’ll need to follow the proper x64 stack layout. (If you’d like to use the x64 calling convention everywhere, you certainly may do so. Test thoroughly.)

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, not happen at runtime. Moreover, you should report all the errors in this program, not just the first one encountered. See the notes on is_well_formed below for implementation details.

These errors, in addition to ParseErrors, are all defined in errors.ml. Additionally, there are two more errors given to you: NotYetImplemented errors, which you should obviously remove and implement; and InternalCompilerErrors, which indicate intended-to-be-impossible scenarios in your compiler. Ideally, your final compiler should not need these (either by coming up with useful semantics in all scenarios, or by using the ML type system to your advantage to avoid any such unplanned scenarios), but in practice you might still need them.

1.4 Implementation🔗

The file assembly.ml 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:

  1. A new structure for ANF

  2. A new is_well_formed function

  3. A new AProgram structure

  4. A new locate_bindings phase

Each of these contains an implementation task; you should complete these four before moving on to tail-calls, below.

1.4.1 A new structure for ANF🔗

You should study and understand it (see Lecture 8: Revisiting ANF: Encoding A-Normal Form with Types) so you can implement the EApp case. This is the first thing you should add.

1.4.2 A new is_well_formed function🔗

This function is called prior to performing ANF and are used to report the errors above. This function either returns the program unchanged, or returns an exn list, which represents all the errors that are found in a program or expression. So a program like

def f(x, x):
  y
f(1)

would report three errors, one for y being unbound, one for duplicated x parameters, and one for the arity mismatch on the call to f.

These errors can be reported in any order; in general (and in grading), it’s easy to test for one at a time. But reporting multiple errors makes using the main of the compiler much more pleasant, and is a nice view into the kinds of compiler ergonomics we should expect from a modern compiler.

1.4.3 The AProgram structure🔗

This contains both function declarations and the expression for our_code_starts_here. You will probably want to generate an assembly structure that looks like:

  ;; extern and global stuff
section .text
...
fun_decl1:
  ;; code for fun_decl1, including stack management
fun_decl2:
  ;; code for fun_decl2, including stack management
...
our_code_starts_here:
  ;; main entrypoint, as before, with stack management

  ;; errors, as before
internal_error_non_number:
...

(Hint: while the AProgram construct is not quite uniform, since the body is treated separately from the function definitions, a relatively simple observation makes generating the output assembly of the entire program very uniform...)

1.4.4 locate_bindings🔗

In Cobra, in compile_expr, you used a stack index parameter, si, that accumulated how many let-bindings were currently in use on the stack and built up an environment mapping each let binding to a stack index, which you could then use to compile EId variable usages by looking up their names in that environment and turning the stack indices into an appropriate location RegOffset(~-8 * si, RBP). Since we’re also splitting compile_expr into several functions over the ANF’ed AST, we should take the opportunity to refactor this logic into its own phase, to keep it simpler and self-contained.

You should define a new function, naive_stack_allocation, that implements the stack-index manipulations and returns an environment mapping every let-bound name to its appropriate RegOffset; then the EId case simplifies to looking up the name in that environment and using the resulting RegOffset directly. Note that in Cobra, you only used the si parameter to allocate stack indices for let-bound variables and not function parameters; your naive_stack_allocation function should do the same. It might seem odd to have an environment containing all of the names in your program, all at once, but because we’ve already performed check_scope to ensure names are only used correctly in scope, and because we’ve already performed rename to ensure every let-binding has a unique name, this whole-program environment is safe to use.

In order for this function to compose into your pipeline and be useful by compile_prog after it, it will actually need to return a pair of the ANF’ed program and the environment you just computed.

Once you’ve implemented this function, you can replace your use of count_vars from Cobra with a call to deepest_stack, which will take an aexpr and the environment, and determine the number of words your stack frame needs by finding the deepest stack offset used by any of the local variables in your expression. If you’ve implemented naive_stack_allocation correctly, then count_vars and deepest_stack will always produce the same answers.

1.5 Tail calls🔗

Refine your compilation of function applications to support tail-calls. There are three levels of complexity here:

To support the last one, you’ll need to be creative with the calling convention. The only truly essential feature of a stack frame is knowing where the saved RSP, RBP and return addresses must be, and all other variables’ locations can be calculated from knowing those. In particular, you’ll need to change the ordering of values in your stack frame, where RBP points between parameters and locals. Instead, both parameters and locals will need to be above RBP: change your compilation of function calls — and anything else that is affected! — to support this new convention. This change will prevent you from using the call instruction (why?), so you’ll need to come up with something clever to save the desired return address. Come see me if you try this, for a hint.

To detect that you’ve implemented tail calls correctly, you may want to attempt the following extra credit.

1.6 Extra credit: Printing stack traces🔗

Implement a new prim1 operator, printStack, that takes a single argument and returns it, just like print does. What makes printStack special is its output: it will print out a stack trace of all the call frames from wherever it’s called, down to wherever our_code_starts_here began. For example, given the following program: 

def fact(acc, n):
  if n < 1: printStack(acc)
  else: fact(acc * n, n - 1) + 0
  # NOTE: This + 0 is to prevent tail-recursion in this example

fact(1, 3)
Here is a potential stack trace:

RSP: 0x00007ffc352b1bb0	==>  0
RBP: 0x00007ffc352b1bd0	==>  70360600251912
(difference: -4)
Requested return val: 0x000000000000000c	==> 6
Num args: 2
    0x00007ffc352b1bb0: 000000000000000000	==>  old rbp
    0x00007ffc352b1bb8: 000000000000000000	==>  0
    0x00007ffc352b1bc0: 000000000000000000	==>  0
    0x00007ffc352b1bc8: 0xffffffffffffffff	==>  true
RBP 0x00007ffc352b1bd0: 0x00007ffc352b1c10	==>  old rbp
    0x00007ffc352b1bd8: 0x0000000000401077	==>  saved ret
    0x00007ffc352b1be0: 0x000000000000000c	==>  6
    0x00007ffc352b1be8: 000000000000000000	==>  0
    0x00007ffc352b1bf0: 000000000000000000	==>  0
    0x00007ffc352b1bf8: 000000000000000000	==>  0
    0x00007ffc352b1c00: 0x000000000000000c	==>  6
    0x00007ffc352b1c08: 0x7fffffffffffffff	==>  false
RBP 0x00007ffc352b1c10: 0x00007ffc352b1c50	==>  old rbp
    0x00007ffc352b1c18: 0x0000000000401077	==>  saved ret
    0x00007ffc352b1c20: 0x000000000000000c	==>  6
    0x00007ffc352b1c28: 0x0000000000000002	==>  1
    0x00007ffc352b1c30: 000000000000000000	==>  0
    0x00007ffc352b1c38: 0x0000000000000002	==>  1
    0x00007ffc352b1c40: 0x000000000000000c	==>  6
    0x00007ffc352b1c48: 0x7fffffffffffffff	==>  false
RBP 0x00007ffc352b1c50: 0x00007ffc352b1c90	==>  old rbp
    0x00007ffc352b1c58: 0x0000000000401077	==>  saved ret
    0x00007ffc352b1c60: 0x0000000000000006	==>  3
    0x00007ffc352b1c68: 0x0000000000000004	==>  2
    0x00007ffc352b1c70: 000000000000000000	==>  0
    0x00007ffc352b1c78: 0x0000000000000004	==>  2
    0x00007ffc352b1c80: 0x0000000000000006	==>  3
    0x00007ffc352b1c88: 0x7fffffffffffffff	==>  false
RBP 0x00007ffc352b1c90: 0x00007ffc352b1cb0	==>  old rbp
    0x00007ffc352b1c98: 0x00000000004010c1	==>  saved ret
    0x00007ffc352b1ca0: 0x0000000000000002	==>  1
    0x00007ffc352b1ca8: 0x0000000000000006	==>  3
BOT 0x00007ffc352b1cb0: 0x00007ffc352b1cf0	==>  old rbp
    0x00007ffc352b1cb8: 0x0000000000400f37	==>  saved ret
    0x00007ffc352b1cc0: 0x00007f04f63949a0	==>  heap
6

The output shows:

Hint: To identify where to stop printing the stack (after all, main isn’t the very last thing in the stack; there are operating-system frames as well...), I used a trick: declare a global, non-const variable in C, uint64_t* STACK_BOTTOM, and mark it as extern. At the beginning of our_code_starts_here, initialize that value with the current value of RBP (you’ll need a new assembly arg for this), and then you’re guaranteed to know where your stack ends, dynamically.

Note: if you’ve properly implemented tail calls, then eliminating the + 0 from the program above, and rerunning it, should produce a much shorter stack trace...

Note: If you implement this extra credit, provide a brief, written explanation (in a comment in main.c, near whatever new functions you define) of why this must be implemented as a EPrim1 and not as a EApp expression.

1.7 Testing🔗

There is one new testing function provided, tvg. This works just like t, except it runs valgrind on the executable it creates, and checks whether or not it reports errors. If valgrind does report memory errors, the test fails and the errors are reported. The test succeeds if there are no memory errors and the answer is correct.

You can test the well-formedness errors using the error tester as usual.

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🔗

Again, please ensure the makefile builds your code properly. The black-box tests will give you an automatic 0 if they cannot compile your code!

DO NOT SUBMIT YOUR .git DIRECTORY! For that matter, don’t submit your output or _build directories.

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 https://handins.khoury.northeastern.edu/ by the above deadline.