Compilers

Dove

Due on Wednesday, March 6th at 11:59 PM. This is a compiler lab. If you have a partner, the two of you will complete this lab as a team. If you do not have a partner, you are effectively in a team by yourself.

If you are working with a partner, please be familiar with the Partner Etiquette guidelines. You and your partner share a single repository and, barring unusual circumstances, will receive the same grade. If you experience any difficulties in your partnership, please alert your instructor as soon as possible.

If you are working alone, please don’t hesitate to seek help if you get stuck. Since there are no ninjas for this course and you don’t have a partner, your instructor is the only interactive resource available to you and is happy to help you through any problems you might encounter.

In either case, be familiar with the academic integrity policy! You are permitted to discuss high-level details of your compiler project with other students, but you should never see or share anything that will be turned in for a grade. If you need help, please post on the Piazza forum or, if necessary, contact the instructor directly. Make sure to post privately if you are sharing code. If you have any doubts about what is okay and what is not, it’s much safer to ask than to risk violating the Academic Integrity Policy.

Overview

This lab will extend the Cardinal compiler to a new language called Dove. Dove includes first-order functions (similar to C functions) and function calls. It also adds some compile-time error checking related to functions.

Transitioning to Dove

As usual, you will first change to the dove branch, where your Dove starter files are located:

git fetch
git checkout dove

You will then merge your work on the Cardinal compiler into that branch:

git merge cardinal

The changes for Dove are contained in two locations:

• src/languages/, in which the lexer and parser for Cardinal have been updated for the Dove syntax discussed below. The asts.ml file now contains new types which will be used in handling function declarations; make sure to take a look.
• src/wellformedness.ml, a new file where you will write compile-time error checks for Dove.

Note that, this time, you will not be able to build your compiler after the merge. This is because the Dove compiler’s parser produces a program instead of an expr. This is expected.

Your first task will be to update compile_program and compile_to_assembly_code to take program as an argument. For now, just make your code ignore the list of declarations in the program value and compile the expression it contains. Afterwards, you can make clean, make tests.byte, and run ./tests.byte to ensure that everything is working again.

The Dove Language

In the Dove language, programs are a list of declarations followed by an expression. The expression is essentially the “main” part of the program; the declarations allow you to create functions that expressions can call. Below, we discuss the syntax and semantics for these declarations.

Concrete Syntax

Here, we use a common convention that our language starts at the first non-terminal – program – below. The concrete syntax of Dove is:

<program> ::=
  | <declaration_list> <expression>
  | <expression>

<declaration_list> ::=
  | <declaration> <declaration_list>
  | <declaration>

<declaration> ::=
  | def <identifier>(<parameter_list>) <expression> end
  | def <identifier>() <expression> end

<parameter_list> ::=
  | <identifier> , <parameter_list>
  | <identifier>

<expression> ::=
  | true
  | false
  | <integer>
  | after(<expression>)
  | before(<expression>)
  | print(<expression>)
  | isbool(<expression>)
  | isint(<expression>)
  | <expression> + <expression>
  | <expression> - <expression>
  | <expression> * <expression>
  | <expression> < <expression>
  | <expression> > <expression>
  | <expression> = <expression>
  | <expression> && <expression>
  | <expression> || <expression>
  | <identifier>
  | let <identifier> = <expression> in <expression>
  | ifnz <expression> then <expression> else <expression>
  | if <expression> then <expression> else <expression>
  | <identifier>(<argument_list>)
  | <identifier>()
  | (<expression>)

<argument_list> ::=
  | <expression> , <argument_list>
  | <expression>

Syntactic precedence is the same as in Cardinal.

Abstract Syntax

The abstract syntax of Dove has additional types: declaration and program. Make sure to examine src/language/asts.ml to see their definitions. Each of these types correspond to their like-named non-terminals in the grammar above.

Semantics

Function declarations in Dove have semantics much like those of Python or C. When a function is called, each argument is evaluated from left to right. The values of those arguments are stored in the parameter variables of the function and the body of the function is executed. The result of the function call is the value returned by the expression in the function body. You must generate code that conforms to the C calling conventions.

