Racket recursion and higher-order list programming
Racket makes the structure of data unusually visible. A list is either empty or it has a first item and a smaller list containing the remaining items. Good l...
Lectures
letrec, quasiquote, and match
Programming-languages work constantly crosses a boundary between using Racket syntax and representing syntax as data. Quasiquote makes symbolic data convenie...
Free and bound variables and lexical address
Variable names do two jobs in source code. A declaration introduces a name, while a reference uses a name. Lexical scope determines which declaration—if any—...
How does an interpreter work? Permalink
Canonical notes on environments, delayed lambda bodies, shadowing, and an interpreter trace.
Representation-independent environments and closures
Our first interpreter represented an environment as a Racket procedure and an object-language closure as another Racket procedure. Those choices were conveni...
Lambda syntax and capture-avoiding substitution
Substitution sounds like textual replacement: replace x with another expression. Binding makes the real operation more careful. We must replace only free occ...
Lexical and dynamic scope
When a program contains a variable reference, which declaration gives that reference its value? A language’s scope rule answers that question. Two languages ...
Lambda calculus and equational reasoning
The untyped lambda calculus has only variables, abstraction, and application. Despite that tiny syntax, it can express data, control, and general computation...
Continuations and continuation-passing style
A direct-style function returns its answer to its caller. A function in continuation-passing style (CPS) instead receives an explicit description of what sho...
A small interpreter in continuation-passing style
An interpreter is an ordinary recursive program, so it can use the same continuation-passing interface as other recursive programs. In a CPS interpreter, the...
Representation-independent continuations
The CPS factorial procedure represents each pending multiplication as a Racket procedure. That representation is convenient, but the rest of the program can ...
Registerization
The original, general transformation development remains on Jason Hemann’s site as Representation Independence Procedure. This course companion uses factoria...
Store-passing style
Store-passing style (SPS) makes changing state explicit. An SPS procedure receives the current store and returns both its ordinary value and the store that t...