Sketchy LISP

An Introduction to Functional Programming in Scheme

Preface

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.