Scheme and SICP

Abstract

In 1975 Gerald Jay Sussman and his student Guy Lewis Steele Jr. at the MIT Artificial Intelligence Laboratory wrote a small Lisp interpreter to understand Carl Hewitt’s actor model, and found that what they had built was a complete, very small programming language. They called it Scheme. A series of MIT AI Memos from 1975 to 1979, later called the Lambda Papers, showed that lexical closures, tail calls and continuations could carry the whole of a language and still compile efficiently. From 1980 Sussman and Harold Abelson taught MIT’s introductory computer science course in Scheme, and their textbook, Structure and Interpretation of Computer Programs (1985), became the “Wizard Book” of hacker culture. MIT retired the course in 2007.

Cover of the second edition of Structure and Interpretation of Computer Programs*, the “Wizard Book.” Image: Harold Abelson and Gerald Jay Sussman with Julie Sussman, MIT Press, CC BY-SA 4.0, via Wikimedia Commons.*

Actors in a Lisp

In the early 1970s the MIT AI Lab was a laboratory for languages as much as for intelligence. Sussman had worked on Micro-Planner (1971) with Eugene Charniak and Terry Winograd, and on Conniver (1972) with Drew McDermott. In November 1972 Carl Hewitt and his students introduced the actor model, in which a computation is a society of independent agents that send each other messages (see Erlang and the Actor Model). To understand the model, Sussman and Steele decided to build a small implementation of it in Maclisp, on the lab’s PDP-10.

They modelled actors on top of the lambda calculus, the formal system behind John McCarthy’s LISP. Their system was called Schemer, after Planner and Conniver, and was cut to Scheme because the lab’s ITS operating system allowed file names of at most six characters.

When the interpreter worked, they noticed that the code for creating an actor and the code for creating a function closure were the same, and so were the code for sending a message to an actor and the code for calling a function. They removed the duplicate. What was left was a small Lisp with lexical scope, in which a function remembers the variables of the place where it was defined, and in which control could be passed on as a continuation instead of returning. Looking back in 1998, the two wrote that they had been “actually trying to build something complicated” and had discovered, by accident, that they had designed something much simpler that met all their goals.

The Lambda Papers

Steele and Sussman described the language in an AI Memo, SCHEME: An Interpreter for Extended Lambda Calculus (AIM-349, December 1975). Over the next four years they wrote a series of further memos that came to be called the Lambda Papers:

LAMBDA: The Ultimate Imperative (AIM-353, March 1976) showed that loops, assignments, gotos and other imperative constructs could be expressed as calls to lambda expressions.
LAMBDA: The Ultimate Declarative (AIM-379, November 1976) worked out the same idea for the structure of programs and the compilation of procedure calls.
Debunking the “Expensive Procedure Call” Myth, or, Procedure Call Implementations Considered Harmful, or, LAMBDA: The Ultimate GOTO (AIM-443, October 1977) argued that a procedure call in tail position is a jump that passes arguments, and need not cost more than a goto.
The Revised Report on SCHEME (AIM-452, January 1978) and The Art of the Interpreter (AIM-453, May 1978).
RABBIT: A Compiler for SCHEME (AI-TR-474, May 1978), Steele’s compiler that turned the whole program into continuation-passing style and then into efficient code.
Design of LISP-based Processors, or SCHEME: A Dielectric LISP, or Finite Memories Considered Harmful, or LAMBDA: The Ultimate Opcode (AIM-514, March 1979), a design for Scheme in hardware.

The titles were jokes, the arguments were serious. At the time, procedure calls were widely thought too slow to use freely, and programmers wrote loops and gotos to avoid them. Steele showed that a compiler could treat a call in tail position as a jump, so that a recursive program could run in constant stack space. The Scheme reports later made this a requirement: a conforming implementation must handle tail calls properly.

Scheme was the first Lisp dialect to adopt lexical scope, and that choice had the widest reach. Steele went on to write Common Lisp the Language (1984), the reference for the next large Lisp, and to co-author the original Java Language Specification. When Brendan Eich wrote JavaScript at Netscape in 1995, he had wanted to put Scheme in the browser, and the closures and first-class functions in JavaScript came from there (see Brendan Eich and JavaScript).

Six Point Double-Oh-One

