Transcription
Think Perl 6How to Think Like a Computer Scientist1st Edition, Version 0.5.0May 2017
Think Perl 6How to Think Like a Computer Scientist1st Edition, Version 0.5.0May 2017Laurent Rosenfeld, with Allen B. DowneyGreen Tea PressNeedham, Massachusetts
Copyright 2017 Allen Downey, Laurent Rosenfeld.Green Tea Press9 Washburn AveNeedham MA 02492Permission is granted to copy, distribute, and/or modify this document under the terms of theCreative Commons Attribution-NonCommercial 3.0 Unported License, which is available at http://creativecommons.org/licenses/by-nc/3.0/.The original form of this book is LATEX source code. Compiling this LATEX source has the effect of generating a device-independent representation of a textbook, which can be converted to other formatsand printed.The LATEX source for this book is available from https://github.com/LaurentRosenfeld/thinkperl6/
PrefaceWelcome to the art of computer programming and to the new Perl 6 language. This willprobably be the first published books using Perl 6 (or one of the first), a powerful, expressive, malleable and highly extensible programming language. But this book is less aboutPerl 6, and more about learning how to write programs for computers.This book is intended for beginners and does not require any prior programming knowledge, but it is my hope that even those of you with programming experience will benefitfrom reading it.The Aim of this BookThis aim of this book is not primarily to teach Perl 6, but instead to teach the art of programming, using the Perl 6 language. After having completed this book, you should hopefullybe able to write programs to solve relatively difficult problems in Perl 6, but my main aim isto teach computer science, software programming, and problem solving rather than solelyto teach the Perl 6 language itself.This means that I will not cover every aspect of Perl 6, but only a (relatively large, butyet incomplete) subset of it. By no means is this book intended to be a reference on thelanguage.It is not possible to learn programming or to learn a new programming language by justreading a book; practicing is essential. This book contains a lot of exercises. You arestrongly encouraged to make a real effort to do them. And, whether successful or notin solving the exercises, you should take a look at the solutions in the Appendix, as, veryoften, several solutions are suggested with further discussion on the subject and the issuesinvolved. Sometimes, the solution section of the Appendix also introduces examples oftopics that will be covered in the next chapter–and sometimes even things that are not covered elsewhere in the book. So, to get the most out the book, I suggest you try to solve theexercises as well as review the solutions and attempt them.There are more than one thousand code examples in this book; study them, make sure tounderstand them, and run them. When possible, try to change them and see what happens.You’re likely to learn a lot from this process.
viChapter 0. PrefaceThe History of this BookIn the course of the last three to four years, I have translated or adapted to French a numberof tutorials and articles on Perl 6, and I’ve also written a few entirely new ones in French. 1Together, these documents represented by the end of 2015 somewhere between 250 and300 pages of material on Perl 6. By that time, I had probably made public more material onPerl 6 in French than all other authors taken together.In late 2015, I began to feel that a Perl 6 document for beginners was something missingthat I was willing to undertake. I looked around and found that it did not seem to existin English either. I came to the idea that, after all, it might be more useful to write such adocument initially in English, to give it a broader audience. I started contemplating writinga beginner introduction to Perl 6 programming. My idea at the time was something like a50- to 70-page tutorial and I started to gather material and ideas in this direction.Then, something happened that changed my plans.In December 2015, friends of mine were contemplating translating into French Allen B.Downey’s Think Python, Second Edition2 . I had read an earlier edition of that book and fullysupported the idea of translating it3 . As it turned out, I ended up being a co-translator andthe technical editor of the French translation of that book4 .While working on the French translation of Allen’s Python book, the idea came to methat, rather than writing a tutorial on Perl 6, it might be more useful to make a “Perl 6translation” of Think Python. Since I was in contact with Allen in the context of the Frenchtranslation, I suggested this to Allen, who warmly welcomed the idea. This is how I startedto write this book late January 2016, just after having completed the work on the Frenchtranslation of his Python book.This book is thus largely derived on Allen’s Think Python, but adapted to Perl 6. As ithappened, it is also much more than just a “Perl 6 translation” of Allen’s book: with quitea lot of new material, it has become a brand new book, largely indebted to Allen’s book,but yet a new book for which I take all responsibility. Any errors are mine, not Allen’s.My hope is that this will be useful to the Perl 6 community, and more broadly to the opensource and general computer programming communities. In an interview with LinuxVoice(July 2015), Larry Wall, the creator of Perl 6, said: “We do think that Perl 6 will be learnableas a first language.” Hopefully this book will contribute to making this happen.AcknowledgmentsI just don’t know how I could thank Larry Wall to the level of gratitude that he deservesfor having created Perl in the first place, and Perl 6 more recently. Be blessed for eternity,Larry, for all of that.And thank to you all of you who took part to this adventure (in no particular order), Tom,Damian, chromatic, Nathan, brian, Jan, Jarkko, John, Johan, Randall, Mark Jason, Ovid,1 See2 Seefor example ttp://greenteapress.com/wp/think-python-2e/.3 I know, it’s about Python, not Perl. But I don’t believe in engaging in “language wars” and think that we allhave to learn from other languages; to me, Perl’s motto, “there is more than one way to do it,” also means thatdoing it in Python (or some other language) is truly an acceptable possibility.4 See ensez-python/.
viiNick, Tim, Andy, Chip, Matt, Michael, Tatsuhiko, Dave, Rafael, Chris, Stevan, Saraty, Malcolm, Graham, Leon, Ricardo, Gurusamy, Scott and too many others to name.All my thanks also to those who believed in this Perl 6 project and made it happen, including those who quit at one point or another but contributed for some time; I know that thiswasn’t always easy.Many thanks to Allen Downey, who very kindly supported my idea of adapting his bookto Perl 6 and helped me in many respects, but also refrained from interfering in what I wasputting into this new book.I very warmly thank the people at O’Reilly who accepted the idea of this book and suggested many corrections or improvements. I want to thank especially Dawn Schanafelt, myeditor at O’Reilly, whose advice has truly contributed to making this a better book. Manythanks also to Charles Roumeliotis, the copy editor, and Kristen Brown, the productioneditor, who fixed many typographical problems and spelling mistakes.Thanks a lot in advance to readers who will offer comments or submit suggestions or corrections, as well as encouragements.If you see anything that needs to be corrected or that could be improved, please kindlysend your comments to think.perl6(at)gmail.com.Contributor ListI would like to thank especially Moritz Lenz and Elizabeth Mattijsen, who reviewed in detail drafts of this book and suggested quite a number of improvements and corrections. Lizspent a lot of time on a detailed review of the full content of this book and I am especiallygrateful to her for her numerous and very useful comments. Thanks also to Timo Paulssenand ryanschoppe who also reviewed early drafts and provided some useful suggestions.Many thanks also to Uri Guttman, who reviewed this book and suggested a number ofsmall corrections and improvements shortly before publication. Kamimura submitted acouple of corrections in the errata list on the O’Reilly web site.
viiiChapter 0. Preface
ContentsPrefacevIStarting with the Basics11The Way of the Program51.1What is a Program? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .51.2Running Perl 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .61.3The First Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .71.4Arithmetic Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .81.5Values and Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .81.6Formal and Natural Languages . . . . . . . . . . . . . . . . . . . . . . . . .111.7Debugging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .121.8Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .121.9Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .132Variables, Expressions and Statements152.1Assignment Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .152.2Variable Names . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .162.3Expressions and Statements . . . . . . . . . . . . . . . . . . . . . . . . . . .182.4Script Mode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .202.5One-Liner Mode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .212.6Order of Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .222.7String Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .232.8Comments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .242.9Debugging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .242.10Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .252.11Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .26
x34ContentsFunctions273.1Function Calls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .273.2Functions and Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .303.3Math functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .303.4Composition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .323.5Adding New Functions (a.k.a. Subroutines) . . . . . . . . . . . . . . . . . .323.6Definitions and Uses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .343.7Flow of Execution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .353.8Parameters and Arguments . . . . . . . . . . . . . . . . . . . . . . . . . . .353.9Variables and Parameters Are Local . . . . . . . . . . . . . . . . . . . . . .373.10Stack Diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .373.11Fruitful Functions and Void Functions . . . . . . . . . . . . . . . . . . . . .383.12Function Signatures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .403.13Immutable and Mutable Parameters . . . . . . . . . . . . . . . . . . . . . .413.14Functions and Subroutines as First-Class Citizens . . . . . . . . . . . . . .423.15Why Functions and Subroutines? . . . . . . . . . . . . . . . . . . . . . . . .443.16Debugging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .443.17Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .453.18Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .46Loops, Conditionals, and Recursion494.1Integer Division and Modulo . . . . . . . . . . . . . . . . . . . . . . . . . .494.2Boolean Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .504.3Logical Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .524.4Conditional Execution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .544.5Alternative Execution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .544.6Chained Conditionals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .554.7Nested Conditionals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .554.8If Conditionals as Statement Modifiers . . . . . . . . . . . . . . . . . . . . .564.9Unless Conditional Statement . . . . . . . . . . . . . . . . . . . . . . . . . .574.10For Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .574.11Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .59
Contents56xi4.12Stack Diagrams for Recursive Subroutines . . . . . . . . . . . . . . . . . . .614.13Infinite Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .614.14Keyboard Input . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .624.15Program Arguments and the MAIN Subroutine . . . . . . . . . . . . . . . .624.16Debugging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .634.17Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .644.18Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .65Fruitful Subroutines695.1Return Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .695.2Incremental Development . . . . . . . . . . . . . . . . . . . . . . . . . . . .715.3Composition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .735.4Boolean Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .735.5A Complete Programming Language . . . . . . . . . . . . . . . . . . . . . .755.6More Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .755.7Leap of Faith . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .775.8One More Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .785.9Checking Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .795.10Multi Subroutines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .805.11Debugging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .815.12Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .825.13Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .83Iteration856.1Assignment Versus Equality . . . . . . . . . . . . . . . . . . . . . . . . . . .856.2Reassignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .866.3Updating Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .866.4The while Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .876.5Local Variables and Variable Scoping . . . . . . . . . . . . . . . . . . . . . .896.6Control Flow Statements (last, next, etc.) . . . . . . . . . . . . . . . . . . .916.7Square Roots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .936.8Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .956.9Debugging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .956.10Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .966.11Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .96
xii7ContentsStrings997.1A String is a Sequence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .997.2Common String Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . .1007.2.1String Length . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1007.2.2Searching For a Substring Within the String . . . . . . . . . . . . . . . 1007.2.3Extracting a Substring from a String . . . . . . . . . . . . . . . . . . . 1017.2.4A Few Other Useful String Functions or Methods . . . . . . . . . . . 1027.3String Traversal With a while or for Loop . . . . . . . . . . . . . . . . . . . 1047.4Looping and Counting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7.5Regular Expressions (Regexes) . . . . . . . . . . . . . . . . . . . . . . . . . 1067.6Using Regexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1077.7Building your Regex Patterns . . . . . . . . . . . . . . . . . . . . . . . . . .1097.87.91067.7.1Literal Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1097.7.2Wildcards and Character Classes . . . . . . . . . . . . . . . . . . . . .1097.7.3Quantifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1107.7.4Anchors and Assertions . . . . . . . . . . . . . . . . . . . . . . . . . .1117.7.5Alternation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1137.7.6Grouping and Capturing . . . . . . . . . . . . . . . . . . . . . . . . .1147.7.7Adverbs (a.k.a. Modifiers) . . . . . . . . . . . . . . . . . . . . . . . . .1147.7.8Exercises on Regexes . . . . . . . . . . . . . . . . . . . . . . . . . . . .115Putting It All Together . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1167.8.1Extracting Dates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1167.8.2Extracting an IP Address . . . . . . . . . . . . . . . . . . . . . . . . .117Substitutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1187.9.1The subst Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1197.9.2The s/search/replace/ Construct . . . . . . . . . . . . . . . . . . . . 1197.9.3Using Captures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1207.9.4Adverbs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1207.10Debugging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1207.11Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1227.12Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .123
Contentsxiii8Case Study: Word Play1278.1Reading from and Writing to Files . . . . . . . . . . . . . . . . . . . . . . .1278.2Reading Word Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1298.3Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1308.4Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .13098.4.1Words Longer Than 20 Characters (Solution) . . . . . . . . . . . . . . 1308.4.2Words with No “e” (Solution) . . . . . . . . . . . . . . . . . . . . . . .8.4.3Avoiding Other Letters (Solution) . . . . . . . . . . . . . . . . . . . . 1328.4.4Using Only Some Letters (Solution) . . . . . . . . . . . . . . . . . . . 1338.4.5Using All Letters of a List (Solution) . . . . . . . . . . . . . . . . . . . 1348.4.6Alphabetic Order (Solution) . . . . . . . . . . . . . . . . . . . . . . . .8.4.7Another Example of Reduction to a Previously Solved Problem . . . 1351311348.5Debugging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1368.6Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1368.7Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .136Arrays and Lists1399.1Lists and Arrays Are Sequences . . . . . . . . . . . . . . . . . . . . . . . . . 1399.2Arrays Are Mutable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .9.3Adding New Elements to an Array or Removing Some . . . . . . . . . . . 1439.4Stacks and Queues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1459.5Other Ways to Modify an Array . . . . . . . . . . . . . . . . . . . . . . . . .1469.6Traversing a List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1489.7New Looping Constructs . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1499.8Map, Filter and Reduce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1511419.8.1Reducing a List to a Value . . . . . . . . . . . . . . . . . . . . . . . . .1519.8.2The Reduction Metaoperator . . . . . . . . . . . . . . . . . . . . . . .1529.8.3Mapping a List to Another List . . . . . . . . . . . . . . . . . . . . . .1529.8.4Filtering the Elements of a List . . . . . . . . . . . . . . . . . . . . . . 1539.8.5Higher Order Functions and Functional Programming . . . . . . . . 1549.9Fixed-Size, Typed and Shaped Arrays . . . . . . . . . . . . . . . . . . . . .1559.10Multidimensional Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . .156
xivContents9.11Sorting Arrays or Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1579.12More Advanced Sorting Techniques . . . . . . . . . . . . . . . . . . . . . . 1589.13Debugging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1619.14Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1629.15Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .16210 Hashes16510.1A Hash is a Mapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .16510.2Common Operations on Hashes . . . . . . . . . . . . . . . . . . . . . . . . .16810.3Hash as a Collection of Counters . . . . . . . . . . . . . . . . . . . . . . . . 16910.4Looping and Hashes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .17010.5Reverse Lookup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .17110.6Testing for Existence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .17210.7Hash Keys Are Unique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .17310.8Hashes and Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .17410.9Memos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .17610.10 Hashes as Dispatch Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . .17810.11 Global Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .17910.12 Debugging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .18010.13 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .18010.14 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .18111 Case Study: Data Structure Selection18311.1The Ternary Conditional Operator . . . . . . . . . . . . . . . . . . . . . . .18311.2The given .11.3Subroutine Named and Optional Parameters . . . . . . . . . . . . . . . . . 185when “Switch” Statement . . . . . . . . . . . . . . . . . . . 18411.3.1 Named Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . .18611.3.2 Optional Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . .18611.4Word Frequency Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . .18711.5Random Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .18811.6Word Histogram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .18911.7Most Common Words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .191
Contentsxv11.8Optional Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .19211.9Hash Subtraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .19211.10 Constructing New Operators . . . . . . . . . . . . . . . . . . . . . . . . . .19311.11 Sets, Bags and Mixes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .19411.12 Random Words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .19611.13 Markov Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .19711.14 Data Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .19911.15 Building Your Own Data Structures . . . . . . . . . . . . . . . . . . . . . . 200II11.15.1 Linked Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .20011.15.2 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .20211.15.3 Binary Heaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .20211.16 Debugging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .20511.17 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .20711.18 Exercises: Huffman Coding . . . . . . . . . . . . . . . . . . . . . . . . . . .20711.18.1 Variable-Length Codes . . . . . . . . . . . . . . . . . . . . . . . . . . .20711.18.2 The Frequency Table . . . . . . . . . . . . . . . . . . . . . . . . . . . .20811.18.3 Building the Huffman Code . . . . . . . . . . . . . . . . . . . . . . . .209Moving Forward12 Classes and Objects21321712.1Objects, Methods and Object-Oriented Programming . . . . . . . . . . . . 21712.2Programmer-Defined Types . . . . . . . . . . . . . . . . . . . . . . . . . . .21912.3Attributes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .22012.4Creating Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .22212.5Rectangles and Object Composition . . . . . . . . . . . . . . . . . . . . . . 22412.6Instances as Return Values . . . . . . . . . . . . . . . . . . . . . . . . . . . .22612.7Inheritance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .22612.7.1 The Pixel Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .22712.7.2 The MovablePoint Class . . . . . . . . . . . . . . . . . . . . . . . . . .22812.7.3 Multiple Inheritance: Attractive, but Is It Wise? . . . . . . . . . . . . 23012.8Roles and Composition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .230
xviContents12.8.1 Classes and Roles: An Example . . . . . . . . . . . . . . . . . . . . . .23112.8.2 Role Composition and Code Reuse . . . . . . . . . . . . . . . . . . . . 23312.8.3 Roles, Classes, Objects, and Types . . . . . . . . . . . . . . . . . . . . 23412.9Method Delegation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .23512.10 Polymorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .23612.11 Encapsulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .23712.11.1 Private Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .23812.11.2 Constructing Objects with Private Attributes . . . . . . . . . . . . . . 23912.12 Interface and Implementation . . . . . . . . . . . . . . . . . . . . . . . . . .24112.13 Object-Oriented Programming: A Tale . . . . . . . . . . . . . . . . . . . . . 24212.13.1 The Fable of the Shepherd . . . . . . . . . . . . . . . . . . . . . . . . .24212.13.2 The Moral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .24312.14 Debugging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .24412.14.1 The Perl 6 Debugger . . . . . . . . . . . . . . . . . . . . . . . . . . . .24412.14.2 Getting Some Help . . . . . . . . . . . . . . . . . . . . . . . . . . . . .24412.14.3 Stepping Through the Code . . . . . . . . . . . . . . . . . . . . . . . .24512.14.4 Stopping at the Right Place with Breakpoints . . . . . . . . . . . . . . 24512.14.5 Logging Information with Trace Points . . . . . . . . . . . . . . . . . 24612.14.6 Stepping Through a Regex Match . . . . . . . . . . . . . . . . . . . . 24612.15 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .13 Regexes and Grammars24724913.1A Brief Refresher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .24913.2Declarative Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . .25013.3Captures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .25113.4Named Rules (a.k.a. Subrules) . . . . . . . . . . . . . . . . . . . . . . . . . .25213.5Grammars . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .25413.6Grammar Inheritance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .25613.7Actions Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .25713.8A grammar for Parsing JSON . . . . . . . . . . . . . . . . . . . . . . . . . .25913.8.1 The JSON Format . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .25913.8.2 Our JSON Sample . . . . . . . . . . . . . . . . . . . . . . . . . . . . .259
Contentsxvii13.8.3 Writing the JSON Grammar Step by Step . . . . . . . . . . . . . . . . 26013.913.8.4 The JSON Grammar . . . . . . . . . . . . . . . . . . . . . . . . . . . .26213.8.5 Adding Actions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .263Inheritance and Mutable Grammars . . . . . . . . . . . . . . . . . . . . . . 26513.10 Debugging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .26613.11 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .26813.12 Exercise: A Grammar for an Arithmetic Calculator . . . . . . . . . . . . . . 26914 Functional Programming in Perl14.1Higher-Order Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . .27127114.1.1 A Refresher on Functions as First-Class Objects . . . . . . . . . . . . 27114.1.2 Anonymous Subroutines and Lambdas . . . . . . . . . . . . . . . . . 27314.1.3 Closures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .14.2274List Processing and Pipeline Programming . . . . . . . . . . . . . . . . . . 27614.2.1 Feed and Backward Feed Operators . . . . . . . . . . . . . . . . . . .27714.2.2 The Reduction Metaoperator . . . . . . . . . . . . . . . . . . . . . . .27714.2.3 The Hyperoperator . . . . . . . . . . . . . . . . . . . . . . . . . . . . .27814.2.4 The Cross (X) and Zip (Z) Operators . . . . . . . . . . . . . . . . . . . 27914.314.2.5 List Operators, a Summary . . . . . . . . . . . . . . . . . . . . . . . .27914.2.6 Creating New Operators . . . . . . . . . . . . . . . . . . . . . . . . . .280Creating Your
probably be the first published books using Perl 6 (or one of the first), a powerful, expres-sive, malleable and highly extensible programming language. But this book is less about Perl 6, and more about learning how to write programs for computers. This book is intended for beginners
