Ingeniero En Informática - Ia

Page iii

Simply Scheme
Introducing Computer Science
Second Edition
Brian Harvey
Matthew Wright
Foreword by Harold Abelson

Page iv

© 1999 by the Massachusetts Institute of Technology
The Scheme programs in this book are copyright © 1993 by Matthew Wright and Brian Harvey.
These programs are free software; you can redistribute them and/or modify them under the terms of the GNUGeneral
Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any
later version.
These programs are distributed in the hope that they will be useful, but WITHOUT ANY WARRANTY; without even
the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
General Public License (Appendix D of this book) for moredetails.
This book was typeset in the Baskerville typeface, using the JOVE text editor and the TEX document formatting
system, for which we thank John Baskerville (1706–75), Jonathan Payne (1964–), and Donald Knuth (1938–),
respectively.
Library of Congress Cataloging-in-Publication Data

Harvey, Brian, 1949–
Simply scheme : introducing computer science / Brian Harvey, Matthew Wright;foreword by Harold Abelson.—2nd ed.
p. cm.
Includes bibliographic references and index.
ISBN 0–262–08281–0 (hc : alk. paper)
1. Scheme (Computer programming language) 2. Computer science.
I. Wright, Matthew. II. Title.
QA76.H3475 1999
005.13'3–dc21
99-10037
CIP
Page v

CONTENTS
Foreword
Preface
One Big Idea: Symbolic Programming

xv
xvii
xviii

Lisp and Radical Computer Sciencexix

Who Should Read This Book

xxii

How to Read This Book

xxiii

To the Instructor

xxv

Lists and Sentences

xxv

Sentences and Words

xxvi

Overloading in the Text Abstraction

xxvii

Higher-Order Procedures, Lambda, and Recursion

xxviii

Mutators and Environments

xxviii

Acknowledgments
I
Introduction: Functions

xxxi
2

1
Showing off Scheme

5Talking to Scheme

5

Recovering from Typing Errors

7

Exiting Scheme

7
Page vi

More Examples

8

Example: Acronyms

8

Example: Pig Latin

10

Example: Ice Cream Choices

12

Example: Combinations from a Set

13

Example: Factorial

14

Play with the Procedures

15

2
Functions

17

Arithmetic

18

Words

19

Domain and Range

20

MoreTypes: Sentences and Booleans

21

Our Favorite Type: Functions

21

Play with It

22

Thinking about What You've Done

22

II
Composition of Functions

26

3
Expressions

29

Little People

30

Result Replacement

33

Plumbing Diagrams

33

Pitfalls

35

4
Defining Your Own Procedures

41

How to Define a Procedure

41

Special Forms

42Functions and Procedures

43

Argument Names Versus Argument Values

45

Procedure as Generalization

46

Composability

47

The Substitution Model

48

Pitfalls

51
Page vii

5
Words and Sentences

57

Selectors

59

Constructors

61

First-Class Words and Sentences

62

Pitfalls

63

6
True and False

71

Predicates

72

Using Predicates74

If Is a Special Form

76

So Are And and Or

76

Everything That Isn't False Is True

77

Decisions, Decisions, Decisions

78

If Is Composable

81

Pitfalls

82

7
Variables

89

How Little People Do Variables

90

Global and Local Variables

92

The Truth about Substitution

94

Let

94

Pitfalls

96

III
Functions as Data

100

8Higher-Order Functions

103

Every

104

A Pause for Reflection

106

Keep

107

Accumulate

108

Combining Higher-Order Functions

109

Choosing the Right Tool

110

First-Class Functions and First-Class Sentences

113

Repeated

113

Pitfalls

115
Page viii

9
Lambda

127

Procedures That Return Procedures

129

The Truth about Define

130...