Higher-Order Perl book cover

Higher-Order Perl

Transforming Programs with Programs

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.

Audience
Intermediate to advanced Perl programmers

Paperback, 600 Pages

Published: March 2005

Imprint: Morgan Kaufmann

ISBN: 978-1-55860-701-9

Reviews

  • “It's well written…everyone who claims to be an expert ought to read it…these techniques allow programmers to accomplish far more than they're used to."
    —Gregory V. Wilson, Dr. Dobb's Journal, November 2005

    "It is, quite simply, one of the best books on programming I have read for a long time."—Martin Schweitzer, Computing Reviews, Association for Computing Machinery, July 2005

    "Mark Jason Dominus has hit his mark with Higher Order Perl. It is a very informative book that is a must read for Perl programmers who want to take their skills to the next level.”
    —Mark Rutz, Linux Journal, November 2005

    “Higher-Order Perl is one of the Perl books that should have a place on the bookshelf of every Perl programmer. It offers an in-depth understanding of important programming techniques and fundamental concepts. The chapter on parsing alone is worth the price of this book. I do not know a better text about parsing in Perl.”
    —Reinhard Voglmaier, Unix Review, November 2005

    “Higher-Order Perl is the most exciting, most clearly-written, most comprehensive, and most forward-looking programming book I've read in at least ten years. It's your map to the future of programming in any language."
    —Sean M. Burke, Leading Programmer, Comprehensive Perl Archive Network (CPAN)

    "There are lots of book that teach you new Perl modules or techniques. This book goes beyond that and teaches a new way to think about Perl programming.”
    —Peter Norvig, Google Inc.

    “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

    “Higher-Order Perl is a terrific book targeted at the advanced Perl programmer with a significant computer science background. The tone, content, and code make Higher-Order Perl memorable; the knowledge, wisdom, and intuition it provides make it a book any Perl programmer should aim to understand and digest in full.”.”
    —Teodor Zlatanov, Programmer, Gold Software Systems

