Scheme and the Art of Programming

[Pete Harlan <silver!harlan@iuvax.cs.indiana.edu>]

manis@cs.ubc.ca (Vincent Manis) writes:

>The classical way to introduce computer science via Scheme is Abelson
>and Sussman's `Structure and Interpretation of Computer Programs',
>published by MIT Press/McGraw-Hill. Paradoxically, this book is not
>about Scheme, and hardly mentions it. Instead, the book concentrates
>upon fundamental principles of computer science, paradigms of program
>design, and the structures of various evaluators, including interpreters
>and compilers for Scheme. The goal isn't so much to have the student be
>a good Scheme programmer, as to be able to understand the principles
>behind programming and computers.

And now of course there is also Springer and Friedman's _Scheme and
the Art of Programming_, also published by MIT Press/McGraw-Hill.  The
difference between these two excellent books is best summed up I think
in the difference between their titles.  For a study of programming
language issues I would prefer Abelson and Sussman, and for learning
the elements of programming I would prefer Springer and Friedman.

The early sections of the book provide a beautiful development of
recursion/iteration and data abstraction.  This is followed by an
amazing two chapters on higher-order procedures that completes the
development of "how to write programs".  In this way the first ~250
pages of the book prepare the student for the topics in the final ~350
pages.

Part 3, Managing State, begins with a functional view of vectors, and
then introduces the reader to mutation by showing the efficiency
gained through mutable vectors vs. functional ones.  The two views of
vectors are then compared throughout the discussion of sorting
techniques.

The following section on mutation presents not only the use of
mutation the way it is typically used in Scheme (eg, memoization), but
also includes a section on imperative-style programming.  The chapter
concludes with a lovely set of exercises that has the student
implement Turing machines as a controller driven by an external
state-transition table.  One could hardly imagine a more fitting
conclusion for a chapter on mutation!

Having given the reader the ability to mutate data, the book then
presents a controllable use for such ability with object-oriented
programming.  Objects are then used to introduce the basic abstract
data structures (accumulators, stacks, queues, buckets and hash
tables) while showing how they incorporate elements of each other.
This is followed by an extended OOP example, a gas-station simulation
that finishes the section on managing state.  To be fair, I must say I
thought this simulation got a little bogged down -- spread over so
many pages, it requires a diligent reader to follow the discussion.

A section on syntactic extension comes next, catering to both the
traditional "macro" declaration and extend-syntax.  Having gained the
power to declare special forms, the book defines streams, developing
recursive data, and ends with an extended example for reformatting a
text file using filters.

"Control" is the title of Part 5, the last section of the book.  This
is a thorough development of the nature of run-time control, and the
capturing of run-time control through the use of call/cc.  The first
chapter develops call/cc, and the second chapter uses it to implement
coroutines.  While the development is careful and the examples lucid,
some of the exercises here are treacherous indeed!

Overall, the book is an excellent introduction to computer programming
and computer science, with excursions into specific areas to provide
applications of what is being learned.  Having read it cover-to-cover,
I couldn't recommend it more highly as a first computer-science text.

Pete Harlan
Indiana University
harlan@silver.ucs.indiana.edu

Disclaimer: I am being as objective as I can about a book I fell in
love with while reading.  The authors of the book are on faculty here,
but should you doubt my review of the book, _read_ it!  I learned
Scheme from _Structure and Interpretation of Computer Programs_, and
have similar accolades for it as a book about interpretation models.
Where the two books overlap, it is a tossup -- Abelson/Sussman favors
the advanced programmer, while Springer/Friedman favors the
development of technique.