The Program Execution Pipeline

Learning Objectives

Trace a program through source text, encoding, lexing, parsing, AST, name resolution, semantic analysis, IR, bytecode generation, verification, loading, initialisation, interpretation, profiling, JIT compilation, native execution, diagnostics and shutdown.

Compare the pipelines of C, Java, Python, JavaScript, C# and WebAssembly.

Explain why the pipeline is a teaching model that real implementations omit, merge, reorder or repeat.

Plain-Language Explanation

Think of an assembly line. Characters come in; a lexer groups them into words (tokens); a parser checks the grammar and builds a tree; later stages check names and types, produce simpler instructions, check those instructions are safe, load them into the runtime and finally run them — sometimes translating hot parts to machine code along the way. Not every language uses every station, and some stations run more than once.

Precise Technical Explanation

Source text and source files Programs arrive as files, strings (eval), network payloads (browser scripts) or REPL lines. Implementations associate each with a name used in diagnostics (<demo>, HelloRuntime.java, a URL).

Character encoding and lexical input Source files are bytes; the implementation decodes them into characters using a declared or assumed encoding (Python 3 defaults to UTF-8; Java's javac -encoding; JavaScript sources are Unicode text). Encoding errors are reported before lexing.

Preprocessing or source transformation where applicable C and C++ run a preprocessor (#include, #define, conditional compilation) before compilation. Other ecosystems transform source with build tools (TypeScript → JavaScript, Babel, annotation processors). MiniLang has no preprocessor.

Lexical analysis (tokenization) The lexer converts characters into tokens — kind, lexeme, optional literal value and position — and discards whitespace and comments (Module 3).

Parsing and grammar The parser checks tokens against a grammar and builds a tree, reporting syntax errors with positions (Module 4).

Abstract syntax tree (AST) The AST keeps the program's structure without punctuation: Binary(+, Variable(base), Variable(adjustment)) (Module 5).

Each identifier use is connected to its declaration: global, local slot or captured variable. MiniLang's compiler resolves locals and upvalues at compile time and leaves globals to run-time lookup.

Determines which declarations are visible where; detects errors such as redeclaring a local in the same block or reading a local in its own initializer.

Type checking and semantic analysis Statically typed languages check types here (javac rejects int x = "s";). Dynamically typed languages check few static rules and defer type errors to run time.

Intermediate representations (IR) Compilers lower the AST into IRs that are easier to analyse and optimise: three-address code, control-flow graphs, SSA (Modules 8, 10, 16).

The compiler emits instructions for a VM, with a constant pool and debug metadata (line tables) — MiniLang's compile().

Bytecode verification or validation Before execution, a VM may check that bytecode is well-formed and type-safe: the JVM verifier, WebAssembly validation, the MiniLang verifier (Module 8). Verification protects the VM from malformed or malicious code.

Loading and linking The runtime reads code units (class files, assemblies, modules, .pyc files), resolves references between them and allocates runtime structures (Module 15).

Static initialisers run, standard libraries are set up, globals are created; then the entry point is called.

The interpreter executes the representation: walking the AST or running a bytecode dispatch loop.

Many VMs count calls, loop iterations and observed types while interpreting, to decide what to optimise.

Hot code is compiled to machine code during execution, often speculatively (Module 16).

Native code execution JIT-compiled or AOT-compiled machine code runs directly on the CPU; the runtime still provides services (GC, exceptions).

Exceptions and diagnostics Errors in any phase are reported with positions: lexical, syntax, compile (static), verification and runtime errors with stack traces.

Program shutdown and cleanup The program returns from its entry point or exits; the runtime runs shutdown hooks and finalisers where defined, flushes buffers and returns an exit code to the OS (Module 15).

Pipeline differences across C, Java, Python, JavaScript, C# and WebAssembly preprocess → compile → optimise → assemble → link to a native executable

OS loader maps it; C runtime start-up calls main Java (javac + HotSpot)

javac → class files (bytecode + constant pool + metadata) class loading → verification → interpretation → profiling → tiered JIT (C1, C2) Python (CPython) none required (optional .pyc caching) parse → AST → compile to code objects → bytecode interpreter (with adaptive specialisation since 3.11) JavaScript (V8) none (source shipped as text) lazy parse → bytecode (Ignition) → baseline and optimising JITs (Sparkplug, Maglev, TurboFan in recent V8s)

csc → assembly with CIL + metadata; optional ReadyToRun or Native AOT assembly loading → JIT (tiered) or precompiled code toolchain (clang, rustc, …) → .wasm binary validation → compilation by the engine (baseline/optimising, engine-specific) → execution in a sandbox Illustrative pipeline

Real pipelines can omit, combine, reorder or repeat stages. This is a teaching model, not a universal mandatory sequence: V8 parses functions lazily (parsing repeats when a function is first called), CPython compiles each module when imported, and a JIT may recompile the same function several times.

Source text
   ↓
Lexer → Tokens
   ↓
Parser → AST
   ↓
Semantic analysis / name resolution
   ↓
IR or bytecode generation
   ↓
Validation / verification
   ↓
Runtime loading and initialization
   ↓
Interpreter execution and/or JIT compilation
   ↓
Machine instructions on the CPU

Why It Matters in Real Systems

Knowing which stage produced an error tells you where to fix it; knowing which stages run at start-up explains cold-start latency; knowing where verification happens tells you what untrusted input can and cannot do.

Key Terms

Categorised unit of source text with a position Tree of a program's syntactic structure

Intermediate representation used inside a compiler Checking code is well-formed and safe before running it Loading / linking

Bringing code into the runtime and connecting references Time from launch to useful work, including pipeline stages

Syntax or Instruction Format

No dedicated source syntax; this is a runtime or architecture concept. Each stage's input and output format is shown in the example below.

Complete Example

One MiniLang program through every stage of the course's implementation. The source:

Stage 1 — tokens (kind, lexeme, literal, line:column):

Stage 2 — AST: Stage 3 — bytecode (offset, source line, instruction, operand, meaning):

Stage 4 — execution on the VM (one line per instruction, stack after it):

let base = 40;
let adjustment = 2;
print(base + adjustment);

1:1   LET            "let"
 1:5   IDENTIFIER     "base"
 1:10  EQUAL          "="
 1:12  NUMBER         "40"         literal=40
 1:14  SEMICOLON      ";"
 2:1   LET            "let"
 2:5   IDENTIFIER     "adjustment"
 2:16  EQUAL          "="
 2:18  NUMBER         "2"          literal=2
 2:19  SEMICOLON      ";"
 3:1   PRINT          "print"
 3:6   LEFT_PAREN     "("
 3:7   IDENTIFIER     "base"
 3:12  PLUS           "+"
 3:14  IDENTIFIER     "adjustment"
 3:24  RIGHT_PAREN    ")"
 3:25  SEMICOLON      ";"
 4:1   EOF            ""

Let(base)
└── Number(40)
Let(adjustment)
└── Number(2)
Print
└── Binary(+)
    ├── Variable(base)
    └── Variable(adjustment)

== <script> ==
constants: 0 → 40, 1 → 2
names:     0 → base, 1 → adjustment
0000    1 CONSTANT         0    ; 40
0002    | DEFINE_GLOBAL    0    ; 'base'
0004    2 CONSTANT         1    ; 2
0006    | DEFINE_GLOBAL    1    ; 'adjustment'
0008    3 GET_GLOBAL       0    ; 'base'
0010    | GET_GLOBAL       1    ; 'adjustment'
0012    | ADD
0013    | PRINT
0014    | HALT

fn          offset  instruction                      stack after
<script>    0000    CONSTANT 0  ; 40                 [40]
<script>    0002    DEFINE_GLOBAL 0  ; 'base'        []
<script>    0004    CONSTANT 1  ; 2                  [2]
<script>    0006    DEFINE_GLOBAL 1  ; 'adjustment'  []
<script>    0008    GET_GLOBAL 0  ; 'base'           [40]
<script>    0010    GET_GLOBAL 1  ; 'adjustment'     [40, 2]
<script>    0012    ADD                              [42]
<script>    0013    PRINT                            []
<script>    0014    HALT                             []
output: 42

Line-by-Line Explanation

Tokens: 17 tokens plus EOF; each carries its line and column so errors can point at the source. Numbers carry their parsed literal value.

AST: three statements. Punctuation (;, parentheses) is gone; structure remains.

Bytecode: constants 40 and 2 live in the constant pool; the global names live in the names table. DEFINE_GLOBAL pops the value and binds the name.

Trace: the stack grows and shrinks exactly as each instruction's stack effect says; PRINT consumes the 42.

Expected Output

42 (the final output: line of the trace).

Step-by-Step Runtime Behavior

The stack is empty at the start and at the end of each statement — a property the compiler maintains and the verifier checks (Module 8).

Common Misconceptions

"Every implementation runs every stage." CPython has no separate verifier; C has no run-time bytecode stage.

"Parsing happens once." Lazy parsers (V8) and REPLs parse repeatedly.

"JIT compilation replaces interpretation." Interpreters keep running cold code and serve as a fallback after deoptimisation.

Common Bugs and Failure Modes

Mismatched encodings (non-ASCII identifiers or strings mangled), confusing a syntax error with a runtime error, caching compiled artefacts across incompatible versions, assuming initialisation order across modules.

Corrected or Safer Patterns

Declare source encodings, keep build artefacts versioned with their toolchain, test start-up paths and error paths explicitly.

Debugging and Inspection Techniques

Dump each stage: tokens and AST (MiniLang visualizers, Python's ast.dump), bytecode (dis, javap -c), JIT activity (-XX:+PrintCompilation, Node's --trace-opt).

Performance Considerations

Front-end stages cost start-up time: caching (.pyc, V8's code cache, ReadyToRun) skips them on later runs.

Security Considerations

Verification and validation are where a VM refuses malformed code; stages before it must not trust their input either (fuzz lexers and parsers — Module 23).

Portability and Version Caveats

Stage boundaries, formats and caches are implementation-specific; the table above describes common configurations of current implementations.

Real-World Use Cases

Build pipelines, language servers (which run lexing/parsing continuously), bundlers, browser script loading, serverless cold-start tuning.

Best Practices

Keep source positions through every stage; make each stage independently testable; document which stages your implementation has.

Exercises

E1 · Beginner. Which stage reports let = 3; and which reports print(1 / 0); in MiniLang?

Answer: The parser reports let = 3; (syntax error: expect variable name); print(1 / 0); passes every compile-time stage and fails at run time (division by zero).

E2 · Intermediate. Why does a JVM verify bytecode that javac produced?

Answer: The JVM cannot know who produced a class file — it may have been modified or generated by another tool. Verification ensures type and stack safety regardless of the producer.

E3 · Advanced challenge. Name two stages V8 may repeat for the same function, and why.

Answer: Parsing (lazy pre-parse first, full parse on first call) and compilation (bytecode first, then baseline and optimised code as the function gets hot; re-optimisation after deoptimisation).

Quiz

? In the MiniLang trace above, which instruction consumes the value 42?
+ PRINT :: It pops the top value and prints it.
- ADD :: ADD produces 42.
- HALT :: The stack is already empty.
- DEFINE_GLOBAL :: Only the two constants are bound to globals.

? What does a lexer produce?
+ Tokens with kinds, lexemes and positions :: Whitespace and comments are skipped.
- An AST :: That is the parser's output.
- Bytecode :: That is the compiler's output.
- Machine code :: Far later, if at all.

? Which statements about the pipeline are correct? (select all that apply)
+ Stages can be omitted, merged or repeated by real implementations. :: It is a teaching model.
+ Verification protects a VM from malformed code. :: The JVM and WebAssembly validate before executing.
- Every language compiles to bytecode. :: C usually compiles straight to native code.
+ Caches can skip front-end stages on later runs. :: .pyc files, V8 code cache, ReadyToRun.

Summary and Key Takeaways

Source becomes tokens, then a tree, then (often) instructions that are checked, loaded and executed — possibly compiled to machine code on the way. Each implementation picks its own subset and order of stages. Keep positions and versions with every artefact.