Preface

The best laid schemes o' mice an' men

Gang aft a-gley.

Robert Burns, ``To a Mouse''

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.

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.

We resolved 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 computer science.

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 Vassar College. 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.

Key Differences From Conventional Approaches

There are six ways in which this book differs from conventional introductions.

Instructional Support

The book is only a part of the comprehensive package we have developed to support the course. This package includes:

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 systems. 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.

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 the reverse.

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.

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: 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.