The core philosophy is that a programming language is not an ad-hoc collection of features but a mathematical object with intrinsic, verifiable properties. To analyze and design such objects, this course introduces students to a toolset of formal systems used to describe a language's syntax, its rules (statics), its behavior (dynamics), and its correctness (safety). The goal is to cultivate an understanding that transcends any single language, allowing one to see the common mathematical structures underpinning vastly different paradigms like functional, imperative, and concurrent programming.
Each method reveals different truths. Operational semantics is good for implementation. Denotational semantics is good for compositionality. Axiomatic semantics is good for reasoning about correctness.
You learn how to design libraries and micro-languages that are intuitive, robust, and impossible for users to misuse. Summary of Major Course Milestones Focus Area Core Question Syntactic Crunch Variable binding and substitution How do we avoid name clashes during execution? Statics & Dynamics Typing rules and transition steps How do we precisely define code execution? Safety Proofs Progress and Preservation Can we mathematically guarantee code won't crash? Modern Features Continuations, references, concurrency How do we safely scale languages for modern hardware?
The formal logic behind garbage collection and resource allocation. 4. The Safety Theorem 15312 foundations of programming languages
Parametric polymorphism enables developers to write reusable code that works with multiple data types. However, manually specifying type parameters can be cumbersome and error-prone. By adding type inference, we can alleviate this burden and make PolyLambda more expressive and user-friendly.
Static semantics dictate what constitutes a "legal" program before execution. This is where type systems are defined. Using formal derivation rules (logical fractions), students learn to prove that an expression has a type under a specific context Γcap gamma (written as
Understanding these historical foundations helps clarify why modern languages (Python, Rust, Scala) function the way they do. 3. Core Concepts in 15312 Foundations The core philosophy is that a programming language
Using type systems to ensure programs make sense before they ever run.
Most programmers enter the field viewing a compiler as a black box: a magical entity that complains when they miss a semicolon. 15-312 shatters this illusion by introducing . Before a program ever runs, it undergoes a "proof" phase. The type system is not a linting tool; it is a logical gatekeeper.
Traces execution clock-cycle by clock-cycle, showing every individual transition. This is crucial for modeling parallelism and concurrency. Each method reveals different truths
: The principles used to build a coherent language apply directly to building clean, bug-resistant software architectures and developer APIs.
A of a Small-step Operational Semantics proof. A comparison of structural vs. nominal type systems. An introduction to Hoare Logic for axiomatic semantics. Let me know which area you'd like to dive into! Share public link
-Calculus: Exploring the limits of computation vs. the stability of types.
Represents a type scheme, which can be either a monomorphic type or a polymorphic type with a universal quantifier.