Land of Lisp Learn to Program in Lisp, One Game at a Time (Conrad Barski, M.D.) (Z-Library)

📄 File Format: PDF

💾 File Size: 18.6 MB

📖 Read Online ⬇️ Download

Registered users can read the full content for free

Register as a Gaohf Library member to read the complete e-book online for free and enjoy a better reading experience.

📄 Page 1

Conrad Barski, M.D.

📄 Page 2

(This page has no text content)

📄 Page 3

LAND OF LISP

📄 Page 4

(This page has no text content)

📄 Page 5

LAND OF LISP L e a r n t o P r o g r a m i n L i s p , O n e G a m e a t a T i m e ! by Conrad Barski , M.D. San Francisco

📄 Page 6

LAND OF LISP. Copyright © 2011 by Conrad Barski, M.D. All rights reserved. No part of this work may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, recording, or by any information storage or retrieval system, without the prior written permission of the copyright owner and the publisher. Printed in Canada 14 13 12 11 10 1 2 3 4 5 6 7 8 9 ISBN-10: 1-59327-281-2 ISBN-13: 978-1-59327-281-4 Publisher: William Pollock Production Editors: Ansel Staton and Serena Yang Developmental Editor: Keith Fancher Technical Reviewers: Philip Fominykh and Heow Eide-Goodman Copyeditor: Marilyn Smith Compositor: Susan Glinert Stevens Proofreader: Linda Seifert Indexer: Nancy Guenther For information on book distributors or translations, please contact No Starch Press, Inc. directly: No Starch Press, Inc. 38 Ringold Street, San Francisco, CA 94103 phone: 415.863.9900; fax: 415.863.9950; info@nostarch.com; www.nostarch.com Library of Congress Cataloging-in-Publication Data Barski, Conrad. Land of Lisp : learn to program in Lisp, one game at a time! / by Conrad Barski. p. cm. Includes index. ISBN-13: 978-1-59327-281-4 ISBN-10: 1-59327-281-2 1. Computer games--Programming 2. COMMON LISP (Computer program language) 3. LISP (Computer program language) I. Title. QA76.76.C672B3693 2010 794.8'1526--dc22 2010026755 No Starch Press and the No Starch Press logo are registered trademarks of No Starch Press, Inc. Other product and company names mentioned herein may be the trademarks of their respective owners. Rather than use a trademark symbol with every occurrence of a trademarked name, we are using the names only in an editorial fashion and to the benefit of the trademark owner, with no intention of infringement of the trademark. The information in this book is distributed on an “As Is” basis, without warranty. While every precaution has been taken in the preparation of this work, neither the author nor No Starch Press, Inc. shall have any liability to any person or entity with respect to any loss or damage caused or alleged to be caused directly or indirectly by the information contained in it.

📄 Page 7

For Lauren

📄 Page 8

(This page has no text content)

📄 Page 9

B R I E F C O N T E N T S Acknowledgments ........................................................................................................xvii Introduction ....................................................................................................................1 SECTION I: LISP IS POWER Chapter 1: Getting Started with Lisp ................................................................................15 Chapter 2: Creating Your First Lisp Program.....................................................................21 Chapter 3: Exploring the Syntax of Lisp Code...................................................................31 SECTION II: LISP IS SYMMETRY Chapter 4: Making Decisions with Conditions ..................................................................49 Chapter 5: Building a Text Game Engine .........................................................................67 Chapter 6: Interacting with the World: Reading and Printing in Lisp ....................................85 Chapter 6.5: lambda: A Function So Important It Deserves Its Own Chapter.......................103 Chapter 7: Going Beyond Basic Lists .............................................................................107 Chapter 8: This Ain’t Your Daddy’s Wumpus..................................................................129 Chapter 9: Advanced Datatypes and Generic Programming ............................................153

📄 Page 10

