Computer Science › Software + Distributed Computing
Programming Paradigms compared what languages let you SAY — OOP vs. functional vs. logic, as features you choose between. This discipline asks a different question: once a language exists on paper, how does a machine actually make a program written in it run?
Before building an interpreter, a language needs a precise, on-paper definition of what each expression actually evaluates to — small-step operational semantics gives exactly that, one inference rule at a time, on a language small enough to write every rule down in full.
Three constructs — a variable, a function, and a function call — turn out to be enough to build every programming language construct that exists; the lambda calculus is that minimal core, stripped of everything else so its evaluation rules can be studied directly.
Beta reduction — substituting an argument for a bound variable — is the lambda calculus's one and only computation rule; the real design choice is WHEN to apply it, and call-by-value vs. call-by-name is that choice, made concrete on a term that behaves differently under each.
Church encodings show that booleans, numbers, and even recursion can be built from nothing but functions — real evidence for the Church-Turing thesis's claim that the lambda calculus, despite having no built-in data types at all, computes exactly what a Turing machine computes.
The first step from raw source text to a running program: a scanner walks the character stream once, left to right, and groups characters into tokens — numbers, identifiers, operators — the smallest units a parser is willing to work with.
A parser takes the token stream and recovers its grammatical structure — literally applying the context-free grammar derivations already covered, but now building a tree instead of just deciding accept-or-reject.
An `eval` function that recurses over the AST, one node type at a time, is small-step operational semantics made runnable — every evaluation rule written on paper earlier becomes one case of a real function here.
A variable name is not the value it holds — an environment is the runtime data structure (a chain of mappings) that actually connects the two, and lexical vs. dynamic scope is a real design choice about which environment a variable resolves against.
Closures were already shown as a language FEATURE — a function that keeps working after its enclosing scope returns. Here is the implementation underneath: a function value is a pair of its code and the environment it was created in, kept alive by that pairing alone.
An `if` or a `while` is not a special magic case for an interpreter — it is one more AST node type whose evaluation rule decides which of its children to evaluate, and how many times, entirely in terms of machinery already built.
The interpreter's own call stack (tree-walk recursion calling itself for a function call) and the real hardware call stack already covered are the same idea at two different levels: one frame per active call, torn down on return either way.
A static type system rejects some programs before they ever run; a dynamic one only discovers a type error the moment it happens at runtime — the same tradeoff (caught early vs. more flexible) that shows up in every real language's design.
"Well-typed programs don't go wrong" is not a slogan — it is exactly two provable properties: progress (a well-typed term is either done or can still take a step) and preservation (taking a step never changes a term's type).
Adding one typing rule per lambda-calculus construct turns the untyped calculus into a small, real type system — a typing judgment written directly under a function, checked against a context, exactly like the progress/preservation properties it's designed to satisfy.
Writing every type annotation by hand gets tedious fast — type inference recovers the same typing judgments without them, by generating constraints between unknown types and solving those constraints by unification.
Manual heap management already showed exactly how a leak or a dangling pointer happens — a language runtime with automatic memory management exists specifically to make that entire bug class structurally impossible, at the cost of runtime work a C program never pays.
Every piece built in this discipline — scanner, parser, AST, environment, closures, control flow, a type checker — wired together into one small, working interpreter, mirroring how the CPU discipline's own capstone assembled gates and a datapath into a working machine.
Part of the Computer Science curriculum.
Programming Paradigms compared what languages let you SAY — OOP vs. functional vs. logic, as features you choose between. This discipline asks a different question: once a language exists on paper, how does a machine actually make a program written in it run?
Before building an interpreter, a language needs a precise, on-paper definition of what each expression actually evaluates to — small-step operational semantics gives exactly that, one inference rule at a time, on a language small enough to write every rule down in full.
Three constructs — a variable, a function, and a function call — turn out to be enough to build every programming language construct that exists; the lambda calculus is that minimal core, stripped of everything else so its evaluation rules can be studied directly.
Beta reduction — substituting an argument for a bound variable — is the lambda calculus's one and only computation rule; the real design choice is WHEN to apply it, and call-by-value vs. call-by-name is that choice, made concrete on a term that behaves differently under each.
Church encodings show that booleans, numbers, and even recursion can be built from nothing but functions — real evidence for the Church-Turing thesis's claim that the lambda calculus, despite having no built-in data types at all, computes exactly what a Turing machine computes.
The first step from raw source text to a running program: a scanner walks the character stream once, left to right, and groups characters into tokens — numbers, identifiers, operators — the smallest units a parser is willing to work with.
A parser takes the token stream and recovers its grammatical structure — literally applying the context-free grammar derivations already covered, but now building a tree instead of just deciding accept-or-reject.
An `eval` function that recurses over the AST, one node type at a time, is small-step operational semantics made runnable — every evaluation rule written on paper earlier becomes one case of a real function here.
A variable name is not the value it holds — an environment is the runtime data structure (a chain of mappings) that actually connects the two, and lexical vs. dynamic scope is a real design choice about which environment a variable resolves against.
Closures were already shown as a language FEATURE — a function that keeps working after its enclosing scope returns. Here is the implementation underneath: a function value is a pair of its code and the environment it was created in, kept alive by that pairing alone.
An `if` or a `while` is not a special magic case for an interpreter — it is one more AST node type whose evaluation rule decides which of its children to evaluate, and how many times, entirely in terms of machinery already built.
The interpreter's own call stack (tree-walk recursion calling itself for a function call) and the real hardware call stack already covered are the same idea at two different levels: one frame per active call, torn down on return either way.
A static type system rejects some programs before they ever run; a dynamic one only discovers a type error the moment it happens at runtime — the same tradeoff (caught early vs. more flexible) that shows up in every real language's design.
"Well-typed programs don't go wrong" is not a slogan — it is exactly two provable properties: progress (a well-typed term is either done or can still take a step) and preservation (taking a step never changes a term's type).
Adding one typing rule per lambda-calculus construct turns the untyped calculus into a small, real type system — a typing judgment written directly under a function, checked against a context, exactly like the progress/preservation properties it's designed to satisfy.
Writing every type annotation by hand gets tedious fast — type inference recovers the same typing judgments without them, by generating constraints between unknown types and solving those constraints by unification.
Manual heap management already showed exactly how a leak or a dangling pointer happens — a language runtime with automatic memory management exists specifically to make that entire bug class structurally impossible, at the cost of runtime work a C program never pays.
Every piece built in this discipline — scanner, parser, AST, environment, closures, control flow, a type checker — wired together into one small, working interpreter, mirroring how the CPU discipline's own capstone assembled gates and a datapath into a working machine.