Study guides · Intermediate

Understand type checking and inference through constraints

Work through small typing rules and constraints to separate checking, inference and runtime validation, including the assumptions and limits of each.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Syntactic structure can still violate typing rules
  2. Compare what is already known
  3. Keep type environments distinct from value environments
  4. Generate constraints for x + 1
  5. Track function type variables without hiding polymorphism
  6. Unify type shapes under the stated rules
  7. Do not extend typing success into validation or authorization
  8. A constraint variable is not arbitrary polymorphism
  9. Exercise: show constraints and the source of failure
  10. Ask Logeia about this articleCheck your understanding

Syntactic structure can still violate typing rules

Parsing asks whether input has a permitted grammatical structure. Type checking applies typing rules to that structure and asks whether operations receive compatible kinds of values. For a teaching language, define distinct Int and Bool types and let addition take two Int operands and return Int. Then 1 + true can have an operator-and-operands shape while failing the typing rule. Do not import Python’s relationship between bool and integers into this deliberately different language. Also distinguish this paper extension from the earlier executable integer parser: that implementation has not silently acquired booleans or conditionals. We introduce a separate small set of typing rules to reason about them. State the available syntax and type contracts before interpreting either acceptance or rejection.

Compare what is already known

Checking can begin with declared information such as x having type Int and an expression expected to produce Int, then verify consistency with the rules. Inference derives information not yet written down. For x + 1, the addition rule constrains x to Int and establishes an Int result. This is not a statistical guess about types observed during execution. Our model generates constraints required by declared rules and asks whether assignments of types satisfy them. It does not imply that every annotation can be omitted in every language or that every program has a convenient inferred type. Supported syntax, polymorphism and recursive types change the problem. Practical systems can combine annotations and inference rather than belonging to two exclusive product categories.

Keep type environments distinct from value environments

The evaluator used an environment mapping x to a value such as twelve. A type environment instead maps x to a type such as Int. These tables resemble each other but answer different questions. Establishing the type of x + 1 does not require knowing whether x currently contains twelve or one hundred. An environment entry x:Int and an integer literal on the right satisfy the addition rule and yield Int. If a name is absent, the language must specify whether that is an undefined-name error or a place where an unknown type variable may be introduced. Our inference examples explicitly use the symbol alpha for an unknown type when that is the selected rule. They do not invent an arbitrary runtime value for x.

Generate constraints for x + 1

Assign unknown type alpha to x and beta to the complete expression. The literal one has type Int. Addition requires alpha = Int for its left operand, Int = Int for the right, and beta = Int for its result. Ignoring the trivial equality, substituting Int for both unknowns satisfies the constraints. This is a complete small inference without evaluating x. Now also use the same x as a conditional guard in a language requiring Bool there. That adds alpha = Bool. Because Int and Bool are distinct in our model, there is no assignment satisfying both requirements for this one binding. Rejection follows inconsistent constraints, not a sampled runtime value. Preserve which operation generated each constraint so that a diagnostic can explain more than simply saying types differ.

Track function type variables without hiding polymorphism

For a separate simple function model, an identity function returning its argument has type alpha to alpha. Applying it once to an integer adds alpha = Int. Whether one binding can then be used with both integers and booleans depends on the model’s polymorphism rules. A monomorphic binding sharing one unknown cannot satisfy alpha = Int and alpha = Bool simultaneously. A system that generalizes a type and instantiates fresh variables at each permitted use can behave differently. The important step is identifying when a type variable is shared and when a fresh one is introduced. Do not conclude that every unannotated identity function can be used at arbitrary types merely because its body is short. This discussion explains a distinction; it does not claim that the earlier parser implements a polymorphic inference engine.

Unify type shapes under the stated rules

The equation alpha = Int can be solved by substituting Int for alpha. Matching function types compares their input and output components separately. For alpha to Int and Bool to beta, the required substitutions are alpha = Bool and beta = Int. Distinct concrete types Int and Bool cannot be unified under our rules. A model restricted to finite simple types also cannot casually expand a variable into an infinite type containing itself; other type systems may support recursive types through their own rules. Do not present this chosen restriction as every language’s universal limit. Follow which shapes are compared and where inconsistency is detected. Retaining a failed constraint as well as a successful final type helps explain which use of an expression needs revision.

Do not extend typing success into validation or authorization

Knowing x has type Int does not establish nonnegative inventory or B’s authority to modify a particular document. An annotation on externally decoded age also need not convert a string into an integer or enforce an application range. Validate external values at a separate boundary before relying on their internal types. A typed expression may still encounter a zero divisor, a missing file or failed communication if those conditions are outside the chosen type system. Expressing more properties through types is a design option, not a reason to equate type compatibility with success under every condition. Combine type checking, tests, runtime validation and authorization according to their distinct contracts. Explaining which property was not encoded is part of using a type guarantee accurately.

A constraint variable is not arbitrary polymorphism

Within one constraint problem, α cannot silently mean whichever type is convenient at each occurrence. If the same α must equal both Int and Bool in this model, the constraints conflict. Supporting a polymorphic function at several types requires rules for generalizing variables and instantiating fresh ones at uses. Merely introducing type variables does not implement polymorphism. Keep the simple inference mechanism here separate from features of a richer type system and name the extra rule before relying on it in an example.

Exercise: show constraints and the source of failure

Infer the unknown types of x and the result in x + 2. The addition rule requires Int for both. Use the same monomorphic x as a Bool guard and the model becomes inconsistent; identify which use introduced each requirement. Next unify alpha to Int with Bool to beta. Setting alpha to Bool and beta to Int matches the input and output shapes. Solving that type problem is not executing the function, so draw type and value environments separately. As a final exercise, name an integer input an application should reject despite its type: negative inventory is one example if the range is not encoded in the type. Being able to trace constraints while stating the remaining runtime responsibilities is the intended outcome.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 19

Choose a learning path