Assignment 3

For this course, we're not going to worry about parsers, the interpreter comes with a parser. But this has a couple caveats:

• it's more convenient to build a single parser and use it for every interpreter we'll use. This means our parser──and in particular our AST──has a lot of stuff we won't be working with initially.

• Since we're using a single parser, we might as well trick it out with nice error messages. To do this, our AST carries metadata about the location of subexpressions in the source program (this is how we know where the error is when we display the message). This isn't terribly complex, but it does affect the way we work with ASTs slightly: we cannot pattern match on an AST directly, we have to pattern match on its associated data, which we get by record access (ASTs are represented as records). This is why──in saltO, for example──you'll see things like:

  match expr.expr with
  | ...
  | _ -> Error (not_implemented expr.meta)
  

  expr.expr is the "actual" AST whereas expr.meta is the location information for expr.

We know what to do here. I've given you some typing rules, you need to implement them.

Just one thing: in order to simplify things, we'll always work within ('a, Error_msg.t) result to deal with type errors.¹ The module Error_msg deals with error messages. For the most part, you don't need to know what's going on here (though I recommend looking if you're interested). The only important function is Error_msg.mk, which takes the location metadata of an AST and a string for the message itself. To make things easy on you, I'll always include a collection of smart constructors in a module called Errors for the kinds of errors you will encounter in writing the type checker. When you're writing an error branch in the type checker, you should use Error e, where e uses a smart constructor. For example, from salt0:

match e.expr with
| PlaceExpr (Var x) -> (
    match Map.find_opt x ctxt with
    | None -> Error (unknown_var e.meta x)
    | Some ty -> Ok ty
  )
| ...

unknown_var is a smart constructor which takes a variable name and the location information for that variable. For example, running the interpreter on the program:

fn main() {
    let x = 2;
    let z = x + y;
}

will display the error message:

error: unknown variable `y`
 --> lib/example.rs:3:17
  |
3 |     let z = x + y;
  |                 ^ unknown variable `y`

Again, there are quite a few parts of the AST that we're not using. You should use the not_implemented smart constructor when you come across something we haven't talked about.

There is one notable tricky case for types: BorrowTy.

• For now, always assume that a reference is Immutable.
• Eventually, we will need references to keep track of multiple place expressions, so the constructor BorrowTy keeps track of a list of place expressions. For now, always assume that the list is a singleton.
• BorrowTy also keeps track of the underlying type associated the reference. This is does so that it's possible to pretty-print the borrow type as it would be printed by Rust (e.g., &i32 and not &x).

You know the evaluation rules, you need to build the evaluator. And there's no need to deal with errors; because of type soundness, if your program type checks, evaluation is guaranteed to succeed (which means assert false will be used quite a bit).

There's a lot I'm probably forgetting to mention here. This is very much an experiment, y'all are helping me stress test these assignments. Please ask lots of questions, and let me know if you have any thoughts about improvements. Also, if you want a hard mode for this assignment, I'll just say that there's a couple parts of the language that are "fair game" in the sense that they don't require new concepts, but are not implemented in the base salt1. These include:

• Booleans
• Assert statements
• Arithmetic/Boolean operators

Generally speaking, explore the AST, see if there's anything you want to add. If you're really feeling up to it, extend the parser(!)