viii Br ie f Contents SECTION III: LISP IS HACKING ..................................................................................191 Chapter 10: Looping with the loop Command ................................................................195 Chapter 11: Printing Text with the format Function...........................................................221 Chapter 12: Working with Streams ...............................................................................237 Chapter 13: Let’s Create a Web Server! ........................................................................253 Functional Programming Is Beautiful ..............................................................................269 SECTION IV: LISP IS SCIENCE Chapter 14: Ramping Lisp Up a Notch with Functional Programming ................................291 Chapter 15: Dice of Doom, a Game Written in the Functional Style ..................................303 Chapter 16: The Magic of Lisp Macros..........................................................................339 Chapter 17: Domain-Specific Languages........................................................................355 Chapter 18: Lazy Programming ....................................................................................375 Chapter 19: Creating a Graphical, Web-Based Version of Dice of Doom ..........................401 Chapter 20: Making Dice of Doom More Fun.................................................................417 Epilogue ....................................................................................................................429 Index .........................................................................................................................465

📄 Page 11

C O N T E N T S I N D E T A I L ACKNOWLEDGMENTS xvii INTRODUCTION 1 What Makes Lisp So Cool and Unusual? .................................................................... 2 If Lisp Is So Great, Why Don’t More People Use It? ...................................................... 3 Where Did Lisp Come From? ..................................................................................... 4 Where Does Lisp Get Its Power? .............................................................................. 10 SECTION I: LISP IS POWER 1 GETTING STARTED WITH LISP 15 Lisp Dialects .......................................................................................................... 15 A Tale of Two Lisps ................................................................................... 16 Up-and-Coming Lisps ................................................................................. 17 Lisp Dialects Used for Scripting ................................................................... 17 ANSI Common Lisp ................................................................................... 17 Getting Started with CLISP ....................................................................................... 18 Installing CLISP ......................................................................................... 18 Starting Up CLISP ...................................................................................... 19 What You’ve Learned ............................................................................................. 19 2 CREATING YOUR FIRST LISP PROGRAM 21 The Guess-My-Number Game .................................................................................. 21 Defining Global Variables in Lisp ............................................................................. 23 Defining the small and big Variables ........................................................... 23 An Alternative Global Variable Definition Function ........................................ 23 Basic Lisp Etiquette ................................................................................................. 24 Defining Global Functions in Lisp ............................................................................. 25 Defining the guess-my-number Function ........................................................ 25 Defining the smaller and bigger Functions .................................................... 27 Defining the start-over Function ................................................................... 28 Defining Local Variables in Lisp ................................................................................ 28 Defining Local Functions in Lisp ................................................................................ 29 What You’ve Learned ............................................................................................. 30

📄 Page 12

x Contents in Detai l 3 EXPLORING THE SYNTAX OF LISP CODE 31 Syntax and Semantics ............................................................................................. 31 The Building Blocks of Lisp Syntax ............................................................................ 32 Symbols ................................................................................................... 33 Numbers .................................................................................................. 34 Strings ..................................................................................................... 35 How Lisp Distinguishes Between Code and Data ........................................................ 35 Code Mode .............................................................................................. 36 Data Mode ............................................................................................... 37 Lists in Lisp ............................................................................................................ 37 Cons Cells ................................................................................................ 38 List Functions ............................................................................................. 38 Nested Lists .............................................................................................. 41 What You’ve Learned ............................................................................................. 45 SECTION II: LISP IS SYMMETRY 4 MAKING DECISIONS WITH CONDITIONS 49 The Symmetry of nil and () ....................................................................................... 49 Empty Equals False .................................................................................... 50 The Four Disguises of () .............................................................................. 51 The Conditionals: if and Beyond .............................................................................. 52 One Thing at a Time with if ........................................................................ 52 Going Beyond if: The when and unless Alternatives ....................................... 55 The Command That Does It All: cond ........................................................... 56 Branching with case .................................................................................. 57 Cool Tricks with Conditions ..................................................................................... 58 Using the Stealth Conditionals and and or .................................................... 58 Using Functions That Return More than Just the Truth ...................................... 60 Comparing Stuff: eq, equal, and More ..................................................................... 62 What You’ve Learned ............................................................................................. 65 5 BUILDING A TEXT GAME ENGINE 67 The Wizard’s Adventure Game ................................................................................ 68 Our Game World ..................................................................................... 68 Basic Requirements .................................................................................... 69 Describing the Scenery with an Association List .......................................................... 70 Describing the Location ........................................................................................... 71 Describing the Paths ............................................................................................... 72 How Quasiquoting Works .......................................................................... 73 Describing Multiple Paths at Once ............................................................... 73 Describing Objects at a Specific Location .................................................................. 77 Listing Visible Objects ................................................................................ 77 Describing Visible Objects ......................................................................... 78

