Praise for Higher-Order Perl . . . As a programmer, your bookshelf is probably overflowing with books that did nothing to change the way you program . . . or think about programming. You’re going to need a completely different shelf for this book. While discussing caching techniques in Chapter 3, Mark Jason Dominus points out how a large enough increase in power can change the fundamental way you think about a technology. And that’s precisely what this entire book does for Perl. It raids the deepest vaults and highest towers of Computer Science, and transforms the many arcane treasures it finds—recursion, iterators, filters, memoization, partitioning, numerical methods, higher-order functions, currying, cutsorting, grammar-based parsing, lazy evaluation, and constraint programming—into powerful and practical tools for real-world programming tasks: file system interactions, HTML processing, database access, web spidering, typesetting, mail processing, home finance, text outlining, and diagram generation. Along the way it also scatters smaller (but equally invaluable) gems, like the elegant explanation of the difference between “scope” and “duration” in Chapter 3, or the careful exploration of how best to return error flags in Chapter 4. It even has practical tips for Perl evangelists. Dominus presents even the most complex ideas in simple, comprehensible ways, but never compromises on the precision and attention to detail for which he is so widely and justly admired. His writing is—as always—lucid, eloquent, witty, and compelling. Aptly named, this truly /is/ a Perl book of a higher order, and essential reading for every serious Perl programmer. —Damian Conway, Co-designer of Perl 6  -  -      Mark Jason Dominus AMSTERDAM • BOSTON • HEIDELBERG • LONDON NEW YORK • OXFORD • PARIS • SAN DIEGO SAN FRANCISCO • SINGAPORE • SYDNEY • TOKYO Morgan Kaufmann Publishers is an imprint of Elsevier Senior Editor Tim Cox Publishing Services Manager Simon Crump Assistant Editor Richard Camp Cover Design Yvo Riezebos Design Cover Illustration Yvo Riezebos Design Composition Cepha Imaging Pvt. Ltd. Technical Illustration Dartmouth Publishing, Inc. Copyeditor Eileen Kramer Proofreader Deborah Prato Interior Printer The Maple-Vail Book Manufacturing Group Cover Printer Phoenix Color Morgan Kaufmann Publishers is an imprint of Elsevier. 500 Sansome Street, Suite 400, San Francisco, CA 94111 This book is printed on acid-free paper. © 2005 by Elsevier Inc. All rights reserved. Designations used by companies to distinguish their products are often claimed as trademarks or registered trademarks. In all instances in which Morgan Kaufmann Publishers is aware of a claim, the product names appear in initial capital or all capital letters. Readers, however, should contact the appropriate companies for more complete information regarding trademarks and registration. No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means—electronic, mechanical, photocopying, scanning, or otherwise—without prior written permission of the publisher. Permissions may be sought directly from Elsevier’s Science & Technology Rights Department in Oxford, UK: phone: (+44) 1865 843830, fax: (+44) 1865 853333, e-mail: For Lorrie  Preface. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xv         Recursion and Callbacks . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1     . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2.1 Why Private Variables Are Important . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3     . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.4   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.5       . . . . . . . . . . . . . . . . . . . . . . 16 1.6   -  . . . . . . . . . . . . . . . . . . . . . . . 25 1.7  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 1.7.1 More Flexible Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 1.8     . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 1.8.1 Fibonacci Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 1.8.2 Partitioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35         Dispatch Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 2.1    . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 2.1.1 Table-Driven Configuration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.1.2 Advantages of Dispatch Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 2.1.3 Dispatch Table Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 2.1.4 Default Actions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 2.2  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 2.2.1 HTML Processing Revisited . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59         Caching and Memoization . . . . . . . . . . . . . . . . . . . . . . . . . 63 3.1    . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 3.2   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 3.2.1 Static Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 3.3   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 3.4  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 ix x         3.5    . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 3.5.1 Scope and Duration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 Scope . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 Duration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 3.5.2 Lexical Closure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 3.5.3 Memoization Again . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 3.6  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 3.6.1 Functions Whose Return Values Do Not Depend on Their Arguments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 3.6.2 Functions with Side Effects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 3.6.3 Functions That Return References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 3.6.4 A Memoized Clock? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 3.6.5 Very Fast Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 3.7   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 3.7.1 More Applications of User-Supplied Key Generators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 3.7.2 Inlined Cache Manager with Argument Normalizer . . . . . . . . . . . . . . . . . . . . 90 3.7.3 Functions with Reference Arguments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 3.7.4 Partitioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 3.7.5 Custom Key Generation for Impure Functions . . . . . . . . . . . . . . . . . . . . . . . 94 3.8     . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 3.8.1 Memoization of Object Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 3.9   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 3.10    . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 3.11  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 3.12     . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 3.12.1 Profiling and Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 3.12.2 Automatic Profiling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 3.12.3 Hooks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113         Iterators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 4.1  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 4.1.1 Filehandles Are Iterators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 4.1.2 Iterators Are Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 4.1.3 Other Common Examples of Iterators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 4.2   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 4.2.1 A Trivial Iterator: upto() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 Syntactic Sugar for Manufacturing Iterators . . . . . . . . . . . . . . . . . . . . . . . . . 122 4.2.2 dir_walk() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 4.2.3 On Clever Inspirations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124