Beautiful code : leading programmers explain how they think

Beautiful Code......Page 1
Contents......Page 8
Foreword......Page 16
How This Book Is Organized......Page 18
Using Code Examples......Page 21
Safari® Enabled......Page 22
A Regular Expression Matcher......Page 24
The Practice of Programming......Page 25
Implementation......Page 26
Discussion......Page 27
Alternatives......Page 28
Building on It......Page 29
Conclusion......Page 31
Subversion’s Delta Editor: Interface As Ontology......Page 34
Version Control and Tree Transformation......Page 35
Expressing Tree Differences......Page 39
The Delta Editor Interface......Page 40
But Is It Art?......Page 46
Abstraction As a Spectator Sport......Page 48
Conclusions......Page 50
The Most Beautiful Code I Never Wrote......Page 52
The Most Beautiful Code I Ever Wrote......Page 53
More and More with Less and Less......Page 54
Perspective......Page 59
A Bonus Analysis......Page 60
What Is Writing?......Page 61
Conclusion......Page 62
Acknowledgments......Page 63
On Time......Page 64
Problem: Weblog Data......Page 65
Putting Regular Expressions to Work......Page 66
Content-Addressable Storage......Page 69
Time to Optimize?......Page 72
Problem: Who Fetched What, When?......Page 73
Binary Search......Page 75
Escaping the Loop......Page 77
Searching with Postings......Page 78
Searching the Web......Page 79
Conclusion......Page 80
The Role of XML Validation......Page 82
The Problem......Page 83
Version 1: The Naïve Implementation......Page 85
Version 2: Imitating the BNF Grammar O(N)......Page 86
Version 3: First Optimization O(log N)......Page 87
Version 4: Second Optimization: Don’t Check Twice......Page 89
Version 5: Third Optimization O(1)......Page 91
Version 6: Fourth Optimization: Caching......Page 95
The Moral of the Story......Page 97
Framework for Integrated Test: Beauty Through Fragility......Page 98
An Acceptance Testing Framework in Three Classes......Page 99
The Challenge of Framework Design......Page 101
An Open Framework......Page 102
How Simple Can an HTML Parser Be?......Page 103
Conclusion......Page 106
Beautiful Tests......Page 108
That Pesky Binary Search......Page 110
Introducing JUnit......Page 112
Nailing Binary Search......Page 113
Smoking Allowed (and Encouraged)......Page 114
Pushing the Boundaries......Page 115
Random Acts of Testing......Page 118
Performance Anxiety......Page 124
Conclusion......Page 125
On-the-Fly Code Generation for Image Processing......Page 128
Top Down Operator Precedence......Page 152
JavaScript......Page 153
Symbol Table......Page 154
Tokens......Page 155
Precedence......Page 156
Infix Operators......Page 157
Prefix Operators......Page 159
Assignment Operators......Page 160
Scope......Page 161
Statements......Page 163
Functions......Page 166
Array and Object Literals......Page 167
Things to Do and Think About......Page 168
The Quest for an Accelerated Population Count......Page 170
Basic Methods......Page 171
Divide and Conquer......Page 172
Other Methods......Page 174
Sum and Difference of Population Counts of Two Words......Page 175
Comparing the Population Counts of Two Words......Page 176
Counting the 1-Bits in an Array......Page 177
Applications......Page 181
Secure Communication: The Technology Of Freedom......Page 184
The Heart of the Start......Page 185
Untangling the Complexity of Secure Messaging......Page 186
Usability Is the Key......Page 188
The Foundation......Page 190
Design Goals and Decisions......Page 191
Basic System Design......Page 192
The Functioning Prototype......Page 195
Clean Up, Plug In, Rock On.........Page 196
Revamping the Mail Store......Page 197
Persistence of Decryption......Page 199
Hacking in the Himalayas......Page 200
Securing the Code......Page 201
Auditing Crypt::GPG......Page 203
The Invisible Hand Moves......Page 205
Speed Does Matter......Page 207
Hacking the Civilization......Page 208
Growing Beautiful Code in BioPerl......Page 210
BioPerl and the Bio::Graphics Module......Page 211
Example of Bio::Graphics Output......Page 212
Bio::Graphics Requirements......Page 213
Designing How the Developer Interacts with the Module......Page 215
Setting Options......Page 219
Choosing Object Classes......Page 221
Option Processing......Page 223
Code Example......Page 228
Dynamic Options......Page 229
Supporting Web Developers......Page 233
Supporting Publication-Quality Images......Page 234
Adding New Glyphs......Page 235
Conclusions and Lessons Learned......Page 237
The Design of the Gene Sorter......Page 240
The User Interface of the Gene Sorter......Page 241
Maintaining a Dialog with the User over the Web......Page 242
A Little Polymorphism Can Go a Long Way......Page 244
Filtering Down to Just the Relevant Genes......Page 247
Theory of Beautiful Code in the Large......Page 248
Conclusion......Page 251
How Elegant Code Evolves with Hardware: The Case of Gaussian Elimination......Page 252
The Effects of Computer Architectures on Matrix Algorithms......Page 253
A Decompositional Approach......Page 255
A Simple Version......Page 256
LINPACK’s DGEFA Subroutine......Page 258
LAPACK DGETRF......Page 260
Recursive LU......Page 263
ScaLAPACK PDGETRF......Page 266
Multithreading for Multi-Core Systems......Page 270
A Word About the Error Analysis and Operation Count......Page 273
Future Directions for Research......Page 274
Further Reading......Page 275
My Idea of Beautiful Code......Page 276
Introducing the CERN Library......Page 277
Outer Beauty......Page 278
Beauty in Brevity and Simplicity......Page 284
Beauty in Frugality......Page 285
Beauty in Flow......Page 288
Conclusion......Page 289
The Linux Kernel Driver Model: The Benefits of Working Together......Page 290
Humble Beginnings......Page 291
Reduced to Even Smaller Bits......Page 296
Scaling Up to Thousands of Devices......Page 299
Small Objects Loosely Joined......Page 300
Another Level of Indirection......Page 302
From Code to Pointers......Page 303
From Function Arguments to Argument Pointers......Page 305
From Filesystems to Filesystem Layers......Page 308
From Code to a Domain-Specific Language......Page 310
Multiplexing and Demultiplexing......Page 312
Layers Forever?......Page 313
Python’s Dictionary Implementation: Being All Things to All People......Page 316
Inside the Dictionary......Page 318
Special Accommodations......Page 319
The C implementation: selecting the storage function dynamically......Page 320
Collisions......Page 321
Determining the New Table Size......Page 322
Iterations and Dynamic Changes......Page 323
Acknowledgments......Page 324
Multidimensional Iterators in NumPy......Page 326
Key Challenges in N-Dimensional Array Operations......Page 327
Memory Models for an N-Dimensional Array......Page 328
Iterator Design......Page 330
Iterator Progression......Page 331
Iterator Setup......Page 332
Iterator Counter Tracking......Page 333
Iterator Structure......Page 335
Iterator Interface......Page 336
Iterator Use......Page 337
Iteration Over All But One Dimension......Page 338
Multiple Iterations......Page 339
Anecdotes......Page 340
Conclusion......Page 341
A Highly Reliable Enterprise System for NASA’s Mars Rover Mission......Page 342
The Mission and the Collaborative Information Portal......Page 343
Mission Needs......Page 344
System Architecture......Page 345
Functionality......Page 348
Service Architecture......Page 349
Reliability......Page 351
Logging......Page 352
Monitoring......Page 357
Robustness......Page 359
Hot Swapping......Page 360
Conclusion......Page 361
ERP5: Designing for Maximum Adaptability......Page 362
ERP5......Page 363
The Underlying Zope Platform......Page 365
ERP5 Project Concepts......Page 369
Coding the ERP5 Project......Page 370
Acknowledgments......Page 374
A Spoonful of Sewage......Page 376
A Motivating Example......Page 394
The MapReduce Programming Model......Page 397
Other MapReduce Examples......Page 398
Execution Overview......Page 400
Extensions to the Model......Page 403
Further Reading......Page 404
Appendix: Word Count Solution......Page 405
Beautiful Concurrency......Page 408
Bank Accounts Using Locks......Page 409
Locks Are Bad......Page 410
Side Effects and Input/Output in Haskell......Page 411
Transactions in Haskell......Page 415
Implementing Transactional Memory......Page 417
Blocking and Choice......Page 418
The Santa Claus Problem......Page 419
Reindeer and Elves......Page 420
Gates and Groups......Page 421
The Main Program......Page 423
Implementing Santa......Page 424
Compiling and Running the Program......Page 426
Conclusion......Page 427
Acknowledgments......Page 429
Syntactic Abstraction: The syntax-case Expander......Page 430
Brief Introduction to syntax-case......Page 434
Expansion Algorithm......Page 436
Representations......Page 437
Stripping Syntax Objects......Page 438
Structural Predicates......Page 439
Creating Wraps......Page 440
Identifier Resolution......Page 441
The Expander......Page 442
Core Transformers......Page 444
Comparing Identifiers......Page 446
Starting Expansion......Page 447
Example......Page 448
Conclusion......Page 451
Labor-Saving Architecture: An Object-Oriented Framework for Networked Software......Page 452
Sample Application: Logging Service......Page 454
Object-Oriented Design of the Logging Server Framework......Page 456
Understanding the Commonalities......Page 457
Accommodating Variation......Page 458
Tying It All Together......Page 460
Implementing Sequential Logging Servers......Page 462
An Iterative Logging Server......Page 463
A Reactive Logging Server......Page 464
Evaluating the Sequential Logging Server Solutions......Page 466
A Thread-per-Connection Logging Server......Page 467
A Process-per-Connection Logging Server......Page 470
Evaluating the Concurrent Logging Server Solutions......Page 472
Conclusion......Page 473
Integrating Business Partners the RESTful Way......Page 474
Exposing Services to External Clients......Page 475
Define the Service Interface......Page 476
Routing the Service Using the Factory Pattern......Page 479
Exchanging Data Using E-Business Protocols......Page 480
Parsing the XML Using XPath......Page 481
Conclusion......Page 485
Beautiful Debugging......Page 486
Debugging a Debugger......Page 487
A Systematic Process......Page 489
A Search Problem......Page 490
Finding the Failure Cause Automatically......Page 491
Delta Debugging......Page 493
Minimizing Input......Page 495
Hunting the Defect......Page 496
A Prototype Problem......Page 498
Further Reading......Page 499
Treating Code As an Essay......Page 500
When a Button Is All That Connects You to the World......Page 506
Basic Design Model......Page 507
Input Interface......Page 510
The Tree......Page 511
The Long Click......Page 512
Dynamic Tree Repopulation......Page 514
Prediction: Word Completion and Next Word......Page 516
Templates and Replace......Page 517
The Cache Implementation......Page 518
Common Words and Favorites......Page 519
The Typing Buffer, Editing, and Scrolling......Page 520
The Clipboard......Page 521
Macros......Page 522
Future Directions......Page 523
Emacspeak: The Complete Audio Desktop......Page 526
Producing Spoken Output......Page 527
Iterating on the First-Cut Implementation......Page 528
Generating Rich Auditory Output......Page 530
Augmenting Emacs to create aural display lists......Page 531
Audio-formatted output from aural display lists......Page 533
Using Aural CSS (ACSS) for Styling Speech Output......Page 534
Adding Auditory Icons......Page 535
The Calendar: Enhancing Spoken Output with Context-Sensitive Semantics......Page 537
Painless Access to Online Information......Page 539
The emacspeak-websearch Module for Task-Oriented Search......Page 540
The Web Command Line and URL Templates......Page 543
Summary......Page 545
Managing Code Complexity Over Time......Page 546
Conclusion......Page 547
Acknowledgments......Page 548
Code in Motion......Page 550
On Being “Bookish”......Page 551
Alike Looking Alike......Page 552
The Perils of Indentation......Page 553
Navigating Code......Page 554
The Tools We Use......Page 555
DiffMerge’s Checkered Past......Page 557
Further Reading......Page 559
Writing Programs for “The Book”......Page 562
Warning to Parenthophobes......Page 563
Three in a Row......Page 564
The Slippery Slope......Page 567
The Triangle Inequality......Page 568
Meandering On......Page 570
“Duh!”—I Mean “Aha!”......Page 571
Further Reading......Page 573
Afterword......Page 576
Contributors......Page 578
Index......Page 588