Turning Text Into Instructions
One Neutral Form in the Middle Turns a Multiplication Into an Addition
Last timeDeciding What It Means
The tree gets flattened into a plain list of tiny operations. That form is deliberately neutral, and the reason is an arithmetic argument about how much work a compiler family costs.
Flattening the tree
The annotated tree from the previous stage is a good description of what the
program means and a poor description of what the machine should do. A machine
does one small thing at a time, in order. So the tree is flattened.
The target is a list of operations, each with at most three parts: a
destination, and one or two sources. Every interior node of the tree becomes
one such operation, and because a node needs somewhere to put its result, the
compiler invents a name for it.
source:
total = a + b * c
lowered:
t1 = b * c
t2 = a + t1
total = t2
source:
if x less than y then do the first thing
lowered:
t3 = x less than y
branch on t3 to block2 else block3
block2:
the first thing
jump to block4| step | step | node visited | operation emitted | name for the result | what happened |
|---|---|---|---|---|---|
| 1 | 1 | leaf b | none | b itself | Leaves need no operation. They already name a value, so lowering a leaf just reports the name it already has. |
| 2 | 2 | leaf c | none | c itself | The same. Only interior nodes do work, which is why the number of operations is the number of operators. |
| 3 | 3 | multiply | t1 equals b times c | t1 | The first real operation, and the first invented name. The compiler will create as many of these as the expression has operators, with no concern for how many exist. |
| 4 | 4 | add | t2 equals a plus t1 | t2 | The child was visited first, so its name is available. Visiting children before parents is what makes the list come out in a runnable order with no second pass. |
The temporaries are worth a word. The compiler invents them freely, thousands
per function, with no attempt to economise. That is deliberate: deciding which
values can share storage is a later stage with its own lesson, and mixing it in
here would make both harder.
Why one form in the middle
Now the structural question. Why have a middle form at all, rather than
translating each language directly to each machine?
The answer is counting. Supporting m languages on n machines by direct
translation needs m times n translators, each one a serious piece of
engineering that has to be maintained separately. With a neutral form in the
middle, each language needs one translator down to it and each machine one
translator out of it, which is m plus n.
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