Higher-Order Perl (eBook)

Transforming Programs with Programs

Mark Jason Dominus (Autor)

eBook Download: EPUB

2005 | 1. Auflage
600 Seiten
Elsevier Science (Verlag)
978-0-08-047834-0 (ISBN)

Infos

Most Perl programmers were originally trained as C and Unix programmers, so the Perl programs that they write bear a strong resemblance to C programs. However, Perl incorporates many features that have their roots in other languages such as Lisp. These advanced features are not well understood and are rarely used by most Perl programmers, but they are very powerful. They can automate tasks in everyday programming that are difficult to solve in any other way. One of the most powerful of these techniques is writing functions that manufacture or modify other functions. For example, instead of writing ten similar functions, a programmer can write a general pattern or framework that can then create the functions as needed according to the pattern. For several years Mark Jason Dominus has worked to apply functional programming techniques to Perl. Now Mark brings these flexible programming methods that he has successfully taught in numerous tutorials and training sessions to a wider audience.

* Introduces powerful programming methods—new to most Perl programmers—that were previously the domain of computer scientists
* Gradually builds up confidence by describing techniques of progressive sophistication
* Shows how to improve everyday programs and includes numerous engaging code examples to illustrate the methods

Inhalt

Front Cover 1
Higher-Order Perl: A Guide to Program Transformation 6
Copyright Page 7
Contents 10
Preface 16
Chapter 1. Recursion and Callbacks 20
1.1 Decimal to Binary Conversion 20
1.2 Factorial 22
1.3 The Tower of Hanoi 25
1.4 Hierarchical Data 31
1.5 Applications and Variations of Directory Walking 35
1.6 Functional Versus Object-Oriented Programming 44
1.7 HTML 45
1.8 When Recursion Blows Up 52
Chapter 2. Dispatch Tables 60
2.1 Configuration File Handling 60
2.2 Calculator 73
Chapter 3. Caching and Memoization 82
3.1 Caching Fixes Recursion 84
3.2 Inline Caching 85
3.3 Good Ideas 87
3.4 Memoization 88
3.5 The Memoize Module 89
3.6 Caveats 99
3.7 Key Generation 103
3.8 Caching in Object Methods 115
3.9 Persistent Caches 119
3.10 Alternatives to Memoization 120
3.11 Evangelism 127
3.12 The Benefits of Speed 128
Chapter 4. Iterators 134
4.1 Introduction 134
4.2 Homemade Iterators 138
4.3 Examples 145
4.4 Filters and Transforms 176
4.5 The Semipredicate Problem 182
4.6 Alternative Interfaces to Iterators 196
4.7 An Extended Example: Web Spiders 206
Chapter 5. From Recursion to Iterators 222
5.1 The Partition Problem Revisited 223
5.2 How to Convert a Recursive Function to an Iterator 234
5.3 A Generic Search Iterator 244
5.4 Other General Techniques for Eliminating Recursion 248
Chapter 6. Indinite Streams 274
6.1 Linked Lists 275
6.2 Lazy Linked Lists 276
6.3 Recursive Streams 282
6.4 The Hamming Problem 288
6.5 Regex String Generation 291
6.6 The Newton-Raphson Method 319
6.7 Power Series 332
Chapter 7. Higher-Order Functions and Currying 344
7.1 Currying 344
7.2 Common Higher-Order Functions 352
7.3 reduce() and combine() 362
7.4 Databases 370
Chapter 8. Parsing 378
8.1 Lexers 378
8.2 Parsing in General 395
8.3 Recursive-Descent Parsers 403
8.4 Arithmetic Expressions 409
8.5 Parsing Regexes 454
8.6 Outlines 459
8.7 Database-Query Parsing 467
8.8 Backtracking Parsers 475
8.9 Overloading 484
Chapter 9. Declarative Programming 490
9.1 Constraint Systems 491
9.2 Local Propagation Networks 491
9.3 Linear Equations 507
9.4 linogram: A Drawing System 509
9.5 Conclusion 582
Index 584
Function Index 594
A Note About the Cover 600

Textauszug

Preface