Contents

    • Preface
    • 1. Recursion and Callbacks
      • 1.1 Decimal to Binary Conversion
      • 1.2 Factorial
        • 1.2.1 Why Private Variables are Important
      • 1.3 The Tower of Hanoi
      • 1.4 Hierarchical Data
      • 1.5 Applications and Variations of Directory Walking
      • 1.6 Functional vs. Object-Oriented Programming
      • 1.7 HTML
        • 1.7.1 More Flexible Selection
      • 1.8 When Recursion Blows Up
        • 1.8.1 Fibonacci Numbers
        • 1.8.2 Partitioning
    • 2. Dispatch Tables
      • 2.1 Configuration File Handling
        • 2.1.1 Table-driven configuration
        • 2.1.2 Advantages of Dispatch Tables
        • 2.1.3 Dispatch Table Strategies
        • 2.1.4 Default Actions
      • 2.2 Calculator
        • 2.2.1 HTML Processing Revisited
    • 3. Caching and Memoization
      • 3.1 Caching Fixes Recursion
      • 3.2 Inline Caching
        • 3.2.1 Static Variables
      • 3.3 Good Ideas
      • 3.4 Memoization
      • 3.5 The Memoize Module
        • 3.5.1 Scope and Duration
          • 3.5.1.1 Scope
          • 3.5.1.2 Duration
        • 3.5.2 Lexical Closure
        • 3.5.3 Memoization Again
      • 3.6 Caveats
        • 3.6.1 Functions whose Return Values do not Depend on their Arguments
        • 3.6.2 Functions with Side Effects
        • 3.6.3 Functions that Return References
        • 3.6.4 A Memoized Clock?
        • 3.6.5 Very Fast Functions
      • 3.7 Key Generation
        • 3.7.1 More Applications of User-Supplied Key Generators
        • 3.7.2 Inlined Cache Manager with Argument Normalizer
        • 3.7.3 Functions with Reference Arguments
        • 3.7.4 Partioning
        • 3.7.5 Custom Key Generation for Impure Functions
      • 3.8 Caching in Object Methods
        • 3.8.1 Memoization of Object Methods
      • 3.9 Persistent Caches
      • 3.10 Alternatives to Memoization
      • 3.11 Evangelism
      • 3.12 The Benefits of Speed
        • 3.12.1 Profiling and Performance Analysis
        • 3.12.2 Automatic Profiling
        • 3.12.3 Hooks
    • 4. Iterators
      • 4.1 Introduction
        • 4.1.1 Filehandles are Iterators
        • 4.1.2 Iterators are Objects
        • 4.1.3 Other Common Examples of Iterators
      • 4.2 Homemade Iterators
        • 4.2.1 A Trivial Iterator: upto()
          • 4.2.1.1 Syntactic Sugar for Manufacturing Iterators
        • 4.2.2 dir_walk()
        • 4.2.3 On Clever Inspirations
      • 4.3 Examples
        • 4.3.1 Permutations
        • 4.3.2 Genomic Sequence Generator
        • 4.3.3 Filehandle Iterators
        • 4.3.4 A Flat-File Database
          • 4.3.4.1 Improved Database
        • 4.3.5 Searching Databases Backwards
          • 4.3.5.1 A Query Package that Transforms Iterators
          • 4.3.5.2 An Iterator that Reads Files Backwards
          • 4.3.5.3 Putting it Together
        • 4.3.6 Random Number Generation
      • 4.4 Filters and Transforms
        • 4.4.1 imap()
        • 4.4.2 igrep()
        • 4.4.3 list_iterator()
        • 4.4.4 append()
      • 4.5 The Semipredicate Problem
        • 4.5.1 Avoiding the Problem
        • 4.5.2 Alternative undefs
        • 4.5.3 Rewriting Utilities
        • 4.5.4 Iterators that Return Multiple Values
        • 4.5.5 Explicit Exhaustion Function
        • 4.5.6 Four-Operation Iterators
        • 4.5.7 Iterator Methods
      • 4.6 Alternative Interfaces to Iterators
        • 4.6.1 Using foreach to Loop over more than one Array
        • 4.6.2 An Iterator with an each-like Interface
        • 4.6.3 Tied Variable Interfaces
          • 4.6.3.1 Summary of tie
          • 4.6.3.2 Tied Scalars
          • 4.6.3.3 Tied Filehandle
      • 4.7 An Extended Example: Web Spiders
        • 4.7.1 Pursuing only Interesting Links
        • 4.7.2 Referring URLs
        • 4.7.3 robots.txt
        • 4.7.4 Summary
    • 5. From Recursion to Iterators
      • 5.1 The Partition Problem Revisited
        • 5.1.1 Finding All Possible Partions
        • 5.1.2 Optimizations
        • 5.1.3 Variations
      • 5.2 How to Convert a Recursive Function to an Iterator
      • 5.3 A Generic Search Iterator
      • 5.4 Other General Techniques for Eliminating Recursion
        • 5.4.1 Tail Call Elimination
          • 5.4.1.1 Someone Else's Problem
          • 5.4.1.2 Creating Tail Calls
          • 5.4.1.3 Explicit Stacks
            • 5.4.1.3.1 Eliminating Recursion from fib()
    • 6. Infinite Streams
      • 6.1 Linked Lists
      • 6.2 Lazy Linked Lists
        • 6.2.1 A Trivial Stream: upto()
        • 6.2.2 Utilities for Streams
      • 6.3 Recursive Streams
        • 6.3.1 Memoizing Streams
      • 6.4 The Hamming Problem
      • 6.5 Regex String Generation
        • 6.5.1 Generating Strings in Order
        • 6.5.2 Regex Matching
        • 6.5.3 Cutsorting
          • 6.5.3.1 Log Files
      • 6.6 The Newton-Raphson Method
        • 6.6.1 Approximation Streams
        • 6.6.2 Derivatives
        • 6.6.3 The Tortoise and the Hare
        • 6.6.4 Finance
      • 6.7 Power Series
        • 6.7.1 Derivatives
        • 6.7.2 Other Functions
        • 6.7.3 Symbolic Computation
    • 7. Higher-Order Functions and Currying
      • 7.1 Currying
      • 7.2 Common Higher-Order Functions
        • 7.2.1 Automatic Currying
        • 7.2.2 Prototypes
          • 7.2.2.1 Prototype Problems
        • 7.2.3 More Currying
        • 7.2.4 Yet More Currying
      • 7.3 reduce() and combine()
        • 7.3.1 Boolean Operators
      • 7.4 Databases
        • 7.4.1 Operator Overloading
    • 8. Parsing
      • 8.1 Lexers
        • 8.1.1 Emulating the <> operator
        • 8.1.2 Lexers More Generally
        • 8.1.3 Chained Lexers
        • 8.1.4 Peeking
      • 8.2 Parsing in General
        • 8.2.1 Grammars
        • 8.2.2 Parsing Grammars
      • 8.3 Recursive Descent Parsers
        • 8.3.1 Very Simple Parsers
        • 8.3.2 Parser Operators
        • 8.3.3 Compound Operators
      • 8.4 Arithmetic Expressions
        • 8.4.1 A Calculator
        • 8.4.2 Left Recursion
        • 8.4.3 A Variation on star()
        • 8.4.4 Generic Operator Parsers
        • 8.4.5 Debugging
        • 8.4.6 The Finished Calculator
        • 8.4.7 Error Diagnosis and Recovery
          • 8.4.7.1 Error Recovery Parsers
          • 8.4.7.2 Exceptions
        • 8.4.8 Big Numbers
      • 8.5 Parsing Regexes
      • 8.6 Outlines
      • 8.7 Databases Query Parsing
        • 8.7.1 The Lexer
        • 8.7.2 The Parser
      • 8.8 Backtracking Parsers
        • 8.8.1 Continuations
        • 8.8.2 Parse Streams
      • 8.9 Overloading
    • 9. Declarative Programming
      • 9.1 Constraint Systems
      • 9.2 Local Propagation Networks
        • 9.2.1 Implementing a Local Propagation Network
        • 9.2.2 Problems with Local Propagation
      • 9.3 Linear Equations
      • 9.4 linogram: a drawing system
        • 9.4.1 Equations
          • 9.4.1.1 ref($base) || $base
          • 9.4.1.2 Solving Equations
          • 9.4.1.3 Constraints
        • 9.4.2 Values
          • 9.4.2.1 Constant Values
          • 9.4.2.2 Tuple Values
          • 9.4.2.3 Feature Values
          • 9.4.2.4 Intrinsic Constraints
          • 9.4.2.5 Synthetic Constraints
          • 9.4.2.6 Feature Value Methods
        • 9.4.3 Feature Types
          • 9.4.3.1 Scalar Types
          • 9.4.3.2 Type methods
        • 9.4.4 The Parser
          • 9.4.4.1 Parser Extensions
          • 9.4.4.2 %TYPES
          • 9.4.4.3 Programs
          • 9.4.4.4 Definitions
          • 9.4.4.5 Declarations
          • 9.4.4.6 Expressions
        • 9.4.5 Missing Features
      • 9.5 Conclusion
    • Index
    • Function Index

Advertisement

advert image