The best laid schemes o' mice an' men
Students need an introductory course in computer science
that exposes them to all of computer science. Computer science is not
just about programming techniques. It rests on deep ideas and the
nature of computation. We want students to understand these deep
ideas, as well as grasp the practicality of computation and
experience the pleasure of computing.
Robert Burns, ``To a Mouse''
We wrote The Schematics of Computation for one reason---we
wanted a book that presents the
fundamental ideas of computer science in a way that
students can understand. Introductory books in other fields such as
physics introduce the areas of the field (mechanics,
electricity and magnetism, and optics), while introductory computer
science books often have chapters on how to use two-dimensional arrays.
to write a book that not only gives students essential programming
skills, but also provides a vision of what computer science is about.
We want to reach those individuals who are already committed to
computer science, as well as those who plan to take computer science
courses as part of a general education. We hope our enthusiasm for
the field will encourage students to pursue advanced studies in
History and Objectives
This book had its genesis in a 1988 decision of the Department of
Computer Science at the University of British Columbia to revitalize
its introductory courses. A Scheme-based approach
was adopted, and one of the authors (Little) set about teaching a
prototype two-course sequence in 1989--90, using Abelson and
Sussman's Structure and Interpretation of Computer Programs.
We decided that we wanted a broader
coverage of CS than Abelson and Sussman offers.
Since 1990, drafts of this book have been used at UBC, Langara,
University College of the Okanagan, and the University College of the
Cariboo, all in British Columbia, as well as at the University of
Saskatchewan in Saskatoon, Saskatchewan. More recently, the book has
been adopted by the University of Kansas and
Our model has been heavily influenced by the interim report
of the ACM Task Force on the Core of Computer Science (CACM, January,
1989) and also by the ACM Curriculum '91 document.
The ACM Task Force Report identifies a number of areas in computer
science, and develops three modes in which each of these areas
can be studied, roughly corresponding to program design and
implementation, empirical experimentation, and theoretical
underpinnings. We have found this framework to be a useful way of
designing a course that is effective in the classroom.
As we began planning this book, we identified several
goals it had to satisfy.
- Whereas most texts give primary emphasis to programming
skills, we give substantial weight to the analysis of
programs and development of conceptual frameworks. We do not wish to
shortchange the skills component of an introductory course. In fact,
employers of students who have studied this material have told us that
the students are stronger programmers than those who have taken
the conventional Pascal course. However, we also want students to
learn how to read programs and understand critical issues such as
- The introductory course sequence offers a chance to recruit
students into computer science. It should therefore offer a view of
the questions a computer scientist studies, and the modes of inquiry
that she or he would use.
Even for students who plan no further studies in the field, we
believe that a broad introduction to the ideas of computer science
provides a strong foundation for acquiring further computing skills, as
well as skills in other areas.
- Although it would be impossible to cover all of the areas
identified by the ACM Task Force, we have given attention to
important areas of computer science that are not studied in the
traditional CS1/CS2 sequence. Databases, artificial intelligence,
and logic programming are the most obvious examples.
- We wanted to show that a small number of powerful ideas
underlies much of computer science, just as concepts such as
``force'' and ``energy'' underlie physics. We present a model of
computation that can be used not only for Scheme, but for almost all
- We wanted a presentation that was accessible to the average
university or college student, requiring only Grade 12 mathematics.
Key Differences From Conventional Approaches
There are six ways in which this book differs from conventional
- Features if necessary, but not necessarily features
Our philosophy is deliberately minimalist---we avoid
introducing new features or concepts until they are absolutely
necessary. This approach applies to our presentation of both the
programming language and the applications.
- Theory and Practice
We strongly believe in balancing theory and practice, and only
presenting theory that is directly useful in solving problems.
Each theoretical topic grows out of a practical problem that is being
- Experiential Learning
We emphasize learning by doing. This emphasis can be seen in
the hundreds of exercises included in the book. These exercises have
one major purpose---students should not read more than a page or two
without being asked to apply what has been learned. The Laboratory
Manual consists of a set of labs that ask students to apply a concept
that has been covered in class.
- System Prototypes
We follow a schematic approach by presenting prototypes of
real, working software systems. It is not feasible for students to
study a real relational database system or inference engine in
an introductory course. But it is possible for students to
understand a simplified database or inference engine. Our goal is not
to study all of the complexity of the ``real'' versions of these
systems. Instead, we want students to understand what such a system
does, and the basic principles that underlie its implementation.
- Broad View of Field
We present a rich, broad view of computer science. An
introductory text is not a closed universe, but a starting-point. Sidebars
present relevant applications, software tools, theoretical questions, and
- Case Studies
The Case Studies located at the end of the chapters
present extended examples of how software is developed and how it can
be used to solve interesting, practical problems. Case Studies
provide additional programming examples and demonstrate how the
techniques covered in chapters have further application. We have
chosen applications across a wide variety of endeavors including
simulation, airline route planning, personal schedule planning, and
The book is only a part of the comprehensive package we
have developed to support the course. This package includes:
- A Laboratory Manual with approximately thirty different
lab assignments keyed to the text, along with sidebars on such
practical topics as debugging code.
- An Instructor's Guide that describes the pedagogy for
each section of the book, as well as providing a number of resources
such as a detailed Scheme manual and a tutorial on C++ for Schemers
that can be distributed to students.
- A Software Package that includes a Microsoft
Windows-based Scheme system, code to adapt other common Scheme
systems to support this book, and all of the programs studied or used
in the text or lab manual. The Software Package is provided in disk
form with the Instructor's Guide, or it can be obtained in electronic
form from the
Internet Getting the software.
The Internet version is preferred, because it may
incorporate bug fixes and additions which have not yet reached the
Choice of Programming Language
Almost nothing can arouse more controversy than the
choice of introductory
programming language (except perhaps which is the best text editor).
Our approach is soundly based upon lambda-calculus
models that have been realized in many languages, and provide simple,
consistent semantics. We have chosen to use Scheme, a lexically-scoped
dialect of Lisp. Our choice was governed by several factors:
Even though Abelson and Sussman's Structure and Interpretation
of Computer Programs influenced many of the ideas we explore, we
certainly did not feel bound to use Scheme. Most other languages are
bound too tightly to a single computational paradigm to be suitable
for some of the areas we proposed to explore. In particular, our
study of evaluators would have been seriously complicated if we had
used a language with a great deal of syntax. The bottom line is that
Scheme is a simple language that can be used in many interesting
ways, and also allows us to produce sophisticated, complex software
What about using a functional language?
Most functional languages
enforce a functional paradigm everywhere, whether or not it is
appropriate. We agree that a database system can be modeled in a
purely functional way, but don't agree that an introductory student
will find such a model convincing. One outstanding exception,
supporting all the paradigms we study in this book, is ML. The first
six chapters of our book would suffer almost no changes if ML were
used instead of Scheme. ML's syntax would most definitely complicate
our discussion of evaluators.
Most functional languages, including ML, have elaborate type
systems. However useful these type systems may be to the experienced
programmer, they are substantial barriers to the introductory
student, and hence destroy the concept of a simple underlying model.
- minimal syntax to make learning fairly easy
- procedures as first-class objects
- support for a wide variety of programming paradigms including
functional, imperative, object-oriented, and logic programming
- list processing capabilities (i.e., garbage collection)
- reasonably standardized implementations, especially for MS-DOS,
Macintosh, and UNIX platforms
What about using an object-oriented language? We renew our objections
to single-paradigm languages. More importantly, we want students to
see that the language we study is well-founded (in a logic sense). It
is easier to understand objects in terms of procedures and state than
What about using an imperative, more ``conventional'' language like
Pascal, Modula-2, or C++ as our teaching vehicle? Everything we do in
this book could be done in one of these languages, though perhaps
with great difficulty. Procedures as first-class citizens, and garbage
collection make code much more perspicuous. We do not deny the importance of
these languages (especially C++) for building sophisticated
applications. However, we think that learning Scheme helps a student
learn one of these languages.
We believe the ideas behind Scheme are not just academic curiosities, but are
immensely practical. Scheme and Scheme-like languages have some industrial
application. Further, many newer languages, ranging from ML and PostScript to
NewtonScript and Dylan, use concepts that Scheme elegantly demonstrates.
Scheme is already widely used as an introductory programming language.
Coverage and Topics
Although we were inspired by Abelson and Sussman's book,
we chose different
topics and a different organization. We include a sequence of topics that
makes sense to students, provides strong programming skills, and gives a
coherent picture of the field. We therefore adopted the following structure.
- Introduction to Programming (Chapters 1 through 3)
- basic data types and programming concepts
- computation as substitution
- procedures and procedural abstraction
- algorithmic complexity
- distinction between value and effect
- program organization
- data abstraction
- List Processing (Chapter 4)
- pairs and symbols
- using pair structure to represent compound values
- lists and list recursion
- State, Mutation, and Objects (Chapters 5 and 6)
- mutating existing data structure
- variables and assignment
- how the environment model explains computation
- how environments model objects
- object-oriented design
- Programming Languages (Chapter 7)
- defining the syntax and semantics of programming languages
- tree representation of programs
- interpreters and compilers
- a Scheme evaluator based upon the environment model
- Databases (Chapter 8)
- relational table model
- fundamental relational operators, select, project, and join
- implementation of a simple database system
- database analysis and design
- Algorithms (Chapter 9)
- algorithms for searching (linear search, binary search trees) and
sorting (insertion sort, Quicksort)
- stacks and queues
- application of stacks to implementing a graphics
language based upon Postscript
- Rule-Based Computing (Chapter 10)
- patterns and pattern matching
- predicate calculus
- logic programming languages
- backward and forward chaining
- Machines and Evaluators (Chapters 11 and 12)
- representation of data
- a simple computer
- programming in assembly language
- building a Scheme evaluator for a conventional machine
- introduction to operating systems
How To Use This Book
We have used this book in a number of ways at the
University of British Columbia and at Langara College. Our original
design was a two-course---CS1 and CS2---introductory sequence for
science students (not necessarily CS majors). We have found little
difference in the performance of students who have a programming
background and those who do not.
We have also used this text in a one-semester course for students who have
already taken CS1. Students in this course are primarily CS or Computer
Engineering majors. Therefore, the course can be more intensive.
This text has been used in a course for students who are
concurrently taking a conventional CS2 course. This course emphasizes the
interrelations between the Scheme-based material and the C++-based content of
the CS2 course. A similar course could be designed at the
second year level for students with CS1 and CS2.
Regardless of the course design, The Schematics of Computation contains
more material than can be covered. We have endeavored to provide a rich enough
package of materials that instructors can tailor courses to their needs. We
also want students to use this text as a reference, as well as a springboard to
further study in CS.
Therefore, the book is divided into three parts:
In a two-semester course sequence, it is reasonable to cover the material
right up to the imperative
evaluator in Chapter 12. A one-semester course can go through the first two
chapters much more quickly, and then cover Chapters 3 through 7 in depth.
From there, the instructor has a number of choices:
- Chapters 1 through 7 are an integrated sequence that covers common
programming paradigms: functional, imperative, and object-oriented.
- Chapters 8 through 10 provide an introduction to algorithms and data
structures, through applications in data bases and logic.
- Chapters 11 and 12 introduce computer hardware and
assembly-language programming, practical Scheme implementations, and
Many instructors will want to cover an additional language such
as Modula-2, Pascal, C/C++, or Turing in the
latter part of a two-course sequence.
The Instructor's Guide contains a tutorial called A
Schemer's Guide to C++, which can be distributed to students and
used to introduce C++. The first part of the tutorial can be used
with Chapter 7; the second part refers to Chapter 11.
- Proceed to Chapters 8, 9, and 10 if algorithms will be
- Proceed to Chapters 11 and 12 if machines will be emphasized.
- A hybrid approach will go through Chapter 8 very quickly, and then cover
Chapters 9 and 11 in depth, ending with the imperative evaluator in