Translating Once

Our interpreter model repeatedly reads and handles a stored statement. Another approach prepares machine instructions before execution.

Translate the whole program first. All of it, before a single line runs. What is left afterwards is a sequence of instructions. The machine still has to perform their work; reading and interpreting the source statement is no longer part of each pass. We translate again when we change the source and rebuild.

A native-code compiler translates higher-level source into instructions for the target processor. For LET total = total + 1, it must arrange for the old value to be read, one to be added, and the result to be stored. It can also combine or remove operations when that preserves the program’s meaning.

The resulting machine code can include calls to library routines for jobs such as arithmetic or printing. Those routines still do work when the program runs; compilation does not make that work disappear.

The build may have several stages. For example, a compiler can produce assembly source, an assembler can encode it, and a linker can join the pieces and library routines into a program. We use “compile” for the overall build in many tools, but these stages have different jobs.

Not every compiler produces native code before a program starts. Some produce bytecode, instructions for a software machine, and some compile while the program is running. Here we are following the route that builds native machine code in advance.

Where an assembler differs

In assembly source, we have already chosen the processor operations. The assembler encodes those instructions and works out details such as the addresses named by labels. A higher-level compiler makes more of those instruction choices for us.

Our invented machine lets us model just the encoding step. Each of its three instruction names has one code:

Look up each name and write down its number. That is the encoding job for this tiny machine. Real instructions can occupy several bytes, including values or addresses used by the operation.

Build it

We use two matching lookup lists, a list for pending output, and loops that check each name. A flag records whether the whole program is valid. Trace this pseudocode:

LET names = ["INC", "DOUBLE", "SHOW"]
LET codes = [1, 2, 3]
LET program = ["INC", "INC", "DOUBLE", "SHOW"]

LET pending = []
LET valid = TRUE

FOR EACH word IN program
  LET found = FALSE
  FOR i = 1 TO LENGTH(names)
    IF word = names[i] THEN
      APPEND codes[i] TO pending
      LET found = TRUE
    END
  END
  IF NOT found THEN
    SHOW "Unknown instruction: ", word
    LET valid = FALSE
  END
END

IF valid THEN
  FOR EACH code IN pending
    SHOW code
  END
ELSE
  SHOW "Translation failed; no code emitted"
END

1
1
2
3

For each word, start found at FALSE and look along the names list. List positions start at 1. When a name matches, append its code to pending and set found to TRUE. The fixed names table contains each name once; the two lists have matching positions.

We keep these codes in a list first. If any word has no match, report it and leave valid FALSE for the rest of this translation. We show the codes only after checking the whole program. A later recognised word cannot erase an earlier error.

For the valid program, we emit 1 1 2 3. You have traced the encoding part of a toy assembler. A real assembler also handles operands, labels, addresses and diagnostics; this small model does not implement those jobs.

Reject a program we cannot translate

Replace the program list with ["INC", "MYSTERY", "DOUBLE", "SHOW"]. Predict whether the translator emits 1 2 3 or rejects the whole translation.

Unknown instruction: MYSTERY
Translation failed; no code emitted

An empty program list has no words to check and emits no codes. That is a valid empty program in this model, distinct from a rejected program with a diagnostic.

What runs afterwards

The machine is handed 1 1 2 3 and runs it without consulting our source-name table. Add one, add one, double, show. We keep the source separately so we can edit and rebuild it.

Imagine a native-code compiler produced those same four codes from a higher-level description. On our tiny machine, given the same starting value, the result would be identical. The processor follows the instructions it receives; there is no extra “compiled” step when it executes them.

Both routes can produce native machine code. Different tools may choose different instruction sequences for the same task, so their speed and size can differ. We need to inspect or measure those sequences to compare them.

Removing the repeated source-name lookup removes that work from execution. Whether a game keeps up with its intended update rate still depends on the instructions, data and hardware work that remain.

Check the distinction

Someone says, “This program was compiled from source, so it cannot be native machine code.” What would we need to find out?

When it’s wrong, see why

• A name was not in the table. Read the diagnostic, correct the source and translate again. Skipping the word would silently change the program. Our toy keeps pending codes private until all names have passed.
• You changed the program and nothing changed. The old numbers are still what the machine has. Translating once means translating again when you change something.
• The program runs but gives the wrong result. Keep the matching source and build information so we can connect execution back to our intentions. The next unit explains how diagnostics and observation help together.

What you’ve learnt

• A native-code compiler chooses machine instructions to implement higher-level source.
• An assembler encodes instructions selected in assembly source.
• Both can produce native machine code for the same processor.
• You traced a toy encoder using lists and loops, with no code emitted after an unknown name.
• Removing runtime translation work does not establish the whole program’s speed.

What’s next

In Unit 4 we compare the responsibilities that come with more explicit control: diagnostics, detail and portability.