📄 Page 13

Contents in Detai l xi Describing It All ..................................................................................................... 79 Walking Around in Our World ................................................................................ 81 Picking Up Objects ................................................................................................. 82 Checking Our Inventory .......................................................................................... 83 What You’ve Learned ............................................................................................. 84 6 INTERACTING WITH THE WORLD: READING AND PRINTING IN LISP 85 Printing and Reading Text ....................................................................................... 86 Printing to the Screen ................................................................................. 86 Saying Hello to the User ........................................................................... 87 Starting with print and read ........................................................................ 88 Reading and Printing Stuff the Way Humans Like It ........................................ 90 The Symmetry Between Code and Data in Lisp ........................................................... 91 Adding a Custom Interface to Our Game Engine ....................................................... 92 Setting Up a Custom REPL .......................................................................... 93 Writing a Custom read Function ................................................................. 94 Writing a game-eval Function ..................................................................... 96 Writing a game-print Function .................................................................... 96 Trying Out Our Fancy New Game Interface .............................................................. 99 The Dangers of read and eval ............................................................................... 101 What You’ve Learned ........................................................................................... 101 6.5 LAMBDA: A FUNCTION SO IMPORTANT IT DESERVES ITS OWN CHAPTER 103 What lambda Does .............................................................................................. 103 Why lambda Is So Important ................................................................................. 105 What You’ve Learned ........................................................................................... 106 7 GOING BEYOND BASIC LISTS 107 Exotic Lists ........................................................................................................... 107 Dotted Lists ............................................................................................. 108 Pairs ...................................................................................................... 109 Circular Lists ........................................................................................... 110 Association Lists ...................................................................................... 111 Coping with Complicated Data .............................................................................. 113 Visualizing Tree-like Data ......................................................................... 113 Visualizing Graphs .................................................................................. 114 Creating a Graph ................................................................................................ 114 Generating the DOT Information ............................................................... 115 Turning the DOT File into a Picture ............................................................ 120 Creating a Picture of Our Graph ............................................................... 123 Creating Undirected Graphs .................................................................................. 124 What You’ve Learned ........................................................................................... 127

📄 Page 14