A well-known saying in the programming racket is that a good Fortran programmer can write Fortran programs in any language. The sad truth, though, is that Fortran programmers write Fortran programs in any language whether they mean to or not. Similarly, we, as Perl programmers, have been writing C programs in Perl whether we meant to or not. This is a shame, because Perl is a much more expressive language than C. We could be doing a lot better, using Perl in ways undreamt of by C programmers, but we’re not.

How did this happen? Perl was originally designed as a replacement for C on the one hand and Unix scripting languages like Bourne Shell and awk on the other. Perl’s first major proponents were Unix system administrators, people familiar with C and with Unix scripting languages; they naturally tended to write Perl programs that resembled C and awk programs. Perl’s inventor, Larry Wall, came from this sysadmin community, as did Randal Schwartz, his coauthor on Programming Perl, the first and still the most important Perl reference work. Other important early contributors include Tom Christiansen, also a C-and-Unix expert from way back. Even when Perl programmers didn’t come from the Unix sysadmin community, they were trained by people who did, or by people who were trained by people who did.

Around 19931 started reading books about Lisp, and I discovered something important: Perl is much more like Lisp than it is like C. If you pick up a good book about Lisp, there will be a section that describes Lisp’s good features. For example, the book Paradigms of Artificial Intelligence Programming, by Peter Norvig, includes a section titled What Makes Lisp Different? that describes seven features of Lisp. Perl shares six of these features; C shares none of them. These are big, important features, features like first-class functions, dynamic access to the symbol table, and automatic storage management. Lisp programmers have been using these features since 1957. They know a lot about how to use these language features in powerful ways. If Perl programmers can find out the things that Lisp programmers already know, they will learn a lot of things that will make their Perl programming jobs easier.

This is easier said than done. Hardly anyone wants to listen to Lisp programmers. Perl folks have a deep suspicion of Lisp, as demonstrated by Larry Wall’s famous remark that Lisp has all the visual appeal of oatmeal with fingernail clippings mixed in. Lisp programmers go around making funny noises like ‘cons’ and ‘cooder,’ and they talk about things like the PC loser-ing problem, whatever that is. They believe that Lisp is better than other programming languages, and they say so, which is irritating. But now it is all okay, because now you do not have to listen to the Lisp folks. You can listen to me instead. I will make soothing noises about hashes and stashes and globs, and talk about the familiar and comforting soft reference and variable suicide problems. Instead of telling you how wonderful Lisp is, I will tell you how wonderful Perl is, and at the end you will not have to know any Lisp, but you will know a lot more about Perl.

Then you can stop writing C programs in Perl. I think that you will find it to be a nice change. Perl is much better at being Perl than it is at being a slow version of C. You will be surprised at what you can get done when you write Perl programs instead of C.

WEB SITE

All the code examples in this book are available from my web site at:

When the notation in the margin is labeled with the tag some-example, the code may be downloaded from:

The web site will also carry the complete text, an errata listing, and other items of interest. Should you wish to send me email about the book, please send your message to [e-mail].

ACKNOWLEDGMENTS

Every acknowledgments section begins with a statement to the effect that “without the untiring support and assistance from my editor, Tim Cox, this book would certainly never have been written”. Until you write a book, you will never realize how true this is. Words fail me here; saying that the book would not have been written without Tim’s untiring support and assistance doesn’t begin to do justice to his contributions, his kindness, and his vast patience. Thank you, Tim.

This book was a long time in coming, and Tim went through three assistants while I was working on it. All these people were helpful and competent, so my thanks to Brenda Modliszewksi, Stacie Pierce, and Richard Camp. “Competent” may sound faint, but I consider it the highest praise.

Many thanks to Troy Lilly and Simon Crump, the production managers, who were not only competent but also fun to work with.

Shortly before the book went into production, I started writing tests for the example code. I realized with horror that hardly any of the programs worked properly. There were numerous small errors (and some not so small), inconsistencies between the code and the output, typos, and so on. Thanks to the heroic eleventh-hour efforts of Robert Spier, I think most of these errors have been caught. Robert was not only unfailingly competent, helpful, and productive, but also unfailingly cheerful, too. If any of the example programs in this book work as they should, you can thank Robert. (If they don’t, you should blame me, not Robert.) Robert was also responsible for naming the MOD document preparation system that I used to prepare the manuscript.

The contributions of my wife, Lorrie Kim, are too large and pervasive to note individually. It is to her that this book is dedicated.

