Programming Language Semantics

Research Depth 61 in the knowledge graph I know this Set as goal
Unlocks 25 downstream topics
semantics formal-methods language-design

Core Idea

Semantics defines what a program means—its runtime behavior. Formal semantics uses denotational (functions mapping programs to meanings), operational (step-by-step execution rules), or axiomatic (assertions about properties) approaches. These frameworks allow compilers to reason about correctness and optimization validity.

Explainer

A grammar tells you whether `x = 3 + y` is a syntactically valid program, but it says nothing about what the program *does*. Programming language semantics fills that gap — it is the formal study of program meaning. If syntax is the grammar of sentences, semantics is what those sentences actually say. Your background in lambda calculus gives you the right foundation here, because lambda calculus is itself a minimal programming language with precisely defined semantics, and much of formal semantics extends its ideas.

Operational semantics is the most concrete approach. It defines meaning by specifying evaluation rules — literally, "given this expression in this state, the next step produces that expression in that state." For example, an operational rule might say: to evaluate `if true then e1 else e2`, evaluate `e1`. These rules resemble an interpreter specification. There are two flavors: small-step (structural) operational semantics breaks evaluation into individual reduction steps, making it easy to reason about intermediate states and non-termination. Big-step (natural) semantics jumps directly from an expression to its final value, which is closer to how you intuitively think about evaluation but hides intermediate computation.

Denotational semantics takes a more mathematical approach. Instead of describing how a program executes step by step, it maps each program to a mathematical object — its "denotation." A variable maps to its value in an environment, a function maps to a mathematical function from inputs to outputs, and a while loop maps to a fixed point. This builds directly on the function-as-value idea from lambda calculus. The advantage is compositionality: the meaning of a compound expression is built entirely from the meanings of its parts, which makes it possible to prove program equivalences algebraically.

Axiomatic semantics, most associated with Hoare logic, defines meaning through the properties you can prove about a program. A Hoare triple `{P} S {Q}` says: if precondition P holds before executing statement S, then postcondition Q holds after. For instance, `{x > 0} x = x - 1 {x >= 0}`. This approach is less about what the program computes and more about what guarantees it provides, making it the foundation for formal verification. For compiler writers, all three frameworks matter: operational semantics guides interpreter and code generator design, denotational semantics justifies optimization (two expressions with the same denotation can be freely substituted), and axiomatic semantics validates that transformations preserve program correctness.

Practice Questions 5 questions

Prerequisite Chain

Counting to 10Counting to 20Understanding ZeroThe Number ZeroCounting to FiveOne-to-One CorrespondenceCombining Small Groups Within 5Addition Within 10Addition Within 20Two-Digit Addition Without RegroupingTwo-Digit Addition with RegroupingAddition Within 100Repeated Addition as MultiplicationMultiplication Facts Within 100Division as Equal SharingDivision as Grouping (Measurement Division)Division: Grouping (Repeated Subtraction) ModelDivision: Fair Sharing ModelDivision as Equal SharingDivision as GroupingBasic Division FactsDivision Facts Within 100Two-Digit by One-Digit DivisionDivision with RemaindersRemainders and Quotients in DivisionDivision Word ProblemsIntroduction to Long DivisionFactors and MultiplesPrime and Composite NumbersEquivalent FractionsRelating Fractions and DecimalsDecimal Place ValueReading and Writing DecimalsComparing and Ordering DecimalsAdding and Subtracting DecimalsMultiplying DecimalsDividing DecimalsDividing FractionsMixed Number ArithmeticOrder of OperationsOperators and ExpressionsArithmetic Operators and Operator PrecedenceComparison Operators and Boolean TestsLogical Operators and Boolean AlgebraBoolean Algebra and Fundamental LawsCombinational Circuit DesignFlip-Flops and LatchesFinite State Machines (FSMs)Deterministic Finite Automata (DFA)Nondeterministic Finite Automata (NFA)Two-Way Finite AutomataNFA to DFA Conversion (Subset Construction)DFA Properties and Minimization AlgorithmsRegular Languages: Definition and CharacterizationContext-Free Grammars (CFGs)Context-Free Grammar Properties and AmbiguityParse Trees, Derivations, and Ambiguity in CFGsContext-Free Grammars in Compiler DesignCompiler Phases and OrganizationGrammar Design for CompilationDomain-Specific Language Design and ImplementationProgramming Language Semantics

Longest path: 62 steps · 277 total prerequisite topics

Prerequisites (3)

Leads To (6)