CS 421 — Programming Languages

        • Chicago City Scholars
        • Communication
        • Creating Your Github Repository
        • Exam Schedule
        • Grad Student Project
        • Grad Student Project
        • How to Succeed in this Course
        • Lecture Schedule
        • Office Hours Schedule
        • Syllabus
        • Your GitHub Repository
        • Final Exam
        • Midterm 1
        • Midterm 2
        • Midterm 3
        • Algebraic Data Types Lecture
        • Big-Step Semantics Lecture
        • Combinator Parsing Lecture
        • Continuation Passing Style Lecture
        • Course Introduction
        • Grammars Lecture
        • Higher Order Functions Lecture
        • Hoare Semantics Lecture
        • Interpreters I Lecture
        • Interpreters II Lecture
        • Lambda Calculus Lecture
        • LL Parsing Lecture
        • Loop Invariants Lecture
        • LR Parsing Lecture
        • Macros Lecture
        • Monads Lecture
        • Monotype Semantics Lecture
        • Polytype Semantics Lecture
        • Prolog Applications Lecture
        • Prolog Lecture
        • Prolog's Cut Operator Lecture
        • Recursion Lecture
        • Regular Languages Lecture
        • Small Step Semantics Lecture
        • State Monad Lecture
        • Type Classes Lecture
        • Unification Lecture
        • Variables Lecture
        • Egan Johnson
        • Jasmine Liu
        • Jiayou He
        • Mattox Beckman
        • Nabarun Deka
        • Sherry Long
        • Vimarsh Sathia
        • Yiqiu Sun
        • Edsger W. Dijstra
        • Pairs
        • The Applicative Type Class
        • The Functor Type Class
        • Basic Recursion
        • Big Step Semantics
        • Church Numerals
        • Closures
        • Combinator Parsing
        • Continuation Passing Style
        • Dynamic Prolog
        • Evaluation Order
        • FIRST Sets
        • Fixing Non-LL Grammars
        • FOLLOW Sets
        • Functors and Applicative
        • Hoare Semantics
        • Induction
        • Interpreters 1
        • Interpreters 2
        • Introduction to Grammars
        • Introduction to Higher Order Functions
        • Introduction to Semantics
        • Lambda Calculus
        • Lambda Calculus Examples
        • LL Parsing
        • Loop Invariants
        • LR Parsing
        • Macros
        • Map and Foldr
        • Monads
        • Monotype Semantics
        • Objects
        • Parameters
        • Polytype Semantics
        • Product Types
        • Prolog
        • Prolog's Cut Operator
        • Regular Languages
        • Right Linear Grammars
        • Shift Reduce Conflicts
        • Small Step Semantics
        • State
        • State Monad
        • State Monad Example
        • Subclasses and Subtyping
        • Sum Types, Part 1
        • Sum Types, Part 2
        • Tail Recursion
        • The Church-Rosser Property
        • The CPS Transform
        • The Y-Combinator
        • Type Classes
        • Unification
        • Variables
    Home

    ❯

    Lectures

    ❯

    Small Step Semantics Lecture

    Small Step Semantics Lecture

    Feb 16, 20261 min read

    • lecture

    Synopsis

    The system we will talk about today is called small-step semantics, also called transition semantics, or even operational semantics. The idea with this semantics is that we model what one step of computation looks like, and use that to describe the meaning of a program.

    One very important concept that comes up with this form is the Church-Rosser theorem.

    Videos

    • Small Step Semantics
    • The Church-Rosser Property

    Handouts

    • Small Step Semantics Activity (PDF)
    • Small Step Rules (PDF)

    Graph View

    • Synopsis
    • Videos
    • Handouts

    Backlinks

    • Lecture Schedule

    Created with Quartz v4.4.0 © 2026

    • GitHub
    • Discord Community