A large number of other people contributed to this book, but many of them were not aware of it at the time. I was fortunate to have a series of excellent teachers, whose patience I must sometimes have tried terribly. Thanks to Mark Foster, Patrick X. Gallagher, Joan Livingston, Cal Lobel (who first taught me to program), Harry McLaughlin, David A. J. Meyer, Bruce Piper, Ronnie Rabassa, Michael Tempel, and Johan Tysk. Mark Foster also arrived from nowhere in the nick of time to suggest the title for this book just when I thought all was lost.

This book was directly inspired by two earlier books: ML for the Working Programmer, by Lawrence Paulson, and Structure and Interpretation of Computer Programs, by Harold Abelson and Gerald Jay Sussman. Other important influences were Introduction to Functional Programming, by Richard Bird and Philip Wadler, and Paradigms of Artificial Intelligence Programming, by Peter Norvig.

The official technical reviewers had a less rewarding job than they might have on other projects. This book took a long time to write, and although I wanted to have long conversations with the reviewers about every little thing, I was afraid that if I did that, I would never ever finish. So I rarely corresponded with the reviewers, and they probably thought that I was just filing their suggestions in the shredder. But I wasn’t; I pored over all their comments with the utmost care, and agonized over most of them. My thanks to the reviewers: Sean Burke, Damian Conway, Kevin Lenzo, Peter Norvig, Dan Schmidt, Kragen Sitaker, Michael Scott, and Adam Turoff.

While I was writing, I ran a mailing list for people who were interested in the book, and sent advance chapters to the mailing list. This was tremendously helpful, and I’d recommend the practice to anyone else. The six hundred and fifty wonderful members of my mailing list are too numerous to list here. All were helpful and supportive, and the book is much better for their input. A few stand out as having contributed a particularly large amount of concrete material: Roland Young, Damien Warman, David “Novalis” Turner, Iain “Spoon” Truskett, Steve Tolkin, Ben Tilly, Rob Svirskas, Roses Longin Odounga, Luc St-Louis, Jeff Mitchell, Steffen Müller, Abhijit Menon-Sen, Walt Mankowski, Wolfgang Laun, Paul Kulchenko, Daniel Koo, Andy Lester, David Landgren, Robin Houston, Torsten Hofmann, Douglas Hunter, Francesc Guasch, Kenneth Graves, Jeff Goff, Michael Fischer, Simon Cozens, David Combs, Stas Bekman, Greg Bacon, Darius Bacon, and Peter Allen. My apologies to the many many helpful contributors whom I have deliberately omitted from this list in the interests of space, and even more so to the several especially helpful contributors whom I have accidentally omitted.

Wolfgang Laun and Per Westerlund were particularly assiduous in helping me correct errors for the second printing.

Before I started writing, I received valuable advice about choosing a publisher from Philip Greenspun, Brian Kernighan, and Adam Turoff. Damian Conway and Abigail gave me helpful advice and criticism about my proposal.

Sean Burke recorded my Ivory Tower talk, cut CDs and sent them to me, and also supplied RTF-related consulting at the last minute. He also sent me periodic mail to remind me how wonderful my book was, which often arrived at times when I wasn’t so sure.

Several specific ideas in Chapter 4 were suggested by other people. Meng Wong suggested the clever and apt “odometer” metaphor. Randal Schwartz helped me with the “append” function. Eric Roode suggested the multiple list iterator.

When I needed to read out-of-print books by Paul Graham, A. E. Sundstrom lent them to me. When I needed a copy of volume 2 of The Art of Computer Programming, Hildo Biersma and Morgan Stanley bought it for me. When I needed money, B. B. King lent me some. Thanks to...

Produkt-Details

• Erscheint lt. Verlag: 31.3.2005
• Sprache: englisch
• Themenwelt: Sachbuch/Ratgeber
• Themenwelt: Mathematik / Informatik ► Informatik ► Programmiersprachen / -werkzeuge
• Themenwelt: Mathematik / Informatik ► Informatik ► Software Entwicklung
• Themenwelt: Mathematik / Informatik ► Informatik ► Web / Internet
• ISBN-10: 0-08-047834-4 / 0080478344
• ISBN-13: 978-0-08-047834-0 / 9780080478340