CS374: Principles of Programming Languages - Lab: Type Checker Starter (100 Points)

Purpose, Task, and Criteria

Purpose: To build the core of the Interpreter assignment's required static type checker with a partner — literal, variable, and operator checks over the class AST, running before any code is evaluated.

Task: With a partner, implement a checker that walks the class AST with a type environment, verifying annotated declarations, variable uses, and operator applications, and reporting positioned type errors.

Criteria: Assessed on a checker that accepts the well-typed programs and rejects each ill-typed program with a positioned two-type error message, plus a set of typing-rule statements written on paper, weighted 70/30 across the two parts; see the rubric below for the full breakdown.

Assignment Goals

The goals of this assignment are:
  1. To implement a static checking pass over the class AST using a type environment that mirrors the Environment class
  2. To check annotated declarations, variable uses, and operator applications, reporting errors with positions and both conflicting types
  3. To state typing rules precisely on paper before encoding them

Background Reading and References

Please refer to the following readings and examples offering templates to help get you started:

The Assignment

This lab builds the core of the Interpreter assignment’s Part 4 — the small static type checker that runs between parsing and evaluation. Here you get the machinery working on the checker’s three foundational cases (literals, variables, operators) with a partner; the assignment then extends it to call sites and return types on your own. Budget two to three hours.

Pair policy: this lab may be completed in pairs. Both partners submit the same files, each naming the other, and both earn the same grade. (You may also work alone.) The Interpreter assignment remains individual work: you may both carry this shared checker core into it, but the extension to calls and returns must be your own.

Part 1: The Checker Core (70 points)

Implement check(program) -> None in typechecker.py, walking the class AST (use your Parser assignment’s AST nodes, or the reference AST) with a type environment — the same parent-chaining discipline as your Environments lab, but binding names to types rather than values:

  • Literals: numbers are Num, strings are Str, booleans are Bool.
  • Declarations: let x: Num = expr; checks that expr’s type equals the annotation, then binds x : Num in the current scope. A mismatch is an error naming both types.
  • Variables: a use of x looks up its declared type; an undeclared use is a positioned error.
  • Operators: + - * / require Num operands and yield Num; < <= > >= require Num and yield Bool; == != require both sides to have the same type and yield Bool; and/or/not require Bool. Every violation is reported as Type error at line L, col C: ... naming both conflicting types.

Verify against the provided programs (course starter repo): six well-typed programs that must pass silently, and six ill-typed programs that must each produce a positioned error — including the classic let x: Num = 1 + true; (error before anything runs) and a shadowing case where an inner let x: Str legitimately changes the type of x for the inner scope only.

Part 2: Typing Rules on Paper (30 points)

In RULES.md, state the typing rule for each construct your checker covers — one rule per construct, premises and conclusion, in either inference-rule layout or a disciplined “if… then…” sentence (e.g., if e1 : Num and e2 : Num, then e1 + e2 : Num). Cite, for each rule, the function or branch in typechecker.py that implements it. This document becomes the seed of the Interpreter assignment’s semantics writeup — and if you later choose the full Hindley-Milner direction, these rules are exactly what inference generalizes.

Close RULES.md with two theory questions from the Type Systems session: (1) place four languages — Python, C, Haskell, and JavaScript — on the static/dynamic × strong/weak quadrant, with one sentence of justification each; (2) your checker makes the class language gradually typed in spirit (annotated declarations are checked, unannotated territory is documented as unchecked) — state one benefit and one risk of that middle ground, using the mypy/TypeScript comparison from class.

Deliverables

Submit a ZIP containing typechecker.py, the run log over the twelve provided programs, and RULES.md with both partners named.

Grading Breakdown

Component Points
Part 1: The Checker Core 70
Part 2: Typing Rules on Paper 30
Total 100

Reflection Prompts

  • Your checker rejects while 1 { ... } if you require a Bool condition, though the evaluator’s truthiness rule would happily run it. Which behavior do you consider correct for the class language, and why?
  • If you worked in a pair, who did what, and name one thing your partner caught that you would have missed. If you worked alone, note that instead.
  • AI disclosure: list any generative-AI tools you used, for what, and how you verified the results (or state ‘none’).
  • Approximately how many hours it took you to finish this lab (I will not judge you for this at all — I am simply using it to gauge if the labs are too easy or hard)?

Submission

In your submission, please include answers to any questions asked on the assignment page, as well as the questions listed below, in your README file. If you wrote code as part of this assignment, please describe your design, approach, and implementation in a separate document prepared using a word processor or typesetting program such as LaTeX. This document should include specific instructions on how to build and run your code, and a description of each code module or function that you created suitable for re-use by a colleague. In your README, please include answers to the following questions:
  • Describe what you did, how you did it, what challenges you encountered, and how you solved them.
  • Please answer any questions found throughout the narrative of this assignment.
  • If collaboration with a buddy was permitted, did you work with a buddy on this assignment? If so, who? If not, do you certify that this submission represents your own original work?
  • Please identify any and all portions of your submission that were not originally written by you (for example, code originally written by your buddy, or anything taken or adapted from a non-classroom resource). It is always OK to use your textbook and instructor notes; however, you are certifying that any portions not designated as coming from an outside person or source are your own original work.
  • Approximately how many hours it took you to finish this assignment (I will not judge you for this at all...I am simply using it to gauge if the assignments are too easy or hard)?
  • Your overall impression of the assignment. Did you love it, hate it, or were you neutral? One word answers are fine, but if you have any suggestions for the future let me know.
  • Using the grading specifications on this page, discuss briefly the grade you would give yourself and why. Discuss each item in the grading specification.
  • Any other concerns that you have. For instance, if you have a bug that you were unable to solve but you made progress, write that here. The more you articulate the problem the more partial credit you will receive (it is fine to leave this blank).

Assignment Rubric

Description Pre-Emerging (< 50%) Beginning (50%) Progressing (85%) Proficient (100%)
The Checker Core (Goals 1, 2) (70%) The checker is missing, or it never rejects an ill-typed program The checker rejects some ill-typed programs but misses operator mismatches, or it crashes on programs it should reject cleanly All provided ill-typed programs are rejected, but error messages lack positions or name only one of the two conflicting types Every provided well-typed program is accepted and every ill-typed program rejected with a message of the form "Type error at line L, col C" naming both conflicting types; the type environment correctly scopes annotations through nested blocks
Typing Rules on Paper (Goal 3) (30%) No rules are written, or they contradict the implemented checker Rules are written for literals only Rules cover literals, variables, and operators but at least one rule is imprecise about its premises Each covered construct has a precise rule (premises above, conclusion below, or a disciplined if/then sentence), and each rule cites the checker function that implements it

Please refer to the Style Guide for code quality examples and guidelines.