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
        • Allison Ye
        • Cody Rivera
        • Helen Ilkiu
        • Krushank Bayyapu
        • Maanav Agrawal
        • Mattox Beckman
        • Paul Krogmeier
        • Shams Alshabani
        • Uche Uche-Ike
        • 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

    Dec 30, 20251 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 © 2025

    • GitHub
    • Discord Community