Abelson recalled that MIT’s electrical engineering and computer science department redesigned its core curriculum around 1978 or 1979. Until then the introductory programming subject, 6.031, had taught ALGOL and then Lisp. Abelson and Sussman were allowed to build a new course, 6.001. “We basically did it without telling people what we were doing, which is why they let us,” Abelson said in 2011. They taught it in its final form from the fall of 1980, and from 1980 to 2007 it was one of the four subjects required of every EECS student at MIT.

They chose Scheme because it had almost no syntax. Students did not spend the first weeks on semicolons and brackets, and the same small language could show functional programming, objects built from closures, and logic programming. “Anything else, the mechanics of the languages just get in the way of the ideas,” Abelson said. The course was not about Scheme. In its second half students wrote a Scheme interpreter in Scheme, the metacircular evaluator, then a register machine simulator and a compiler, so that by the end they had seen every layer between a program and the hardware it ran on.

The Wizard Book

The course notes became a textbook, Structure and Interpretation of Computer Programs, by Harold Abelson and Gerald Jay Sussman with Julie Sussman, published by MIT Press in 1985, with a second edition in 1996. Alan Perlis wrote the foreword (see Alan Perlis and the Epigrams on Programming). The authors’ preface contained the sentence most often quoted from it: “programs must be written for people to read, and only incidentally for machines to execute.”

The cover showed a robed wizard holding up an orb labelled “Eval” and “Apply,” the two procedures that call each other at the core of the interpreter, facing a woman across a radiant lambda. Readers called it the Wizard Book, and it was adopted by universities in many countries; a German translation, Struktur und Interpretation von Computerprogrammen, appeared with Springer in 1991.

In July 1986 Abelson and Sussman gave the course as twenty videotaped lectures for Hewlett-Packard employees, produced by Hewlett-Packard Television. The tapes were used in corporate training and at universities, and MIT later released them under a Creative Commons licence. Later the second edition itself was put online free of charge and under a Creative Commons licence.

Not everyone liked the approach. In March 1987 Philip Wadler published “A critique of Abelson and Sussman, or Why calculating is better than scheming” in SIGPLAN Notices, arguing that a language with pattern matching, a type system and lazy evaluation, such as the Miranda he used, made programs easier to reason about (see Haskell and Pure Functional Programming). Matthias Felleisen, Robert Findler, Matthew Flatt and Shriram Krishnamurthi argued from inside the Scheme community that the book lacked an explicit method for designing programs and relied on mathematical and engineering knowledge that beginners did not have; their textbook How to Design Programs (2001) and the PLT Scheme environment were an answer, and PLT Scheme was renamed Racket on 7 June 2010.

Standards

Scheme was defined by a sequence of reports, each written by a committee and named after the previous one: the Revised Report (1978), the Revised Revised Report or R2RS, then R3RS (1986) and R4RS (1991). The IEEE published a formal standard, IEEE 1178, in 1990. R5RS (1998) was about fifty pages long, and “50-page purists” became a recognised faction; it became the most widely implemented version. R6RS (2007) added a module system and a large standard library. It was ratified by 67 votes, 65.7 percent of those voting, against a 60 percent threshold, and split the community. In August 2009 the steering committee proposed dividing the next report in two: R7RS “small” (2013), close to R5RS, and an R7RS “large” that is not finished.

Dead End: Scheme as the First Language

For about twenty years Scheme was the first language of computer science students at MIT, Berkeley, many European universities and the schools that taught from How to Design Programs. That ended in the 2000s. 6.001 was taught for the last time in the fall of 2007, with Sussman giving the final lecture, and its successor, 6.01, used Python and small robots. Berkeley moved its SICP-based CS 61A to Python in 2011, with John DeNero’s adaptation of the book.

Abelson said the language was the least important part of the change. The department had decided that the first course should be a broad survey of electrical engineering and computer science, not a deep course on programming. “We could have done it in Scheme and I sort of wish we had. And for random reasons we didn’t.” Sussman, asked at the International Lisp Conference in March 2009 why MIT had dropped Scheme, said, in Andy Wingo’s notes of the answer, that “engineering in 1980 was not what it was in the mid-90s or in 2000.” In 1980 a programmer could understand a system down to the bottom and compose it from small parts known to work. Now, he said, “you have to do basic science on your libraries to see how they work,” and Python was chosen because “it probably just had a library already implemented for the robotics interface, that was all.”

The book outlived the course. In April 2022 MIT Press published a JavaScript edition, adapted by Martin Henz and Tobias Wrigstad with Julie Sussman, which kept the structure of the second edition, including the evaluator and the compiler, in a language students already knew.