Turning Text Into Instructions
The Stage That Finds Out Whether Your Names Refer to Anything
Last timeFrom Pieces to a Tree
A correct shape is not a correct program. This stage works out what every name refers to and what type every node has, and it is the last one that can refuse.
What a name refers to
After the previous stage the program has a shape. It does not yet have a
meaning. The tree contains names, and nothing so far has asked whether those
names refer to anything at all.
A name is resolved by looking it up, and the lookup is not a single table. It
is a chain of them, one per enclosing region of the program, searched from the
inside out.
file scope
count is declared here, a whole number
function scope
count is declared here too, a decimal
block scope
nothing named count declared
the use of count inside this block
finds the decimal, because the search
stops at the first scope that has it
a use of count out here finds the whole number- time to resolve one name
- how many scopes out the declaration is
- the cost of one scope lookup
Types from the leaves upward
With every name pointing at a declaration, every leaf of the tree has a type.
A literal number has one from its form, and a name has one from the
declaration it was just linked to.
Type checking is then one pass upwards. Each kind of operation carries a rule
saying what types it accepts and what type it produces, and the checker applies
that rule at every node using the types already computed for the children.
| step | step | node | types of the children | type produced | what happened |
|---|---|---|---|---|---|
| 1 | 1 | leaf b | none, it is a leaf | whole number | From the declaration the previous phase linked it to. Leaves are where types enter the tree, and everything above is derived. |
| 2 | 2 | leaf c | none, it is a leaf | decimal | A different type from its sibling, which is going to force a decision one level up. |
| 3 | 3 | multiply | whole number and decimal | decimal | The rule for multiplication accepts a mixed pair and produces the wider of the two, inserting a conversion into the tree. In a stricter language the same node would be an error instead. |
| 4 | 4 | add | whole number and decimal | decimal | The same rule again, using the type the child produced rather than anything written in the source. Four nodes, one pass, every node typed. |
The interesting part is what the checker does when the rule does not fit. In a
permissive language it inserts a conversion, which is why mixed arithmetic
works and also why a decimal can quietly lose its fractional part. In a strict
one it reports an error. The difference between those two languages is not a
difference of philosophy at this stage, it is a difference of a few lines in
the rule for each operator.
The lesson stops here
3 more paragraphs to go
You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.
The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.
See the planThe contentsThis is the reading half
Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.
The contents