Sketchy LISP

An Introduction to Functional Programming in Scheme

Preface

A lot has happened since the release of the previous edition of Sketchy LISP. The Six'th Revised Report on the Algorithmic Language Scheme (R⁶RS) was ratified and Scheme is no longer the language it used to be.

This edition is dedicated to the principle that made Scheme a language that was esteemed by researchers, educators, and creative coders all around the world:

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.
-- RⁿRS introduction

Unfortunately this principle was abandoned in the R⁶RS process. I created this edition in the hope that enough people will stay interested in the small and beautiful language that Scheme used to be, so the R⁵RS will remain a de-facto standard.

After publishing the second edition of Sketchy LISP a lot of people mailed me with really good ideas on how to improve the book. I considered all of them and implemented most of them:

This edition uses a more consistent style in the examples, which is particularly important to beginners. A style guide was added to the appendix.

A new chapter was added that illustrates what real-world Scheme code looks like by discussing a more complex program in great detail.

Some subtle flaws in the code were fixed. In particular the case syntax of chapter 3 now works in exactly the same way as the actual Scheme syntax.

Have fun reading the new edition!

Nils M Holm, August 2008

Acknowledgements

Thanks to all the people who pointed out subtle flaws in the code, suggested improvements, and proposed additions.

Preface to the Second Edition

This is the revised and extended second edition of Sketchy LISP. This edition discusses the Scheme language in much more general terms and makes fewer references to an actual implementation. The terminology is much more schemy, for example functions are called procedures now and pseudo functions are explained in terms of syntax transformation.

This edition adds various topics that were not covered in the previous edition. The section about Scheme syntax has been extended and now covers macros, there is a new section about quasiquotation, and there are two additional appendices containing a table of example programs and brief summary of all Scheme functions discussed in the book.

Overall, the book has been made more general. All references to procedures that were part of a specific implementation have been removed. For example, letrec is explained in terms of let and set! now rather than introducing an implementation-dependent model.

Finally, the prose was revised, some typos were removed, and the text was streamlined for easier reading. I hope that you enjoy reading this new edition!

Nils M Holm, May 2007

Acknowledgements

Thanks to Diana Jeschag for catching some typos that slipped past me.

Preface to the First Edition

This book presents an overview of the Scheme programming language with strong emphasis on functional programming. Language elements and programming techniques are explained by means of simple examples which are used to form more complex programs.

Functional programming is an approach that focuses on the evaluation of expressions. Programs are formed by combining functions. Most functions are free of side effects which allows to examine programs formally and prove properties of algorithms.

The first chapter of this book introduces basic concepts such as definitions, conditional evaluation, recursion, procedures, and elementary data types.

While the second chapter continues this tour, it puts emphasis on more complex programs by introducing problems of varying complexity and then outlining the way to their solution step by step.

The last chapter takes up some lose ends and briefly introduces continuations, one of the more advanced features of Scheme. It also demonstrates how Scheme can be viewed as a formal system by constructing a Y combinator.

To make best use of this book, experimenting with the given examples is strongly recommended. See the appendix for download URLs and a brief introduction to the program development cycle.

The Scheme language achieves what only few languages have managed before: to bring fun back to programming. Its simple syntax, clean semantics, and powerful functions open the door to a fresh perspective on program design. Programming in Scheme is fun, and this book is an attempt to share some of that fun.

Nils M Holm, Feb. 2006

Acknowledgements

Thanks to Diana Jeschag for proof reading, to Al Petrofsky for explaining some of the more subtle details of binding constructs and continuations, and to Jens Axel Søgaard, Anton van Straaten, and other regulars of the comp.lang.scheme newsgroup for helping me to get used to the concept of continuations.