A language you can hold in your head
Most programming languages grow. Each version adds syntax for a new kind of loop, a new way to declare things, a new special case. After a few decades the language specification runs to well over a thousand pages, and no single person knows all of it.
Scheme went the other way. Its designers asked what is the smallest set of ideas from which everything else can be built, and kept only those. The result is a language whose core you can learn in a week and whose official definition, the R7RS-small report, is about ninety pages including its formal semantics. Since 1986 the Scheme reports have opened with a sentence that sums up the philosophy:
"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." (Revised Reports on the Algorithmic Language Scheme)
What survives the removing is remarkably powerful. Procedures are values you can pass around and return. Any procedure call in tail position is a jump, so loops can be written as recursion without ever running out of stack. Programs can define new syntax that is guaranteed not to clash with the names around it. And a program can capture "the rest of the computation" as a value and resume it later, the feature (called a continuation) that lets Scheme express exceptions, generators and backtracking without any of them being built in.
That is why Scheme has had an outsized influence on computer science education and on language design. Ideas that were first worked out in Scheme now appear in JavaScript, Python, Ruby, Rust, Clojure and many others. Learning Scheme is learning those ideas in their simplest, clearest form.
Where Scheme came from
Lisp, created by John McCarthy in 1958, is the second-oldest high-level language still in use (only Fortran is older). Its programs are written as nested lists, its central data structure is the list, and it pioneered garbage collection, conditionals as expressions and the read-eval-print loop. Lisp became a family rather than a single language: Common Lisp, Emacs Lisp, Scheme, Racket and Clojure are all relatives.
In 1975, Gerald Jay Sussman and Guy L. Steele Jr. at the MIT Artificial Intelligence Laboratory wanted to understand Carl Hewitt's actor model of computation. They wrote a tiny Lisp interpreter to experiment with it and discovered that actors, as they had implemented them, were essentially the same thing as closures: procedures that remember the variables around them. That interpreter, described in an MIT AI Memo in December 1975, was Scheme. A series of follow-up memos, now called the Lambda Papers, showed that lexically scoped procedures and tail calls could express loops, jumps, actors and much more.
The language was then defined by a series of community reports:
| Report | Year | Notes |
|---|---|---|
| Revised Report (RRS) | 1978 | the first full description |
| R2RS, R3RS, R4RS | 1985 to 1991 | refinement; an IEEE standard (1178) followed in 1990 |
| R5RS | 1998 | added hygienic macros; the long-time baseline |
| R6RS | 2007 | a much larger language with a module system; controversial in the community |
| R7RS-small | 2013 | a return to minimalism, with libraries; the current standard |
| R7RS-large | in progress | a large library-oriented language built on R7RS-small |
Scheme's influence on teaching came largely through one book: Structure and Interpretation of Computer Programs (SICP), by Harold Abelson and Gerald Jay Sussman with Julie Sussman (1985; second edition 1996). It was the text of MIT's introductory computer science course for more than two decades and was adopted by universities around the world. Lesson 8 returns to SICP and to today's implementations.
This course follows R7RS-small. Its programs are portable: they run on any conforming implementation. We run them with Chibi-Scheme 0.12, a small, careful implementation written by Alex Shinn, who also chaired the R7RS-small working group.
Implementations, libraries and running a program
Definition— Implementation
A program that runs Scheme code: an interpreter, a compiler, or both. Scheme is a standard with many implementations, not a single product. Popular ones include Racket, Chez Scheme, GNU Guile, CHICKEN, Gauche, Gambit, MIT/GNU Scheme and Chibi-Scheme. They share the standard core and differ in speed, libraries and extensions.
Definition— Library
A named collection of definitions. R7RS programs begin with an import declaration listing the libraries they use, such as (scheme base) for the core language and (scheme write) for output. A conforming implementation provides all the standard libraries.
To install Chibi-Scheme, build it from its repository with make and sudo make install (the README covers the details), or install the chibi-scheme package from your system's package manager where one exists. Then:
chibi-scheme -V # print the version
chibi-scheme main.scm # run a program
chibi-scheme # start the REPL; Ctrl-D to quitThere is no official online playground. If you already have another R7RS implementation installed, such as Gauche or Guile 3, the programs in this course should run there too; get.scheme.org lists the options.
The standard libraries you will use most:
| Library | Provides |
|---|---|
(scheme base) | the core: define, lambda, if, arithmetic, lists, strings, vectors, records, exceptions |
(scheme write) | display and write |
(scheme char) | character tests and case conversion, such as char-upcase and string-upcase |
(scheme inexact) | sqrt, exp, log, sin and other floating-point functions |
(scheme cxr) | caddr, cdddr and the other deep list accessors |
(scheme lazy) | delay, force and lazy streams |
First programs
Hello, world
(import (scheme base) (scheme write))
(display "Hello, world!")
(newline)
(display "Hujambo, dunia! Olá, mundo! こんにちは、世界!")
(newline)Hello, world!
Hujambo, dunia! Olá, mundo! こんにちは、世界!The first line imports two libraries. Each later line is an S-expression (short for "symbolic expression"): either an atom such as a number, string or name, or a parenthesised list of S-expressions. (display "Hello, world!") is a list of two elements, the name display and a string; because it is a list, Scheme treats it as a procedure call. display prints a value for humans, and newline ends the line. Scheme strings are Unicode, so Swahili, Portuguese and Japanese print as written.
Numbers: exact and inexact
Scheme takes numbers more seriously than most languages. It distinguishes exact numbers (integers of any size and fractions, computed without error) from inexact ones (floating-point approximations).
(import (scheme base) (scheme write) (scheme inexact))
(define (show first . rest)
(write first)
(for-each (lambda (x) (display " ") (write x)) rest)
(newline))
(show (+ 1 2 3 4) (* 2 (+ 3 4)) (- 10 4 3) (- 5))
(show (/ 10 4) (/ 10.0 4) (/ 9 3))
(show (quotient 17 5) (remainder 17 5) (modulo -7 3))
(show (expt 2 100))
(show (exact? 1/3) (inexact? 0.5) (exact 2.5) (inexact 1/3))
(show (< 1 2 3) (< 1 3 2) (= 1 1.0) (max 3 9 4) (max 3 9.0))
(show (sqrt 16) (sqrt 2) (exact-integer? (sqrt 16)))10 14 3 -5
5/2 2.5 3
3 2 2
1267650600228229401496703205376
#t #t 5/2 0.3333333333333333
#t #f #t 9 9.0
4 1.4142135623730951 #tThe show helper at the top prints several values on one line; read it for its shape now; lessons 2 and 5 explain every part.
- Operators come first and most accept any number of arguments.
(- 5)with one argument negates. - Dividing exact integers gives an exact rational,
5/2. Any inexact argument makes the result inexact. quotientandremaindertruncate toward zero;modulotakes the sign of the divisor, so(modulo -7 3)is 2.- Exact integers have no size limit:
(expt 2 100)is computed exactly. exactandinexactconvert between the two kinds. (Older code uses the R5RS namesinexact->exactandexact->inexact.)=compares numbers by value, so(= 1 1.0)is true. Note that an inexact argument is "contagious":(max 3 9.0)is9.0.sqrtlives in(scheme inexact). Where it can, it returns an exact result for an exact perfect square.- Booleans are written
#tand#f.
display versus write
(import (scheme base) (scheme write))
(write "a string") (display " | ") (display "a string") (newline)
(write #\a) (display " | ") (display #\a) (newline)
(write 'symbol) (display " | ") (write #t) (display " ") (write #f) (newline)
(write '(1 "two" #\3 four)) (newline)
(write (list 1 (+ 1 1) "three")) (newline)
(write (string-append "Sch" "eme")) (newline)
(write (string-length "lambda")) (newline)
(write (if (> 3 2) 'yes 'no)) (newline)"a string" | a string
#\a | a
symbol | #t #f
(1 "two" #\3 four)
(1 2 "three")
"Scheme"
6
yeswrite prints a value the way you would type it in a program: strings in quotes, characters as #\a. display prints for people. Use write when debugging, so you can tell the string "6" from the number 6.
Two new pieces of syntax appear here. 'symbol and '(1 "two" #\3 four) are quoted: the quote mark tells Scheme "this is data, do not evaluate it". A symbol such as four or yes is a name used as a value; lesson 4 is devoted to symbols and quotation. And if chooses between two expressions, returning the value of the one it picks.
How Scheme evaluates an expression
Every Scheme program is a sequence of expressions, and running it means evaluating them. The rules are few:
- Self-evaluating values (numbers, strings, characters, booleans) evaluate to themselves.
- A variable (a name such as
displayorprice) evaluates to the value it is bound to. An unbound name is an error. - A procedure call
(operator operand ...)is evaluated by evaluating the operator and all the operands, then applying the procedure that the operator produced to the argument values. - A special form is a list that begins with a keyword such as
define,if,lambda,quote,letorcond. Each special form has its own rule about which parts are evaluated and when.(if test a b)evaluatestestand then only one ofaandb;(quote x)does not evaluatexat all.
Example— Evaluating by hand
Evaluate (* (+ 2 3) (- 10 (/ 12 4))).
- It is a call. The operator
*evaluates to the multiplication procedure. - First operand:
(+ 2 3)is a call; it evaluates to 5. - Second operand:
(- 10 (/ 12 4))is a call. Its operands are 10 and(/ 12 4), which is 3, so it evaluates to 7. - Apply multiplication to 5 and 7: the result is 35.
One detail surprises people coming from other languages: the R7RS standard does not specify the order in which a procedure call's operands are evaluated. An implementation may evaluate them left to right, right to left, or in any order it likes. For pure expressions such as arithmetic this makes no difference at all. It matters only when operands have side effects, such as (list (read-line) (read-line)), and the Scheme answer is: if order matters, make it explicit with let* or begin (lesson 2). Leaving it unspecified gives compilers freedom to optimise.
The REPL
Run chibi-scheme with no file to get an interactive prompt. Each expression you type is read, evaluated, and its value printed:
$ chibi-scheme
> (+ 1 2)
3
> (define price 12.5)
> (* price 4)
50.0
> (/ 1 3)
1/3define gives a name to a value and prints nothing. Typing (1 2 3) produces an error mentioning a "non procedure application", because by rule 3 the list is a call and the number 1 is not a procedure. Scheme programmers use the REPL to try out each procedure as they write it; most editors (Emacs with Geiser, VS Code extensions, DrRacket for Racket) can send code from a file to a running REPL.
Common first-day mistakes
Misconception
Forgetting the imports. An R7RS program that calls display without (import (scheme write)) fails with "undefined variable: display". Chibi-Scheme helpfully lists the libraries that export a missing name. The REPL pre-loads the whole standard, which is why the same code may work interactively but not in a file.
Misconception
Treating the empty list as false. In Scheme exactly one value is false: #f. The empty list '(), the number 0 and the empty string are all true. (if '() 'yes 'no) gives yes. (Some older Lisps treated the empty list as false, and Clojure treats nil as false, so this trips up people who know them.)
Misconception
Expecting (/ 1 3) to be 0 or 0.333. With exact integers Scheme keeps the exact answer, 1/3. Use quotient for whole-number division and inexact (or an inexact operand such as 1.0) for a decimal approximation.
Misconception
Relying on operand evaluation order. (+ (begin (display "a") 1) (begin (display "b") 2)) may print ab or ba depending on the implementation. Write side effects in sequence explicitly.
Exercises
1. First steps: the Lisp family and Scheme's minimalism
Warm-upComputationalWhat value does this expression have?
(* (+ 2 3) (- 10 (/ 12 4)))
2. First steps: the Lisp family and Scheme's minimalism
Warm-upComputationalWhat does (write (/ 6 4)) print?
3. First steps: the Lisp family and Scheme's minimalism
Warm-upHumanWhich of these values counts as false in a Scheme if?
4. First steps: the Lisp family and Scheme's minimalism
CoreComputationalWhat does this print? Type the line exactly.
(import (scheme base) (scheme write))
(write "hi") (display "hi") (newline)
5. First steps: the Lisp family and Scheme's minimalism
CoreComputationalWhat is the value of (remainder -7 3)?
6. First steps: the Lisp family and Scheme's minimalism
CoreComputationalWhat does (write (list (exact 0.5) (inexact 3/4))) print?
7. First steps: the Lisp family and Scheme's minimalism
Warm-upHumanA program file contains only (import (scheme base)) followed by (display "hello"). Running it with chibi-scheme fails with "undefined variable: display". Why?
8. First steps: the Lisp family and Scheme's minimalism
Warm-upHumanWhich Scheme standard does this course follow, and when was it completed?
Further reading and resources
- R7RS home pageThe current standard and links to its documents.
- R7RS-small, errata-corrected edition (HTML)Read sections 1 and 2 for the overview and lexical conventions.
- The Lambda PapersSussman and Steele's original MIT AI Memos, including the 1975 memo that introduced Scheme.
- Scheme implementationsCurrent implementations and the standards they support.
- Chibi-SchemeSource code and build instructions for the implementation used in this course.