You are previewing Beautiful Code.
O'Reilly logo
Beautiful Code

Book Description

How do the experts solve difficult problems in software development? In this unique and insightful book, leading computer scientists offer case studies that reveal how they found unusual, carefully designed solutions to high-profile projects. You will be able to look over the shoulder of major coding and design experts to see problems through their eyes. This is not simply another design patterns book, or another software engineering treatise on the right and wrong way to do things. The authors think aloud as they work through their project's architecture, the tradeoffs made in its construction, and when it was important to break rules. This book contains 33 chapters contributed by Brian Kernighan, Karl Fogel, Jon Bentley, Tim Bray, Elliotte Rusty Harold, Michael Feathers, Alberto Savoia, Charles Petzold, Douglas Crockford, Henry S. Warren, Jr., Ashish Gulhati, Lincoln Stein, Jim Kent, Jack Dongarra and Piotr Luszczek, Adam Kolawa, Greg Kroah-Hartman, Diomidis Spinellis, Andrew Kuchling, Travis E. Oliphant, Ronald Mak, Rogerio Atem de Carvalho and Rafael Monnerat, Bryan Cantrill, Jeff Dean and Sanjay Ghemawat, Simon Peyton Jones, Kent Dybvig, William Otte and Douglas C. Schmidt, Andrew Patzer, Andreas Zeller, Yukihiro Matsumoto, Arun Mehta, TV Raman, Laura Wingerd and Christopher Seiwald, and Brian Hayes. Beautiful Code is an opportunity for master coders to tell their story. All author royalties will be donated to Amnesty International.