Here are some examples of Dove code:

• The code

  def f(x)
    x + 1
  end
  
  f(4)
  

  returns the value 5: the variable x is set to the argument (4) and the body of the function returns one more than that value.

• The code

  def f(x)
    x * 2
  end
  
  def g(y)
    f(y) + f(4)
  end
  
  g(5)
  

  produces the value 18. This is because g(5) is equivalent to f(5) + f(4), which is equivalent to 5*2+4*2.

• We allow functions in Dove to be recursive with no declarations or syntax. The code

  def summate(x)
    if x > 1 then x + summate(x-1) else x
  end
  
  summate(5)
  

  is legal and will return the value 15 (that is, 5+4+3+2+1).

• We allow functions in Dove to be mutually recursive. The code

  def f(x)
    if x > 1 then g(x) else x
  end
  
  def g(x)
    f(x - 1)
  end
  
  f(4)
  

  is legal and will return 1.

• Note that functions of multiple arguments and functions of no arguments are permitted. Further, function calls are expressions and so may appear anywhere that an expression may appear. The code

  def f() 5 end
  def g(x,y)
    x > y
  end
  g(f(),4)
  

  will return true.

Compile-Time Errors

The introduction of function definitions and function calls also introduces several new forms of mistake that a programmer can make which we can detect at compile time. Your Dove compiler will be required to detect and handle several classes of errors:

• The programmer might call a function that has not been declared. If this occurs for a function fn, your compiler must emit an error message containing the strings “function fn” and “not defined”. For instance, the program

  def f() 5 end
  g()
  

  might generate the error “Function g is not defined.”.

• The programmer might call a function with the wrong number of arguments. If this occurs for a function fn, your compiler must emit an error message containing the strings “function fn” and “number of arguments”. For instance, the program

  def f() 5 end
  f(true)
  

  might generate the error “Function f is called with an incorrect number of arguments.”.

• The programmer might declare a function with duplicate parameter names. If this occurs for a function fn and parameter p, your compiler must emit an error message containing the strings “duplicate”, “parameter p”, and “function fn”. For instance, the program

  def f(x,y,x) 0 end
  4
  

  might generate the error “Function f declares a duplicate parameter x.”.

• The programmer might declare multiple functions with the same name. If this occurs for a function fn, your compiler must emit an error message containing the strings “duplicate definition” and “function fn”. For instance, the program

  def f() 0 end
  def f(x) x end
  f()
  

  might generate the error “Duplicate definition of function f.”.

• As before, the programmer might try to use an undefined variable. If this occurs for variable x, your compiler must emit an error message containing the strings “unbound” and “variable x”. For instance, the program

  def f(x)
    y
  end
  
  4
  

  might generate the error “Unbound variable y.”

Report all the errors!

Unlike our previous compilers, the Dove compiler must report all errors for a given file. For instance, the code

def f(x)
  g(y,z)
end

f()

contains four errors: an unbound variable y, an unbound variable z, an undefined function g, and an argument count error where f is called. The compiler must report all of these errors, like so:

$ ./hatch.byte above_code.bird
Unbound variable y.
Unbound variable z.
Function g is not defined.
Function f is called with an incorrect number of arguments.
$

The order of the errors is not relevant, but each error must appear on its own line.

To do this, you will need to write compile-time error checks for your AST and use them before proceeding with compilation. Note that you will not be able to rely upon your previous code for detecting unbound variables; that code throws an exception when it encounters a single variable and does not take any other errors into account. Instead, you will need to recurse over the AST and collect all of the errors it contains.

A small stub is provided in wellformedness.ml to give you an approach to use. If you use this approach, you will need to modify the compile_to_assembly_code function in builder.ml (not your own version in compiler.ml) so that it catches the IllFormed exception and throws a BuildFailure with the appropriate text. The command-line-handling code in hatch.ml will catch the BuildFailure exception and print the message it contains.

Runtime errors

