SCHEME PROGRAMMING IN Springer NewYork Berlin Heidelberg Barcelona Budapest HongKong London Milan Paris Santa Clara Singapore Tokyo Mark Watson SCHEME PROGRAMMING IN SCHEME LEARN THROUGH ARTIFICIAL INTELLIGENCE PROGRAMS With 22Illustrations Springer MarkWatson 535 MarVista Drive SolanaBeach, CA92075, USA Coverillustration: Networkofgeometricshapes. StevenHuntfTheImageBank LibraryofCongressCataloginginPublicationData Watson, Mark, 1951- ProgramminginScheme:learnSchemethroughartificialintelligence programs/MarkWatson. p. cm. Includesbibliographicalreferencesandindex. ISBN-13:978-0-387-94681-8 e-ISBN-13:978-1-4612-2394-8 DOl:10.1007/978-1-4612-2394-8 1.Scheme(Computerprogramlanguage)2.Artificialintelligence. I.Title. QA76.73.S34W37 1996 005.13'3-dc20 96-10599 Printedonacid-freepaper. © 1996Springer-VerlagNewYork,Inc. Allrightsreserved.Thisworkmaynotbetranslatedorcopiedinwholeorinpartwithout thewritten permissionofthe publisher(Springer-Verlag NewYork, Inc., 175 FifthAv enue,NewYork,NY10010,USA),exceptforbriefexcerptsinconnectionwithreviewsor scholarlyanalysis.Useinconnectionwithanyformofinformationstorageandretrieval, electronicadaptation,computersoftware,orbysimilarordissimilarmethodologynow knownorhereafterdevelopedisforbidden. Theuseofgeneraldescriptivenames, tradenames,trademarks,etc.,inthispublication, even ifthe former are not especially identified, is not to be taken as a sign that such names,asunderstoodbytheTradeMarksandMerchandiseMarksAct,mayaccordingly beusedfreelybyanyone. ProductionmanagedbyFrankGanz;manufacturingsupervisedbyJoeQuatela. TypesetinTEXfrom theauthor'sfiles. 987654321 ISBN-13:978-0-387-94681-8Springer-VerlagNewYorkBerlinHeidelberg SPIN 10524195 CONTENTS Preface ix Acknowledgments Xl CHAPTER 1 Introduction 1 CHAPTER 2 Tutorial Introduction to Scheme 3 2.1 Lists 3 2.1.1 Evaluating expressions 4 2.1.2 Listdata structures 4 2.1.3 Built-in functions for lists 7 2.2 Vectors 9 2.3 Logical tests 10 2.3.1 Testing for equality 10 2.3.2 Arithmetictests 11 2.3.3 Conditionaltests 11 2.4 Defining local variables 12 2.5 Defining functions 14 2.5.1 Recursion 17 2.6 Miscellaneous Scheme utility functions 22 CHAPTER 3 Designing for Reuse 25 3.1 Modularity 26 3.2 Cohesion in function libraries 27 3.3 Loose couplingbetween library modules 27 3.4 Example: a library for genetic algorithms 28 3.4.1 Requirements 29 3.4.2 Thedesign process 29 3.4.3 An implementation 33 3.5 Example application: allocating resources for sales and marketing 41 3.5.1 Problem description 41 3.5.2 Method for allocating resources 41 3.5.3 Program for allocating resources 41 vi CONTENTS CHAPTER 4 Writing PortableScheme Code 45 4.1 Designing for portability 46 4.2 Isolating operating system and graphics code 46 4.3 Aportablegraphicslibrary 47 4.4 Examplelibrary for displayinggraphstructures 52 4.5 Example: plotting Mandelbrot sets 62 4.6 Example: plotting chaoticpopulationgrowth 65 CHAPTER 5 An Iterative Approach to Analysis, Design, and Implementation 71 5.1 Preliminaryanalysis, design, and implementation ofa networksearchprogram 71 5.2 Evaluationofthefirst implementation ofthe networksearchprogram 80 5.3 Improvingouranalysis, design, and implementation 80 CHAPTER 6 Neural NetworkLibrary 89 6.1 Requirements for a neural networklibrary 89 6.2 Design ofa neural networklibrary 90 6.2.1 Designing a separate libraryfor two-dimensional arrays 92 6.2.2 Algorithm for supervised learning in neural networks 92 6.3 Implementation ofa neural networklibrary 94 6.3.1 Two-dimensional arraylibrary 95 6.3.2 Neural networklibrary 99 6.4 Example application: characterrecognition 128 CHAPTER 7 Complex DataStructures 141 7.1 Using Scheme effectivelyto prototype and testcomplexdata structures 141 7.2 Example application: naturallanguage processing 142 7.2.1 Analysis 142 7.2.2 Design 143 7.2.3 Implementation 143 CHAPTER 8 Chess Playing Program 151 8.1 Analysis 151 8.2 Design 152 8.3 Implementation 152 CHAPTER 9 Go PlayingProgram 183 9.1 Requirements andanalysis 186 9.1.1 The rules ofGo 186 9.1.2 Datastructures for maintaininginformation required to play Go 188 9.2 Modulearchitecture 190 CONTENTS vII 9.3 Interactivelyprototypingdata structures 192 9.4 Lowlevel Scheme functions to manipulate Godatastructures 198 9.5 Go program design 214 9.6 Go program implementation 216 9.7 Ideas for improvingthe Go playingprogram 229 APPENDIXA Installingand Running the MIT Scheme System 231 APPENDIX B More InformationAvailable onthe Internet 233 Bibliography 235 Index 237 PREFACE Thereisa populardebate overusing Schemeorc++ toteachpro gramming. At a recent conference a computer science professor asked me which language was better for learning programming, Schemeorc++ (Schemeisa modemdialectoftheLISPprogram ming language). At the time, I had written only one LISP book andthreec++ books, soheexpectedthatIwouldfavorc++. Ihad to admit that I W;1S not sure which was the better language for teaching programming. Formyown use, I like to use Scheme for experimentingwith datastructures and exploring new ideas. For large projects and commercial software development I use C++. I believe that dynamic languages like Scheme are the most.ef ficient languages to use for many programming tasks where we want to minimize software development time rather than execu tionspeed.InwritingthisbookIwantedtobothprovideaconcise guide to learning the Scheme language and to demonstrate the useofthe languagetosolveinteresting, non-trivial problemspre sented as complete programs consisting ofreusable libraries and application-specificcode. Byworking through this book, you will learn the syntax of the Scheme language, control and iteration techniques howtowriteportableand reusableSchemecode, how touseScheme'sdynamicmemoryallocationtosimplifyrapidpro totypingtheapplicationoftechnologieslikegeneticprogramming and neural networks artificialintelligencetechniqueslike natural languageprocessingefficientsearchstrategies, howto programa computer to play chess, how to program a computerto play Go, and effective use ofgraphics in Scheme programs. This is a lot of material to cover in a rather short book, but most ofwhat you will learn from this book will be the result of yourown experimentation and modification ofthe example pro grams. The secondchapterofthis book is a tutorial introduction totheSchemelanguage.Thereaderisurgedtoreadthetutorialto Scheme with the MIT Scheme (or any other Scheme implemen tation) runningonhisorhercomputer. Thistutorialis briefsince Schemeis a simpleprogramminglanguage, butitis importantto readthetutorialcarefully,tryingtheexamplesasyoureadthetext. Thetutor;aldoes notattempttocovereveryaspectofthe Scheme programming language; rather, it covers only those elements of the language used in the example programs in this book. x PREFACE This book is not an exhaustive reference for the Scheme lan guage. Rather, the purpose ofthis book is to teach the reader to solve interesting problems using the Scheme language. I place moreemphasisonteachingthereaderhowto analyzea problem, design an algorithm for solving the problem, and quickly write a working prototypeprogramto solvethe problem. Formost prob lems, it is important both to get a prototype program running quickly and to design the prototype so that it can be modified when future requirements change and also lend itself to a mod ular implementation so that we develop reusable libraries while solvingwhateveris today's programming problem. This book is based on the freely distributable MIT Scheme system, which requires Microsoft Windows 3.1, Windows 95, or Windows NT to run. An OS/2 version of MIT Scheme is avail able on the Internet (see Appendix B). Acopy ofa minimal MIT Scheme development system is provided on the disks included with this book. You can also obtain new versions of the MIT Schemesystem,aswellasanEmacs-likeeditorandanativemode compiler, from various Internet FTP sites listed in Appendix B (e.g., ftp.cs.cmu.edu and ftp.cs.indiana.edu). I also use and recommend three otherpublic domain Scheme implementations: MacGambit Scheme onthe Macintosh PC Scheme from Texas Instruments, now in the public domain SCM Scheme, with versions for DOS, OS/2, and UNIX SomeoftheexamplesinthisbookrelyonMITScheme-specific functions thatare not partofthe Scheme language standard: the chessplayingprogramusestheMITSchemesortfunction,andthe geneticalgorithmandneuralnetworkexamplesrequirea random numbergenerator. The source code and executables of MIT Scheme are freely availableonthe Internet. MarkWatson SolanaBeach, California [email protected] [email protected] ACKNOWLEDGMENTS Iwouldliketothankmywife, Carol, forherencouragementwhile Iwaswritingthisbook.IwouldliketothankbothGuyLewisSteel Jr. and Gerald J. Sussman, who designed and first implemented the Scheme language. I would like to thank the team at MIT for writing the MIT Scheme development system, which is included with this book. I would like to thank my editor, Martin Gilchrist, bothfor recommending thisprojectandforhisencouragement. I wouldliketothankmyproductioneditorFrankGanzandmycopy editorDavidKramer. Iwouldliketo thankmytechnical reviewer, Jonathan Rossie, for manysuggested improvements.