Higher-Order Perl: Transforming Programs with Programs

Description:

"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)
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.

 

 

Table of Contents:

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.4.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
7.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 Mulitple 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

描述：
《Higher-Order Perl》是我在至少十年中讀過的最令人興奮、最清晰寫作、最全面和最具前瞻性的編程書籍。它是你在任何語言中編程未來的地圖。-Sean M. Burke，領先的程序員，綜合Perl存檔網絡（CPAN）。大多數Perl程序員最初接受的是C和Unix程序員的培訓，因此他們編寫的Perl程序與C程序非常相似。然而，Perl包含了許多源於其他語言（如Lisp）的功能。這些高級功能並不被大多數Perl程序員很好地理解，也很少被使用，但它們非常強大。它們可以自動化日常編程中難以以其他方式解決的任務。其中最強大的技術之一是編寫製造或修改其他函數的函數。例如，程序員可以編寫一個通用的模式或框架，根據該模式根據需要創建函數，而不是編寫十個相似的函數。多年來，Mark Jason Dominus一直致力於將函數編程技術應用於Perl。現在，Mark將這些靈活的編程方法帶給更廣泛的受眾，這些方法他在許多教程和培訓課程中已經成功教授過。

目錄：
1. 遞歸和回調
1.1 十進制轉二進制轉換
1.2 階乘
1.2.1 私有變量的重要性
1.3 河內塔
1.4 分層數據
1.5 目錄遍歷的應用和變化
1.6 函數式編程與面向對象編程
1.7 HTML
1.7.1 更靈活的選擇
1.8 遞歸失控時
1.8.1 斐波那契數列
1.8.2 分割

2. 調度表
2.1 配置文件處理
2.1.1 基於表的配置
2.1.2 調度表的優點
2.1.3 調度表策略
2.1.4 默認操作
2.2 計算器
2.2.1 HTML處理重訪

3. 緩存和記憶化
3.1 緩存修復遞歸
3.2 內聯緩存
3.2.1 靜態變量
3.3 好主意
3.4 記憶化
3.5 記憶化模塊
3.5.1 作用域和持續時間
3.5.1.1 作用域
3.5.1.2 持續時間
3.5.2 閉包
3.5.3 再次記憶化
3.6 注意事項
3.6.1 函數的返回值不依賴於其參數
3.6.2 具有副作用的函數
3.6.3 返回引用的函數
3.6.4 記憶化時鐘？
3.4.5 非常快的函數
3.7 生成密鑰
3.7.1 用戶提供的密鑰生成器的更多應用
3.7.2 具有參數規範化器的內聯緩存管理器
3.7.3 具有引用參數的函數
3.7.4 分割
3.7.5 不純函數的自定義密鑰生成
7.8 對象方法的緩存
3.8.1 對象方法的記憶化
3.9 持久緩存
3.10 記憶化的替代方案
3.11 傳教
3.12 速度的好處
3.12.1 分析和性能分析
3.12.2 自動分析
3.12.3 鉤子

4. 迭代器
4.1 簡介
4.1.1 文件處理器是迭代器
4.1.2 迭代器是對象
4.1.3 其他常見的迭代器示例
4.2 自製迭代器
4.2.1 簡單的迭代器：upto()