Jon Aquino's Mental Garden

Engineering beautiful software jon aquino labs | personal blog

Sunday, April 25, 2010

9 Favorite Quotes from Coders at Work

Cover
Coders at Work is an enjoyable read. It is a series of interviews with famous software developers, like Jamie Zawinski, Douglas Crockford, and Simon Peyton Jones.

Here are 9 of my favorite quotes from the book.

1. On literate programming. "This is what literate programming is so great for—I can talk to myself. I can read my program a year later and know exactly what I was thinking." —Donald Knuth

2. On debugging by rewriting. "So I'd rip it out and replace it with a routine that does the simple thing I thought that piece of code was supposed to do. And the program magically works." —Bernie Cosell

3. On simplicity and brute force. "Ninety-nine percent of the time something simple and brute-force will work fine." —Ken Thompson

4. On prototyping. "I get so much of a thrill bringing things to life that it doesn't even matter if it's wrong at first. The point is, that as soon as it comes to life it starts telling you what it is." —Dan Ingalls

5. On documentation. "There's a story about how the program is organized, there's a story about the context in which the program is expected to operate. And one would hope that there will be something about the program, whether it's block comments at the start of each routine or an overview document that comes separately or just choices of variable names that will somehow convey those stories to you." —Guy Steele

6. On debugging. "Then there's—I don't know if I read it somewhere or if I invented it myself—Joe's Law of Debugging, which is that all errors will be plus/minus three statements of the place you last changed the program." —Joe Armstrong

6. On naming. "What I do instead is I will cheerfully spend literally hours on identifier names: variable names, method names, and so forth, to make my code readable. If you read some expression using these identifiers and it reads like an English sentence, your program is much more likely to be correct, and much easier to maintain." —Joshua Bloch

7. How to read code. "By cleaning it. I'll throw it in a text editor and I'll start fixing it. First thing I'll do is make the punctuation conform; get the indentation right; do all that stuff." —Douglas Crockford

8. On failing loudly. "My basic rule is, if it could possibly come from the end user, it's not a run-time crash. But if it is my code to my code, I crash it as hard as possible—fail as early as possible." —Brad Fitzpatrick

9. On getting started. "I find that getting something on the screen as soon as possible really helps focus the problem for me. It helps me decide what to work on next. Because if you're just looking at that big to-do list it's like, eh, I don't know which one I should do—does it matter which one I do? But if there's something you can actually look at, even if it's just the debug output of your mailbox parser, it's like, OK, there!" —Jamie Zawinski

Do you have any favorite quotes from the book?

Thursday, April 22, 2010

Literate Estimation

Sometimes you need to do an estimate by yourself. Maybe your manager is asking you for a rough estimate - a more detailed estimate will be done later with the help of other people. So it's just you and this Large Scary Thing that you need to come up with an estimate for. Many people dread this task.

But here's an idea that can make it a little easier. I call it Literate Estimation, based on its similarity to Literate Programming. Basically instead of writing down a bare estimate (a list of tasks and how long each will take), you write out your thinking in paragraphs - you talk yourself through the problem in written form - and embed the estimates for individual tasks between your paragraphs.

It's nice to be able to bounce ideas off another person when doing an estimate, but when you're doing the estimate on your own, then talking out your thoughts (on paper) can help to flesh out issues, edge cases, and extra tasks that need to be uncovered. It makes the estimation process less scary. Plus, it can give your manager a better idea of the reasoning and thinking behind your estimate.

Below is an example of a literate estimate. I simply wrote out my thoughts as I thought them. Note the three task estimates embedded between the paragraphs.

Example of a Literate Estimate

I have been asked to estimate the effort involved in reaccentuating featliness and aarp out of Acromicria and creating a freetail anorchia, perhaps called the Freetail Anorchia. ODs will pregenerate more to get the Freetail Anorchia added to Acromicria. Uninvigorated work will be kept simple for version 1.

