Questions: Bidirectional Type Checking

Question 1

A type checker encounters the expression `λx. x + 1` in isolation. A pure type inference system cannot assign it a type. Under bidirectional type checking, what makes it possible to type this expression?

• A. The checker automatically infers the most general polymorphic type for the lambda
• B. An expected type propagated from surrounding context switches the checker to checking mode, pushing the parameter type inward
• C. The checker decomposes the lambda and infers each subexpression's type independently
• D. The compiler inserts a default type annotation when the programmer omits one

Answer: (B)

In synthesis (inference) mode, `λx. x + 1` cannot assign a type to `x` — the inference gets stuck. But if surrounding context provides an expected type like `Int → Int`, the checker switches to checking mode: the expected input type `Int` is pushed inward and assigned to `x`, then the body `x + 1` is verified against the output type `Int`. This direction-switching is the core mechanism of bidirectional checking — type information from annotations flows inward via checking mode to resolve expressions that synthesis mode cannot type alone.

Question 2

Bidirectional type checking produces better error messages than pure Hindley-Milner type inference primarily because:

• A. It uses a more powerful constraint solver that catches more errors
• B. It always requires explicit annotations, so errors are always at annotated sites
• C. Errors are reported at the exact subexpression where the actual type conflicts with the locally expected type, rather than where two distant constraints collide during unification
• D. It checks each expression twice — once in each direction — catching errors earlier in compilation

Answer: (C)

In pure Hindley-Milner, the unification engine accumulates constraints globally and may only discover a conflict far from its source — reporting an error in a function call when the real mistake was in a type annotation several scopes up. Bidirectional checking localizes errors because it always carries an expected type into checking mode: if you check `"hello"` against `Int`, the error points directly at `"hello"` and says it is not an `Int`. The expected type flows inward and catches mismatches at the exact subexpression, not at a distant indirect consequence.

Question 3

In bidirectional type checking, synthesis mode and checking mode are mutually exclusive — a given type checker uses one or the other throughout a program, not both.

• T. True
• F. False

Answer: False

False. Bidirectional type checking works by dynamically switching between synthesis and checking modes during a single pass over the program. A function application might synthesize the function's type, then switch to checking mode for each argument. A let-binding with an annotation switches to checking mode for the bound expression. The two modes are complementary and interdependent — this is the 'bidirectional' in the name. Forcing everything into one mode either loses information (pure checking with insufficient annotations) or becomes computationally expensive (pure inference with constraint solving).

Question 4

A lambda expression like `λx. x + 1` can be successfully type-checked in checking mode if the surrounding context provides an expected function type, even without an explicit annotation on the parameter `x`.

• T. True
• F. False

Answer: True

True. This is the canonical use case for checking mode. When an expected type like `Int → Int` is pushed into the lambda, the checker extracts the input type `Int` and adds `x : Int` to the local type environment. The body `x + 1` can then be verified against the output type `Int`. No explicit annotation on `x` is needed — the type information flows inward from the context. This is the practical value of bidirectional checking: reducing annotation burden while still typing expressions that pure inference cannot handle.

Question 5

Explain the difference between synthesis mode and checking mode in bidirectional type checking, and give an example of why each mode is needed.

Model answer: Synthesis mode produces a type from an expression — information flows out. It is used when the expression determines its own type, such as a variable (look up in context) or an integer literal. Checking mode verifies an expression against a supplied expected type — information flows in. It is used when the expression's structure does not determine a unique type, such as a lambda whose parameter type is unknown until the expected function type is provided. Both modes are necessary because different language constructs have different information-flow directions.

Pure inference (synthesis-only) tries to discover every type from scratch. For complex type systems this requires solving constraint systems globally, which is expensive and yields poor error messages. Pure checking (annotations everywhere) is correct but tedious. Bidirectional checking exploits each construct's natural information flow: function type annotations and let-binding signatures seed type information that flows inward through checking mode, while simple terms like variables, literals, and applications generate types upward through synthesis mode. The interaction propagates types efficiently and localizes errors naturally.