arrproc programs depend on the fruntime library rather than the runtime library (as did the previous two projects). You should read more about fruntime before starting this assignment.

IL operands are now split into doperands (destination operands for writing) and soperands (source operands for reading). Any destination operand can become a source operand using the Dest constructor. For example, an svar s as a destination operand appears as Svar s. As a source operand, it would look like Dest (Svar s).

A complete lexer and parser are provided for this assignment in lexer.mll and parser.mly. You should understand these files, but do not modify them.

This assignment's lexer and parser keep track of token locations from source files. This will allow you to raise helpful error messages that point to the exact tokens that cause problems.

The includes section of a program can contain zero or more files to inline. The compiler will topologically sort included files according to the dependency graph before doing any inlining. Files are kept track of only by name, so trying to include both a/a.ap and b/a.ap will have undefined results. When the compiler merges file B in after A (because B includes A), B's declarations are appended to A's declarations and B's expression is appended to A's expression using a sequencing operator. Consider the following example:

Compiling inlineD.ap will yield the following program:

By default, the compiler searches in the lib and . directories for includes. You can add more include directories with the -i option.

AT's typechecker requires explicit typing annotations. The relevant rules in the grammar for types are:

That is, you can form regular types (unit, string, and int). You can also form arrays using Java-style syntax: a single-dimensional array of int is int[]; a multi-dimensional array is int[][]. Some types, like unit[], are not well-formed. These are caught during typechecking.

A declaration can either declare a new function or a new constant. Names for functions and constants must be unique (you may not have a function named foo and a constant named foo, or two functions named foo or two constants named foo). The order of declaration does not matter for functions, but it does matter for constants (see the information on mutual recursion below).

The declaration of a constant looks like:

Note the mandatory semicolon. A function declaration looks like:

Note that the parenthesis surrounding the function body are mandatory and that there is no semicolon following the declaration. Some functions may be declared as external (because they appear in the runtime):

And in code:

There are several new syntactic forms beyond those that were in the control flow language. These include:

• String literals: "Like this." The escape codes \n, \t, \\ and \" are supported.
• The null keyword: null can take on any reference type.
• The unit value: As in OCaml, unit looks like () and has the type unit. This value is useful only where you need a unit return value (as in a function with side effects) or for ending a file meant only to be included by other files.
• Function calls: These look like C or Java function calls: foo(a, b, c) calls function foo with the arguments a, b, and c.
• Array indexing: Like C or Java: arr[i].
• Array allocation: Like Java, but with a twist: you must provide an initial value that is copied to every element of the array. For example, to allocate a new array of ints (all equal to zero), use new int[42](0).

The topmost expression of a program must return something of type int. This becomes the return code of the program.

Constants and functions both exist in the same global namespace and all global names must be unique (there is no 'shadowing'). A function may not share its name with a constant. Locally bound variables may shadow constants; you may have a locally bound variable with the same name as a global function, but that variable will not shadow the function.

Function declarations are mutually recursive: the body of any function can refer to the name of any other function irrespective of their order of declaration.

Constant declarations are not mutually recursive. A constant C2 may refer to a constant C1 only if C1 was declared before C2. In addition, constants may not refer to any functions.

Complete typecheck as defined in aptypecheck.mli. There is some code in aptypecheck.ml to get you started. Part of your grade for this section depends on the quality of the error messages you raise for the user. Simply printing Type error. for badly-formed programs is insufficient. Give more details about what kind of error occurred.

Typechecking constants occurs under the empty binding context. The signature context contains nothing but constants that have been declared previously to the constant being checked.

Typechecking functions occurs under the binding context consisting only of that function's argument names. The signature context contains all constants and all functions (including the one being checked).

• If the function body is None (as in an extern function), just pass on the None through the typechecker.

You are given functions for testing type equality, well-formedness (of types for arguments, arrays and variables), and join ().

The following inference rules apply to expressions under a variable binding context and an implied signature context S. is read as 'any operator'.

• Variables, constants, and function names will appear as Ident AST nodes.
• For T-Assign-Var, you can assign the variable v its type T.
• For T-Assign-Arr, you can assign the array a its type TRef (TArray T)
• For T-For, if either i or c are None , just pass None into the typed AST. (It is not a type error to be missing those components.)
• In T-Invoke-Name, the name of the function to invoke will appear as an Ident AST node.
• The return type of a program's expression (the code that does not appear in any function or constant) must be TInt.

Complete il_of_ast as defined in arrproc.mli by filling in the missing cases for rev_il_of_ast.

To compile code that deals with arrays, you will need to use the new InvokeCdecl, CheckedDeref and CheckedMove IL instructions.

• For array indexing (a[i]), evaluate a, then evaluate i.
• For array creation (new T[i](e)), evaluate i, then evaluate e. The runtime system exposes a function called newarr that takes two arguments: the first is the length of the array and the second is the array's initialization value. You must call this function to allocate the array.
• Assignment always evaluates its right hand side first. If the left hand side is a variable, set the variable. If the left hand side is an index expression a[i], first evaluate a, then evaluate i.
• All array operations should be checked for nullness (eg, you should always set the null check flag on the IL instructions).

To compile code that deals with procedures, you will need to use the new InvokeCdecl IL instruction. Instead of building a single proc as you did in the previous project, this time around you will map each non-extern function to its own proc and pull everything together into an app. You will need to declare at least one special proc that first initializes the program's constants in order and then executes the program's expression. The provided code takes care of this.

• Function arguments in Invoke AST nodes are evaluated from left to right.
• The cdecl calling convention gives certain rules for decorating function names. When you want to create a name for or call a non-extern function, create a label using Apil.decorate_internal_function. If you want to call an extern function (including functions from the runtime system), create a label using Apil.decorate_external_function. Both of these functions use mk_label_named, so you need to make sure (for internal functions) that function names are distinct. The provided code takes care of decorating functions in the code generation context.

• Binary operators always evaluate their left-hand sides first, then their right-hand sides.
• Variable bindings in for loops appear (and are executed) in order. The expression for(int x = 1, int y = 2, int z = 3;;) () is equivalent to (int x = 1; int y = 2; int z = 3; for (; ; ) (()))
• null has a runtime representation of 0.
• () (unit) has no runtime representation.
• The return values of && and || are only defined up to zero or nonzero. 0 || 6 could be 1 or 6 (or even 42), but it can't be 0.

You can receive extra credit for this project for any of the following:

• Improvements to the runtime system.
• An especially clever or clear typechecker implementation.
• An especially clever or clear IL generator.
• A rigorous test suite.
• An interesting program implemented in the AT language that demonstrates new features. (We're looking for something closer to the Game of Life or robotfindskitten examples and farther from factorial.)

If you have an ambitious idea, you should check with us to see how much we think it could add to your grade.