PL asks what a language is independent of any compiler that implements it. A language is a grammar, a set of evaluation rules, and a set of guarantees, and nearly every design argument in the field is about what a language promises versus what it costs to keep that promise.
The clusters below run roughly from surface to depth: how a language is written down, how it runs, what its types rule out, and how implementations make it fast. Concrete-language treatments live in Languages; this section stays at the level of ideas.
Orientation
- Syntax and Semantics - the two halves of defining a language
- Programming Paradigms - models of computation behind the paradigms
- Levels of Artificial Languages - where programming languages sit among formal languages
- History and Genealogy of Languages - how the family tree actually branched
Grammar and parsing
- Grammars: BNF and EBNF - the notation for writing a syntax down
- Ambiguity and Parse Trees - when one string has two readings
- Context-Free Grammar Design - refactoring a grammar to say what you meant
Lambda calculus
The smallest language that can compute anything, and the substrate most semantics are explained on.
- Syntax and Substitution - terms, binding, capture-avoiding substitution
- Evaluation Strategies - call by name, call by value, normal order
- Encodings - booleans, pairs, and Church numerals from nothing but functions
Semantics and evaluation
- Operational Semantics - big-step and small-step rules
- Evaluation Order and Strictness - eager against lazy, and what laziness buys
- Booleans and Conditionals - why conditionals cannot be ordinary functions in a strict language
- Abstract Machines: CEK and SECD - semantics made mechanical
- Continuations and CPS - the rest of the computation as a value
Binding, state, and control
- Values, Variables, Environments - what a name denotes
- Scoping, Binding, and Closures - lexical scope and captured environments
- Mutable State, References, Effects - what changes when a language admits assignment
- Exceptions and Non-Local Control - leaving a computation early
- Coroutines and Generators - suspending and resuming a computation
Type systems
- Type Systems: Goals and Guarantees - what a type system is for
- Type Soundness - progress and preservation, the soundness proof shape
- Hindley-Milner Type Inference - inferring types with no annotations
- Parametric Polymorphism and ADTs - one implementation, many types
- Subtyping and Variance - when one type may stand in for another
- Records, Variants, Pattern Matching - product and sum types, and how you take them apart
- Type Classes and Traits - ad-hoc polymorphism and dictionary passing
- Ownership and Linear Types - types that constrain how many times a value may be used
Abstraction and program structure
- Objects, Classes, and Dispatch - dispatch as the defining mechanism
- Modules and Signatures - sealing an implementation behind an interface
- Macros and Metaprogramming - programs that write programs, and hygiene
Implementation
- Compilation vs Interpretation - a spectrum rather than a dichotomy
- Intermediate Representations and SSA - the form that makes optimization tractable
- Garbage Collection Concepts - reachability as the definition of live
- GC Algorithms - mark-sweep, copying, generational
- Concurrency Models - threads and locks, actors, and the alternatives
The full file listing follows below, generated automatically by Quartz.