xii Contents in Detai l 8 THIS AIN’T YOUR DADDY’S WUMPUS 129 The Grand Theft Wumpus Game ............................................................................ 131 Defining the Edges of Congestion City .................................................................... 135 Generating Random Edges ....................................................................... 135 Looping with the loop Command ............................................................... 136 Preventing Islands .................................................................................... 137 Building the Final Edges for Congestion City ............................................... 139 Building the Nodes for Congestion City .................................................................. 142 Initializing a New Game of Grand Theft Wumpus .................................................... 144 Drawing a Map of Our City .................................................................................. 145 Drawing a City from Partial Knowledge ..................................................... 146 Walking Around Town ............................................................................. 148 Let’s Hunt Some Wumpus! ..................................................................................... 149 What You’ve Learned ........................................................................................... 152 9 ADVANCED DATATYPES AND GENERIC PROGRAMMING 153 Arrays ................................................................................................................ 153 Working with Arrays ............................................................................... 154 Using a Generic Setter ............................................................................. 154 Arrays vs. Lists ........................................................................................ 156 Hash Tables ........................................................................................................ 157 Working with Hash Tables ....................................................................... 157 Returning Multiple Values ......................................................................... 159 Hash Table Performance .......................................................................... 160 A Faster Grand Theft Wumpus Using Hash Tables ....................................... 161 Common Lisp Structures ........................................................................................ 163 Working with Structures ........................................................................... 163 When to Use Structures ............................................................................ 165 Handling Data in a Generic Way .......................................................................... 166 Working with Sequences ......................................................................... 166 Creating Your Own Generic Functions with Type Predicates ......................... 170 The Orc Battle Game ............................................................................................ 172 Global Variables for the Player and Monsters ............................................. 173 Main Game Functions .............................................................................. 174 Player Management Functions .................................................................. 175 Helper Functions for Player Attacks ............................................................ 177 Monster Management Functions ................................................................ 178 The Monsters .......................................................................................... 179 To Battle! ............................................................................................... 187 What You’ve Learned ........................................................................................... 189 SECTION III: LISP IS HACKING loop and format: The Seedy Underbelly of Lisp ......................................................... 193

📄 Page 15

Contents in Detai l xiii 10 LOOPING WITH THE LOOP COMMAND 195 The loop Macro ................................................................................................... 195 Some loop Tricks ..................................................................................... 196 Everything You Ever Wanted to Know About loop ....................................... 202 Using loop to Evolve! ............................................................................................ 202 Growing Plants in Our World ................................................................... 204 Creating Animals .................................................................................... 205 Simulating a Day in Our World ................................................................ 212 Drawing Our World ................................................................................ 212 Creating a User Interface ......................................................................... 213 Let’s Watch Some Evolution! ..................................................................... 214 Explaining the Evolution ........................................................................... 218 What You’ve Learned ........................................................................................... 219 11 PRINTING TEXT WITH THE FORMAT FUNCTION 221 Anatomy of the format Function .............................................................................. 221 The Destination Parameter ........................................................................ 222 The Control String Parameter .................................................................... 222 Value Parameters .................................................................................... 223 Control Sequences for Printing Lisp Values ............................................................... 223 Control Sequences for Formatting Numbers ............................................................. 225 Control Sequences for Formatting Integers .................................................. 225 Control Sequences for Formatting Floating-Point Numbers ............................ 226 Printing Multiple Lines of Output ............................................................................. 226 Justifying Output ................................................................................................... 228 Iterating Through Lists Using Control Sequences ....................................................... 231 A Crazy Formatting Trick for Creating Pretty Tables of Data ...................................... 232 Attack of the Robots! ............................................................................................. 233 What You’ve Learned ........................................................................................... 235 12 WORKING WITH STREAMS 237 Types of Streams .................................................................................................. 238 Streams by Type of Resource .................................................................... 238 Streams by Direction ................................................................................ 238 Working with Files ............................................................................................... 242 Working with Sockets ........................................................................................... 244 Socket Addresses .................................................................................... 245 Socket Connections ................................................................................. 246 Sending a Message over a Socket ............................................................ 246 Tidying Up After Ourselves ....................................................................... 248 String Streams: The Oddball Type .......................................................................... 249 Sending Streams to Functions .................................................................... 249 Working with Long Strings ....................................................................... 250 Reading and Debugging .......................................................................... 250 What You’ve Learned ........................................................................................... 251

📄 Page 16

