Answers · How a program runs

Why does the compiler catch a type mismatch but not division by zero?

In shortA compiler checks types before running because types are known for every possible run; it cannot know a divisor is zero until the program actually runs.

The compiler catches a type mismatch because types are known before the program runs, and a rule about types must hold for every possible run. It cannot catch division by zero in general because whether a divisor is zero depends on a value that exists only while the program runs.

What is known before execution

Before any instruction executes, the names in the tree have been resolved to declarations. Each leaf then has a type: a literal from its form, a name from the declaration it points at. The checker walks upwards. At each operation it applies the rule for that operation to the types of the children. If the children fit, the node gets a type. If they do not, the node is an error. This is the last point at which the compiler can refuse the program, and the refusal is based on the tree alone. Nothing in that description needs a value. It needs only the shape of the expression and the declarations it refers to.

\frac{\Gamma \vdash a : \mathsf{whole} \qquad \Gamma \vdash b : \mathsf{whole}}{\Gamma \vdash a / b : \mathsf{whole}}

Take an expression such as 6 / b, where b is a whole-number name. The leaf 6 is a whole number by its form. The leaf b is a whole number by its declaration. The division rule accepts a pair of whole numbers and produces a whole number. That is the whole type check for the node. It is true whether b later holds 2, 3, or 0. The rule is not asking what b is. It is asking what kind of thing b is.

A mismatch looks different. Suppose count is a whole number and f is a function. The add rule wants a matching pair of numbers. The leaf count gives a whole number. The leaf f gives a function. At the add node the children do not fit, so no type can be produced. The checker does not need to know what count is, or what f would do if called. It needs only the types that came up from the leaves.

Where the value enters

Now run the same expression with different values in b. With b equal to 2 the result is 3. With b equal to 3 the result is 2. With b equal to 0 there is no result: the division has no value. The type of every leaf is unchanged across those runs. What changes is the value, and the value is not present at the earlier stage. The checker can see that b is a whole number. It cannot see that this particular b is zero unless the language makes the zero part of the type.

\frac{6}{2}=3,\qquad \frac{6}{3}=2,\qquad \frac{6}{0}\ \text{is undefined}.

The natural guess is that a compiler should catch every error it can describe. That guess fails because the two errors are not the same kind of claim. 6 / b where b is a function is a mismatch at the node: the division rule requires numbers and gets a function, so the node cannot be typed. 6 / 0 has no mismatch at the node: both children are numbers and the rule fits. The failure is in the value, after the rule has already been satisfied. A compiler that rejected every division because the divisor might be zero would reject 6 / 2, which is fine. A compiler that accepted every division because some divisors are nonzero would miss the zero. Without values it has no way to tell those runs apart.

FIG 1

Mistake	What it depends on	Settled before the run?
a misspelt name	the declarations in scope	yes
adding a number to a function	the types of the children	yes
dividing by a value that turns out to be zero	the value at run time	no
reading past the end of a list	the length at run time	no

Why not decide it in general

It is not that the checker lacks effort. The general question, whether a program ever divides by zero on some input, is not answerable by any procedure that always finishes. Every checker therefore makes a conservative choice: it rejects some programs that would have run correctly, in exchange for never accepting a program that breaks the rule it is checking. Type rules are a clean choice because they can be checked from the tree alone. Division by zero is not, unless the type system is given more information.

Languages can move the boundary by making the divisor carry a type that says it is not zero. If b has type NonZero rather than plain whole number, the division rule can require a NonZero denominator, and 6 / b is checked before the run. Nothing is free: the information has to come from somewhere, either a literal that is visibly nonzero or a check at the point where an outside value enters. The compiler is then checking a stronger type, not performing a magic runtime inspection.

Before the program runs there is no zero to find, only a name whose type permits zero and whose value has not been chosen.

Worth keeping

A type rule is a statement about every possible run, so it can be checked from the program text alone.
Whether a divisor is zero is a statement about one value in one run, so it is not available before execution.
A language can make division by zero checkable only by requiring the programmer or the boundary code to prove that the divisor is not zero.

Where this goes next

This question is one step of Turning Text Into Instructions, a course that works through its subject from the beginning. The page that teaches this part of it is Deciding What It Means, and it reads the whole way through whether or not you have an account.

What an account changes is the practice: problems standing under every idea, marked with a reason rather than a tick, in a copy of the course that is yours.

Read that page The whole course