Overview
free

Appendix A: Diagram Templates by Step
Appendix B: Mapping to Existing Technologies
Appendix C: Readiness Assessments
Appendix D: Glossary

Course Setup and the Incremental Ladder
Why "Structure to Interpretation"
How to Use This Course
The Incremental Ladder (Step 0 to Step 7)
The Course Lenses
Diagram Legend and Notation Types

What Is a Programming Language?
Languages as Interfaces
Models of Computation
Design vs Implementation

Syntax, Semantics, and Pragmatics
Syntax vs Semantics vs Pragmatics
Static vs Dynamic Semantics
Informal vs Formal Specs

Homoiconicity and Code as Data
Representations of Code
Homoiconicity
Implications for Macros and Reflection

Compiled vs Interpreted and Everything In Between
Execution Model Spectrum
Trade-offs and Where Complexity Migrates
Compilation as a Pipeline

Diagramming Languages and Implementations
Grammar Diagrams
AST and Evaluation Flow
Pipelines and Runtime Diagrams

Lexing: Turning Text into Tokens
Characters to Tokens
Regular Expressions and Automata Intuition
Hand-Written vs Generated Lexers

Grammars and Parsing
Context-Free Grammars
Parsing Strategies
Errors and Recovery

Designing a Tiny Expression Language
Minimal Language Surface
Grammar and Precedence Design
Parser Construction and Validation

Abstract Syntax Trees and IRs
Parse Tree vs AST
AST Node Design and Invariants
IR as "Compiler Currency"

Tree-Walk Interpreters
Environments: Name-to-Value Mappings and the Boundary Between Syntax and Execution
Evaluation by Recursion: Interpreting Expressions Through AST Traversal and Rule Application
Diagnostics and Stack Traces: Making Runtime Errors Explainable in a Tree-Walk World

Extending the Tiny Language with Statements
Statements and Sequencing: Blocks, Sequences, and the Shift from "Expression Only" to "Program"
Scope and Shadowing: Lifetime Rules as Semantics, Not Syntax
Expression vs Statement Languages: Designing the Semantic Boundary and Its Consequences

Variables, State, and the Store
Environment vs Store: References vs Values and Why Mutation Needs a Second Structure
Assignment Semantics: Modeling State Changes Precisely and Avoiding Hidden Aliasing Surprises
State in Interpreters and IRs: Representing Mutation So Later Compilation Stays Correct

Control Flow Constructs
Conditionals and Loops: Structured Control and How Evaluation Order Becomes Observable
Desugaring: Translating "Nice Syntax" into Core Constructs You Can Reason About
Non-Local Control: Exceptions, Early Returns, and the Semantics of Unwinding

Functions, Closures, and Scope
First-Class Functions: Lambdas as Values and What It Means for a Language to Treat Behavior as Data
Lexical vs Dynamic Scope: Closure Capture and How Name Resolution Becomes a Design Choice
Calling Conventions at a High Level: Call Stacks, Environments, and the Observable Consequences for Debugging

Typing Discipline and Design Choices
Static vs Dynamic Typing: Where Errors Surface and What You Can Guarantee
Strong vs Weak and Mixed Regimes: What Coercion Buys and What It Breaks
Designing a Type Philosophy: Aligning Types with Language Goals, Ergonomics, and Tooling

Type Systems and Type Checking
Core Type Building Blocks: Primitives, Records, Pairs, and Algebraic Data Types
Typing Judgments and Environments: Rules as the Executable Spec of Static Semantics
Algorithmic Type Checking: Implementable Checking and What Makes Error Messages Usable

Type Inference and Polymorphism
Unification Intuition: Constraints, Solving, and Why Inference Reshapes API Design
Parametric Polymorphism: Generics and Type Parameters as Abstraction Mechanisms
Ad-hoc Polymorphism: Overloading and Type-Class-Like Ideas and Where Complexity Accumulates

Operational and Denotational Semantics
Big-Step vs Small-Step: What Each Style Explains About Evaluation and Control
Denotational Semantics: Mapping Programs to Mathematical Objects to Reason About Equivalence
Semantics for Transformation: Using Meaning to Justify Optimizations and Refactorings