xiv Contents in Detai l 13 LET’S CREATE A WEB SERVER! 253 Error Handling in Common Lisp ............................................................................. 253 Signaling a Condition .............................................................................. 254 Creating Custom Conditions ..................................................................... 254 Intercepting Conditions ............................................................................ 255 Protecting Resources Against Unexpected Conditions ................................... 255 Writing a Web Server from Scratch ....................................................................... 256 How a Web Server Works ....................................................................... 256 Request Parameters ................................................................................. 258 Parsing the Request Header ...................................................................... 261 Testing get-header with a String Stream ..................................................... 262 Parsing the Request Body ......................................................................... 263 Our Grand Finale: The serve Function! ....................................................... 263 Building a Dynamic Website ................................................................................. 265 Testing the Request Handler ...................................................................... 265 Launching the Website ............................................................................. 266 What You’ve Learned ........................................................................................... 267 FUNCTIONAL PROGRAMMING IS BEAUTIFUL 269 SECTION IV: LISP IS SCIENCE 14 RAMPING LISP UP A NOTCH WITH FUNCTIONAL PROGRAMMING 291 What Is Functional Programming? .......................................................................... 292 Anatomy of a Program Written in the Functional Style ............................................... 295 Higher-Order Programming ................................................................................... 298 Code Composition with Imperative Code ................................................... 298 Using the Functional Style ......................................................................... 299 Higher-Order Programming to the Rescue ................................................... 300 Why Functional Programming Is Crazy ................................................................... 300 Why Functional Programming Is Fantastic ............................................................... 301 Functional Programming Reduces Bugs ...................................................... 301 Functional Programs Are More Compact .................................................... 301 Functional Code Is More Elegant ............................................................... 302 What You’ve Learned ........................................................................................... 302 15 DICE OF DOOM, A GAME WRITTEN IN THE FUNCTIONAL STYLE 303 The Rules of Dice of Doom ..................................................................................... 304 A Sample Game of Dice of Doom .......................................................................... 304

📄 Page 17

Contents in Detai l xv Implementing Dice of Doom, Version 1 ................................................................... 306 Defining Some Global Variables ............................................................... 306 Representing the Game Board .................................................................. 307 Decoupling Dice of Doom’s Rules from the Rest of the Game ........................ 309 Generating a Game Tree ......................................................................... 311 Calculating Passing Moves ....................................................................... 312 Calculating Attacking Moves .................................................................... 313 Finding the Neighbors ............................................................................. 314 Attacking ............................................................................................... 315 Reinforcements ........................................................................................ 316 Trying Out Our New game-tree Function .................................................... 317 Playing Dice of Doom Against Another Human ........................................... 318 Creating an Intelligent Computer Opponent ............................................................. 321 The Minimax Algorithm ............................................................................ 323 Turning Minimax into Actual Code ............................................................ 323 Creating a Game Loop with an AI Player ................................................... 324 Playing Our First Human vs. Computer Game ............................................. 325 Making Dice of Doom Faster ................................................................................. 326 Closures ................................................................................................. 326 Memoization .......................................................................................... 328 Tail Call Optimization .............................................................................. 331 A Sample Game on the 3-by-3 Board ........................................................ 334 What You’ve Learned ........................................................................................... 336 16 THE MAGIC OF LISP MACROS 339 A Simple Lisp Macro ............................................................................................ 340 Macro Expansion .................................................................................... 341 How Macros Are Transformed .................................................................. 342 Using the Simple Macro ........................................................................... 345 More Complex Macros ......................................................................................... 345 A Macro for Splitting Lists ......................................................................... 346 Avoiding Repeated Execution in Macros .................................................... 347 Avoiding Variable Capture ....................................................................... 348 A Recursion Macro .................................................................................. 350 Macros: Dangers and Alternatives .......................................................................... 352 What You’ve Learned ........................................................................................... 353 17 DOMAIN-SPECIFIC LANGUAGES 355 What Is a Domain? .............................................................................................. 355 Writing SVG Files ................................................................................................ 356 Creating XML and HTML with the tag Macro .............................................. 357 Creating SVG-Specific Macros and Functions ............................................. 361 Building a More Complicated SVG Example .............................................. 362 Creating Custom Game Commands for Wizard’s Adventure Game ............................ 365 Creating New Game Commands by Hand ................................................. 366 Let’s Try the Completed Wizard’s Adventure Game! .................................... 371 What You’ve Learned ........................................................................................... 373

📄 Page 18

