Lesson 6.3 — Syntax-directed checking, implicit conversions and overloading¶

Techniques: syntax-directed (bottom-up) type checking with an error type, as in C and Java compilers (Algol 68, Pascal, C; [ALSU07, §6.5]); implicit conversions and numeric promotion — C's usual arithmetic conversions [C11, §6.3.1.8], Java's widening contexts [JLS21-5], explicit casts in Rust, Swift and Pebble — and coercion as an alternative to subtyping (Reynolds 1980; [BTCGS91]); type-directed overload resolution by conversion ranking (C++ [CPP-Over]; Java's three phases; Swift's constraint solver) · Pebble implements: synthesis for every expression form, the error type, no implicit conversions (E1, E2, E6) · Drills: typing-derivation · Prerequisites: Lesson 6.1; Lesson 5.4 (overload resolution as name resolution) · Time: 4 hours

Lesson 6.1's algorithm assumed a perfect program: the first failed premise ended the run. A compiler's checker must do more. It checks declarations and statements, not only expressions; it reports every independent mistake in one run without drowning the real ones in consequences; and in most languages it silently changes the program, inserting conversions (C's int to double) or choosing among same-named functions by their argument types. This lesson is the checker that C and Java compilers run — every type computed bottom-up from the leaves — with the error type that keeps diagnostics honest, the conversion rules that make -1 < 1u false in C, and the ranking that makes f(1, 2) ambiguous in C++.

1. Problem and motivation¶

Syntax-directed type checking¶

The problem. Given a resolved AST (Chapter 5), compute the type of every expression and declaration, check every statement, and report every error once, at the right place. The syntax-directed discipline computes each expression's type from its subexpressions' types alone (a synthesized attribute, Lesson 5.5): information flows only upward. It is the discipline of the Dragon book's type checker [ALSU07, §6.5], of C and Pascal compilers, and of Java's checker for most expression forms (Java adds target typing for lambdas and generic methods: Lesson 6.4). It makes the checker a single post-order walk and its errors local; its limitation is that nothing above an expression can influence its type, which is why C needs a cast to write (double)1 / 3 and why Lesson 6.4 adds a second mode. In Pebble, every expression form of pebble-spec §8 has a synthesis rule; E1–E3 implement them.

Implicit conversions and numeric promotion¶

The problem. Programs mix char, int, long and double. A language either converts operands implicitly to a common type before an operation (C, C++, Java, JavaScript), or requires every conversion to be written (Rust's as, Swift's initializers, Pebble's as). C's rules — integer promotion and the usual arithmetic conversions [C11, §6.3.1.1, §6.3.1.8] — date from the PDP-11 implementation, where char operands were widened to int registers anyway. They make mixed arithmetic convenient and are a classic source of bugs (-1 < 1u is false). Formally, an implicit conversion is a coercion: the checker elaborates the program by inserting conversion functions [BTCGS91], an alternative to subtyping for relating types (int is not a subtype of double; it converts to one). Pebble has none except the literal rule (pebble-spec §5), so let n = 1; let x: float = n; is E0401.

Overload resolution¶

The problem. When one name denotes several functions (abs(int), abs(double)), the checker must pick one per call, using the arguments' types. C++'s solution — build the candidate set, keep the viable functions, rank each argument's implicit conversion sequence, and select a function that is at least as good on every argument and better on one — goes back to the ARM (Ellis and Stroustrup 1990; the rationale is [Str94, §11.2]) and is now [CPP-Over]. Java resolves in three phases (without boxing, with boxing, with varargs) [JLS21-5]; Swift ranks whole solutions of its constraint system (Chapter 7). Lesson 5.4 treated overloading as a name-resolution problem; here it is a typing problem: resolution needs the arguments' types, so it runs inside the checker, after the arguments have been synthesized. Pebble has no overloading, which keeps its checker syntax-directed; the lesson's C++ and Java boxes show what the extra step costs in error quality.

2. Definitions and algorithms¶

Syntax-directed type checking¶

Definition 6.3.1 (Checker as elaboration)

A checker maps a resolved AST to an annotated AST in which every expression node carries a type (Pebble: Expr::setType; Clang: the type of every Expr), every declaration its type, and every implicit operation an explicit node (Clang's ImplicitCastExpr); or it reports errors. It is syntax-directed if the type of each expression node is a function of its form and its children's types only (a synthesized attribute, Lesson 5.5).

Definition 6.3.2 (The error type and compatibility)

Add a type \(\mathsf{err}\) (Pebble <error>) given to every expression whose typing rule failed or that depends on one. Two types are compatible, \(\tau \approx \sigma\), if \(\tau = \sigma\) or either is \(\mathsf{err}\). Every premise of the form "has type \(\tau\)" is checked up to \(\approx\), and every rule whose operand has type \(\mathsf{err}\) returns \(\mathsf{err}\) without reporting (for operators) or returns its fixed result type (for casts and calls, whose result type does not depend on the operands).

Algorithm 6.3.3 (Syntax-directed checker with error recovery)

Input: a module whose names are resolved; for Pebble, the output of resolveNames.
Output: every declaration and expression annotated with a type; a list of diagnostics.
Precondition: every name use is bound to its declaration (or to an error symbol, Lesson 5.8).
Postcondition: every node has a type (none is left unset); a diagnostic is reported at node \(n\) only if no child of \(n\) has type \(\mathsf{err}\) (Proposition 6.3.9).
Invariant: when Synth(e) returns, e and every subexpression of e carry a type.

function CheckModule(M):
    for each struct S: for each field f: f.type ← Declared(f.typeRepr)
    for each function F: F.params, F.result ← Declared(…)      # pass 1: signatures
    for each function F with a body: CheckBlock(F.body, F)       # pass 2: bodies

function Synth(e):                                   # returns e's type and records it
    τ ← case e of
        literal:      its type
        name x:       x.decl.type                    # err if x did not resolve
        e1 op e2:     a ← Synth(e1);  b ← Synth(e2)
                      if a = err or b = err: err
                      elif (op, a, b) ∈ OperatorTable: result type from the table
                      else: Report(E0402 at op);  err
        f(e1, …, ek): ts ← [Synth(ei) for each i]
                      if f.decl is none: err
                      elif k ≠ arity(f): Report(E0405 at f); f.result
                      else: for each i: if not ts[i] ≈ f.param[i]: Report(E0401 at ei)
                            f.result
        e1[e2]:       a ← Synth(e1);  i ← Synth(e2)
                      if not i ≈ int: Report(E0401 at e2)
                      if a = err: err elif a = [T; N]: T else Report(E0406 at e1); err
        …             # one case per form of pebble-spec §8
    e.type ← τ;  return τ

function CheckStmt(s, F):
    case s of
        let x [: T] = e:  τ ← Synth(e)
                          if T given: if not τ ≈ T: Report(E0401 at e);  x.type ← T
                          else: x.type ← τ
        place = e:        if not Synth(e) ≈ Synth(place): Report(E0401 at e)
        if c { … }:       if not Synth(c) ≈ bool: Report(E0410 at c);  check branches
        return e:         if not Synth(e) ≈ F.result: Report(E0401 at e)
        …

Declared(r) turns a type repr (already resolved by Chapter 5) into a type, reporting invalid ones (E0419, E0420) and returning err for them. The OperatorTable of Pebble is pebble-spec §8.3–§8.5: + on (int, int) or (float, float), && on (bool, bool), and so on.

Implicit conversions and numeric promotion¶

Definition 6.3.4 (Integer conversion rank, promotion, widening)

In C [C11, §6.3.1.1], each integer type has a rank: _Bool < char = signed char = unsigned char < short < int < long < long long, with signed and unsigned variants of equal rank. Integer promotion converts an operand of rank below int to int if int can represent all its values, otherwise to unsigned int. A widening conversion is one whose target can represent every value of the source (Java's §5.1.2: byte → short → int → long → float → double, where int → float may lose precision but not magnitude).

Definition 6.3.5 (Coercion; coherence)

A coercion from \(\sigma\) to \(\tau\) is a function \(c_{\sigma \to \tau}\) that the checker inserts where a value of type \(\sigma\) is used where \(\tau\) is required; the elaborated program applies it explicitly. A set of coercions is coherent if any two chains of coercions from \(\sigma\) to \(\tau\) denote the same function, so that the meaning of a program does not depend on which chain the checker picked [BTCGS91].

Algorithm 6.3.6 (C's usual arithmetic conversions, C11 §6.3.1.8)

Input: the types \(A\), \(B\) of the two operands of a binary arithmetic or comparison operator.
Output: the common type \(C\) to which both operands are converted, and the operator's operand type.
Precondition: \(A\) and \(B\) are arithmetic types (after array/function decay).
Postcondition: \(C\) is determined by the types alone (not the values); the operation is performed in \(C\).
Invariant: each rule applies only if all earlier rules did not.

function UsualArithmeticConversions(A, B):
    if A or B is long double: return long double
    if A or B is double:      return double
    if A or B is float:       return float
    A ← IntegerPromotion(A);  B ← IntegerPromotion(B)     # Definition 6.3.4
    if A = B: return A
    if A and B are both signed or both unsigned:
        return the one of greater rank
    let U be the unsigned one, S the signed one
    if rank(U) ≥ rank(S): return U
    if S can represent every value of U: return S
    return the unsigned type corresponding to S

Overload resolution¶

Definition 6.3.7 (Candidates, viability, conversion sequences, ranking)

For a call \(f(a_1, \dots, a_k)\) with argument types \(A_1, \dots, A_k\): the candidate set is every function named \(f\) found by lookup (including ADL, Lesson 5.4). A candidate \(F(P_1, \dots, P_k)\) is viable if each \(A_i\) converts to \(P_i\) by an implicit conversion sequence \(\mathrm{ICS}_i(F)\). Standard conversion sequences have a rank [CPP-Over, [over.ics.rank]]: Exact match (identity, l-value-to-r-value, array/function decay, qualification) \(<\) Promotion (integral promotion, float → double) \(<\) Conversion (every other arithmetic conversion, pointer conversions). \(F\) is better than \(G\), \(F \succ G\), if \(\mathrm{ICS}_i(F)\) is not worse than \(\mathrm{ICS}_i(G)\) for every \(i\) and better for at least one.

Algorithm 6.3.8 (Best viable function)

Input: the candidates of a call and the synthesized argument types.
Output: the unique best viable function, no viable function, or ambiguous (with the tied candidates).
Precondition: every argument's type has been synthesized (syntax-directed: arguments first).
Postcondition: the returned \(W\) is viable and \(W \succ G\) for every other viable \(G\) (Theorem 6.3.13).
Invariant: after the first loop, no candidate after \(W\) in the list is better than \(W\).

function BestViable(cands, argTypes):
    viable ← [F in cands if every argTypes[i] converts to F.param[i]]
    if viable is empty: return NoViable
    W ← viable[0]
    for F in viable[1..]:                      # pass 1: a tournament
        if Better(F, W): W ← F
    for F in viable, F ≠ W:                    # pass 2: W must beat everyone
        if not Better(W, F): return Ambiguous(W, F)
    return W

function Better(F, G):                         # F ≻ G, Definition 6.3.7
    some ← false
    for i in 1..k:
        c ← CompareRank(ICS_i(F), ICS_i(G))
        if c = worse: return false
        if c = better: some ← true
    return some

3. Worked examples¶

Syntax-directed type checking¶

The Pebble function below has two independent mistakes. Algorithm 6.3.3 visits its expressions in post-order (the synthesis mode of the reference checker; the note "expected ... because of this" of E0401 comes from Lesson 6.4's checking mode and is left out here):

fn area(w: int, h: float) -> float {
    let a = w * h;              // line 2
    let b = a + 1.0;            // line 3
    let ok = b > 0.0 && w;      // line 4
    return b;
}

step	node	children's types	rule	type	report
1	`w` (2:13)	—	name	`int`	—
2	`h` (2:17)	—	name	`float`	—
3	`w * h`	int, float	`*` needs equal numeric operands	`<error>`	*E0402 at `` (2:15)**
4	`let a`	`<error>`	no annotation	`a : <error>`	—
5	`a` (3:13)	—	name	`<error>`	—
6	`1.0`	—	literal	`float`	—
7	`a + 1.0`	`<error>`, float	an operand is `err`	`<error>`	none (would be a cascade)
8	`let b`	`<error>`		`b : <error>`	—
9	`b > 0.0`	`<error>`, float	an operand is `err`	`<error>`	none
10	`w` (4:25)	—	name	`int`	—
11	`b > 0.0 && w`	`<error>`, int	an operand is `err`	`<error>`	none
12	`return b`	`<error>` vs `float`	\(\approx\)	—	none

Only one error is reported, at the root cause (step 3). Without the error type, steps 7, 9, 11 and 12 would each report a consequence.
The second mistake, && w with w : int, is hidden by the first one: b is already <error>. After fixing line 2 (w as float * h), a re-run reports E0402 at && (4:22). Hiding an independent error is the price of never reporting a cascade (Proposition 6.3.9).

Implicit conversions and numeric promotion¶

Algorithm 6.3.6 on double g(int a, unsigned char c, float x) { return a * c + x; } (the box in §7 shows Clang's elaborated tree):

step	expression	operand types	rule of Algorithm 6.3.6	common type	inserted conversions
1	`a * c`	int, unsigned char	no floating operand; promote `unsigned char` → `int` (all values fit)	`int`	`c` : IntegralCast to `int`
2	`(a * c) + x`	int, float	one operand is `float`	`float`	`a * c` : IntegralToFloating
3	`return …`	float to `double`	assignment conversion to the result type	`double`	FloatingCast

And on the comparison -1 < 1u (int, unsigned int): both already promoted; one signed, one unsigned of equal rank → rule "rank(U) ≥ rank(S)": the common type is unsigned int; -1 converts to \(2^{32} - 1\) and the comparison is false.

Overload resolution¶

Algorithm 6.3.8 on the three calls of the clang++ box in §7 ('a' has type char):

call	viable candidates	ICS per argument	pass 1 winner	pass 2	result
`f(1, 2)`	`f(int, double)`, `f(double, int)`	(Exact, Conversion) vs (Conversion, Exact)	`f(int, double)` (the second is not better)	`f(int, double)` does not beat `f(double, int)` either	ambiguous
`g(1)`	`g(long)`, `g(unsigned)`	Conversion vs Conversion	`g(long)`	neither is better	ambiguous
`h('a')`	`h(int)`, `h(double)`	Promotion vs Conversion	`h(int)`	`h(int)` beats `h(double)`	`h(int)`

Java's three phases on m(1) with m(long) and m(Integer): phase 1 (no boxing) finds m(long) by widening, so phase 2 (boxing) never runs; on n(1) with n(Object) and n(int...): phase 1 finds nothing, phase 2 finds n(Object) by boxing to Integer, so the varargs phase never runs (the javac box prints m(long) n(Object)).

4. Invariants and correctness¶

Syntax-directed type checking¶

Proposition 6.3.9 (The error type prevents cascades)

In Algorithm 6.3.3, a diagnostic is reported at a node \(n\) only if none of the types it compares is \(\mathsf{err}\); in particular, a node whose children include one of type \(\mathsf{err}\) reports nothing about that child. Every node receives a type, and \(\mathsf{err}\) is given only to nodes whose rule failed or that depend on such a node.

Proof

By inspection of the cases, which is an induction on the post-order visit: every case either (i) returns \(\mathsf{err}\) immediately when an operand type is \(\mathsf{err}\), or (ii) compares types with \(\approx\), which holds whenever one side is \(\mathsf{err}\) (Definition 6.3.2), so no report follows. A report is issued only on a comparison between two non-\(\mathsf{err}\) types or a structural failure of a non-\(\mathsf{err}\) type (E0406 on int), and in that case the node's type becomes \(\mathsf{err}\), which by (i)–(ii) silences every ancestor that depends on it. Totality: every case ends with e.type ← τ for a defined \(\tau\), and the recursion visits every child (Invariant).

Theorem 6.3.10 (Conservativity of the error type)

On a program with no type error, Algorithm 6.3.3 reports nothing and assigns every expression the type of Lesson 6.1's derivation (Algorithm 6.1.6 extended to the same forms); on a program with type errors it reports at least one.

Proof

If no rule fails, \(\mathsf{err}\) is never introduced (by Proposition 6.3.9 it is only introduced on failure), so every comparison with \(\approx\) is an equality comparison and every case computes exactly the type Algorithm 6.1.6 computes; by Theorem 6.1.11 that is the derivation's type. Conversely, if the program has a type error, consider a node of minimal depth-first finishing time whose rule fails: its children all carry non-\(\mathsf{err}\) types (they finished earlier and none failed, and \(\mathsf{err}\) only arises from failures), so by Proposition 6.3.9 its failure is reported.

Implicit conversions and numeric promotion¶

Proposition 6.3.11 (The usual arithmetic conversions are total and symmetric but not value-preserving)

For all arithmetic types \(A, B\), Algorithm 6.3.6 returns a type \(C\) with \(\mathrm{UAC}(A, B) = \mathrm{UAC}(B, A)\); there are \(A\), \(B\) and values \(a : A\), \(b : B\) for which the mathematical comparison \(a < b\) differs from its value in \(C\).

Proof

Totality: every path of the algorithm returns (the last line covers the remaining case). Symmetry: every test is symmetric in \(A\) and \(B\) ("A or B is double", "both signed", "the unsigned one" and "the signed one" are defined without order). Not value-preserving: take \(A = \mathsf{int}\), \(B = \mathsf{unsigned\ int}\), \(a = -1\), \(b = 1\): both promoted types are themselves, one is signed and one unsigned with equal rank, so \(C = \mathsf{unsigned\ int}\); converting \(-1\) gives \(2^{32} - 1\) [C11, §6.3.1.3], and \(2^{32} - 1 < 1\) is false while \(-1 < 1\) is true.

Proposition 6.3.12 (C's implicit integer conversions are not coherent)

There are two chains of implicit conversions from int to long long that denote different functions on some implementation where int is 32 bits and unsigned int is 32 bits.

Proof

Chain 1: int → long long directly maps \(-1\) to \(-1\) (the value is representable, §6.3.1.3 ¶1). Chain 2: int → unsigned int → long long maps \(-1\) to \(2^{32} - 1\) and then to \(2^{32} - 1\) (representable in long long). Both chains arise in real code: long long y = x; vs long long y = x + 0u; for int x = -1 (the second through the usual arithmetic conversions of the addition). The two results differ, so the coercions are not coherent (Definition 6.3.5).

Incoherence is why C++ and Java rank conversions and why Rust, Swift and Pebble make every conversion explicit: the meaning of a program should not depend on which implicit path a checker happened to choose.

Overload resolution¶

Theorem 6.3.13 (Algorithm 6.3.8 finds the best viable function exactly when one exists)

\(\succ\) is a strict partial order on viable candidates. Algorithm 6.3.8 returns \(W\) iff \(W \succ G\) for every other viable \(G\); it returns Ambiguous iff no such \(W\) exists (and NoViable iff there is no viable candidate).

Proof

Order: irreflexivity holds because \(F \succ F\) needs a strictly better sequence; transitivity because "not worse on every argument" composes (the comparison of conversion sequences is a preorder per argument) and "better on some argument" is kept (if \(F\) is better than \(G\) at \(i\) and \(G\) is not worse than \(H\) at \(i\), then \(F\) is better than \(H\) at \(i\)). If a best \(B\) exists: in pass 1, once \(W = B\) no later \(F\) is better than \(B\) (\(B \succ F\) and asymmetry), so \(W\) stays \(B\); before reaching \(B\), \(W\) is replaced by \(B\) when \(B\) is examined, because \(B \succ W\). So \(W = B\) after pass 1, and pass 2 confirms \(B \succ F\) for all \(F\). If no best exists: whatever \(W\) pass 1 ends with, some viable \(F \neq W\) has \(W \not\succ F\) (otherwise \(W\) would be best), and pass 2 finds it and returns Ambiguous. (This is the argument of Lesson 5.4's Theorem 5.4.8, specialized to conversion ranks.)

5. Complexity¶

Technique	Time (worst)	Time (typical)	Space	Variables
Syntax-directed checking (Algorithm 6.3.3)	\(\Theta(n)\) with interned types	linear; dominated by hash lookups of types	\(O(n)\) annotations	\(n\) AST nodes
Usual arithmetic conversions (Algorithm 6.3.6)	\(O(1)\) per operator	a table lookup	—	—
Overload resolution (Algorithm 6.3.8)	\(\Theta(c \cdot k)\) per call, plus the cost of each conversion check	\(c \le 4\) in most code	\(O(c)\)	\(c\) candidates, \(k\) arguments

Justification. Algorithm 6.3.3 visits each node once and does \(O(1)\) work per node (Lesson 6.1 §5); the error type adds a constant test. Algorithm 6.3.6 is a fixed sequence of comparisons on ranks. Algorithm 6.3.8 computes \(k\) conversion sequences for each of \(c\) candidates, then makes at most \(2(c - 1)\) calls to Better, each \(O(k)\).

Pathological family. Nested overloaded calls \(f(f(\cdots f(x)))\) do not compound in C++, because each argument's type is fixed before its call is resolved (bottom-up), so \(d\) nested calls cost \(\Theta(d \cdot c \cdot k)\). They do compound in a checker that resolves overloads jointly with inference (Swift, Chapter 7): with \(c\) overloads per call and no local information, the search space of \(d\) nested calls is \(c^d\). Templates make the conversion checks themselves expensive: each viable function template requires template-argument deduction and possibly instantiation.

Scale. In template-heavy C++, instantiation (and the overload resolution it triggers inside each instantiated body) is the front-end cost worth measuring; clang -ftime-trace reports it per InstantiateFunction and InstantiateClass event, while plain expression checking does not appear as a separate cost.

Syntax-directed type checking¶

Attribute grammars (Lesson 5.5): the checker is an S-attributed definition (types synthesized), with the context as an inherited attribute. Trade-off: a generator can derive the evaluator, but recovery rules are hard to express.
Error types with provenance (Clang's RecoveryExpr, rustc's {type error} with an ErrorGuaranteed token): the error type carries a proof that a diagnostic was already emitted, so later phases can assert they never report without one.
Checking statements by "expected type" (Pebble's let x: T = e, Java's assignment contexts): the first step away from pure synthesis; Lesson 6.4 makes it systematic.

Implicit conversions and numeric promotion¶

Explicit conversions only (Rust as/From, Swift Double(x), Go, Pebble): no coercions to be incoherent; the cost is verbosity, reduced by literal typing (Pebble's literal rule, Go's untyped constants, Swift's literal protocols).
Coercion as subtyping (Java's int → long in method invocation contexts, OCaml's explicit :>): a subtyping-like relation whose derivations denote conversions; coherence must be proved [BTCGS91].
Value-range-aware warnings (Clang/GCC -Wconversion, -Wsign-compare): keep C's rules and warn when a conversion may change a value; heuristics, not rules (the boxes show both compilers missing the narrowing to unsigned char).

Overload resolution¶

Phases instead of ranks (Java §15.12.2): try exact/widening, then boxing, then varargs; within a phase pick the most specific method. Simpler to specify; different from C++ on mixed cases.
Joint resolution with inference (Swift, C# lambdas, Ada): overloads of nested calls are resolved together by a constraint solver that scores whole solutions; more programs resolve, at exponential worst-case cost (Chapter 7).
No overloading (Go, Rust functions, Pebble): one function per name; ad-hoc polymorphism through traits/type classes instead (Lesson 6.9, Chapter 7).

7. In real compilers¶

Syntax-directed type checking¶

Clang's Sema is Algorithm 6.3.3 for C: Sema::CheckAssignmentConstraints [CLANG-SemaExpr] decides the assignment premise, and invalid expressions become RecoveryExpr with a dependent (error-like) type. javac's Attr.visitBinary [JAVAC-Attr] synthesizes an operator's type from its operands' types and reports "bad operand types".

javac 21 checks bottom-up and reports at the operand

Reproduce (javac 21.0.10):

mkdir -p java && cat > java/Checks.java <<'EOF'
class Checks {
    static int twice(int x) { return 2 * x; }
    static int f(boolean b, String s) {
        int n = s;                 // incompatible types
        int m = twice(b);          // wrong argument type
        boolean c = n + 1;         // int where boolean is expected
        return b + 1;              // bad operand types for +
    }
}
EOF
javac -d java java/Checks.java

Output (complete; the container's Picked up JAVA_TOOL_OPTIONS banner removed):

java/Checks.java:4: error: incompatible types: String cannot be converted to int
        int n = s;                 // incompatible types
                ^
java/Checks.java:5: error: incompatible types: boolean cannot be converted to int
        int m = twice(b);          // wrong argument type
                      ^
java/Checks.java:6: error: incompatible types: int cannot be converted to boolean
        boolean c = n + 1;         // int where boolean is expected
                      ^
java/Checks.java:7: error: bad operand types for binary operator '+'
        return b + 1;              // bad operand types for +
                 ^
  first type:  boolean
  second type: int
Note: Some messages have been simplified; recompile with -Xdiags:verbose to get full output
4 errors

What to notice: four independent errors, four reports, no cascades: after int n = s; fails, n still has its declared type int, so line 6 is checked normally (Pebble does the same for an annotated let). The operator error points at the operator (Pebble's E0402), the others at the expression whose synthesized type fails the comparison (E0401).

Implicit conversions and numeric promotion¶

Sema::UsualArithmeticConversions [CLANG-SemaExpr] is Algorithm 6.3.6; Sema::PerformImplicitConversion [CLANG-SemaExprCXX] inserts the ImplicitCastExpr nodes; CheckImplicitConversion [CLANG-SemaChecking] issues the -Wconversion warnings. rustc has no promotion: its only implicit conversions are the reference coercions of coercion.rs [RUSTC-Coercion].

Conversions made visible: Clang 23's elaborated tree, and Clang, GCC 14 and rustc 1.94 on mixed arithmetic

Reproduce (clang 23.1.2, gcc 14.2.0, rustc 1.94.1):

cat > conv.c <<'EOF'
double g(int a, unsigned char c, float x) { return a * c + x; }
EOF
clang-23 -fsyntax-only -Xclang -ast-dump -fno-color-diagnostics conv.c | sed -n '/FunctionDecl.* g /,$p' | sed -E 's/ 0x[0-9a-f]+//g' | tail -12
cat > uac.c <<'EOF'
#include <stdio.h>
int main(void) {
  unsigned char a = 200, b = 100;
  int sum = a + b;               /* both promoted to int: 300 */
  unsigned char wrapped = a + b; /* converted back: 44 */
  long long big = 1u << 31;      /* unsigned int shift, then widened */
  int neg = -1;
  unsigned int one = 1;
  float f = 16777217;            /* int -> float loses a bit */
  printf("%d %d %lld %d %.1f\n", sum, wrapped, big, neg < one, f);
  return 0;
}
EOF
clang-23 -std=c17 -Wconversion -Wsign-compare uac.c -o uac && ./uac
LC_ALL=C gcc-14 -std=c17 -Wconversion -Wsign-compare -c uac.c -o /dev/null
mkdir -p rs && cat > rs/conv.rs <<'EOF'
fn main() {
    let a: u8 = 200;
    let b: u8 = 100;
    let sum: i32 = a + b;            // no promotion: u8 + u8 is u8, and u8 is not i32
    let wide: i32 = a as i32 + b as i32;
    let x: f64 = 1;                  // no int -> float conversion either
    let n = -1i32;
    let one = 1u32;
    println!("{} {} {}", sum, wide, n < one);
}
EOF
rustc --edition 2021 rs/conv.rs -o rs/conv 2>&1 | grep -E '^(error| *-->|help)' | sed 's/ *$//'

Output (complete):

    `-ReturnStmt <col:45, col:60>
      `-ImplicitCastExpr <col:52, col:60> 'double' <FloatingCast>
        `-BinaryOperator <col:52, col:60> 'float' '+'
          |-ImplicitCastExpr <col:52, col:56> 'float' <IntegralToFloating>
          | `-BinaryOperator <col:52, col:56> 'int' '*'
          |   |-ImplicitCastExpr <col:52> 'int' <LValueToRValue>
          |   | `-DeclRefExpr <col:52> 'int' lvalue ParmVar 'a' 'int'
          |   `-ImplicitCastExpr <col:56> 'int' <IntegralCast>
          |     `-ImplicitCastExpr <col:56> 'unsigned char' <LValueToRValue>
          |       `-DeclRefExpr <col:56> 'unsigned char' lvalue ParmVar 'c' 'unsigned char'
          `-ImplicitCastExpr <col:60> 'float' <LValueToRValue>
            `-DeclRefExpr <col:60> 'float' lvalue ParmVar 'x' 'float'
uac.c:9:13: warning: implicit conversion from 'int' to 'float' changes value from 16777217 to 16777216 [-Wimplicit-const-int-float-conversion]
    9 |   float f = 16777217;            /* int -> float loses a bit */
      |         ~   ^~~~~~~~
uac.c:10:57: warning: comparison of integers of different signs: 'int' and 'unsigned int' [-Wsign-compare]
   10 |   printf("%d %d %lld %d %.1f\n", sum, wrapped, big, neg < one, f);
      |                                                     ~~~ ^ ~~~
2 warnings generated.
300 44 2147483648 0 16777216.0
uac.c: In function 'main':
uac.c:9:13: warning: conversion from 'int' to 'float' changes value from '16777217' to '1.6777216e+7f' [-Wfloat-conversion]
    9 |   float f = 16777217;            /* int -> float loses a bit */
      |             ^~~~~~~~
uac.c:10:57: warning: comparison of integer expressions of different signedness: 'int' and 'unsigned int' [-Wsign-compare]
   10 |   printf("%d %d %lld %d %.1f\n", sum, wrapped, big, neg < one, f);
      |                                                         ^
error[E0308]: mismatched types
 --> rs/conv.rs:4:20
help: you can convert a `u8` to an `i32`
error[E0308]: mismatched types
 --> rs/conv.rs:6:18
help: use a float literal
error[E0308]: mismatched types
 --> rs/conv.rs:9:41
help: you can convert a `u32` to an `i32` and panic if the converted value doesn't fit
error: aborting due to 3 previous errors

What to notice: the tree is the §3 trace: c gets an IntegralCast to int (promotion), the product an IntegralToFloating to float (the usual arithmetic conversions), the sum a FloatingCast to the result type double. The C program prints 44 for wrapped with no warning from either compiler, and 0 for -1 < 1u (Proposition 6.3.11). rustc converts nothing: all three mixed-type expressions are E0308 errors with a suggested explicit conversion; the full messages (Lesson 6.4's box) show where the expected type came from.

Overload resolution¶

Clang's OverloadCandidateSet::BestViableFunction [CLANG-SemaOverload] is Algorithm 6.3.8's two passes; CompareStandardConversionSequences ranks sequences and IsIntegralPromotion recognizes the char → int promotion that makes h('a') pick h(int). javac's Resolve.findMethod and mostSpecific implement Java's phases.

Ambiguous calls in clang++ 23 and Java 21's phases

Reproduce (clang 23.1.2, javac/java 21.0.10):

cat > over.cpp <<'EOF'
void f(int, double);
void f(double, int);
void g(long);
void g(unsigned);
void h(int);
void h(double);
int main() {
  f(1, 2);      // ambiguous: each candidate wins one argument
  g(1);         // ambiguous: int -> long and int -> unsigned are both conversions
  h('a');       // char -> int is a promotion: h(int) wins
}
EOF
clang++-23 -std=c++23 -fsyntax-only -fno-color-diagnostics over.cpp
mkdir -p java && cat > java/Phases.java <<'EOF'
public class Phases {
    static String m(long x) { return "m(long)"; }        // phase 1: widening int -> long
    static String m(Integer x) { return "m(Integer)"; }  // phase 2: boxing int -> Integer
    static String n(Object x) { return "n(Object)"; }
    static String n(int... xs) { return "n(int...)"; }   // phase 3: varargs
    public static void main(String[] args) {
        System.out.println(m(1) + " " + n(1));
    }
}
EOF
javac -d java java/Phases.java && java -cp java Phases

Output (complete; the container's Picked up JAVA_TOOL_OPTIONS banner removed):

over.cpp:8:3: error: call to 'f' is ambiguous
    8 |   f(1, 2);      // ambiguous: each candidate wins one argument
      |   ^
over.cpp:1:6: note: candidate function
    1 | void f(int, double);
      |      ^
over.cpp:2:6: note: candidate function
    2 | void f(double, int);
      |      ^
over.cpp:9:3: error: call to 'g' is ambiguous
    9 |   g(1);         // ambiguous: int -> long and int -> unsigned are both conversions
      |   ^
over.cpp:3:6: note: candidate function
    3 | void g(long);
      |      ^
over.cpp:4:6: note: candidate function
    4 | void g(unsigned);
      |      ^
2 errors generated.
m(long) n(Object)

What to notice: the ambiguity notes list the two candidates Algorithm 6.3.8's pass 2 could not separate (the §3 table); h('a') compiles, because promotion beats conversion. Java resolves m(1) in phase 1 by widening before boxing is even considered, and n(1) in phase 2 before varargs.

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Syntax-directed checking	Types flow only upward: unannotated λs, `[]`, overloaded literals need help from above	\(\Theta(n)\) · negligible	Local errors at the failing premise; one per root cause with the error type (Proposition 6.3.9)	Lowest: one post-order walk	C, Pascal, Go, Java (most forms), the Dragon book's checker
Implicit conversions and promotion	Mixed arithmetic "just works"; not coherent in C (Proposition 6.3.12), not value-preserving (Proposition 6.3.11)	\(O(1)\) per operator at compile time; conversions cost instructions at run time	Silent value changes; warnings are heuristic	Low for C's table; high to keep coherent	C, C++, Java, JavaScript; not Rust, Swift, Go, Pebble
Overload resolution by ranking	One name for many types; ambiguity is an error (Theorem 6.3.13)	\(\Theta(c \cdot k)\) per call; templates make it costly	Ambiguity/no-viable errors list candidates; hard to read with many overloads	High (ranking rules, ADL, templates)	C++, Java (phases), C#, Swift (joint solving)

Choose syntax-directed checking as the backbone of any checker; add a checking mode (Lesson 6.4) only where information must flow downward. Choose explicit conversions for a new language — Pebble, Rust and Swift show the verbosity is manageable with literal typing — or, if you must convert implicitly, only along a coherent widening order. Choose overloading only with a ranking that makes the common cases unambiguous and an error message that lists the candidates.

9. Assessment¶

Technique	Quiz ids	Drill	Flashcard tag	Exercises
Syntax-directed checking	`error-type-cascade`, `synth-order`, `find-clang-assignment`	`typing-derivation` (the synthesized types of every node)	`syntax-directed`	E1, E2, E6
Implicit conversions and promotion	`uac-result`, `uac-minus-one`, `find-clang-uac`	— (Algorithm 6.3.6 is a fixed table; the quiz traces it)	`conversions`	E3 (the literal rule is Pebble's only conversion)
Overload resolution	`overload-ambiguity`, `java-phases`	— (Lesson 5.4's material; the quiz traces Algorithm 6.3.8)	`overloading`	—

References¶

See the chapter references.

Lesson 6.3 — Syntax-directed checking, implicit conversions and overloading¶

1. Problem and motivation¶

Syntax-directed type checking¶

Implicit conversions and numeric promotion¶

Overload resolution¶

2. Definitions and algorithms¶

Syntax-directed type checking¶

Implicit conversions and numeric promotion¶

Overload resolution¶

3. Worked examples¶

Syntax-directed type checking¶

Implicit conversions and numeric promotion¶

Overload resolution¶

4. Invariants and correctness¶

Syntax-directed type checking¶

Implicit conversions and numeric promotion¶

Overload resolution¶

5. Complexity¶

6. Variants and refinements¶

Syntax-directed type checking¶

Implicit conversions and numeric promotion¶

Overload resolution¶

7. In real compilers¶

Syntax-directed type checking¶

Implicit conversions and numeric promotion¶

Overload resolution¶

8. Comparison¶

9. Assessment¶

References¶