Static Analysis Beyond Types
Dataflow Analysis: Liveness, Reachability, and the Shape of "Safe Approximations"
CFGs and SSA: Why Control-Flow Graphs and SSA Form Dominate Compiler Reasoning
Soundness vs Completeness: How Analyses Become Warnings, Errors, and Developer Guidance

From AST to IR: Lowering and Desugaring
Surface vs Core Language: Designing a Minimal Core You Can Compile Reliably
Desugaring as Semantics Preservation: What Transformations Must Preserve to Stay Correct
High-Level IR Design: Representing Control and Data for Compilation and Optimization

Designing a Bytecode and VM
Bytecode Instruction Sets: Stack-Based vs Register-Based Design Trade-offs
VM Architecture: Dispatch, Frames, Stack/Heap Boundaries, and What Makes Debugging Possible
Debug Metadata: Line Tables and Source Mapping as First-Class VM Requirements

Code Generation to Bytecode
Translating AST/IR to Bytecode: Preserving Evaluation Order and Side Effects
Control Flow in Bytecode: Labels, Jumps, and Structuring Constructs Without Losing Clarity
Functions and Closures: Representing Calls, Environments, and Upvalues in a VM Model

Interpreting and Optimizing Bytecode
Interpreter Techniques: Switch Dispatch vs Threaded Code and Why It Matters for Performance
Simple Compile-Time Optimizations: Peephole and Constant Folding as "Cheap Wins"
Instrumentation and Profiling: Gathering Evidence to Guide Later Optimizations and JIT Choices

Exceptions, Error Handling, and Debugging Support
Exception Models: Unwinding vs Resumption and What They Imply for Language Semantics
Debugging Interfaces: Breakpoints, Stepping, Inspection, and VM Support Requirements
Tracing and Tool APIs: Designing Stable Hooks for Debuggers and Observability Tools

Lowering to Low-Level IR
SSA Form: What SSA Guarantees and Why Optimizers Love It
CFGs, Dominance, Phi Nodes: Encoding Merges and Control-Dependent Values Precisely
Mapping High-Level Constructs: Translating Closures, Objects, and Control into Low-Level IR

Code Generation to Native Architectures
Calling Conventions and ABIs: Stable Contracts Between Compiled Code and the Platform
Instruction Selection and Scheduling: Turning IR into Machine Code Without Leaving Performance on the Table
Multi-ISA Backends: Designing Portability Boundaries When Targeting Multiple Architectures

Optimization Passes
Local vs Global Optimizations: What "Global" Requires in Terms of Analysis and Invariants
Canonical Passes: Inlining, Constant Propagation, DCE, Loop Transforms and Their Semantic Constraints
Trade-offs: Compile Time Versus Runtime Performance and How to Justify Complexity

Garbage Collection and Memory Management
Explicit vs GC: Ownership Ideas and the Boundary Between Language Semantics and Runtime Policy
Tracing, Reference Counting, Generational GC: Collectors as Different Failure and Latency Profiles
Interactions: FFI, Concurrency, and Real-Time Constraints as the Hard Edges of Memory Management

JIT Compilation and Hybrid Execution
JIT vs AOT vs Interpreter: Selecting an Execution Strategy for Your Product Constraints
Hot Paths and PGO: Profiling-Guided Decisions and What "Hot" Really Means
Tiering and Deoptimization: Why Adaptive Systems Need a Safe Escape Hatch

Code as Data in Practice
Internal Representation vs External Syntax: Where Metaprogramming Hooks Attach
AST Manipulation and Reflection APIs: Capabilities, Invariants, and How Tools Stay Correct
Risks and Guardrails: Hygiene Pressures, Invariant Breakage, and Why Tooling Becomes Harder

Macros: From Textual to Syntactic
Text Macros vs AST Macros: Failure Modes and Why Syntactic Macros Dominate Serious Use
Hygiene and Scope: Avoiding Accidental Capture and Keeping Expansions Predictable
Expansion Phases: Compile-Time Evaluation, Staging Boundaries, and Reproducibility

Designing Homoiconic Languages
Uniform Representations: S-Expressions and What They Buy You in Simplicity and Transformation Power
Quoting and Quasiquotation: Controlling Evaluation Boundaries and Building Code Safely
DSLs via Embedding: Using Homoiconicity to Create Language Families and Internal DSLs

Staging, Partial Evaluation, and Generative Programming
Multi-Stage Programming: Staged IRs and the Semantics of Run Now vs Run Later
Partial Evaluation: Specialization as an Optimization Technique with Semantic Obligations
Code Generation Tooling: Templates, Builders, and Maintaining Debuggability

Metaprogramming Tooling and Debugging
Inspecting Expansions: Viewing Expanded Macros and Staged Code as a Primary Debugging Workflow
Source Maps and Expansion Traces: Preserving User Intent Through Transformations
Safety Boundaries for Metaprogramming: Policy, Conventions, and Limitations That Keep Ecosystems Sane

Modules, Packages, and Namespaces
Module Systems: Visibility Rules, Encapsulation, and Compilation Units
Package Managers: Versioning, Dependency Resolution, Registries, and Supply-Chain Implications
Namespaces and Imports: Avoiding Global Chaos While Keeping Code Readable

Build Systems, Toolchains, and REPLs
Toolchains as Products: Compiler, Linker, Runner, and What "One Command Works" Requires
REPL Design: Interactive Evaluation, State, and Aligning REPL Semantics with Compiled Semantics
Incremental Compilation and Hot Reloading: Feedback Loops, Caching, and Correctness Pitfalls

Interoperability and FFI
Calling Out to Other Worlds: C/System Libraries and Runtime Integration Strategies
Marshalling and Representation: Data Layout Across Boundaries and What Can Go Wrong
Safety, Performance, Versioning: Maintaining a Stable Boundary Under Evolution

Multi-Target and Multi-Backend Languages
VM Targets vs Native: Portability Boundaries and Performance Ceilings
Shared Core IR: Designing a Common Middle Layer That Supports Multiple Backends
Where Portability Lives: Choosing Which Features Are Portable and Which Are Platform-Shaped

Designing for Developer Experience
Diagnostics as Design: Error Messages, Hints, and How They Encode Language Philosophy
Formatting, Linting, Refactoring: Making Consistency and Correctness Cheap
Language Servers and IDEs: APIs, Incremental Analysis, and the Ergonomics of Tooling Integration

Evolving a Language Over Time
Versioning and Deprecation: Migration Strategy as Part of the Language Contract
Backward Compatibility vs Progress: What You Preserve and What You Break, and Why
Governance Processes: RFCs, Community Norms, and Decision-Making Structures That Scale

Language Design Patterns
Expression vs Statement Orientation: How Surface Form Shapes Semantics and Tooling
Effects and Explicitness: Implicit vs Explicit Control, Side Effects, and Composability
Surface Syntax Patterns: Keywords vs Operators vs Punctuation and the Trade-offs in Readability and Parsing

Semantic and Type System Patterns
Safe-by-Default Design: Invariants You Enforce and What You Leave to Convention
Effect Systems and Ownership Ideas: High-Level Patterns for Taming Side Effects and Resources
Refinement and Advanced Types: Power Versus Simplicity Versus Learnability as a Product Constraint

Runtime and Execution Patterns
VM Patterns: Stack vs Register, Object Models, and Dispatch Strategies
Memory Layout Patterns: Tagged Values, Headers, Vtables, and Representation Leak
Concurrency Models: Threads, Async/Await, Actors, Green Threads, and Runtime Assumptions

Implementing DSLs and Embedded Languages
Internal vs External DSLs: Design Goals, Tooling Implications, and Maintenance Costs
Embedding vs Standalone: When a Host Language Is Enough and When It Becomes a Constraint
New Language vs Library: Decision Criteria and Failure Modes of Each Path

Checklists for New Language Designs
Syntax Checklist: Grammar, Precedence, Readability, and Error Recovery as First-Order Design Concerns
Semantics and Types Checklist: Evaluation Rules, Type Philosophy, and Static Reasoning Guarantees
Runtime, Tooling, Ecosystem Checklist: Execution Strategy, Debugging Story, Packaging, and Long-Term Evolution

/structure-to-interpretation/structure-to-interpretation

Designing a Tiny Expression Language

Sign in to access this lesson.

Sign in Create account