xvi Contents in Detai l 18 LAZY PROGRAMMING 375 Adding Lazy Evaluation to Lisp .............................................................................. 376 Creating the lazy and force Commands ..................................................... 378 Creating a Lazy Lists Library ..................................................................... 380 Converting Between Regular Lists and Lazy Lists .......................................... 381 Mapping and Searching Across Lazy Lists .................................................. 383 Dice of Doom, Version 2 ....................................................................................... 384 Making Our AI Work on Larger Game Boards ........................................................ 387 Trimming the Game Tree .......................................................................... 387 Applying Heuristics ................................................................................. 389 Winning by a Lot vs. Winning by a Little .................................................... 389 Alpha Beta Pruning ................................................................................. 393 What You’ve Learned ........................................................................................... 400 19 CREATING A GRAPHICAL, WEB-BASED VERSION OF DICE OF DOOM 401 Drawing the Game Board Using the SVG Format ..................................................... 402 Drawing a Die ........................................................................................ 403 Drawing a Tile ........................................................................................ 405 Drawing the Board .................................................................................. 406 Building the Web Server Interface .......................................................................... 408 Writing Our Web Request Handler ........................................................... 408 Limitations of Our Game Web Server ........................................................ 409 Initializing a New Game .......................................................................... 410 Announcing a Winner ............................................................................. 410 Handling the Human Player ...................................................................... 410 Handling the Computer Player .................................................................. 412 Drawing the SVG Game Board from Within the HTML ................................. 412 Playing Version 3 of Dice of Doom ......................................................................... 413 What You’ve Learned ........................................................................................... 415 20 MAKING DICE OF DOOM MORE FUN 417 Increasing the Number of Players ........................................................................... 417 Rolling the Dice .................................................................................................... 418 Building Chance Nodes ........................................................................... 419 Doing the Actual Dice Rolling ................................................................... 420 Calling the Dice Rolling Code from Our Game Engine ................................. 420 Updating the AI ...................................................................................... 422 Improving the Dice of Doom Reinforcement Rules ..................................................... 423 Conclusion .......................................................................................................... 425 EPILOGUE 429 INDEX 465

📄 Page 19

A C K N O W L E D G M E N T S First of all, I’d like to thank my wife Lauren for letting me spend so many weekends on this book project. I am also particularly grateful to Philip Fominykh, the main technical reviewer for this book, whose extensive experience with proper Common Lisp form and style helped to reign in many (but not too many) quirks in the source code and in the discussions of Lisp philosophy. I also owe a great deal to Heow Eide-Goodman, who reviewed the final chapters and helped complete this project. Many folks at No Starch Press had to wrestle with the idiosyncratic prose and structure of this book to bring it into publishable form. First and foremost, I want to thank Keith Fancher, my primary editor for most of this project. Great effort was also put in by Bill Pollock, Serena Yang, Ansel Staton, Riley Hoffman, Alison Petersen, Magnolia Molcan, Kathleen Mish, Don Marti, Tyler Ortman, and Adam Wright. I’d also like to thank Aaron Feng for early feedback on the style of the book. This book project originally began as an expansion of my “Casting SPELs in Lisp” web tutorial. I want to thank everyone who emailed or talked with me about this tutorial and helped me expand my understanding of Lisp

📄 Page 20

xviii Acknowledgments along the way. rms (Richard Stallman), in particular, gave me a lot of feedback on Lisp style and helped me put together the Emacs Lisp version of the tutorial. Please consider donating to the Free Software Foundation (http://www.fsf.org/), a nonprofit organization he founded to support the development of open source and free software, which includes many great Lisp tools. James Webb also helped greatly with the Emacs Lisp version. And among the countless folks who gave feedback and/or corrections on “Casting SPELs in Lisp,” I’d especially like to thank Kenny Tilton, Marshall Quander, Wei-Ju Wu, Christopher Brown, Stephen Gravrock, Paul Schulz, Andy Cowell, and Johan Bockgård.