Matthias Felleisen - How to Design Programs: An Introduction to Programming and Computing

An Introduction to Programming and Computing

Matthias Felleisen

Robert Bruce Findler

Matthew Flatt

Shriram Krishnamurthi

Third printing, 2002
2001 Massachusetts Institute of Technology

Illustrations 2000 Torrey Butzer

All rights reserved. No part of this book may be reproduced in any form by any electronic or mechanical means (including photocopying, recording, or information storage and retrieval) without permission in writing from the publisher.

Library of Congress Cataloging-in-Publication Data

How to design programs: an introduction to programming and computing / Matthias Felleisen, Robert Bruce Findler, Matthew Flatt, Shriram Krishnamurthi; chapter art by Torrey Butzer
p. cm.

Includes index.
ISBN 0-262-06218-6 (hc.: alk. paper)
1. Computer Programming. 2. Electronic data processing.

QA76.6 .H697 2001
005.12dc21

00-048169

Contents

List of Figures

Preface

Why Everyone Should Learn to Program

Design Recipes

The Choice of Scheme and DrScheme

The Parts of the Book

Acknowledgments

I Processing Simple Forms of Data

1 Students, Teachers, and Computers

2 Numbers, Expressions, Simple Programs

2.1 Numbers and Arithmetic

2.2 Variables and Programs

2.3 Word Problems

2.4 Errors

2.5 Designing Programs

3 Programs are Function Plus Variable Definitions

3.1 Composing Functions

3.2 Variable Definitions

3.3 Finger Exercises on Composing Functions

4 Conditional Expressions and Functions

4.1 Booleans and Relations

4.2 Functions that Test Conditions

4.3 Conditionals and Conditional Functions

4.4 Designing Conditional Functions

5.1 Finger Exercises with Symbols

6 Compound Data, Part 1: Structures

6.1 Structures

6.2 Extended Exercise: Drawing Simple Pictures

6.3 Structure Definitions

6.4 Data Definitions

6.5 Designing Functions for Compound Data

6.6 Extended Exercise: Moving Circles and Rectangles

6.7 Extended Exercise: Hangman

7 The Varieties of Data

7.1 Mixing and Distinguishing Data

7.2 Designing Functions for Mixed Data

7.3 Composing Functions, Revisited

7.4 Extended Exercise: Moving Shapes

7.5 Input Errors

Intermezzo 1: Syntax and Semantics

The Scheme Vocabulary

The Scheme Grammar

The Meaning of Scheme

Errors

Boolean Expressions

Variable Definitions

Structure Definitions

II Processing Arbitrarily Large Data

9 Compound Data, Part 2: Lists

9.1 Lists

9.2 Data Definitions for Lists of Arbitrary Length

9.3 Processing Lists of Arbitrary Length

9.4 Designing Functions for Self-Referential Data Definitions

9.5 More on Processing Simple Lists

10.1 Functions that Produce Lists

10.2 Lists that Contain Structures

10.3 Extended Exercise: Moving Pictures

11 Natural Numbers

11.1 Defining Natural Numbers

11.2 Processing Natural Numbers of Arbitrary Size

11.3 Extended Exercise: Creating Lists, Testing Functions

11.4 Alternative Data Definitions for Natural Numbers

11.5 More on the Nature of Natural Numbers

12 Composing Functions, Revisited Again

12.1 Designing Complex Programs

12.2 Recursive Auxiliary Functions

12.3 Generalizing Problems, Generalizing Functions

12.4 Extended Exercise: Rearranging Words

Intermezzo 2: List Abbreviations

III More on Processing Arbitrarily Large Data

14 More Self-referential Data Definitions

14.1 Structures in Structures

14.2 Extended Exercise: Binary Search Trees

14.3 Lists in Lists

14.4 Extended Exercise: Evaluating Scheme

15 Mutually Referential Data Definitions

15.1 Lists of Structures, Lists in Structures

15.2 Designing Functions for Mutually Referential Definitions

15.3 Extended Exercise: More on Web Pages

16 Development through Iterative Refinement

16.1 Data Analysis

16.2 Defining Data Classes and Refining Them

16.3 Refining Functions and Programs

17.1 Processing Two Lists Simultaneously: Case 1

17.2 Processing Two Lists Simultaneously: Case 2

17.3 Processing Two Lists Simultaneously: Case 3

17.4 Function Simplification

17.5 Designing Functions that Consume Two Complex Inputs

17.6 Exercises on Processing Two Complex Inputs

17.7 Extended Exercise: Evaluating Scheme, Part 2

17.8 Equality and Testing

Intermezzo 3: Local Definitions and Lexical Scope

Organizing Programs with local

Lexical Scope and Block Structure

IV Abstracting Designs

19 Similarities in Definitions

19.1 Similarities in Functions

19.2 Similarities in Data Definitions

20 Functions are Values

20.1 Syntax and Semantics

20.2 Contracts for Abstract and Polymorphic Functions

21 Designing Abstractions from Examples

21.1 Abstracting from Examples

21.2 Finger Exercises with Abstract List Functions

21.3 Abstraction and a Single Point of Control

21.4 Extended Exercise: Moving Pictures, Again

21.5 Note: Designing Abstractions from Templates

22 Designing Abstractions with First-Class Functions

22.1 Functions that Produce Functions

22.2 Designing Abstractions with Functions-as-Values

22.3 A First Look at Graphical User Interfaces

23.1 Sequences and Series

23.2 Arithmetic Sequences and Series

23.3 Geometric Sequences and Series

23.4 The Area Under a Function

23.5 The Slope of a Function

Intermezzo 4: Defining Functions on the Fly

V Generative Recursion

25 A New Form of Recursion

25.1 Modeling a Ball on a Table

25.2 Sorting Quickly

26 Designing Algorithms

26.1 Termination

26.2 Structural versus Generative Recursion

26.3 Making Choices

27 Variations on a Theme

27.1 Fractals

27.2 From Files to Lines, from Lists to Lists of Lists

27.3 Binary Search

27.4 Newtons Method

27.5 Extended Exercise: Gaussian Elimination

28 Algorithms that Backtrack

28.1 Traversing Graphs

28.2 Extended Exercise: Checking (on) Queens

Intermezzo 5: The Cost of Computing and Vectors

Concrete Time, Abstract Time

The Definition of on the Order of

A First Look at Vectors

30 The Loss of Knowledge

30.1 A Problem with Structural Processing

30.2 A Problem with Generative Recursion

31 Designing Accumulator-Style Functions

31.1 Recognizing the Need for an Accumulator

31.2 Accumulator-Style Functions

31.3 Transforming Functions into Accumulator-Style

32 More Uses of Accumulation

32.1 Extended Exercise: Accumulators on Trees

32.2 Extended Exercise: Missionaries and Cannibals

32.3 Extended Exercise: Board Solitaire

Intermezzo 6: The Nature of Inexact Numbers

Fixed-size Number Arithmetic