In this project, you’ll implement the semantic analysis for this mini-language. I’ve already implemented the bits that fill in the symbol table (which is basically the same as the mega-example’s scope_test program). You’ll be implementing the type inference rules for expressions.

Quick start guide:

  1. git clone the project 2 repo to your computer.
  2. Edit the src/sem/typecheck.rs file to make the the typechecker work. (Read below.)
    • Use cargo test to see how you’re doing.
  3. As you work, make use of git commits to keep track of your progress.
  4. When you’re done (or when you’re not done but it’s due):
    1. Update the README.txt to include your name and username and any information you think will be useful to the grader.
    2. Also update this line in Cargo.toml:
      • authors = ["YOUR NAME <YOUR PITT EMAIL>"]
    3. Commit those changes, and…
    4. git push origin master to submit it.
      • the last commit before the due date is what we will grade.

The starting point

There isn’t really a main program for this project, so cargo run doesn’t do anything useful.

If you cargo test right now, you’ll get some warnings about unused methods and variables (that’s fine). It’ll show the outputs of several tests, and all but two are failing. Once again, your goal is to make all the tests happy!

src/sem/typecheck.rs is where you’ll be doing your work. Here is what is currently implemented:

Finally, the visit_exp method is where you’ll be doing your work. Right now, it says that every expression is type Error, which is a placeholder type that is never valid.


The helper functions I’ve given you


Starting easy (tests: expr_literals, expr_global_identifiers)

First, look at the test functions. They’re in tests/tests.rs (outside the src/ directory). The ones named expr_ are the primary ones you’re trying to make work. The ones named stmt_ will begin working as you implement expressions. Keep this file open so you can refer to it when your tests fail.

Right now, these two tests succeed: stmt_func_decls and stmt_globals_and_func_signatures, only because I gave you the code for those.

Now, back in src/sem/typecheck.rs, in the visit_exp method, you’ll see these three lines:

IntLit(..) =>  Box::new(Type::Error),
BoolLit(..) => Box::new(Type::Error),
StrLit(..) =>  Box::new(Type::Error),

That seems easy to fix. Change the Type::Errors to Type::Int, Type::Bool, and Type::String instead, then cargo test again. Great! expr_literals and stmt_for now pass.

Another low-hanging fruit is the Id(name) case. Replace Box::new(Type::Error) with self.lookup(&name)?. Now these three tests pass: expr_global_identifiers, stmt_func_returns, and stmt_local_variables.

Wow, 7 tests down, 8 to go. This’ll be easy, right? ;)


A little harder (test: expr_unary_operators)

In the Unary { op, lhs } case, you’ll do something like this.

  1. recursively visit lhs using visit_exp to get its type ty.
    • See visit_stmt’s Exp { exp } case to see how to write that.
  2. match on op, and…
    • if it’s UnOp::Neg, ty should be Int.
    • if it’s UnOp::Not, ty should be Bool.
  3. return ty.

You’ll be using check_types_match to do the checking, like how visit_stmt checks the type of the conditions for if and while statements. For the third argument, you can pass &e.to_string().

Now expr_unary_operators should pass.

The tests are picky about the exact error messages your code gives. If your test is failing with a message like “expected error… but your code gave error…”, look carefully at how you wrote the error message!


Function calls (test: expr_call)

In Call { callee, args }, recursively visit callee and get its type.

The rule for function calls works like this:

Whew… now expr_call should pass.


Relational operators (test: expr_relational_operators)

Finally, the Binary { op, lhs, rhs } case, and it has several parts. Let’s start with the relational and logical operators.

First, recursively get the types of lhs and rhs. Then, match on op.

You can reduce typing with use, like so:

use BinOp::*; // brings in all the binary operator types

match op {
    Add => ...
    Sub => ...
}

You can also match multiple values by writing them like this:

match op {
    Less | Greater | LessEq | GreaterEq | Eq | NotEq | And | Or => ...
}

These operators all have the same behavior: <, >, <=, >=, ==, !=:

  1. the lhs must be an int or string.
    • if not, return Err(self.type_mismatch_error(&lhs_type, "'int' or 'string'", &format!("lhs of '{}'", e))).
  2. the rhs’s type must be the same as the lhs’s.
    • important: pass the rhs’s type as the first argument to check_types_match!
      • I totally didn’t make this mistake, nope ;O
    • the third argument is &format!("rhs of '{}'", e)
  3. the resulting type is always bool.

For and, and or (and and or are our language’s spelling of && and ||):

  1. both lhs and rhs must be bool.
  2. the resulting type is always bool.

Now expr_relational_operators should pass… but so should several others! The only ones left are expr_assignment, expr_arithmetic_operators, and stmt_exp.


Assignment (test: expr_assignment)

Assignment is a little funny. It works like this:

  1. check that the lhs is actually a valid place to assign into, with self.is_assignment_lhs().
    • if not, return Err(SemError::InvalidLhs(e.to_string())).
  2. check that the rhs’s type matches the lhs’s, like above.
  3. the resulting type is always void. yep!

Making assignments void solves a few things. It makes the common typo if(x = 5) a semantic error, since the condition must be bool, not void. Also, expression statements must give void so that every statement does something (has a side effect). Writing 3 + 5; is a semantic error because its type is int. Where does the 8 go? Well, we can assign it, or we can pass it to a function that returns void.

With that, all but one test should now pass!


Arithmetic operators (test: expr_arithmetic_operators)

Most of these operators behave the same: +, -, *, /, %, <<, and >>. However, + is also going to be our stupid “addition and string concatenation” operator! Whee!

For the Add operator, the lhs can be int or string. For all the others, the lhs must be int.

After that, they’re all the same:

  1. the rhs type must be the same as the lhs type.
  2. the resulting type is the lhs type.

That’s it. Now all tests should pass, and you’re done.


Submission and Grading

Project submissions will only be accepted through GitHub. If you are having trouble using git, please get in touch sooner rather than at 11:58 PM on the due date.

The project is due at midnight on the due date, but there is some wiggle room there. (We can see the time that you pushed to GitHub.)

You can turn it in for late credit until midnight on the day after the due date. You’ll get 10% off your grade.

Grading rubric: