Programming Language Concepts (Peter Sestoft)（Z-Library）

# Programming Language Concepts ## 【One-Line Pitch】 A hands-on, F#-based tour of how programming languages work—from abstract syntax and interpreters to compilers, type systems, and garbage collection—ideal for computer science students or self-taught programmers who want to understand the machinery behind Java, C#, and ML-style languages by building working implementations. ## 【Book Arc】 - **Opening (~0%–10%)**: Sets the stage with the book's philosophy—using F# as a "metalanguage" to present all concepts operationally, so readers can experiment as they learn. The introduction distinguishes syntax from static semantics and previews the journey from interpretation to compilation. - **Early (~10%–25%)**: Builds the foundation with abstract syntax trees and expression interpreters. Readers learn to represent arithmetic expressions as datatypes, write evaluation functions, and tackle exercises on simplification, formatting, and symbolic differentiation—establishing the pattern of "define syntax, then interpret it." - **Early–Middle (~25%–40%)**: Moves from interpretation to compilation. A two-stage design splits the environment into compile-time (variable names) and run-time (values), leading to a stack machine with bytecode instructions. The stack machine is then implemented in Java, bridging the gap between abstract machines and real hardware. - **Middle (~40%–50%)**: Covers the practical construction of lexers and parsers using F# tools (fslex and fsyacc). Readers learn about operator precedence, associativity, shift/reduce conflicts, and how to generate parsers—including a micro-SQL example that can be extended for larger SELECT statements. - **Late (~50%–100%)**: Advances into type checking, polymorphic type inference using unification, co- and contravariant types, continuations, and backwards code generation with peephole optimization. The book culminates in a compiler for Micro-C, a usable subset of C, complete with a garbage collector and command-line tooling. ## 【Key Takeaways】 - **Abstract syntax is the backbone of language implementation** (Early): Separating concrete syntax (text) from abstract syntax (trees) lets you write interpreters and compilers that are clean and composable. The book's exercises on formatting and simplifying expressions show how the same tree structure supports multiple operations. - **Interpretation and compilation are two sides of the same coin** (Early): A one-stage interpreter keeps names and values in one environment; a two-stage compiler splits them into compile-time and run-time environments. This split is the conceptual leap from "evaluating" to "generating code." - **Stack machines are a sweet spot between abstraction and reality** (Early): The abstract machine with instructions like SCst, SVar, SAdd, and SSwap demonstrates how let-bindings and intermediate results are managed on a single stack—the same strategy used by many real functional language compilers. - **Bytecode representation makes abstract machines concrete** (Early): Encoding instructions as numbers (e.g., SCst i → 0 i, SVar x → 1 x) lets you implement the stack machine in Java, showing how virtual machines bridge the gap between high-level languages and hardware. - **Parser generators require understanding conflicts** (Middle): Shift/reduce and reduce/reduce conflicts arise from ambiguous grammars; the book shows how precedence and associativity declarations (%left) resolve them, and how to read the generated .output files to debug parser states. - **Type checking and inference are separate, powerful tools** (Late): Static semantics can be enforced by closedness checks (are all variables defined?) and type checks (are operators used correctly?), while type inference using unification extends this to ML-style polymorphic types—a major intellectual payoff. - **Compilation is a pipeline of small, verifiable steps** (Late): From abstract syntax to stack machine code to optimized bytecode, each transformation can be proven correct relative to the interpreter. The Micro-C compiler ties everything together, including dead code elimination and tail call optimization. ## 【Reading Tips】 - **Skim the F# crash course (Appendix A) if you're new to functional programming** (Early): The book assumes you can read F#; the appendix covers expressions, pattern matching, lists, datatypes, and higher-order functions. Work through it quickly, then return to it as a reference. - **Do the exercises—they're the real content** (Throughout): Exercises like writing a simplifier, a symbolic differentiator, or extending micro-SQL are where the concepts click. The book provides hints (e.g., "pattern matching is your friend") that teach idiomatic F#. - **Deep-read the two-stage compilation chapter** (Early): The split between compile-time and run-time environments is the hardest conceptual hurdle. Trace through the example with let-bindings on the stack (SCstI 20, SCstI 17, SVar 0, SCst 2, SAdd, SSwap, SPop) until you see why SSwap and SPop are needed. - **Use the parser conflict output as a debugging tool** (Middle): When fsyacc reports shift/reduce conflicts, don't just add %left declarations blindly. Read the ExprPar.fsyacc.output file to understand the parser states—this skill transfers to any LR parser generator. - **Treat the Micro-C compiler as a capstone project** (Late): Rather than reading it passively, try extending it (e.g., adding new optimizations or language features). The book's "remaining deficiencies" section is a goldmine for project ideas. ## 【Coverage Limits】 This guide covers the book's opening through the parser construction chapters in detail; the later chapters on type inference, continuations, and code optimization are summarized from the table of contents and blurb, as the excerpts do not include their full content. ##