Chapter 4: Scheme - The Academic Beauty
“Programming languages should be designed not by piling feature on top of feature, but by removing the weaknesses and restrictions that make additional features appear necessary.” - The Revised⁷ Report on Scheme
If Common Lisp is a Swiss Army knife, Scheme is a scalpel—precise, minimal, and devastatingly effective in the right hands. It’s the language that proves you can derive infinite complexity from ultimate simplicity. It’s mathematical poetry that happens to execute.
Scheme doesn’t just teach you programming; it teaches you the essence of computation itself. It’s the language where students discover that loops are an illusion, that goto can be a virtue (when it’s called call/cc), and that the Y combinator isn’t just abstract theory but a practical tool.
Minimalism as a Feature
The entire R5RS Scheme specification is 50 pages. The Java Language Specification is over 700 pages. This isn’t because Scheme does less—it’s because Scheme is built on principles so fundamental that everything else emerges naturally.
Here’s the entirety of special forms in R5RS Scheme:
quote- Prevent evaluationlambda- Create functionsif- Conditional evaluationset!- Assignmentdefine- Bind namesbegin- Sequencing
That’s essentially it. Everything else—including let, and, or, cond, case—can be derived from these primitives. Watch:
;; 'let' is just lambda in disguise
(let ((x 5)
(y 10))
(+ x y))
;; Is exactly equivalent to:
((lambda (x y) (+ x y)) 5 10)
;; 'and' is just nested ifs
(define-syntax and
(syntax-rules ()
((and) #t)
((and test) test)
((and test1 test2 ...)
(if test1 (and test2 ...) #f))))
;; Even 'cond' is just nested ifs
(define-syntax cond
(syntax-rules (else)
((cond (else result))
result)
((cond (test result) clause ...)
(if test result (cond clause ...)))))
This isn’t minimalism for its own sake. It’s minimalism that teaches. When you understand how Scheme builds complex features from simple ones, you understand how computation itself works.
Setting Up Racket and Guile
In 2025, two Scheme implementations dominate: Racket (the academic powerhouse) and Guile (the GNU extension language). Let’s set up both.
Installing Racket
Racket has evolved beyond just Scheme—it’s now a platform for creating languages. But it still runs beautiful Scheme code.
On macOS:
brew install --cask racket
On Linux:
# Ubuntu/Debian
sudo apt-get install racket
# Or download from racket-lang.org for the latest version
On Windows:
# Download the installer from racket-lang.org
# Racket has excellent Windows support
Start the Racket REPL:
racket
Or use the spectacular DrRacket IDE:
drracket &
Installing Guile
Guile is GNU’s official extension language, designed to be embedded in other programs. It’s Scheme with practical extensions.
# macOS
brew install guile
# Linux
sudo apt-get install guile-3.0
# From source (for the latest features)
wget https://ftp.gnu.org/gnu/guile/guile-3.0.9.tar.gz
tar xzf guile-3.0.9.tar.gz
cd guile-3.0.9
./configure && make && sudo make install
Your First Scheme Session
Let’s explore what makes Scheme special:
;; Start with Racket
#lang r5rs ; Use the R5RS standard
;; Functions are values
(define square (lambda (x) (* x x)))
(define cube (lambda (x) (* x x x)))
;; Higher-order functions are natural
(define (compose f g)
(lambda (x) (f (g x))))
(define sixth-power (compose cube square))
(sixth-power 2) ; => 64
;; Recursion is the primary control structure
(define (factorial n)
(if (zero? n)
1
(* n (factorial (- n 1)))))
;; But with proper tail recursion, it's efficient
(define (factorial-iter n)
(define (iter n acc)
(if (zero? n)
acc
(iter (- n 1) (* n acc))))
(iter n 1))
;; The calls to 'iter' don't grow the stack!
(factorial-iter 100000) ; Works fine (returns a very large number)
Continuations and Tail Call Optimization
Scheme’s two superpowers are proper tail recursion and first-class continuations. Let’s understand both.
Tail Call Optimization: Loops Without Loops
In Scheme, if the last thing a function does is call another function (including itself), the call doesn’t use additional stack space. This isn’t an optimization—it’s guaranteed by the specification.
;; This looks like it should blow the stack, but it doesn't
(define (count-to n)
(define (loop i)
(if (>= i n)
'done
(begin
(display i) (newline)
(loop (+ i 1))))) ; Tail call - no stack growth
(loop 0))
(count-to 1000000) ; No problem!
;; Compare with this non-tail-recursive version:
(define (count-to-bad n)
(define (loop i)
(if (>= i n)
'done
(begin
(display i) (newline)
(loop (+ i 1))
'not-tail))) ; Not in tail position!
(loop 0))
;; This will blow the stack on large inputs
This means Scheme doesn’t need loop constructs. Recursion is the loop, and it’s just as efficient:
;; A 'while' loop in Scheme
(define (while condition body)
(if (condition)
(begin
(body)
(while condition body)) ; Tail recursive
'done))
;; Use it
(define counter 0)
(while (lambda () (< counter 10))
(lambda ()
(display counter) (newline)
(set! counter (+ counter 1))))
Continuations: Time Travel for Programs
A continuation represents “the rest of the computation.” In Scheme, you can capture the current continuation and invoke it later, effectively implementing time travel for your program.
;; call/cc = call with current continuation
(define (demonstrate-continuations)
(display "Starting\n")
(call/cc (lambda (exit)
(display "Inside call/cc\n")
(exit 'early-return) ; Jump out early
(display "This never prints\n")))
(display "After call/cc\n"))
;; More powerful: save continuations for later
(define saved-continuation #f)
(define (save-and-return)
(call/cc (lambda (k)
(set! saved-continuation k)
'first-time)))
(save-and-return) ; => 'first-time
(saved-continuation 'second-time) ; => 'second-time
(saved-continuation 'third-time) ; => 'third-time
Continuations let you implement any control flow mechanism:
;; Implement exceptions with continuations
(define *exception-handler* (lambda (x) (error "Unhandled exception" x)))
(define (try thunk handler)
(let ((old-handler *exception-handler*))
(call/cc (lambda (escape)
(set! *exception-handler*
(lambda (error)
(set! *exception-handler* old-handler)
(escape (handler error))))
(let ((result (thunk)))
(set! *exception-handler* old-handler)
result)))))
(define (throw exception)
(*exception-handler* exception))
;; Use it
(try (lambda ()
(display "Trying something dangerous\n")
(throw 'oops)
(display "This won't print\n"))
(lambda (error)
(display "Caught: ")
(display error)
(newline)
'recovered))
Even coroutines and generators:
;; A generator using continuations
(define (make-generator proc)
(let ((cont #f))
(lambda ()
(call/cc (lambda (return)
(if cont
(cont return)
(proc (lambda (v)
(call/cc (lambda (k)
(set! cont k)
(return v))))))))))))
(define count-gen
(make-generator
(lambda (yield)
(let loop ((i 0))
(yield i)
(loop (+ i 1))))))
(count-gen) ; => 0
(count-gen) ; => 1
(count-gen) ; => 2
Educational Excellence
Scheme is the teaching language par excellence. MIT’s Structure and Interpretation of Computer Programs (SICP), often called the best computer science textbook ever written, uses Scheme to teach fundamental concepts.
Why Scheme excels at teaching:
1. No Syntax Distractions
;; Everything has the same shape
(+ 1 2) ; Addition
(define x 5) ; Definition
(lambda (x) x) ; Function
(if test then else) ; Conditional
;; Compare with JavaScript:
// Different syntax for everything
1 + 2 // Addition
let x = 5 // Definition
(x) => x // Function
test ? then : else // Conditional
2. Ideas in Their Purest Form
;; Recursion without loops to confuse things
(define (map f lst)
(if (null? lst)
'()
(cons (f (car lst))
(map f (cdr lst)))))
;; Higher-order functions without syntax sugar
(define (twice f)
(lambda (x) (f (f x))))
((twice square) 3) ; => 81
;; Lexical scope you can see
(define (make-counter)
(let ((count 0))
(lambda ()
(set! count (+ count 1))
count)))
3. Build Your Own Language Features
Scheme’s macro system (hygienic macros) lets students implement language features themselves:
;; Implement a for loop
(define-syntax for
(syntax-rules ()
((for (var start end) body ...)
(let loop ((var start))
(if (< var end)
(begin
body ...
(loop (+ var 1))))))))
;; Use it
(for (i 0 10)
(display i)
(display " "))
; Prints: 0 1 2 3 4 5 6 7 8 9
;; Implement pattern matching
(define-syntax match
(syntax-rules ()
((match expr
(pattern result) ...)
(cond
((equal? expr pattern) result) ...))))
The Beauty of Functional Programming
Scheme doesn’t enforce functional programming, but it makes it so natural that you can’t help but think functionally:
;; Everything returns a value
(define x (if (> 5 3) 'yes 'no)) ; x = 'yes
;; Functions are values
(define operations (list + - * /))
(map (lambda (op) (op 10 5)) operations) ; => (15 5 50 2)
;; Closures capture their environment
(define (make-adder n)
(lambda (x) (+ x n)))
(define add5 (make-adder 5))
(add5 10) ; => 15
;; Fold (reduce) as the universal list operation
(define (fold-right op init lst)
(if (null? lst)
init
(op (car lst)
(fold-right op init (cdr lst)))))
;; Everything is fold
(define (map f lst)
(fold-right (lambda (x acc) (cons (f x) acc)) '() lst))
(define (filter pred lst)
(fold-right (lambda (x acc)
(if (pred x) (cons x acc) acc))
'() lst))
(define (length lst)
(fold-right (lambda (x acc) (+ 1 acc)) 0 lst))
Practical Scheme: It’s Not Just Academic
While Scheme is beloved in academia, it’s also practical. GNU Guile, in particular, is designed for real-world use:
;; A web server in Guile
(use-modules (web server)
(web request)
(web response)
(web uri)
(sxml simple))
(define (handler request request-body)
(let ((path (uri-path (request-uri request))))
(cond
((string=? path "/")
(values '((content-type . (text/html)))
(sxml->xml
`(html
(head (title "Scheme Web App"))
(body
(h1 "Hello from Scheme!")
(p "The current time is "
,(strftime "%c" (localtime (current-time))))
(ul
(li (a (@ (href "/about")) "About"))
(li (a (@ (href "/api")) "API"))))))))
((string=? path "/about")
(values '((content-type . (text/plain)))
"This is a Scheme web server!"))
((string=? path "/api")
(values '((content-type . (application/json)))
"{\"language\": \"Scheme\", \"awesome\": true}"))
(else
(values (build-response #:code 404)
"Not found")))))
(run-server handler 'http '(#:port 8080))
Guile is also the extension language for many GNU programs:
;; Extending GDB with Guile
(use-modules (gdb))
(define (break-on-malloc)
"Set a breakpoint on every call to malloc"
(break "malloc")
(commands
(print "Malloc called!")
(backtrace 3)
(continue)))
;; Configuring GNU Guix (the Scheme-based package manager)
(operating-system
(host-name "scheme-machine")
(timezone "America/New_York")
(locale "en_US.utf8")
(bootloader (bootloader-configuration
(bootloader grub-efi-bootloader)
(target "/boot/efi")))
(packages (cons* emacs git guile-3.0 %base-packages))
(services (cons* (service openssh-service-type)
%base-services)))
The Metacircular Evaluator: Scheme in Scheme
One of Scheme’s most mind-bending exercises is writing Scheme in Scheme. This isn’t just an academic exercise—it’s how you truly understand what computation means:
;; A complete Scheme interpreter in Scheme
(define (eval expr env)
(cond
;; Self-evaluating
((number? expr) expr)
((string? expr) expr)
((boolean? expr) expr)
;; Variable lookup
((symbol? expr) (lookup expr env))
;; Special forms
((eq? (car expr) 'quote) (cadr expr))
((eq? (car expr) 'if)
(if (eval (cadr expr) env)
(eval (caddr expr) env)
(eval (cadddr expr) env)))
((eq? (car expr) 'lambda)
(list 'closure (cadr expr) (cddr expr) env))
((eq? (car expr) 'define)
(define-var! (cadr expr) (eval (caddr expr) env) env))
;; Function application
(else
(apply-proc (eval (car expr) env)
(map (lambda (arg) (eval arg env))
(cdr expr))))))
(define (apply-proc proc args)
(if (eq? (car proc) 'closure)
(let ((params (cadr proc))
(body (caddr proc))
(env (cadddr proc)))
(eval (if (= (length body) 1)
(car body)
(cons 'begin body))
(extend-env params args env)))
(error "Not a procedure" proc)))
;; Now you have Scheme running in Scheme!
This metacircular evaluator reveals the essence of computation. Once you understand it, you understand interpreters, compilers, and computation itself.
The Scheme Philosophy
Scheme embodies a philosophy that goes beyond programming:
Orthogonality: Features should be independent and composable. Don’t special-case; generalize.
Uniformity: Similar things should look similar. All values are first-class. All positions are evaluated the same way.
Simplicity: Complexity should emerge from combining simple pieces, not from complex primitives.
Mathematics: Programming is applied mathematics. Lambda calculus isn’t just theory; it’s the foundation.
This philosophy influences how you think about problems. In Scheme, you don’t ask “What syntax do I need?” You ask “What abstraction captures this pattern?”
Modern Scheme: R7RS and Beyond
Scheme continues to evolve. R7RS (2013) split into a small language (R7RS-small) and a large language (R7RS-large, still in progress):
;; R7RS features
(import (scheme base)
(scheme write)
(scheme file))
;; Libraries and modules
(define-library (my utils)
(export square cube)
(import (scheme base))
(begin
(define (square x) (* x x))
(define (cube x) (* x x x))))
;; Record types
(define-record-type point
(make-point x y)
point?
(x point-x)
(y point-y))
;; Parameters (dynamic variables)
(define current-output (make-parameter (current-output-port)))
(parameterize ((current-output (open-output-string)))
(display "Hidden output")
(let ((str-port (current-output)))
(get-output-string str-port)))
The Scheme Enlightenment
Learning Scheme is like learning mathematics through programming. You don’t just learn how to program; you learn what programming is. Concepts that seem complex in other languages become simple:
- Loops are just recursion
- Objects are just closures
- Exceptions are just continuations
- Syntax is just macros
- Types are just predicates
This isn’t reductionism—it’s understanding. Once you see how these complex features emerge from simple principles, you can implement them yourself. You’re no longer limited by your language; you can extend it.
When to Choose Scheme
Choose Scheme when:
Learning or Teaching: No language teaches computer science concepts better than Scheme.
Language Experimentation: Racket’s language-building facilities are unmatched.
Embedded Scripting: Guile is designed to be embedded in C programs.
Mathematical Computing: Scheme’s clean semantics make it perfect for symbolic computation.
Understanding Computation: If you want to truly understand interpreters, compilers, and computation itself.
The Eternal Student
Scheme teaches humility. Just when you think you understand it, you discover another layer. The Y combinator, delimited continuations, syntax-case macros, the metacircular evaluator—each concept opens new vistas of understanding.
But Scheme also teaches power. With a few simple principles, you can derive anything. You’re not learning a programming language; you’re learning the principles from which all programming languages emerge.
This is why Scheme endures in education. Languages come and go, but the principles Scheme teaches are eternal. Students who learn Scheme don’t just become better Scheme programmers; they become better programmers, period.
The Joy of Simplicity
There’s a joy in Scheme’s simplicity that’s hard to convey. It’s the joy of understanding something completely. No special cases, no arbitrary restrictions, no historical baggage. Just pure, simple, powerful ideas.
When you write Scheme, you’re not fighting the language. You’re expressing ideas as directly as possible. The language disappears, leaving only the problem and its solution.
This is the gift of Scheme: it shows you that programming doesn’t have to be complicated. Complexity in programs should come from complex problems, not complex languages. And sometimes, the simplest solution is also the most powerful.
“Programs must be written for people to read, and only incidentally for machines to execute.” - Structure and Interpretation of Computer Programs
Next, we dive into Emacs Lisp—the Lisp that’s also an editor, an operating system, and a way of life. We’ll learn how to bend Emacs to our will, write modes that make us more productive, and understand why some people never leave Emacs. Not even to sleep.