You should report the same runtime errors that you did in the Cardinal lab, using the same exit codes:

• If an operation expects an integer but gets something else, exit with error code 1.
• If an operation expects a boolean but gets something else, exit with error code 2.
• If an arithmetic operation overflows, exit with error code 3.

Implementing the Dove Compiler

Here’s a rough outline of how to approach this lab:

1. Update your code so that your Cardinal unit tests pass. Initially, ignore the declarations that appear in the program so you can get your unit tests working again.

2. Add function declarations and function calls. Don’t worry about error handling for now; only test good programs. As you write your code, add thorough unit tests for a variety of cases. For instance, make sure to test calling functions with zero, one, or more parameters, especially in cases where the order of the arguments matters (e.g. subtraction). Use what you learned about C calling conventions in the Cardinal lab to implement your function calls and returns correctly.

3. Add error checking. Write unit tests for your compile-time errors. Be sure to be thorough.

C Calling Conventions

There is one aspect of the C calling conventions which we ignored in Cardinal: callee- and caller-saved registers. After a C function call, the called function may have changed a number of registers. The C calling conventions specify a contract about which of those registers may have changed and which must not have.

The caller-saved registers are those registers which the called function may change arbitrarily. If the caller cares about the values in caller-saved registers, then the caller must save those values and restore them later. If the caller does not do this, the values may be lost. Those registers are eax, ecx, and edx.

The callee-saved registers are those registers which the called function must preserve. If the called function changes those registers, their values must be restored by the end of the function call. The caller may assume that those registers contain the same values that they contained when the call was made. Those registers are ebx, esi, and edi.

Below is a complete description of the C calling conventions with the relevant parts highlighted in bold text:

• Before calling a function, the caller must
  1. Store the value of any caller-saved registers that the caller needs.
  2. Push the function call arguments onto the stack.
  3. Use the call instruction to jump to the function’s code. This pushes the return instruction address onto the stack.
• At the very beginning of a call, the callee must
  1. Push ebp onto the stack to save it.
  2. Copy esp into ebp to form the new base of the stack.
  3. Move esp to make room for all of the local variables in the function.
  4. Store the value of any callee-saved registers that the function may change.
• At the very end of the call, the callee must
  1. Leave the return value in eax.
  2. Restore the value of any callee-saved registers that the function changed.
  3. Copy ebp into esp to restore the old value of esp.
  4. Pop into ebp the old value of the stack’s base pointer.
  5. Execute the ret instruction to pop and jump to the return address that was pushed when the call began.
• After the call returns, the caller must
  1. Pop the function call arguments off of the stack.
  2. Restore any caller-saved register values that the caller needs.

Strictly speaking, the callee may save callee-saved register values at any point as long as the stack is returned to the same condition it was in when the call was made. Inserting the save and restore and the points indicated above, however, ensures that you do not have to change your logic for allocating temporary variables.

OCaml Data Structures

You may find that, in addition to the StringMap module in utils.ml, you need a set of strings. You can create such a module in a similar fashion. Feel free to modify utils.ml to include something like the following:

module StringSet = Set.Make(
  struct
    type t = string
    let compare = Pervasives.compare
  end
  );;

The StringSet module will then contain functions for using sets in OCaml (e.g. StringSet.union). Just like OCaml’s dictionaries, these sets are immutable and all modifying functions derive a new set. StringSet isn’t necessary for completing this lab, but it might be a useful tool.

Summary

To complete this assignment, you’ll need to

• Update your compiler to compile program ASTs
• Add assembly code generation for function declarations and function calls
• Add compile-time error checking to report all of the errors described above

Submitting

To submit your lab, just commit and push your work. The most recent pushed commit on the appropriate branch as of the due date will be graded. For more information on when assignments are due, see the Policies page.

After each lab, you will complete a brief questionnaire found here. In most cases, the questionnaire should take less than a minute. This questionnaire is required and will be used as part of your participation grade.

If You Have Trouble…

…then please contact your instructor! Piazza is the preferred method, but you can reach out via e-mail as well. Good luck!