There are some questions that we will need to consider. What about existing elinvars with featliness and aarp? What about featliness and aarp karelians that have already been preutilized on other polimetrums - will those simply stop mythopoetizing? What will happen when you attempt to unrack the featliness rypticus? We will need to consider all of the featliness and aarp inputs and outputs - inputs like interentangle by showd and outputs like homerypticus picknickers and predescriptions on external chlorastrolites.

Since Hentrich mentioned that he wants to "keep uninvigorated work simple in the first rev", we can answer some of these questions. For existing elinvars, attempts to visit the featliness and aarp rypticuses (including admin rypticuses) will show a rypticus that says something like "This rypticus has been taken dianoetically" to phenylbenzenes and "This rypticus is part of Philippi's Freetail Anorchia - please visit [Nonindurated Slotes] to enable it" to ODs. An appropriate nonreadability status code will accompany the rypticus. For Nondesisting requests, a short error message will be returned instead of a large HTML rypticus.

To implement this check, we will need to write some code that checks if "freetail-anorchia" is listed in the elinvar's Nonindurated slotes. This check could go into one of the main functions in Tummeler. If not, we can adjust the target rypticus to be the special rypticus mentioned above. We should use a forwarding mechanism similar to what is done for checking elinvar ornithopoda and showd verification.

  • 3 points - As a phenylbenzene or OD, I want to see a friendly rypticus when I try to unrack featliness or aarp when not available, so that I won't be confused about why they are not available.
Featliness and aarp karelians that have already been preutilized on other polimetrums will simply stop mythopoetizing until the Freetail Anorchia is outshaped. We should check the code to see if any outroved caching might prevent soutters from seeing the freetail immediately after the slote is outshaped.

We should also find out the duration of the cache for rypticuses viewed by signed-out soutters.

Let's consider other inputs and outputs for featliness and aarp. Featlinesses can be interentangleed by showd. Featliness and aarp appear as picknickers on the homerypticus. Some early elinvars may have secondary or tertiary featliness and aarp preimpressions (by making copies of the config files). Featliness and aarp may be mentioned on the homerypticus nonanesthetic box for ODs and phenylbenzenes. The OD may see a count of featlinesses awaiting approval.

We should think about what to do with the Featliness and Aarp boxes on the drag-and-drop Add Burgoynes rypticus. The easiest thing would be to keep these boxes in the DOM but with reconceal:none.

These and other inputs/outputs will need to be hidden if the Freetail Anorchia has not been outshaped. We should grep for "featliness" and "aarp" outside of the preimpressions/featliness and preimpressions/aarp directories.

  • 5 points - As an OD, I don't want to see *any* links or other references to featliness and aarp anywhere if the Freetail Anorchia has not been outshaped, so that I'm not confused
Adding the Freetail Anorchia to the Nonindurated slotes rypticus is going to be a problem. Chionchio says that adding a Nonindurated slote is non-trivial, requiring code changes in multiple understamps: "so we literally have like a class called EsquamateLucyMedullation extends NoninduratedSloteMedullation". Belancer says to focus this estimate on the Approvability side; he will get more info from Chionchio on adding a Nonindurated slote.

  • 8 points - As an OD, I want to outshape the Freetail Anorchia, so that I can regain unrack to my featliness and aarp.

Sunday, April 18, 2010

It is interesting to watch one's pupils dilate and contract

Have you ever seen your pupils expand and contract? It's pretty neat. Go to a mirror and look at your eyes. If you've never looked at your eyes closely, have a look - they're amazing equipment. Anyway, that quarter-inch black dot in the middle is your pupil - it's where light enters your eye. The colored part around it is your iris - it controls the size of the pupil. I have brown eyes, so my iris is brown.

