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, KarlFogel, 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 PiotrLuszczek, Adam Kolawa, Greg Kroah-Hartman, Diomidis Spinellis, AndrewKuchling, Travis E. Oliphant, Ronald Mak, Rogerio Atem de Carvalho andRafael Monnerat, Bryan Cantrill, Jeff Dean and Sanjay Ghemawat, SimonPeyton Jones, Kent Dybvig, William Otte and Douglas C. Schmidt, AndrewPatzer, 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.

Publisher resources

View/Submit Errata

Table of contents

  1. Dedication
  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. Copyright

Product information

  • Title: Beautiful Code
  • Author(s): Andy Oram, Greg Wilson
  • Release date: June 2007
  • Publisher(s): O'Reilly Media, Inc.
  • ISBN: 9780596510046