Lumenary CS · Programming languages
Scheme
The minimalist Lisp that taught generations to think about computation: a few simple ideas, combined without limit, from a first expression to an interpreter of your own.
Scheme is a small, elegant dialect of Lisp created by Gerald Jay Sussman and Guy L. Steele Jr. at MIT in 1975. Its design removes rather than adds: a handful of special forms, procedures as first-class values, lexical scope, proper tail calls, hygienic macros and first-class continuations are enough to build everything else. It is defined by a series of community reports; the current one, R7RS-small (2013), is short enough to read in an afternoon. Scheme has been used to teach computer science for decades, most famously through Structure and Interpretation of Computer Programs, and lives on in research on programming languages, as an extension language (GNU Guile), and in implementations such as Racket, Chez Scheme and Chibi-Scheme.
This course is for anyone who already knows what a variable, a loop and a function are: the Start level of Lumenary CS or equivalent experience in any language. It starts with expressions and evaluation, works through recursion, lists, higher-order procedures and closures, and finishes with hygienic macros, continuations, the landscape of implementations, and an interpreter for a small language written in Scheme itself.
Scheme is a standard with many implementations rather than a single product, and there is no official online playground. This course uses portable R7RS-small code and runs it with Chibi-Scheme, a compact implementation that follows the standard closely; build it from its repository (make && sudo make install) or install it from your system's package manager, then run a program with chibi-scheme main.scm. Other R7RS implementations, such as Gauche, Guile 3 or CHICKEN with its r7rs extension, run the same programs; get.scheme.org lists them. Every complete program in these lessons was run with Chibi-Scheme 0.12 by Lumenary's test suite, and the output shown is the output it printed. The lessons were drafted with AI assistance and are awaiting review by a human computer scientist.
- Chloe · The Designer
“Why is the language built this way?” - Margaret · The Profiler
“What does it print, and what does it cost?” - Gideon · The Language Lawyer
“What exactly does the language guarantee?”
Foundations · 3 lessons
Foundations
Meet the Lisp family and Scheme's minimalism, run programs with an R7RS implementation, and master expressions, define, lambda, lexical scope, recursion and proper tail calls.
- 1First steps: the Lisp family and Scheme's minimalismWhere Scheme came from, why it is so small, how to run it, and how an expression is evaluated. 50 min
- 2Expressions, define, lambda and lexical scopeNaming values and procedures, making decisions, and the let forms that control where a name can be seen. 55 min
- 3Recursion and proper tail callsHow Scheme repeats without loop statements, why its tail calls never run out of stack, and how to tell a recursive process from an iterative one. 60 min
Practice · 3 lessons
Practice
Build data from pairs and lists, use symbols and quotation, write higher-order procedures and closures, and organise data with association lists, vectors, strings and records.
- 4Pairs, lists, symbols and quotingOne tiny data structure, the pair, builds lists, trees and Scheme code itself; quotation lets programs treat code as data. 60 min
- 5Higher-order procedures and closuresProcedures that take and return procedures, folds that capture every list loop, and closures that carry their own private state. 60 min
- 6Association lists, vectors, strings and recordsLookup tables made of pairs, constant-time indexed vectors, text as characters and strings, and record types with named fields. 60 min
Professional · 2 lessons
Professional
Extend the language with hygienic macros, take a careful first look at continuations and exceptions, survey the implementations, and write an interpreter for a small language.
- 7Hygienic macros, continuations and exceptionsExtending the language with syntax-rules, a careful first look at call/cc, and how R7RS signals and handles errors. 70 min
- 8Project: an interpreter, the implementations, and SICPWrite an evaluator for a small Scheme in Scheme, survey today's implementations, and see why one textbook shaped a generation of computer scientists. 75 min
Further reading and resources
- R7RS: Revised7 Report on the Algorithmic Language SchemeThe home of the current standard: the small language report (2013) and the ongoing large language.
- R7RS-small, errata-corrected edition (HTML)The full text of the standard this course follows, readable in a browser.
- Scheme.orgThe community's home page: documentation, standards, implementations and research.
- Chibi-SchemeThe implementation used to run this course's programs, with build instructions.
- Chibi-Scheme user manualHow to run, configure and extend Chibi-Scheme.
- Scheme implementationsA list of current implementations and the standards each supports.
- Structure and Interpretation of Computer Programs, second edition · Harold Abelson and Gerald Jay Sussman with Julie Sussman · 1996MIT Press's web site for the book, with its full text online.