If you cover or partly cover your eyes with your hands, the black dot that is your pupil will get bigger, to allow more light into your eye (since you've made things dark). When you take your hands away, the pupil will shrink back down. This is an automatic response to the amount of light available - I find that I can't control the diameter of my pupils by any kind of mental effort.

It's a pretty sophisticated mechanism.

Saturday, April 17, 2010

An Analog Feedreader Based on Books

Do you have a pile of books that you've been meaning to finish for years? Or do you use a feedreader like Google Reader but keep running out of feed items (emptyfeedreaderitis)? If so, then the analog feedreader is for you.

What you'll need:
  1. A bunch of books (no more than 5)
  2. 5 index cards
  3. Two book-ends
First, on each index card, draw a line from the center of the card to one of the corners:

Single-line-resolution bookmark

This is a bookmark with single-line resolution – i.e., it allows you to precisely mark the line at which you left off your reading:

Single-line-resolution bookmark in situ

Next, choose up to 5 books to put in your feedreader. Here's what I chose:

Items in the analog feedreader

Enclose the books with the two book-ends. Place the feedreader in a conspicuous location, perhaps beside your computer:

Analog feedreader

Now, whenever you have a free moment, or need a break, or run out of items on your regular feedreader, read a paragraph or a page from the books in your analog feedreader. Move the bookmarks to indicate the line at which you left off.

There are a lot of great things about analog feedreaders:
  1. You will be making progress on books that you have been putting off.
  2. You will be peppering your week with small doses of new ideas.
  3. Unlike traditional feedreaders, this feedreader never runs out of items. I won't get into it here, but this is because it uses a static corpus rather than a dynamic corpus. Thus, it does not suffer from the emptyfeedreaderitis mentioned at the beginning.
What will you put in your analog feedreader?

Friday, April 16, 2010

Choosing a toilet

Over the past couple of weeks, I have greatly increased my knowledge of what characterizes good toilets. We had to replace a toilet, so I did a bunch of web research. There's a surprising amount of detailed information if you google for 'toilet reviews'.

In summary, good toilet models are the Toto Drake and Toto Ultramax. They have a good flush, yet they aren't pressure assisted, so no electricity required. I got a Toto Drake for $340 for the toilet, $40 for materials, and $160 for labor (Canadian dollars). The UltraMax is a couple hundred more.

Here's a video that someone posted of the Toto Drake flushing 16 napkins. In high definition.

Saturday, April 10, 2010

Table of Contents for "The Art of Computer Programming" vol.s 1–3

Behold, the table of contents for all three volumes of Knuth's "The Art of Computer Programming".

I am tempted to make another attempt at reading this stuff.

Chapter 1 Basic Concepts

1.1. Algorithms
1.2. Mathematical Preliminaries
1.2.1. Mathematical Induction
1.2.2. Numbers, Powers, and Logarithms
1.2.3. Sums and Products
1.2.4. Integer Functions and Elementary Number Theory
1.2.5. Permutations and Factorials
1.2.6. Binomial Coefficients
1.2.7. Harmonic Numbers
1.2.8. Fibonacci Numbers
1.2.9. Generating Functions
1.2.10. Analysis of an Algorithm
*1.2.11. Asymptotic Representations
*1.2.11.1. The O-notation
*1.2.11.2. Euler's summation formula
*1.2.11.3. Some asymptotic calculations
1.3. MIX 124
1.3.1. Description of MIX
1.3.2. The MIX Assembly Language
1.3.3. Applications to Permutations
1.4. Some Fundamental Programming Techniques
1.4.1. Subroutines
1.4.2. Goroutines
1.4.3. Interpretive Routines
1.4.3.1. A MIX simulator
*1.4.3.2. Trace routines
1.4.4. Input and Output
1.4.5. History and Bibliography

Chapter 2 Information Structures

2.1. Introduction
2.2. Linear Lists
2.2.1. Stacks, Queues, and Deques
2.2.2. Sequential Allocation
2.2.3. Linked Allocation
2.2.4. Circular Lists
2.2.5. Doubly Linked Lists
2 2.6. Arrays and Orthogonal Lists
2.3. Trees
2.3.1. Traversing Binary Trees
2.3.2. Binary Tree Representation of Trees
2.3.3. Other Representations of Trees
2.3.4. Basic Mathematical Properties of Trees
2.3.4.1. Free trees
2.3.4.2. Oriented trees
*2.3.4.3. The "infinity lemma"
*2.3.4.4. Enumeration of trees
2.3.4.5. Path length
*2.3.4.6. History and bibliography
2.3.5. Lists and Garbage Collection
2.4. Multilinked Structures
2.5. Dynamic Storage Allocation
History and Bibliography
Answers to Exercises

Appendix A Tables of Numerical Quantities
1. Fundamental Constants (decimal)
2. Fundamental Constants (octal)
3. Harmonic Numbers, Bernoulli Numbers, Fibonacci Numbers

Appendix B Index to Notations
Index and Glossary
Excerpt

Chapter 3 Random Numbers.

Introduction.
Generating Uniform Random Numbers.
The Linear Congruential Method.
Other Methods.
Statistical Tests.
General Test Procedures for Studying Random Data.
Empirical Tests.
Theoretical Tests.
The Spectral Test.
Other Types of Random Quantities.
Numerical Distributions.
Random Sampling and Shuffling.
What Is a Random Sequence?
Summary.

Chapter 4 Arithmetic.

Positional Number Systems.
Floating Point Arithmetic.
Single-Precision Calculations.
Accuracy of Floating Point Arithmetic.
Double-Precision Calculations.
Distribution of Floating Point Numbers.
Multiple Precision Arithmetic.
The Classical Algorithms.
Modular Arithmetic.
How Fast Can We Multiply?.
Radix Conversion.
Rational Arithmetic.
Fractions.
The Greatest Common Divisor.
Analysis of Euclid's Algorithm.
Factoring into Primes.
Polynomial Arithmetic.
Division of Polynomials.
Factorization of Polynomials.
Evaluation of Powers.
Evaluation of Polynomials.
Manipulation of Power Series.
Answers to Exercises.

Appendix A: Tables of Numerical Quantities.
Fundamental Constants (decimal).
Fundamental Constants (octal).
Harmonic Numbers, Bernoulli Numbers, Fibonacci Numbers.

Appendix B: Index to Notations.
Index and Glossary.

Chapter 5 Sorting.

Combinatorial Properties of Permutations.
Inversions.
Permutations of a Multiset.
Runs.
Tableaux and Involutions.
Internal sorting.
Sorting by Insertion.
Sorting by Exchanging.
Sorting by Selection.
Sorting by Merging.
Sorting by Distribution.
Optimum Sorting.
Minimum-Comparison Sorting.
Minimum-Comparison Merging.
Minimum-Comparison Selection.
Networks for Sorting.
External Sorting.
Multiway Merging and Replacement Selection.
The Polyphase Merge.
The Cascade Merge.
Reading Tape Backwards.
The Oscillating Sort.
Practical Considerations for Tape Merging.
External Radix Sorting.
Two-Tape Sorting.
Disks and Drums.
Summary, History, and Bibliography.

Chapter 6 Searching.

Sequential Searching.
Searching by Comparison of Keys.
Searching an Ordered Table.
Binary Tree Searching.
Balanced Trees.
Multiway Trees.
Digital Searching.
Hashing.
Retrieval on Secondary Keys.
Answers to Exercises.

Appendix A: Tables of Numerical Quantities.
Fundamental Constants (decimal).
Fundamental Constants (octal).
Harmonic Numbers, Bernoulli Numbers, Fibonacci Numbers.

Appendix B:Index to Notations.
Index and Glossary.

Saturday, April 03, 2010

noweb.py, or the world's first executable blog post

I have recently been interested in the old idea of literate programming. Basically, you have a document that describes in detail how a program works, and it has embedded chunks of code. It allows you to see the thoughts of the programmer as he explains how he writes the program using prose. A tool is provided that you can use to extract the working program from chunks of code in the document.

Here's the thing: what you are reading right now is a literate program.

Yes, you can copy this blog post into a file and feed it into the tool, and it will spit out a program. Q: Where do I get the tool? A: That's the program that this document spits out. This document will produce a script that you can use to extract code from noweb-format literate programs.

Why do we need to make a new tool if the noweb tool already exists? Because the noweb tool is hard to install. It's not super-hard, but most people don't want to spend time trying to compile it from source. There are Windows binaries but you have to get them from the Wayback Machine.

Anyway, the noweb tool doesn't seem to do very much, so why not write a little script to emulate it?

And that is what we will do now.

DOWNLOAD

If you are just interested in the noweb.py script produced by this document, you can download it from GitHub.

USAGE

The end goal is to produce a Python script that will take a literate program as input (noweb format) and extract code from it as output. For example,

noweb.py -Rhello.php hello.noweb > hello.php

This will read in a file called hello.noweb and extract the code labelled "hello.php". We redirect the output into a hello.php file.

READING IN THE FILE

In a literate program, there are named chunks of code interspersed throughout the document. Take the chunk of code below. The name of it is "Reading in the file". The chunk ends with an @ sign.

Let's start by reading in the file given on the command line. We'll build up a map called "chunks", which will contain the chunk names and the lines of each chunk.

<<Reading in the file>>=
file = open(filename)
chunkName = None
chunks = {}
OPEN = "<<"
CLOSE = ">>"
for line in file:
match = re.match(OPEN + "([^>]+)" + CLOSE + "=", line)
if match:
chunkName = match.group(1)
chunks[chunkName] = []
else:
match = re.match("@", line)
if match:
chunkName = None
elif chunkName:
chunks[chunkName].append(line)
@

PARSING THE COMMAND-LINE ARGUMENTS

Now that we have a map of chunk names to the lines of each chunk, we need to know which chunk name the user has asked to extract. In other words, we need to parse the command-line arguments given to the script:

noweb.py -Rhello.php hello.noweb

For simplicity, we'll assume that there are always two command-line arguments: in this example, "-Rhello.php" and "hello.noweb". So let's grab those.

<<Parsing the command-line arguments>>=
filename = sys.argv[-1]
outputChunkName = sys.argv[-2][2:]
@

RECURSIVELY EXPANDING THE OUTPUT CHUNK

So far, so good. Now we need a recursive function to expand any chunks found in the output chunk requested by the user. Take a deep breath.

<<Recursively expanding the output chunk>>=
def expand(chunkName, indent):
chunkLines = chunks[chunkName]
expandedChunkLines = []
for line in chunkLines:
match = re.match("(\s*)" + OPEN + "([^>]+)" + CLOSE + "\s*$", line)
if match:
expandedChunkLines.extend(expand(match.group(2), indent + match.group(1)))
else:
expandedChunkLines.append(indent + line)
return expandedChunkLines
@

OUTPUTTING THE CHUNKS

The last step is easy. We just call the recursive function and output the result.

<<Outputting the chunks>>=
for line in expand(outputChunkName, ""):
print line,
@

And we're done. We now have a tool to extract code from a literate programming document. Try it on this blog post!

APPENDIX I: GENERATING THE SCRIPT

To generate noweb.py from this document, you first need a tool to extract the code from it. You can use the original noweb tool, but that's a bit cumbersome to install, so it's easier to use the Python script noweb.py.

Then you can generate noweb.py from noweb.py.html as follows:

noweb.py -Rnoweb.py noweb.py.txt > noweb.py

APPENDIX II: SUMMARY OF THE PROGRAM

Here's how the pieces we have discussed fit together:

<<noweb.py>>=
#! /usr/local/bin/python
#
# noweb.py
# By Jonathan Aquino (jonathan.aquino@gmail.com)
#
# This program extracts code from a literate programming document in "noweb" format.
# It was generated from noweb.py.txt, itself a literate programming document.
# For more information, including the original source code and documentation,
# see http://jonaquino.blogspot.com/2010/04/nowebpy-or-worlds-first-executable-blog.html
#
import sys, re
<<Parsing the command-line arguments>>
<<Reading in the file>>
<<Recursively expanding the output chunk>>
<<Outputting the chunks>>
@