Table of Contents

  1. Beautiful Code
    1. SPECIAL OFFER: Upgrade this ebook with O’Reilly
    2. A Note Regarding Supplemental Files
    3. Foreword
    4. Preface
      1. How This Book Is Organized
      2. Conventions Used in This Book
      3. Using Code Examples
      4. How to Contact Us
      5. Safari® Enabled
    5. 1. A Regular Expression Matcher
      1. 1.1. The Practice of Programming
      2. 1.2. Implementation
      3. 1.3. Discussion
      4. 1.4. Alternatives
      5. 1.5. Building on It
      6. 1.6. Conclusion
    6. 2. Subversion's Delta Editor: Interface As Ontology
      1. 2.1. Version Control and Tree Transformation
      2. 2.2. Expressing Tree Differences
      3. 2.3. The Delta Editor Interface
      4. 2.4. But Is It Art?
      5. 2.5. Abstraction As a Spectator Sport
      6. 2.6. Conclusions
    7. 3. The Most Beautiful Code I Never Wrote
      1. 3.1. The Most Beautiful Code I Ever Wrote
      2. 3.2. More and More with Less and Less
      3. 3.3. Perspective
        1. 3.3.1. A Bonus Analysis
      4. 3.4. What Is Writing?
      5. 3.5. Conclusion
      6. 3.6. Acknowledgments
    8. 4. Finding Things
      1. 4.1. On Time
      2. 4.2. Problem: Weblog Data
        1. 4.2.1. Regular Expressions
        2. 4.2.2. Putting Regular Expressions to Work
        3. 4.2.3. Content-Addressable Storage
        4. 4.2.4. Time to Optimize?
      3. 4.3. Problem: Who Fetched What, When?
        1. 4.3.1. Binary Search
        2. 4.3.2. Binary Search Trade-offs
        3. 4.3.3. Escaping the Loop
      4. 4.4. Search in the Large
        1. 4.4.1. Searching with Postings
        2. 4.4.2. Ranking Results
        3. 4.4.3. Searching the Web
      5. 4.5. Conclusion
    9. 5. Correct, Beautiful, Fast (in That Order): Lessons from Designing XML Verifiers
      1. 5.1. The Role of XML Validation
      2. 5.2. The Problem
      3. 5.3. Version 1: The Naïve Implementation
      4. 5.4. Version 2: Imitating the BNF Grammar O(N)
      5. 5.5. Version 3: First Optimization O(log N)
      6. 5.6. Version 4: Second Optimization: Don't Check Twice
      7. 5.7. Version 5: Third Optimization O(1)
      8. 5.8. Version 6: Fourth Optimization: Caching
      9. 5.9. The Moral of the Story
    10. 6. Framework for Integrated Test: Beauty Through Fragility
      1. 6.1. An Acceptance Testing Framework in Three Classes
      2. 6.2. The Challenge of Framework Design
      3. 6.3. An Open Framework
      4. 6.4. How Simple Can an HTML Parser Be?
      5. 6.5. Conclusion
    11. 7. Beautiful Tests
      1. 7.1. That Pesky Binary Search
      2. 7.2. Introducing JUnit
      3. 7.3. Nailing Binary Search
        1. 7.3.1. Smoking Allowed (and Encouraged)
        2. 7.3.2. Pushing the Boundaries
        3. 7.3.3. Random Acts of Testing
        4. 7.3.4. Performance Anxiety
      4. 7.4. Conclusion
    12. 8. On-the-Fly Code Generation for Image Processing
    13. 9. Top Down Operator Precedence
      1. 9.1. JavaScript
      2. 9.2. Symbol Table
      3. 9.3. Tokens
      4. 9.4. Precedence
      5. 9.5. Expressions
      6. 9.6. Infix Operators
      7. 9.7. Prefix Operators
      8. 9.8. Assignment Operators
      9. 9.9. Constants
      10. 9.10. Scope
      11. 9.11. Statements
      12. 9.12. Functions
      13. 9.13. Array and Object Literals
      14. 9.14. Things to Do and Think About
    14. 10. The Quest for an Accelerated Population Count
      1. 10.1. Basic Methods
      2. 10.2. Divide and Conquer
      3. 10.3. Other Methods
      4. 10.4. Sum and Difference of Population Counts of Two Words
      5. 10.5. Comparing the Population Counts of Two Words
      6. 10.6. Counting the 1-Bits in an Array
      7. 10.7. Applications
    15. 11. Secure Communication: The Technology Of Freedom
      1. 11.1. The Heart of the Start
      2. 11.2. Untangling the Complexity of Secure Messaging
      3. 11.3. Usability Is the Key
      4. 11.4. The Foundation
        1. 11.4.1. Design Goals and Decisions
        2. 11.4.2. Basic System Design
      5. 11.5. The Test Suite
      6. 11.6. The Functioning Prototype
      7. 11.7. Clean Up, Plug In, Rock On…
        1. 11.7.1. Revamping the Mail Store
        2. 11.7.2. Persistence of Decryption
      8. 11.8. Hacking in the Himalayas
        1. 11.8.1. Securing the Code
        2. 11.8.2. Auditing Crypt::GPG
      9. 11.9. The Invisible Hand Moves
      10. 11.10. Speed Does Matter
      11. 11.11. Communications Privacy for Individual Rights
      12. 11.12. Hacking the Civilization
    16. 12. Growing Beautiful Code in BioPerl
      1. 12.1. BioPerl and the Bio::Graphics Module
        1. 12.1.1. Example of Bio::Graphics Output
        2. 12.1.2. Bio::Graphics Requirements
      2. 12.2. The Bio::Graphics Design Process
        1. 12.2.1. Designing How the Developer Interacts with the Module
        2. 12.2.2. Setting Options
        3. 12.2.3. Choosing Object Classes
        4. 12.2.4. Option Processing
        5. 12.2.5. Code Example
        6. 12.2.6. Dynamic Options
      3. 12.3. Extending Bio::Graphics
        1. 12.3.1. Supporting Web Developers
        2. 12.3.2. Supporting Publication-Quality Images
        3. 12.3.3. Adding New Glyphs
      4. 12.4. Conclusions and Lessons Learned
    17. 13. The Design of the Gene Sorte
      1. 13.1. The User Interface of the Gene Sorter
      2. 13.2. Maintaining a Dialog with the User over the Web
      3. 13.3. A Little Polymorphism Can Go a Long Way
      4. 13.4. Filtering Down to Just the Relevant Genes
      5. 13.5. Theory of Beautiful Code in the Large
      6. 13.6. Conclusion
    18. 14. How Elegant Code Evolves with Hardware The Case of Gaussian Elimination
      1. 14.1. The Effects of Computer Architectures on Matrix Algorithms
      2. 14.2. A Decompositional Approach
      3. 14.3. A Simple Version
      4. 14.4. LINPACK's DGEFA Subroutine
      5. 14.5. LAPACK DGETRF
      6. 14.6. Recursive LU
      7. 14.7. ScaLAPACK PDGETRF
      8. 14.8. Multithreading for Multi-Core Systems
      9. 14.9. A Word About the Error Analysis and Operation Count
      10. 14.10. Future Directions for Research
      11. 14.11. Further Reading
    19. 15. The Long-Term Benefits of Beautiful Design
      1. 15.1. My Idea of Beautiful Code
      2. 15.2. Introducing the CERN Library
      3. 15.3. Outer Beauty
      4. 15.4. Inner Beauty
        1. 15.4.1. Beauty in Brevity and Simplicity
        2. 15.4.2. Beauty in Frugality
        3. 15.4.3. Beauty in Flow
      5. 15.5. Conclusion
    20. 16. The Linux Kernel Driver Model: The Benefits of Working Together
      1. 16.1. Humble Beginnings
      2. 16.2. Reduced to Even Smaller Bits
      3. 16.3. Scaling Up to Thousands of Devices
      4. 16.4. Small Objects Loosely Joined
    21. 17. Another Level of Indirection
      1. 17.1. From Code to Pointers
      2. 17.2. From Function Arguments to Argument Pointers
      3. 17.3. From Filesystems to Filesystem Layers
      4. 17.4. From Code to a Domain-Specific Language
      5. 17.5. Multiplexing and Demultiplexing
      6. 17.6. Layers Forever?
    22. 18. Python's Dictionary Implementation: Being All Things to All People
      1. 18.1. Inside the Dictionary
      2. 18.2. Special Accommodations
        1. 18.2.1. A Special-Case Optimization for Small Hashes
        2. 18.2.2. When Special-Casing Is Worth the Overhead
          1. 18.2.2.1. The Java implementation: another special-case optimization
          2. 18.2.2.2. The C implementation: selecting the storage function dynamically
      3. 18.3. Collisions
      4. 18.4. Resizing
        1. 18.4.1. Determining the New Table Size
        2. 18.4.2. A Memory Trade-Off That's Worth It: The Free List
      5. 18.5. Iterations and Dynamic Changes
      6. 18.6. Conclusion
      7. 18.7. Acknowledgments
    23. 19. Multidimensional Iterators in NumPy
      1. 19.1. Key Challenges in N-Dimensional Array Operations
      2. 19.2. Memory Models for an N-Dimensional Array
      3. 19.3. NumPy Iterator Origins
      4. 19.4. Iterator Design
        1. 19.4.1. Iterator Progression
        2. 19.4.2. Iterator Termination
        3. 19.4.3. Iterator Setup
        4. 19.4.4. Iterator Counter Tracking
        5. 19.4.5. Iterator Structure
      5. 19.5. Iterator Interface
      6. 19.6. Iterator Use
        1. 19.6.1. Iteration Over All But One Dimension
        2. 19.6.2. Multiple Iterations
        3. 19.6.3. Anecdotes
      7. 19.7. Conclusion
    24. 20. A Highly Reliable Enterprise System for NASA's Mars Rover Mission
      1. 20.1. The Mission and the Collaborative Information Portal
      2. 20.2. Mission Needs
      3. 20.3. System Architecture
      4. 20.4. Case Study: The Streamer Service
        1. 20.4.1. Functionality
        2. 20.4.2. Service Architecture
      5. 20.5. Reliability
        1. 20.5.1. Logging
        2. 20.5.2. Monitoring
      6. 20.6. Robustness
        1. 20.6.1. Dynamic Reconfiguration
        2. 20.6.2. Hot Swapping
      7. 20.7. Conclusion
    25. 21. ERP5: Designing for Maximum Adaptability
      1. 21.1. General Goals of ERP
      2. 21.2. ERP5
      3. 21.3. The Underlying Zope Platform
      4. 21.4. ERP5 Project Concepts
      5. 21.5. Coding the ERP5 Project
      6. 21.6. Conclusion
        1. 21.6.1. Acknowledgments
    26. 22. A Spoonful of Sewage
    27. 23. Distributed Programming with MapReduce
      1. 23.1. A Motivating Example
      2. 23.2. The MapReduce Programming Model
      3. 23.3. Other MapReduce Examples
      4. 23.4. A Distributed MapReduce Implementation
        1. 23.4.1. Execution Overview
      5. 23.5. Extensions to the Model
      6. 23.6. Conclusion
      7. 23.7. Further Reading
      8. 23.8. Acknowledgments
      9. 23.9. Appendix: Word Count Solution
    28. 24. Beautiful Concurrency
      1. 24.1. A Simple Example: Bank Accounts
        1. 24.1.1. Bank Accounts Using Locks
        2. 24.1.2. Locks Are Bad
      2. 24.2. Software Transactional Memory
        1. 24.2.1. Side Effects and Input/Output in Haskell
        2. 24.2.2. Transactions in Haskell
        3. 24.2.3. Implementing Transactional Memory
        4. 24.2.4. Blocking and Choice
        5. 24.2.5. Summary of Basic STM Operations
      3. 24.3. The Santa Claus Problem
        1. 24.3.1. Reindeer and Elves
        2. 24.3.2. Gates and Groups
        3. 24.3.3. The Main Program
        4. 24.3.4. Implementing Santa
        5. 24.3.5. Compiling and Running the Program
      4. 24.4. Reflections on Haskell
      5. 24.5. Conclusion
      6. 24.6. Acknowledgments
    29. 25. Syntactic Abstraction: The syntax-case Expander
      1. 25.1. Brief Introduction to syntax-case
      2. 25.2. Expansion Algorithm
        1. 25.2.1. Representations
        2. 25.2.2. Producing Expander Output
        3. 25.2.3. Stripping Syntax Objects
        4. 25.2.4. Syntax Errors
        5. 25.2.5. Structural Predicates
        6. 25.2.6. Creating Wraps
        7. 25.2.7. Manipulating Environments
        8. 25.2.8. Identifier Resolution
        9. 25.2.9. The Expander
        10. 25.2.10. Core Transformers
        11. 25.2.11. Parsing and Constructing Syntax Objects
        12. 25.2.12. Comparing Identifiers
        13. 25.2.13. Conversions
        14. 25.2.14. Starting Expansion
      3. 25.3. Example
      4. 25.4. Conclusion
    30. 26. Labor-Saving Architecture: An Object-Oriented Framework for Networked Software
      1. 26.1. Sample Application: Logging Service
      2. 26.2. Object-Oriented Design of the Logging Server Framework
        1. 26.2.1. Understanding the Commonalities
        2. 26.2.2. Accommodating Variation
        3. 26.2.3. Tying It All Together
      3. 26.3. Implementing Sequential Logging Servers
        1. 26.3.1. An Iterative Logging Server
        2. 26.3.2. A Reactive Logging Server
        3. 26.3.3. Evaluating the Sequential Logging Server Solutions
      4. 26.4. Implementing Concurrent Logging Servers
        1. 26.4.1. A Thread-per-Connection Logging Server
        2. 26.4.2. A Process-per-Connection Logging Server
        3. 26.4.3. Evaluating the Concurrent Logging Server Solutions
      5. 26.5. Conclusion
    31. 27. Integrating Business Partners the RESTful Way
      1. 27.1. Project Background
      2. 27.2. Exposing Services to External Clients
        1. 27.2.1. Define the Service Interface
      3. 27.3. Routing the Service Using the Factory Pattern
      4. 27.4. Exchanging Data Using E-Business Protocols
        1. 27.4.1. Parsing the XML Using XPath
        2. 27.4.2. Assembling the XML Response
      5. 27.5. Conclusion
    32. 28. Beautiful Debugging
      1. 28.1. Debugging a Debugger
      2. 28.2. A Systematic Process
      3. 28.3. A Search Problem
      4. 28.4. Finding the Failure Cause Automatically
      5. 28.5. Delta Debugging
      6. 28.6. Minimizing Input
      7. 28.7. Hunting the Defect
      8. 28.8. A Prototype Problem
      9. 28.9. Conclusion
      10. 28.10. Acknowledgments
      11. 28.11. Further Reading
    33. 29. Treating Code As an Essay
    34. 30. When a Button Is All That Connects You to the World
      1. 30.1. Basic Design Model
      2. 30.2. Input Interface
        1. 30.2.1. The Tree
        2. 30.2.2. The Long Click
        3. 30.2.3. Dynamic Tree Repopulation
        4. 30.2.4. Simple Typing
        5. 30.2.5. Prediction: Word Completion and Next Word
        6. 30.2.6. Templates and Replace
        7. 30.2.7. The Cache Implementation
        8. 30.2.8. Common Words and Favorites
        9. 30.2.9. Retracing Paths
        10. 30.2.10. The Typing Buffer, Editing, and Scrolling
        11. 30.2.11. The Clipboard
        12. 30.2.12. Searching
        13. 30.2.13. Macros
      3. 30.3. Efficiency of the User Interface
      4. 30.4. Download
      5. 30.5. Future Directions
    35. 31. Emacspeak: The Complete Audio Desktop
      1. 31.1. Producing Spoken Output
      2. 31.2. Speech-Enabling Emacs
        1. 31.2.1. A Simple First-Cut Implementation
        2. 31.2.2. Iterating on the First-Cut Implementation
        3. 31.2.3. A Brief advice Tutorial
        4. 31.2.4. Generating Rich Auditory Output
          1. 31.2.4.1. Audio formatting using voice-lock
          2. 31.2.4.2. Augmenting Emacs to create aural display lists
          3. 31.2.4.3. Audio-formatted output from aural display lists
        5. 31.2.5. Using Aural CSS (ACSS) for Styling Speech Output
        6. 31.2.6. Adding Auditory Icons
        7. 31.2.7. Producing Auditory Icons While Speaking Content
        8. 31.2.8. The Calendar: Enhancing Spoken Output with Context-Sensitive Semantics
      3. 31.3. Painless Access to Online Information
        1. 31.3.1. Basic HTML with Emacs W3 and Aural CSS
        2. 31.3.2. The emacspeak-websearch Module for Task-Oriented Search
        3. 31.3.3. The Web Command Line and URL Templates
        4. 31.3.4. The Advent of Feed Readers
      4. 31.4. Summary
        1. 31.4.1. Managing Code Complexity Over Time
        2. 31.4.2. Conclusion
      5. 31.5. Acknowledgments
    36. 32. Code in Motion
      1. 32.1. On Being "Bookish"
      2. 32.2. Alike Looking Alike
      3. 32.3. The Perils of Indentation
      4. 32.4. Navigating Code
      5. 32.5. The Tools We Use
      6. 32.6. DiffMerge's Checkered Past
      7. 32.7. Conclusion
      8. 32.8. Acknowledgments
      9. 32.9. Further Reading
    37. 33. Writing Programs for "The Book"
      1. 33.1. The Nonroyal Road
      2. 33.2. Warning to Parenthophobes
      3. 33.3. Three in a Row
      4. 33.4. The Slippery Slope
      5. 33.5. The Triangle Inequality
      6. 33.6. Meandering On
      7. 33.7. "Duh!"—I Mean "Aha!"
      8. 33.8. Conclusion
      9. 33.9. Further Reading
    38. A. Afterword
    39. B. Contributors
    40. Colophon
    41. SPECIAL OFFER: Upgrade this ebook with O’Reilly