Moserware

Just Enough MBA to Be a Programmer

2009-07-20T08:00:00.003-04:00

There's that awkward moment in your software development life when you realize that most of the people in your company aren't programmers. Scanning your address book reveals Marketing, Sales, Accounting, Human Resources, and yes, the "business people" with their Masters of Business Administration (MBAs).

I've always been curious about what MBAs really do. In my weaker moments, I've even thought that the only reason people got an MBA was to demand a higher salary or to "move up the corporate ladder" into some management job. What did these MBA ninjas actually learn in school? Would having an MBA help me better understand how I affected my company's bottom line? Although I had the curiosity, I never acted on it. This changed when another programmer recommended that I read The Ten-Day MBA by Steven Silbiger.

Sure, I knew that no one would anoint me with a real MBA at the end of the book any more than watching MIT lectures online would make me an MIT grad. Besides, going to a nice MBA school is more about being around other motivated people and professors. The real value in having an MBA is in applying the concepts, not the concepts themselves.

Disclaimers aside, I was determined to read the book and take notes on what a programmer should know about an MBA.

Day 1 - Marketing

Every developer painfully learns that technology doesn't win on its own. At best, it just gives you a shot at marketing. Marketing is proof that software doesn't sell itself, no matter how good it is.

A software company might have a Marketing Requirements Document (MRD) that outlines what the next version will contain. This usually is the result of a standard marketing analysis that the book outlined:

Consumer Analysis - Who are they? What do they want? How many different segments of people do you have? Is the buyer of your product different than the user? (The book gives the example that women buy the majority of men's socks and underwear, thus it's good to market appropriately).
Market Analysis - How big is your target market? Is it new? Is it growing? Where is the product in the life cycle?
Competitive Analysis - How do your Strengths, Weaknesses, Opportunities, and Threats (SWOTs) compare to your competition?
Distribution Analysis - What "channels" does your company use to reach your customer? Who are the intermediate players (e.g. the Apple Store, Amazon.com, etc)? What cuts do they take? What are their motivations?
Plan the Marketing Mix - How will you differentiate your products? How will you place it, promote it, and price it?
Determine the Economics - How long will it take before you break even? What are your fixed costs vs. margin costs? (Thankfully software has a low marginal cost)
Revise - Tweak and repeat as needed.

One big marketing theme is to "own a word in the consumer's mind":

If you establish one benefit in the consumer's mind, the consumer may attribute other positives as well to your product. FedEx means "overnight delivery." Only one company can own a word and it is tough to change it once it's established... The easiest way to own a word is to be first. Consumers tend to stick with products that work for them. Kleenex cleans runny noses. p.26

This explains why your family still uses MapQuest despite your repeated attempts to show them how much better Google Maps is. It's also helpful if your product name matches what it does. "Drano" is easier to remember than a "Web 2.0" name like Qoop.

I was surprised to learn that the popular online advertising term Cost per Thousand (CPM), is a relatively old term that has long existed in print media. In general, the more targeted a group is, the higher the CPM is. This explains why a programming ad on Stack Overflow can probably fetch a better CPM than the same ad on a site like Pandora, even though programmers use both.

Marketing people typically have their reasons for doing things that frustrate us. For example, if your software will take a long time to get through a distribution channel or marketing foresees a long customer buying process, they might begin to "market" your code long before a beta is available with the belief that it'll hopefully be read by the time the customer is ready to buy.

Sometimes marketing has to make an extreme choice. When GTE faced rebuilding its tarnished brand in the 1990's, it was probably a clever marketing person who suggested that they give up on fixing their brand name and re-brand themselves as Verizon.

Despite all the good advice, I was disappointed by the book's lack of coverage of the Apple/BMW style of "marketing" the engineering department can do by creating a remarkable product. Creating a product that allows users to quickly jump over the "suck threshold" is just one example where a programmer can make a tremendous "marketing" contribution.

Day 2 - Ethics

Ethics seems easy to understand: "Do to others as you would have them do to you." The hard part is realizing how the "others" are affected by your actions. Others include customers, executives, shareholders, suppliers, employees (and their families), the government, the planet, and the "future generations."

Unfortunately, when simplicity is lost, Sarbanes-Oxley Acts are found.

Day 3 - Accounting

In theory, accounting is simple. Just answer these questions about your entity/business:

What does a company own?
How much does a company owe others?
How well did a company's operations perform?
How does the company get the cash to fund itself? - p.72

If you get nothing else out of accounting, know how to read a balance sheet. Although Microsoft CEO Steve Ballmer dropped out of Stanford's MBA program to become employee #24, he knew balance sheets were important:

In 1980, I came in to "be a business person" whatever that meant. Didn't know much. Frankly all I'd ever really done is interview for jobs and market brownie mix. I wasn't exactly well credentialed. I'd taken the first year at Stanford Business School so I can read a balance sheet -- that was pretty important. We didn't have that much money back then so there wasn't much to read. But anyway those lessons were important.

Balance sheets are simple to follow:

As the name implies, the balance sheet is a "balance" sheet. The fundamental equation that rules over accounting balance is:
Assets (A) = Liabilities (L) + Owners' Equity (OE)
What you own (assets) equals the total of what you borrowed (liabilities) and what you have invested (equity) to pay for it. This equation or "identity" explains everything that happens in the accounting records of a company over time. Remember it! - p.83

For example, your work computer is a company asset (which explains the "asset" tag on it). Your company created an equal liability to pay for it. When your company started, the founders gave up some of their money to increase the new company's cash assets (left side) in exchange for stock in the company (right side).

For example, we can read Google's balance sheet for the first quarter of 2009 and see:

Assets = $33.51 Billion
Liabilities = $3.66 Billion
Owner Equity = $29.85 Billion (which includes $14.98 Billion in "retained earnings" that Google is keeping for growth rather than giving it back to the owners of its 315.75 million shares)

Sure enough, everything "balances":

From basic data, we can derive a bunch of helpful ratios to see how healthy Google is:

Liquidity/Current Ratio = (Current Assets / Current Liabilities) = 33.51 / 3.66 = 9.14 (Greater than 1 means there's room to pay for liabilities)
Financial Leverage = (Total Liabilities + Owners' Equity) / OE = (3.66 + 29.85) / 29.85 = 1.12 (Greater than 2 indicates a company is using a lot of debt to operate)
Return on Equity = (Net Income / Owners' Equity) = 1.42 / 29.85 = 4.77% (Which indicates how efficiently the company is using shareholder equity)
... and many more ...

Day 4 - Organizational Behavior

The whole purpose of Organizational Behavior (OB) is to get you to think before you act around people. You want to motivate people? OB has an equation for that:

Motivation = Expectation of Work will lead to Performance * Expectation Performance will lead to Reward * Value of Reward.

Feel free to tweak the variables as you see fit. You can Manage by Objective (MBO) where you set goals and then get out of the way or you can Manage by Walking Around (MBWA) where you play a more active role in day-to-day execution. The best choice depends on your environment and culture. You might need to mix the two. Remember that we humans are delicate creatures with our own wants and desires. Be careful.

Day 5 - Quantitative Analysis

Quantitative Analysis (QA) explains why Excel has so many functions that I'd never heard of. A core idea is that "a dollar today is worth more than a dollar received in the future." (p.173).

Imagine that someone promises to pay you a dollar in a year if you give them money now. What is that worth to you today? Obviously, it matters on how much you trust them to pay you back. The more you trust them, the more you're willing to give them now. Similarly, the less you trust them, the more you might "discount" that dollar in the future because they're tying up money that could be used for better investments. This is called the "discount" or "hurdle" rate. Having a 10% discount rate means that the dollar in the future has a net present value of $0.91 today:

$1 * (1 + 10%)^-1 = $0.91

This simple idea has lots of consequences. For example, let's oversimplify things and say that you can spend $2,000 today to buy and maintain a server that will last for 3 years or you can lock in a price with Amazon for that same server for $800 a year for the same 3 years. A naïve person would just see that $2000 is less than $2400, but a QA person that assigns a 10% discount rate would see:

... and come to the conclusion that it's about $10 cheaper, in today's dollars, to have Amazon maintain the server.

You can also do the inverse calculation. Assume you're Amazon and that server costs you $1800 today and you can get someone to pay you $800 a year for it for 3 years. What is your internal rate of return for this investment?

Here we see an internal rate of return of about 16% on the server.

We could also use the time value of money to include valuing users. Early adopters of eBay and Twitter were worth more per user than late adopters because the early ones were more likely to tell their friends who hadn't used the service and thus attract more new people.

Day 6 - Finance

Finance blends time, money, and risk.

To start, a business needs a structure that gives it some capital. Popular options include:

Sole Proprietorships - An individual or a married couple. You are effectively your business. All earnings are treated as personal income and taxed appropriately. You take in all the profits but also have unlimited liability. You can't divide the company up. It's simple, but the downside is that it makes it hard to raise money.
Partnerships - Involves more people than a proprietorship. Several people come together and can be general partners (each having unlimited liability) or limited partners (liable up to the investment). As a partner, you pay taxes on your percentage of the business's income on your personal taxes.
Corporations - Effectively you give birth to a new legal entity that is distinct from the shareholders. Most large companies are "C Corporations" and have a double taxation issue where the corporation's income is taxed and the dividends it issues to shareholders are taxed as well. If you have a smaller company with fewer than 100 shareholders, you may qualify for "S Corporation" status. S Corporations usually don't pay income tax and instead rely on shareholders to pay the associated tax on their percentage of the income. This tends to give S Corporations the legal liability benefit of corporation status and the single taxation benefit of partnerships.

Corporations issue stock to raise money. Stock entitles the holder to a residual claim on earnings and assets after other debt obligations have been met. One obvious question is "what's a good stock price?" This has a lot of factors, such as a company's growth potential and the company's earnings. Popular metrics include a company's ratio of its stock price divided by its earnings (P/E ratio). Higher P/E ratios tend to indicate that shareholders have higher expectations the company will grow and eventually make more money in the future. Some examples:

Company	P/E Ratio
Google	31.47
Microsoft	13.98
Amazon.com	54.98

After you raised some capital, you should carefully think how you'll spend it. There are many ways to do this. The Payback Period Method has you calculate how long it'll take to recover your investment. The shorter the payback period, the less risky the investment is. For example, adding RAM is so cheap that the productivity boost has a short payback period. In contrast, completely rewriting a huge codebase might have put your company out of business before you get your money back.

Another approach is to use the Net Present Value Method to see how much the investment will return over its lifetime in terms of today's dollars. Once you determine the discount factor to reflect the risk, you only consider investments that have a positive Net Present Value.

Day 7 - Operations

Operations is about making stuff. Popular operations guys include Frederick Taylor from the late 1800's who is famous for breaking up tasks into small pieces and walking around factories with a stopwatch to find the "one right way" of doing them. Elton Mayo's bold claim was that caring about your employees mattered. You could even make terrible working conditions if the employees were otherwise treated well and felt important.

Although some MBAs might use some programming techniques like optimizing flow-charts to improve operations, it's more likely to see factory techniques used when managing programmers. Oversimplifying things, software development is a factory that turns capital into code. To this end, you'll often see popular manufacturing processes like Toyota's Kanban method of using visual cards to control workflow making their way into our world as "new" or "agile" software methodologies.

Day 8 - Economics

Economics is the magic that allows me to write software in exchange for steak burritos. As Adam Smith realized, society as a whole becomes "wealthier" when we seek division of labor to specialize and do something well rather than trying to do everything ourselves poorly.

At a micro level, economics is a simple matter of supply equals demand. When you look at the larger/macro economies, more complicated equations pop up like this one:

Money * Velocity = Price Level * Real Gross National Product

This equation shows that it's important that money is moving around (e.g. isn't hidden under your mattress) and that prices are stable or have reasonable growth.

One of the best things about the economics of software is that it has really low marginal costs (e.g. the cost to copy it). With processors, bandwidth, and storage all roughly following Moore's Law exponential curves, the capacity is doubling every 18 - 24 months which implies that the cost for a fixed amount is falling by half over the same period.

As Chris Anderson points out in his book Free, it can sometimes makes sense to round these increasingly lower marginal costs down to zero and make money in different ways such as advertising or selling complements. It's hard to find other industries that have as many economic freedoms as software.

Day 9 - Strategy

Strategy should be simple: have a remarkable product that people want. Bad things happen if you don't do this. It's especially helpful if you have a cash cow you can milk for lots of money to fund new initiatives. For example, Google makes so much money from ads that it can have this strategy:

Revenue = Amount of Web Pages Viewed

Google's strategy of getting you to view lots of pages (which conveniently have Google ads on them) explains a lot of what it does. From wanting to speed up the web, to making a free phone OS, to creating a ton of free services to keep you hooked on the web. Google really doesn't care what you do so long as you enjoy it and take in the targeted ads.

The book tended to focus on more traditional forms of strategy such as "cost leadership", "differentiation", and "focus on the customer" as well as applying lessons from the famous prisoner's dilemma. I acknowledge that these are important as well, but I think that at its core, strategy can be simple.

Day 10 - Minicourses

The book ended with "minicourses" in areas relevant to business such as:

Property (real estate, patents, copyright, etc)
Leadership (e.g. schools want to create 'leaders' because they'll be better future donors).

Although those were interesting, the section I enjoyed the most was on business law.

In our jobs, we often bump into legal matters. We face End User License Agreements (EULAs) and Non-Disclosure Agreements (NDAs) that we rarely read and often don't fully understand. It was interesting to see any proper contract requires the following four conditions to be valid:

Capacity of Parties - Parties must have legal authorization and be mentally capable to enter into the agreement.
Mutual Agreement (Assent) or Meeting of the Minds - There must be a valid offer and an acceptance.
Consideration Given - Value must be given for the promise to be enforceable.
Legality - You can't enforce a contract dealing with illegal goods or actions.

When bad things happen, it can sometimes escalate to a "legal action" which has a standard procedure involving steps you sometimes hear in the news:

Jurisdiction - For a court to hear a case, it must have "jurisdiction" to hear the case and power to bind the parties the decision.
Pleadings - The paperwork to start the trial process. The plaintiff (p) files a complaint asserting that the defendant (?) has done something wrong and requests a punishment or remedy.
Discovery - Lawyers gather witnesses and evidence before a trial. Each side is allowed to see the evidence held by the other side.
Pretrial Conference - The lawyers and judge try to focus the case on the most important issues. This is also good time for out-of-court settlements if possible.
Trial - Occurs before the court. The jury decides the factual disputes. The case can be thrown out by the judge with a "summary judgment" if it has no merit.
Jury Instruction by the Judge and the Verdict - The judge instructs the jury about the relevant law involved and the jury makes its decision about the facts and penalty within its authority.
Posttrial Motions - Options include asking for a retrial if an error of law or procedure occurred (e.g. jury misconduct).
Appeal - Each party in a lawsuit is entitled to one appeal at an appellate court where they can file a written brief with arguments for a new trial.
Secure or Enforce the Judgment - Send the person to jail and/or collect money.

While the short overview was intriguing, it enforced my belief that it's important to have an attorney or a lawyer when it comes to the legal matters. At the very least, they usually have malpractice insurance if things go really bad.

Conclusion

The Ten Day MBA helped me move from being unconsciously incompetent about business administration to becoming consciously incompetent in just a few days. I think that alone made it worth the time. I don't have aspirations to get a real MBA, but I now have more respect for those that do.

And now, back to programming...

The First Few Milliseconds of an HTTPS Connection

2009-06-10T08:57:00.011-04:00

Convinced from spending hours reading rave reviews, Bob eagerly clicked "Proceed to Checkout" for his gallon of Tuscan Whole Milk and...

Whoa! What just happened?

In the 220 milliseconds that flew by, a lot of interesting stuff happened to make Firefox change the address bar color and put a lock in the lower right corner. With the help of Wireshark, my favorite network tool, and a slightly modified debug build of Firefox, we can see exactly what's going on.

By agreement of RFC 2818, Firefox knew that "https" meant it should connect to port 443 at Amazon.com:

Most people associate HTTPS with SSL (Secure Sockets Layer) which was created by Netscape in the mid 90's. This is becoming less true over time. As Netscape lost market share, SSL's maintenance moved to the Internet Engineering Task Force (IETF). The first post-Netscape version was re-branded as Transport Layer Security (TLS) 1.0 which was released in January 1999. It's rare to see true "SSL" traffic given that TLS has been around for 10 years.

Client Hello

TLS wraps all traffic in "records" of different types. We see that the first byte out of our browser is the hex byte 0x16 = 22 which means that this is a "handshake" record:

The next two bytes are 0x0301 which indicate that this is a version 3.1 record which shows that TLS 1.0 is essentially SSL 3.1.

The handshake record is broken out into several messages. The first is our "Client Hello" message (0x01). There are a few important things here:

Random:

There are four bytes representing the current Coordinated Universal Time (UTC) in the Unix epoch format, which is the number of seconds since January 1, 1970. In this case, 0x4a2f07ca. It's followed by 28 random bytes. This will be used later on.
Session ID:

Here it's empty/null. If we had previously connected to Amazon.com a few seconds ago, we could potentially resume a session and avoid a full handshake.
Cipher Suites:

This is a list of all of the encryption algorithms that the browser is willing to support. Its top pick is a very strong choice of "TLS_ECDHE_ECDSA_WITH_AES_256_CBC_SHA" followed by 33 others that it's willing to accept. Don't worry if none of that makes sense. We'll find out later that Amazon doesn't pick our first choice anyway.
server_name extension:

This is a way to tell Amazon.com that our browser is trying to reach https://www.amazon.com/. This is really convenient because our TLS handshake occurs long before any HTTP traffic. HTTP has a "Host" header which allows a cost-cutting Internet hosting companies to pile hundreds of websites onto a single IP address. SSL has traditionally required a different IP for each site, but this extension allows the server to respond with the appropriate certificate that the browser is looking for. If nothing else, this extension should allow an extra week or so of IPv4 addresses.

Server Hello

Amazon.com replies with a handshake record that's a massive two packets in size (2,551 bytes). The record has version bytes of 0x0301 meaning that Amazon agreed to our request to use TLS 1.0. This record has three sub-messages with some interesting data:

"Server Hello" Message (2):
- We get the server's four byte time Unix epoch time representation and its 28 random bytes that will be used later.
- A 32 byte session ID in case we want to reconnect without a big handshake.
- Of the 34 cipher suites we offered, Amazon picked "TLS_RSA_WITH_RC4_128_MD5" (0x0004). This means that it will use the "RSA" public key algorithm to verify certificate signatures and exchange keys, the RC4 encryption algorithm to encrypt data, and the MD5 hash function to verify the contents of messages. We'll cover these in depth later on. I personally think Amazon had selfish reasons for choosing this cipher suite. Of the ones on the list, it was the one that was least CPU intensive to use so that Amazon could crowd more connections onto each of their servers. A much less likely possibility is that they wanted to pay special tribute to Ron Rivest, who created all three of these algorithms.
Certificate Message (11):
- This message takes a whopping 2,464 bytes and is the certificate that the client can use to validate Amazon's. It isn't anything fancy. You can view most of its contents in your browser:
"Server Hello Done" Message (14):
- This is a zero byte message that tells the client that it's done with the "Hello" process and indicate that the server won't be asking the client for a certificate.

Checking out the Certificate

The browser has to figure out if it should trust Amazon.com. In this case, it's using certificates. It looks at Amazon's certificate and sees that the current time is between the "not before" time of August 26th, 2008 and before the "not after" time of August 27, 2009. It also checks to make sure that the certificate's public key is authorized for exchanging secret keys.

Why should we trust this certificate?

Attached to the certificate is a "signature" that is just a really long number in big-endian format:

Anyone could have sent us these bytes. Why should we trust this signature? To answer that question, need to make a speedy detour into mathemagic land:

Interlude: A Short, Not Too Scary, Guide to RSA

People sometimes wonder if math has any relevance to programming. Certificates give a very practical example of applied math. Amazon's certificate tells us that we should use the RSA algorithm to check the signature. RSA was created in the 1970's by MIT professors Ron *R*ivest, Adi *S*hamir, and Len *A*dleman who found a clever way to combine ideas spanning 2000 years of math development to come up with a beautifully simple algorithm:

You pick two huge prime numbers "p" and "q." Multiply them to get "n = p*q." Next, you pick a small public exponent "e" which is the "encryption exponent" and a specially crafted inverse of "e" called "d" as the "decryption exponent." You then make "n" and "e" public and keep "d" as secret as you possibly can and then throw away "p" and "q" (or keep them as secret as "d"). It's really important to remember that "e" and "d" are inverses of each other.

Now, if you have some message, you just need to interpret its bytes as a number "M." If you want to "encrypt" a message to create a "ciphertext", you'd calculate:

C ≡ M^e (mod n)

This means that you multiply "M" by itself "e" times. The "mod n" means that we only take the remainder (e.g. "modulus") when dividing by "n." For example, 11 AM + 3 hours ≡ 2 (PM) (mod 12 hours). The recipient knows "d" which allows them to invert the message to recover the original message:

C^d ≡ (M^e)^d ≡ M^e*d ≡ M¹ ≡ M (mod n)

Just as interesting is that the person with "d" can "sign" a document by raising a message "M" to the "d" exponent:

M^d ≡ S (mod n)

This works because "signer" makes public "S", "M", "e", and "n." Anyone can verify the signature "S" with a simple calculation:

S^e ≡ (M^d)^e ≡ M^d*e ≡ M^e*d ≡ M¹ ≡ M (mod n)

Public key cryptography algorithms like RSA are often called "asymmetric" algorithms because the encryption key (in our case, "e") is not equal to (e.g. "symmetric" with) the decryption key "d". Reducing everything "mod n" makes it impossible to use the easy techniques that we're used to such as normal logarithms. The magic of RSA works because you can calculate/encrypt C ≡ M^e (mod n) very quickly, but it is really hard to calculate/decrypt C^d ≡ M (mod n) without knowing "d." As we saw earlier, "d" is derived from factoring "n" back to its "p" and "q", which is a tough problem.

Verifying Signatures

The big thing to keep in mind with RSA in the real world is that all of the numbers involved have to be big to make things really hard to break using the best algorithms that we have. How big? Amazon.com's certificate was "signed" by "VeriSign Class 3 Secure Server CA." From the certificate, we see that this VeriSign modulus "n" is 2048 bits long which has this 617 digit base-10 representation:

1890572922 9464742433 9498401781 6528521078 8629616064 3051642608 4317020197 7241822595 6075980039 8371048211 4887504542 4200635317 0422636532 2091550579 0341204005 1169453804 7325464426 0479594122 4167270607 6731441028 3698615569 9947933786 3789783838 5829991518 1037601365 0218058341 7944190228 0926880299 3425241541 4300090021 1055372661 2125414429 9349272172 5333752665 6605550620 5558450610 3253786958 8361121949 2417723618 5199653627 5260212221 0847786057 9342235500 9443918198 9038906234 1550747726 8041766919 1500918876 1961879460 3091993360 6376719337 6644159792 1249204891 7079005527 7689341573 9395596650 5484628101 0469658502 1566385762 0175231997 6268718746 7514321

(Good luck trying to find "p" and "q" from this "n" - if you could, you could generate real-looking VeriSign certificates.)

VeriSign's "e" is 2^16 + 1 = 65537. Of course, they keep their "d" value secret, probably on a safe hardware device protected by retinal scanners and armed guards. Before signing, VeriSign checked the validity of the contents that Amazon.com claimed on its certificate using a real-world "handshake" that involved looking at several of their business documents. Once VeriSign was satisfied with the documents, they used the SHA-1 hash algorithm to get a hash value of the certificate that had all the claims. In Wireshark, the full certificate shows up as the "signedCertificate" part:

It's sort of a misnomer since it actually means that those are the bytes that the signer is going to sign and not the bytes that already include a signature.

The actual signature, "S", is simply called "encrypted" in Wireshark. If we raise "S" to VeriSign's public "e" exponent of 65537 and then take the remainder when divided by the modulus "n", we get this "decrypted" signature hex value:

0001FFFFFFFFFFFF FFFFFFFFFFFFFFFF FFFFFFFFFFFFFFFF FFFFFFFFFFFFFFFF FFFFFFFFFFFFFFFF FFFFFFFFFFFFFFFF FFFFFFFFFFFFFFFF FFFFFFFFFFFFFFFF FFFFFFFFFFFFFFFF FFFFFFFFFFFFFFFF FFFFFFFFFFFFFFFF FFFFFFFFFFFFFFFF FFFFFFFFFFFFFFFF FFFFFFFFFFFFFFFF FFFFFFFFFFFFFFFF FFFFFFFFFFFFFFFF FFFFFFFFFFFFFFFF FFFFFFFFFFFFFFFF FFFFFFFFFFFFFFFF FFFFFFFFFFFFFFFF FFFFFFFFFFFFFFFF FFFFFFFFFFFFFFFF FFFFFFFFFFFFFFFF FFFFFFFFFFFFFFFF FFFFFFFFFFFFFFFF FFFFFFFFFFFFFFFF FFFFFFFFFFFFFFFF FFFFFFFF00302130 0906052B0E03021A 05000414C19F8786 871775C60EFE0542 E4C2167C830539DB

Per the PKCS #1 v1.5 standard, the first byte is "00" and it "ensures that the encryption block, [when] converted to an integer, is less than the modulus." The second byte of "01" indicates that this is a private key operation (e.g. it's a signature). This is followed by a lot of "FF" bytes that are used to pad the result to make sure that it's big enough. The padding is terminated by a "00" byte. It's followed by "30 21 30 09 06 05 2B 0E 03 02 1A 05 00 04 14" which is the PKCS #1 v2.1 way of specifying the SHA-1 hash algorithm. The last 20 bytes are SHA-1 hash digest of the bytes in "signedCertificate."

Since the decrypted value is properly formatted and the last bytes are the same hash value that we can calculate independently, we can assume that whoever knew "VeriSign Class 3 Secure Server CA"'s private key "signed" it. We implicitly trust that only VeriSign knows the private key "d."

We can repeat the process to verify that "VeriSign Class 3 Secure Server CA"'s certificate was signed by VeriSign's "Class 3 Public Primary Certification Authority."

But why should we trust that? There are no more levels on the trust chain.

The top "VeriSign Class 3 Public Primary Certification Authority" was signed by itself. This certificate has been built into Mozilla products as an implicitly trusted good certificate since version 1.4 of certdata.txt in the Network Security Services (NSS) library. It was checked-in on September 6, 2000 by Netscape's Robert Relyea with the following comment:

"Make the framework compile with the rest of NSS. Include a 'live' certdata.txt with those certs we have permission to push to open source (additional certs will be added as we get permission from the owners)."

This decision has had a relatively long impact since the certificate has a validity range of January 28, 1996 - August 1, 2028.

As Ken Thompson explained so well in his "Reflections on Trusting Trust", you ultimately have to implicitly trust somebody. There is no way around this problem. In this case, we're implicitly trusting that Robert Relyea made a good choice. We also hope that Mozilla's built-in certificate policy is reasonable for the other built-in certificates.

One thing to keep in mind here is that all these certificates and signatures were simply used to form a trust chain. On the public Internet, VeriSign's root certificate is implicitly trusted by Firefox long before you go to any website. In a company, you can create your own root certificate authority (CA) that you can install on everyone's machine.

Alternatively, you can get around having to pay companies like VeriSign and avoid certificate trust chains altogether. Certificates are used to establish trust by using a trusted third-party (in this case, VeriSign). If you have a secure means of sharing a secret "key", such as whispering a long password into someone's ear, then you can use that pre-shared key (PSK) to establish trust. There are extensions to TLS to allow this, such as TLS-PSK, and my personal favorite, TLS with Secure Remote Password (SRP) extensions. Unfortunately, these extensions aren't nearly as widely deployed and supported, so they're usually not practical. Additionally, these alternatives impose a burden that we have to have some other secure means of communicating the secret that's more cumbersome than what we're trying to establish with TLS (otherwise, why wouldn't we use that for everything?).

One final check that we need to do is to verify that the host name on the certificate is what we expected. Nelson Bolyard's comment in the SSL_AuthCertificate function explains why:

/* cert is OK. This is the client side of an SSL connection.
 * Now check the name field in the cert against the desired hostname.
 * NB: This is our only defense against Man-In-The-Middle (MITM) attacks! */

This check helps prevent against a man-in-the-middle attack because we are implicitly trusting that the people on the certificate trust chain wouldn't do something bad, like sign a certificate claiming to be from Amazon.com unless it actually was Amazon.com. If an attacker is able to modify your DNS server by using a technique like DNS cache poisoning, you might be fooled into thinking you're at a trusted site (like Amazon.com) because the address bar will look normal. This last check implicitly trusts certificate authorities to stop these bad things from happening.

Pre-Master Secret

We've verified some claims about Amazon.com and know its public encryption exponent "e" and modulus "n." Anyone listening in on the traffic can know this as well (as evidenced because we are using Wireshark captures). Now we need to create a random secret key that an eavesdropper/attacker can't figure out. This isn't as easy as it sounds. In 1996, researchers figured out that Netscape Navigator 1.1 was using only three sources to seed their pseudo-random number generator (PRNG). The sources were: the time of day, the process id, and the parent process id. As the researchers showed, these "random" sources aren't that random and were relatively easy to figure out.

Since everything else was derived from these three "random" sources, it was possible to "break" the SSL "security" in 25 seconds on a 1996 era machine. If you still don't believe that finding randomness is hard, just ask the Debian OpenSSL maintainers. If you mess it up, all the security built on top of it is suspect.

On Windows, random numbers used for cryptographic purposes are generated by calling the CryptGenRandom function that hashes bits sampled from over 125 sources. Firefox uses this function along with some bits derived from its own function to seed its pseudo-random number generator.

The 48 byte "pre-master secret" random value that's generated isn't used directly, but it's very important to keep it secret since a lot of things are derived from it. Not surprisingly, Firefox makes it hard to find out this value. I had to compile a debug version and set the SSLDEBUGFILE and SSLTRACE environment variables to see it.

In this particular session, the pre-master secret showed up in the SSLDEBUGFILE as:

4456: SSL[131491792]: Pre-Master Secret [Len: 48]
03 01 bb 7b 08 98 a7 49 de e8 e9 b8 91 52 ec 81 ...{...I.....R..
4c c2 39 7b f6 ba 1c 0a b1 95 50 29 be 02 ad e6 L.9{......P)....
ad 6e 11 3f 20 c4 66 f0 64 22 57 7e e1 06 7a 3b .n.? .f.d"W~..z;

Note that it's not completely random. The first two bytes are, by convention, the TLS version (03 01).

Trading Secrets

We now need to get this secret value over to Amazon.com. By Amazon's wishes of "TLS_RSA_WITH_RC4_128_MD5", we will use RSA to do this. You could make your input message equal to just the 48 byte pre-master secret, but the Public Key Cryptography Standard (PKCS) #1, version 1.5 RFC tells us that we should pad these bytes with random data to make the input equal to exactly the size of the modulus (1024 bits/128 bytes). This makes it harder for an attacker to determine our pre-master secret. It also gives us one last chance to protect ourselves in case we did something really bone-headed, like reusing the same secret. If we reused the key, the eavesdropper would likely see a different value placed on the network due to the random padding.

Again, Firefox makes it hard to see these random values. I had to insert debugging statements into the padding function to see what was going on:

wrapperHandle = fopen("plaintextpadding.txt", "a");
fprintf(wrapperHandle, "PLAINTEXT = ");
for(i = 0; i < modulusLen; i++)
{
    fprintf(wrapperHandle, "%02X ", block[i]);
}
fprintf(wrapperHandle, "\r\n");
fclose(wrapperHandle);

In this session, the full padded value was:

00 02 12 A3 EA B1 65 D6 81 6C 13 14 13 62 10 53 23 B3 96 85 FF 24 FA CC 46 11 21 24 A4 81 EA 30 63 95 D4 DC BF 9C CC D0 2E DD 5A A6 41 6A 4E 82 65 7D 70 7D 50 09 17 CD 10 55 97 B9 C1 A1 84 F2 A9 AB EA 7D F4 CC 54 E4 64 6E 3A E5 91 A0 06 00 03 01 BB 7B 08 98 A7 49 DE E8 E9 B8 91 52 EC 81 4C C2 39 7B F6 BA 1C 0A B1 95 50 29 BE 02 AD E6 AD 6E 11 3F 20 C4 66 F0 64 22 57 7E E1 06 7A 3B

Firefox took this value and calculated "C ≡ M^e (mod n)" to get the value we see in the "Client Key Exchange" record:

Finally, Firefox sent out one last unencrypted message, a "Change Cipher Spec" record:

This is Firefox's way of telling Amazon that it's going to start using the agreed upon secret to encrypt its next message.

Deriving the Master Secret

If we've done everything correctly, both sides (and only those sides) now know the 48 byte (256 bit) pre-master secret. There's a slight trust issue here from Amazon's perspective: the pre-master secret just has bits that were generated by the client, they don't take anything into account from the server or anything we said earlier. We'll fix that be computing the "master secret." Per the spec, this is done by calculating:

master_secret = PRF(pre_master_secret, "master secret", ClientHello.random + ServerHello.random)

The "pre_master_secret" is the secret value we sent earlier. The "master secret" is simply a string whose ASCII bytes (e.g. "6d 61 73 74 65 72 ...") are used. We then concatenate the random values that were sent in the ClientHello and ServerHello (from Amazon) messages that we saw at the beginning.

The PRF is the "Pseudo-Random Function" that's also defined in the spec and is quite clever. It combines the secret, the ASCII label, and the seed data we give it by using the keyed-Hash Message Authentication Code (HMAC) versions of both MD5 and SHA-1 hash functions. Half of the input is sent to each hash function. It's clever because it is quite resistant to attack, even in the face of weaknesses in MD5 and SHA-1. This process can feedback on itself and iterate forever to generate as many bytes as we need.

Following this procedure, we obtain a 48 byte "master secret" of

4C AF 20 30 8F 4C AA C5 66 4A 02 90 F2 AC 10 00 39 DB 1D E0 1F CB E0 E0 9D D7 E6 BE 62 A4 6C 18 06 AD 79 21 DB 82 1D 53 84 DB 35 A7 1F C1 01 19

Generating Lots of Keys

Now that both sides have a "master secrets", the spec shows us how we can derive all the needed session keys we need using the PRF to create a "key block" where we will pull data from:

key_block = PRF(SecurityParameters.master_secret, "key expansion", SecurityParameters.server_random + SecurityParameters.client_random);

The bytes from "key_block" are used to populate the following:

client_write_MAC_secret[SecurityParameters.hash_size]
server_write_MAC_secret[SecurityParameters.hash_size]
client_write_key[SecurityParameters.key_material_length]
server_write_key[SecurityParameters.key_material_length]
client_write_IV[SecurityParameters.IV_size]
server_write_IV[SecurityParameters.IV_size]

Since we're using a stream cipher instead of a block cipher like the Advanced Encryption Standard (AES), we don't need the Initialization Vectors (IVs). Therefore, we just need two Message Authentication Code (MAC) keys for each side that are 16 bytes (128 bits) each since the specified MD5 hash digest size is 16 bytes. In addition, the RC4 cipher uses a 16 byte (128 bit) key that both sides will need as well. All told, we need 2*16 + 2*16 = 64 bytes from the key block.

Running the PRF, we get these values:

client_write_MAC_secret = 80 B8 F6 09 51 74 EA DB 29 28 EF 6F 9A B8 81 B0
server_write_MAC_secret = 67 7C 96 7B 70 C5 BC 62 9D 1D 1F 4A A6 79 81 61
client_write_key = 32 13 2C DD 1B 39 36 40 84 4A DE E5 6C 52 46 72
server_write_key = 58 36 C4 0D 8C 7C 74 DA 6D B7 34 0A 91 B6 8F A7

Prepare to be Encrypted!

The last handshake message the client sends out is the "Finished message." This is a clever message that proves that no one tampered with the handshake and it proves that we know the key. The client takes all bytes from all handshake messages and puts them into a "handshake_messages" buffer. We then calculate 12 bytes of "verify_data" using the pseudo-random function (PRF) with our master key, the label "client finished", and an MD5 and SHA-1 hash of "handshake_messages":

verify_data = PRF(master_secret, "client finished", MD5(handshake_messages) + SHA-1(handshake_messages)) [12]

We take the result and add a record header byte "0x14" to indicate "finished" and length bytes "00 00 0c" to indicate that we're sending 12 bytes of verify data. Then, like all future encrypted messages, we need to make sure the decrypted contents haven't been tampered with. Since our cipher suite in use is TLS_RSA_WITH_RC4_128_MD5, this means we use the MD5 hash function.

Some people get paranoid when they hear MD5 because it has some weaknesses. I certainly don't advocate using it as-is. However, TLS is smart in that it doesn't use MD5 directly, but rather the HMAC version of it. This means that instead of using MD5(m) directly, we calculate:

HMAC_MD5(Key, m) = MD5((Key ⊕ opad) ++ MD5((Key ⊕ ipad) ++ m)

(The ⊕ means XOR, ++ means concatenate, "opad" is the bytes "5c 5c ... 5c", and "ipad" is the bytes "36 36 ... 36").

In particular, we calculate:

HMAC_MD5(client_write_MAC_secret, seq_num + TLSCompressed.type + TLSCompressed.version + TLSCompressed.length + TLSCompressed.fragment));

As you can see, we include a sequence number ("seq_num") along with attributes of the plaintext message (here it's called "TLSCompressed"). The sequence number foils attackers who might try to take a previously encrypted message and insert it midstream. If this occurred, the sequence numbers would definitely be different than what we expected. This also protects us from an attacker dropping a message.

All that's left is to encrypt these bytes.

RC4 Encryption

Our negotiated cipher suite was TLS_RSA_WITH_RC4_128_MD5. This tells us that we need to use Ron's Code #4 (RC4) to encrypt the traffic. Ron Rivest developed the RC4 algorithm to generate random bytes based on a 256 byte key. The algorithm is so simple you can actually memorize it in a few minutes.

RC4 begins by creating a 256-byte "S" byte array and populating it with 0 to 255. You then iterate over the array by mixing in bytes from the key. You do this to create a state machine that is used to generate "random" bytes. To generate a random byte, we shuffle around the "S" array.

Put graphically, it looks like this:

To encrypt a byte, we xor this pseudo-random byte with the byte we want to encrypt. Remember that xor'ing a bit with 1 causes it to flip. Since we're generating random numbers, on average the xor will flip half of the bits. This random bit flipping is effectively how we encrypt data. As you can see, it's not very complicated and thus it runs quickly. I think that's why Amazon chose it.

Recall that we have a "client_write_key" and a "server_write_key." The means we need to create two RC4 instances: one to encrypt what our browser sends and the other to decrypt what the server sent us.

The first few random bytes out of the "client_write" RC4 instance are "7E 20 7A 4D FE FB 78 A7 33 ..." If we xor these bytes with the unencrypted header and verify message bytes of "14 00 00 0C 98 F0 AE CB C4 ...", we'll get what appears in the encrypted portion that we can see in Wireshark:

The server does almost the same thing. It sends out a "Change Cipher Spec" and then a "Finished Message" that includes all handshake messages, including the decrypted version of the client's "Finished Message." Consequently, this proves to the client that the server was able to successfully decrypt our message.

Welcome to the Application Layer!

Now, 220 milliseconds after we started, we're finally ready for the application layer. We can now send normal HTTP traffic that'll be encrypted by the TLS layer with the RC4 write instance and decrypt traffic with the server RC4 write instance. In addition, the TLS layer will check each record for tampering by computing the HMAC_MD5 hash of the contents.

At this point, the handshake is over. Our TLS record's content type is now 23 (0x17). Encrypted traffic begins with "17 03 01" which indicate the record type and TLS version. These bytes are followed by our encrypted size, which includes the HMAC hash.

Encrypting the plaintext of:

GET /gp/cart/view.html/ref=pd_luc_mri HTTP/1.1
Host: www.amazon.com
User-Agent: Mozilla/5.0 (Windows; U; Windows NT 6.0; en-US; rv:1.9.0.10) Gecko/2009060911 Minefield/3.0.10 (.NET CLR 3.5.30729)
Accept: text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8
Accept-Language: en-us,en;q=0.5
Accept-Encoding: gzip,deflate
Accept-Charset: ISO-8859-1,utf-8;q=0.7,*;q=0.7
Keep-Alive: 300
Connection: keep-alive
...

will give us the bytes we see on the wire:

The only other interesting fact is that the sequence number increases on each record, it's now 1 (and the next record will be 2, etc).

The server does the same type of thing on its side using the server_write_key. We see its response, including the tell-tale application data header:

Decrypting this gives us:

HTTP/1.1 200 OK
Date: Wed, 10 Jun 2009 01:09:30 GMT
Server: Server
...
Cneonction: close
Transfer-Encoding: chunked

which is a normal HTTP reply that includes a non-descriptive "Server: Server" header and a misspelled "Cneonction: close" header coming from Amazon's load balancers.

TLS is just below the application layer. The HTTP server software can act as if it's sending unencrypted traffic. The only change is that it writes to a library that does all the encryption. OpenSSL is a popular open-source library for TLS.

The connection will stay open while both sides send and receive encrypted data until either side sends out a "closure alert" message and then closes the connection. If we reconnect shortly after disconnecting, we can re-use the negotiated keys (if the server still has them cached) without using public key operations, otherwise we do a completely new full handshake.

It's important to realize that application data records can be anything. The only reason "HTTPS" is special is because the web is so popular. There are lots of other TCP/IP based protocols that ride on top of TLS. For example, TLS is used by FTPS and secure extensions to SMTP. It's certainly better to use TLS than inventing your own solution. Additionally, you'll benefit from a protocol that has withstood careful security analysis.

... And We're Done!

The very readable TLS RFC covers many more details that were missed here. We covered just one single path in our observation of the 220 millisecond dance between Firefox and Amazon's server. Quite a bit of the process was affected by the TLS_RSA_WITH_RC4_128_MD5 Cipher Suite selection that Amazon made with its ServerHello message. It's a reasonable choice that slightly favors speed over security.

As we saw, if someone could secretly factor Amazon's "n" modulus into its respective "p" and "q", they could effectively decrypt all "secure" traffic until Amazon changes their certificate. Amazon counter-balances this concern this with a short one year duration certificate:

One of the cipher suites that was offered was "TLS_DHE_RSA_WITH_AES_256_CBC_SHA" which uses the Diffie-Hellman key exchange that has a nice property of "forward secrecy." This means that if someone cracked the mathematics of the key exchange, they'd be no better off to decrypt another session. One downside to this algorithm is that it requires more math with big numbers, and thus is a little more computationally taxing on a busy server. The "Advanced Encryption Standard" (AES) algorithm was present in many of the suites that we offered. It's different than RC4 in that it works on 16 byte "blocks" at a time rather than a single byte. Since its key can be up to 256 bits, many consider this to be more secure than RC4.

In just 220 milliseconds, two endpoints on the Internet came together, provided enough credentials to trust each other, set up encryption algorithms, and started to send encrypted traffic.

And to think, all of this just so Bob can buy milk.

UPDATE: I wrote a program that walks through the handshake steps mentioned in this article. I posted it to GitHub.

Using Obscure Windows COM APIs in .NET

2009-04-24T08:37:00.004-04:00

Most native Windows APIs are simple to call from .NET. For example, if you need to do something special when showing a window, you can use the ShowWindow API using Platform Invocation Services (P/Invoke) like this:

[DllImport("user32.dll")]
static extern bool ShowWindow(IntPtr hWnd, int nCmdShow);

When you call this function, here's roughly what happens:

The CLR calls LoadLibrary on the file (e.g. "user32.dll")
The CLR then calls GetProcAddress on the function name (e.g. "ShowWindow") to get the address of where the function is located.

For the most part, it just magically works. If we had used a function like "MessageBox", the CLR would notice that it doesn't exist and would then pick between the ANSI version (e.g. "MessageBoxA") or the Unicode version (e.g. "MessageBoxW").

With the address in hand, it's easy to jump to it and you're all set. Simple and easy.

I was expecting a simple API like this when I was investigating how to register my program as the default handler for ".wav" files on Vista. In the pre-Vista days, most programs would write directly into a registry key for the file extension (e.g. "HKEY_CLASSES_ROOT\.wav") and move on. Problems come when your program wants to register itself as a handler for a "popular" extension like .MP3 or .HTM. Some programs go into an all out arms race with other programs in a fight of wills to make sure they keep the extension.

In Windows Vista and later, Microsoft wants us to use the new "Default Programs" feature. The idea is that you register what file extensions your program supports in the registry and then a nice UI allows people to easily pick which of those extensions they want to associate with your program. Digging around the documentation led me to discover that the bulk of the functionality was exposed via the IApplicationAssociationRegistration COM interface.

Ah, COM.

Over the years, I've tried to keep my distance from it. This irrational fear came from wizards that "next, next, finish"'d your way into thousands of lines of inscrutable code. It took me years of passing glances to finally understand its basics. Even then, when I needed to use it from .NET, I'd right click on my project references and click "Add Reference":

I'd pick the library I needed and then somehow I could use the types as if they were .NET objects. I didn't ask further questions and moved on.

Unfortunately, IApplicationAssociationRegistration was nowhere to be found on the "Add Reference" list since it doesn't seem to have a registered type library associated with it. Using my basic COM knowledge, I knew that if I wanted to use it I would need to know the interface identifier (IID) as well as a class identifier (CLSID) that pointed to a concrete implementation.

Following the MSDN documentation, I knew I'd probably find success in shobjidl.idl:

Sure enough, shobjidl.idl was sitting in my "C:\Program Files\Microsoft SDKs\Windows\v6.1\Include" directory and had this interface definition:

[
 object,
 uuid(4e530b0a-e611-4c77-a3ac-9031d022281b),
 pointer_default(unique),
 helpstring("Protocol URL and Extension File Application")
]
interface IApplicationAssociationRegistration : IUnknown
{
 HRESULT QueryCurrentDefault(
     [in, string] LPCWSTR pszQuery,
     [in] ASSOCIATIONTYPE atQueryType,
     [in] ASSOCIATIONLEVEL alQueryLevel,
     [out, string] LPWSTR* ppszAssociation);

...
}

A little further down was the declaration for the concrete class (coclass) and its associated class id (CLSID):

// CLSID_ApplicationAssociationRegistration
[ uuid(591209c7-767b-42b2-9fba-44ee4615f2c7) ] coclass ApplicationAssociationRegistration
{
 interface IApplicationAssociationRegistration;
}

In the IDL, we also see the definitions for the enums that the functions use:

typedef [v1_enum] enum tagASSOCIATIONLEVEL
{
 AL_MACHINE,
 AL_EFFECTIVE,
 AL_USER,
} ASSOCIATIONLEVEL;

typedef [v1_enum] enum tagASSOCIATIONTYPE
{
 AT_FILEEXTENSION,
 AT_URLPROTOCOL,
 AT_STARTMENUCLIENT,
 AT_MIMETYPE,
} ASSOCIATIONTYPE;

Getting this to work in .NET was surprisingly easy. The basic idea is that the CLR has to have just enough information to find the types:

The "ComImportAttribute" is almost as simple to use as DllImportAttribute. In addition, you need to use the GuidAttribute to specify the gigantic GUIDs.
You use the "InterfaceTypeAttribute" to specify the basic interface(s) that the interface you're importing uses. In COM, all interfaces derive from IUnknown. If the interface supports scripting then it implements IDispatch. If you provide a speedy C++ way of accessing your interface (e.g. vtable definition) and the scripting IDispatch interface, you've got a "dual" interface.
You need to translate the parameter types to their .NET equivalents. This is an incredibly mechanical process that's straightforward. If there is a chance that the underlying bits are different between COM and .NET (e.g. they're not blittable) then you need to use the MarshalAsAttribute to tell the CLR how to convert the types as necessary.
You need to remember that COM handles errors by returning HRESULTs instead of natively using exceptions like .NET uses. By default, the CLR will make the last parameter that is an OUT parameter in the IDL to be the return value (it helps if it's marked by "retval"). Therefore, you can act as if the function really returns its last parameter and the CLR will automatically check the HRESULT and throw a corresponding .NET exception as needed.
Optionally, and perhaps most controversially, you're free de-Hungarianize the parameter names and PascalCase the enum names to make them much more friendly looking to people in .NET. It's optional since it might confuse people that use MSDN documentation and expecting the original names.

In a minute or so, I translated the definitions and gladly got rid of the Hungarian prefixes by converting parameter names of "pszQuery" to just "query." I also converted all the enums and removed their unnecessary prefixes. The end result was this:

[ComImport]
[Guid("4e530b0a-e611-4c77-a3ac-9031d022281b")]
[InterfaceType(ComInterfaceType.InterfaceIsIUnknown)]
internal interface IApplicationAssociationRegistration
{   
 [return: MarshalAs(UnmanagedType.LPWStr)]
 string QueryCurrentDefault( [MarshalAs(UnmanagedType.LPWStr)] string query,
                           AssociationType queryType,
                           AssociationLevel queryLevel);
 [return: MarshalAs(UnmanagedType.Bool)]
 bool QueryAppIsDefault([MarshalAs(UnmanagedType.LPWStr)] string query,
                        AssociationType queryType,
                        AssociationLevel queryLevel,
                        [MarshalAs(UnmanagedType.LPWStr)] string appRegistryName);
 [return: MarshalAs(UnmanagedType.Bool)]
 bool QueryAppIsDefaultAll(AssociationLevel queryLevel,
                           [MarshalAs(UnmanagedType.LPWStr)] string appRegistryName);
 void SetAppAsDefault([MarshalAs(UnmanagedType.LPWStr)] string appRegistryName,
                      [MarshalAs(UnmanagedType.LPWStr)] string set,
                      AssociationType setType);
 void SetAppAsDefaultAll([MarshalAs(UnmanagedType.LPWStr)] string appRegistryName);
 void ClearUserAssociations();
}

Importing the concrete class that implements the interface was just a matter of specifying its CLSID:

[ComImport]
[Guid("591209c7-767b-42b2-9fba-44ee4615f2c7")]
internal class ApplicationAssociationRegistration
{
 // coclass is implemented by the runtime callable wrapper
}

With all of that goo out of the way, you can use the interface like a normal .NET type:

var aa = new ApplicationAssociationRegistration();
var iaar = (IApplicationAssociationRegistration)aa;
string myCurrentMp3Player = iaar.QueryCurrentDefault(".mp3", AssociationType.FileExtension, AssociationLevel.Effective);

Behind the scenes, the runtime callable wrapper has to do something like this:

Load in ole32.dll where COM functions reside.
Call CoInitialize to initialize COM.
Look up your CLSID and IID in the registry under HKEY_CLASSES_ROOT and find their associated DLL (in our case, "shell32.dll")
Create a factory for your class.
Use the factory to create an instance.
Call QueryInterface to get the specific interface we want (e.g. IApplicationAssociationRegistration)
Get a pointer to the function we want using the vtable.

After all that, we finally have a place to jump to like we did with P/Invoke.

Why bother with all of this? One reason is that Microsoft has a huge legacy investment in C and C++ in Windows. There's no compelling reason for them to rewrite things in .NET. A natural consequence is that the C++ code that implements their latest APIs will be exposed using COM for the foreseeable future. Recently, Microsoft has gone ahead and published .NET COM wrappers for some of the popular new APIs like the Libraries feature in Windows 7. With just a little work, you don't have to wait on Microsoft to do this for you.

Given that .NET was designed as a successor to COM, it's no surprise that Microsoft has made interoperability with it very seamless. The runtime callable wrapper does a good job of hiding most of the messier details. The garbage collector handles much of the bookkeeping involved with memory management that used to be the bane of COM programming. The runtime is very aware of typical COM semantics of when to allocate and free memory. It's not always perfect. Sometimes you can be pre-emptive and force your COM object to be cleaned up via Marshal.ReleaseComObject so you don't have to wait on the garbage collector, but you should be careful.

I just presented the basics of what I learned to get my job done. There's a lot more out there for more advanced scenarios. I've found the free book "COM and .NET Interop" by Andrew Troelsen to be helpful.

There's plenty of obscure Windows APIs out there for the taking. Enjoy!

How .NET Regular Expressions Really Work

2009-03-16T07:47:00.006-04:00

Remember when you first tried to parse text?

My early BASIC programs were littered with IF statements that dissected strings using LEFT$, RIGHT$, MID$, TRIM$, and UCASE$. It took me hours to write a program that parsed a simple text file. Just trying to support whitespace and mixed casing was enough to drive me crazy.

Years later when I started programming in Java, I discovered the StringTokenizer class. I thought it was a huge leap forward. I no longer had to worry about whitespace. However, I still had to use functions like "substring" and "toUpperCase", but I thought that was as good as it could get.

And then one day I found regular expressions.

I almost cried when I realized that I could replace parsing code that took me hours to write with a simple regular expression. It still took me several years to become comfortable with the syntax, but the learning curve was worth the power obtained.

And yet with all of this love, I still had this nagging suspicion that I was doing it wrong. After reading Pragmatic Thinking and Learning, I was determined to try to imagine what life was like inside the code I wrote. But I just couldn't connect with a regular expression.

The last straw came recently when I was trying to help a coworker craft a regex to properly handle name/value string pairs with escaped strings. In the end, our regex worked, but I felt that it was duct-taped together. I knew there was a better way.

I picked up a copy of Jeffrey Friedl's book "Mastering Regular Expressions" and couldn't put it down. In less than a week, I had flown through 400+ pages and had finally started to feel like I understood how regular expressions worked. I finally had a sense for what backtracking really meant and I had a better idea for how a regex could go catastrophically out of control.

I had extremely high hopes for chapter 9 which covered the .NET regular expression "flavor." Since I work with .NET every day, I thought this would be the best chapter. I did learn a few things like how to properly use RegexOptions.ExplicitCapture, how to use the special per-match replacement sequences that Regex.Replace offers, how to save compiled regular expressions to a DLL, and how to match balanced parentheses -a feat that's theoretically not possible with a regex. Despite learning all of this in the chapter, I still didn't feel that I could "connect" with the very .NET regular expression engine that I know and love.

To be fair, the vast benefit of the book comes from the first six chapters that deal with how regular expressions work in general since regex implementations share many ideas. The book laid a solid foundation, but I wanted more.

I wanted to stop all my hand-waving at regular expressions and actually understand how they really work.

I knew I wanted to drill into the code. Although tools like Reflector are amazing, I knew I wanted to see the actual code. It's fairly easy now to step into the framework source code in the debugger. Unlike understanding the details of locking, which had me dive into C++ and x86 assembly, it was refreshing to see that the .NET regular expression engine was written entirely in C#.

I decided to use a really simple regular expression and search string and then follow it from cradle to grave. If you'd like to follow along at home, I've linked to relevant lines in the .NET regular expression source code.

My very simple regex consisted of looking for a basic URL:

string textToSearch = "Welcome to http://www.moserware.com/!";
string regexPattern = @"http://([^\s/]+)/?";
Match m = Regex.Match(textToSearch, regexPattern); 
Console.WriteLine("Full uri = '{0}'", m.Value);
Console.WriteLine("Host ='{0}'", m.Groups[1].Value);

Our journey begins at Regex.Match where we checking an internal cache of the past 15 regex values to see if there a match for:

"0:ENU:http://([^\\s/]+)/?"

This is a compact representation of:

RegexOptions : Culture : Regex pattern

The regex doesn't find this in the cache, so it starts scanning the pattern. Note that out of respect for the authors, our regex pattern doesn't have any comments or whitespace in it:

// It would be nice to get rid of the comment modes, since the 
// ScanBlank() calls are just kind of duct-taped in.

We start creating an internal tree representation of the regex by adding a multi-character (aka "Multi") node to contain the "http://" part. Next, we see that the scanner made it to first real capture:

http://([^\s/]+)/?

This capture contains a character class that says that we don't want to match spaces or a forward slash. It is converted into an obscure five character string:

"\x1\x2\x1\x2F\x30\x64"

Later we'll see why it had to all fit in one string, but for now we can use a helpful comment to decode each character:

Offset	Hex Value	Meaning
0	0x01	The set should be negated
1	0x02	There are two characters in the character part of the set
2	0x01	There is one Unicode category
3	0x2F	Inclusive lower-bound of the character set. It's a '/' in Unicode
4	0x30	Exclusive upper-bound of the character set. It's a '0' in Unicode
5	0x64	This is a magic number that means the "Space" category.

Before I realized that this string had meaning, I was utterly confused.

As we continue scanning, we find a '+' quantifier:

http://([^\\s/]+)/?

This is noted as a Oneloop node since it's a "loop" of what came before (e.g. the character class set). It has arguments of 1 and Int32.MaxValue to denote 1 or more matches. We see that the next character isn't a '?', so we can assert this is not a lazy match which means it's a greedy match.

The first group is recorded when we hit the ')' character. At the end of the pattern, we note a One (character) node for the '/' and we see it's followed by a '?' which is just another quantifier, this time with a minimum of 0 and a maximum of 1.

All those nodes come together to give us this "RegexTree:"

We still need to convert the tree to code that the regular expression "machine" can execute later. The bulk of the work is done by an aptly named RegexCodeFromRegexTree function that has a decent comment:

/*
 * The top level RegexCode generator. It does a depth-first walk 
 * through the tree and calls EmitFragment to emits code before 
 * and after each child of an interior node, and at each leaf. 
 * 
 * It runs two passes, first to count the size of the generated 
 * code, and second to generate the code. 
 * 
 * <CONSIDER>we need to time it against the alternative, which is 
 * to just generate the code and grow the array as we go.</CONSIDER> 
 */

I love the anonymous "CONSIDER" comment and would have had a similar reaction. Instead of using an ArrayList or List<int> to store the op codes, which can automatically resize as needed, the code diligently goes through the entire RegexTree twice. The class is peppered with "if(_counting)" expressions that just increase a counter by the size they will use in the next pass.

As predicted by the comment, the bulk of the work is done by the 250 line switch statement that makes up the EmitFragment function. This function breaks up RegexTree "fragments" and converts them to a simpler RegexCode. The first fragment is:

EmitFragment(nodetype=RegexNode.Capture | BeforeChild, node=[RegexNode.Capture, Group=0, Length=-1], childIndex=0)

This is shorthand for emitting the RegexCode that should come before the children of the top level "RegexNode.Capture" node that represents group 0 and that goes until the end of the string (e.g. has length -1). The last 0 means that it's the 0th child of the parent node (this is sort of meaningless since it has no parent). The subsequent calls walk the rest of the tree:

EmitFragment(RegexNode.Concatenate | BeforeChild, [RegexNode.Concatenate], childIndex=0)
EmitFragment(RegexNode.Multi, [RegexNode.Multi, string="http://"], childIndex=0)
EmitFragment(RegexNode.Concatenate | AfterChild, [RegexNode.Concatenate], childIndex=0)
EmitFragment(RegexNode.Concatenate | BeforeChild, [RegexNode.Concatenate], childIndex=1)
EmitFragment(RegexNode.Capture | BeforeChild, [RegexNode.Capture, Group=1, -1], childIndex=0)
EmitFragment(RegexNode.SetLoop, [RegexNode.SetLoop, min=1, max=Int32.MaxValue], childIndex=0)
EmitFragment(RegexNode.Capture | AfterChild, [RegexNode.Capture, Group=1, Length=-1], childIndex=0)
EmitFragment(RegexNode.Concatenate | AfterChild, [RegexNode.Concatenate], childIndex=1)
EmitFragment(RegexNode.Concatenate | BeforeChild, [RegexNode.Concatenate], childIndex=2)
EmitFragment(RegexNode.Oneloop, [RegexNode.Oneloop, min=0, max=1, character='/'], childIndex=0)
EmitFragment(RegexNode.Concatenate | AfterChild, [RegexNode.Concatenate], childIndex=2)
EmitFragment(RegexNode.Capture | AfterChild, [RegexNode.Capture, Group=0, Length=-1], childIndex=0)

The reward for all this work is an integer array that describes the RegexCode "op codes" and their arguments. You can see that some instructions like "Setrep" take a string argument. These arguments point to offsets in a string table. This is why it was critical to pack everything about a set into the obscure string we saw earlier. It was the only way to pass that information to the instruction.

Decoding the code array, we see:

Index	Instruction	Op Code/Argument	String Table Reference	Description
0	Lazybranch	23		Lazily branch to the Stop instruction at offset 21.
1		21		Lazily branch to the Stop instruction at offset 21.
2	Setmark	31		Push our current state onto a stack in case we need to backtrack later.
3	Multi	12		Perform a multi-character match of string table item 0 which is "http://".
4		0	"http://"
5	Setmark	31		Push our current state onto a stack in case we need to backtrack later.
6	Setrep	2		Perform a set repetition match of length 1 on the set stored at string table position 1, which represents [^\s/].
7		1	"\x1\x2\x1\x2F\x30\x64"
8		1
9	Setloop	5		Match the set [^\s/] in a loop at most Int32.MaxValue times.
10		1	"\x1\x2\x1\x2F\x30\x64"
11		2147483647
12	Capturemark	32		Capture into group #1, the string between the mark set by the last Setmark and the current position.
13		1
14		-1
15	Oneloop	3		Match Unicode character 47 (a '/') in a loop for a maximum of 1 time.
16		47
17		1
18	Capturemark	32		Capture into group #0, the contents between the first Setmark instruction and the current position.
19		0
20		-1
21	Stop	40		Stop the regex.

We can now see that our regex has turned into a simple "program" that will be executed later.

Prefix Optimizations

We could stop here, but we'd miss the fun "optimizations." With our pattern and search string, the optimizations will actually slow things down, but the code generator is oblivious to that. The basic idea behind prefix optimizations is to quickly jump to where the match might start. It does this by using a RegexFCD class that I'm guessing stands for "Regex First Character Descriptor."

With our regex, the FirstChars functions notices our "http://" 'Multi' node and determines that any match must start with an 'h'. If we had alternations, the first character of each alternation would be added to make a limited set of potential first characters. With this optimization alone, we can skip all characters in the text that aren't in this approved "white list" of first characters without having to execute any of the above RegexCode.

But wait... there's an even trickier optimization! The optimizer discovers that the first thing the regex must match is a simple string literal: a 'Multi' node. This means that we can use the RegexBoyerMoore class which applies the Boyer-Moore search algorithm.

The key insight is that we don't have to check each character of the text. We only need to look at last character to see if it's even worth checking the rest.

For example, if our sample text is "Welcome to http://www.moserware.com/!" and we're searching for "http://" which is 7 characters, we first look at the 7th character of the text which is 'e'. Since 'e' is not the 7th character of what we're looking for (which is a '/'), we know that there couldn't possibly be a match and so we don't need to bother checking all previous 6 characters because there isn't even an 'e' in what we're looking for. The tricky part is what to do if the what we find is in the string that we're trying to match, but it isn't the last '/' character.

The specifics are handled in straightforward way with some minor optimizations to reduce memory needs given 65,000+ possible Unicode characters. For each character, the maximum possible skip is calculated.

For "http://", we come up with this skip table:

Character	Characters to skip ahead
/	0
:	2
h	6
p	3
t	4
all others	7

This table tells us that if we find an 'e' then we can skip ahead 7 characters without even checking the previous 6 characters. If we find a 'p', then we can skip ahead at least 3 characters before performing a full check, and if we find a '/' then we could be on the last character and need to check other characters (e.g. skip ahead 0).

There is one more optimization that looks for anchors, but none apply to our regex, so it's ignored.

We're done! We made it to the end of the RegexWriter phase. The "RegexCode" internal representation consists of these critical parts:

The regex code we created.
The string table derived from the regex that the code uses (e.g. our "Multi" and "Setrep" instructions have string table references).
The maximum size of our backtracking stack. (Ours is 7, this will make more sense later.)
A mapping of named captures to their group numbers. (We don't have any in our regex, so this is empty.)
The total number of captures. (We have 2.)
The RegexBoyerMoore prefix that we calculated. (This applies to us since we have a string literal at the start.)
The possible first characters in our prefix. (In our case, we calculated this to be an 'h'.)
Our anchors. (We don't have any.)
An indicator whether this should be a RightToLeft match. (In our case, we use the default which is false.)

Every regex passes through this step. It applies to our measly regex with a code size of 21 as much as it does to a gnarly RFC2822 compliant regex that has 175. These nine items completely describe everything that we'll do with our regex and they never change.

In need of an interpreter

Now that we have the RegexCode, the match method will run and create a RegexRunner which is the "driver" for the regex matching process. Since we didn't specify the "Compiled" flag, we'll use the RegexInterpreter runner.

Before the interpreter starts scanning, it notices that we have a valid Boyer-Moore prefix optimization and it uses it to quickly locate the start of the regex:

Index	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36
Character	W	e	l	c	o	m	e		t	o		h	t	t	p	:	/	/	w	w	w	.	m	o	s	e	r	w	a	r	e	.	c	o	m	/	!
Scan Order							1					9	8	2 & 7	6	5	4	3

It first looks at the 7th character and finds an 'e' instead of the '/' that it wanted. The skip table tells it that 'e' isn't in any possible match, so it jumps ahead 7 more characters where it finds a 't'. The skip table tells it to jump ahead 4 more characters where it finally finds the '/' it wanted. It then verifies that this is the last character of our "http://" prefix. With a valid prefix found, we prepare for a match in case we're lucky and the rest of the regex matches.

The bulk of the interpreter is in its "Go" method which is a 700 line switch statement that interprets the RegexCode we created earlier. The only interesting part is that the interpreter keeps two stacks to keep its state in case it needs to backtrack and abandon a path it took. The "run stack" records where in the search string an operation begins while the "run track" records the RegexCode instruction that could potentially backtrack. Any time there is a chance that the interpreter could go down a wrong path, it pushes its state onto these stacks so that it can potentially try something else later.

On our string, the following instructions execute:

Lazybranch - This is a branch that is "lazy." It will only occur if we fail and have to backtrack to this instruction. In case there are problems, we push 11 (the string offset to the start of "http://") onto the "run stack" and 0 (the RegexCode offset for this instruction) onto the "run track." The branch is to code offset 21 which is the "Stop" instruction.
Setmark - We save our position in case we have to backtrack.
Multi - A multi-character match. The string to match is at offset 0 in the string table (which is "http://").
Setmark - Another position save in case of a backtrack. Since the Multi code succeeded, we push our "run stack" offset of 18 (the start of "www.") and our "run track" code position of 5
Setrep - Loads the "\x1\x2\x1\x2F\x30\x64" set representation at offset 1 in the string table that we calculated earlier. It reads an operand from the execution stack that we should verify that the set repeats exactly once. It calls CharInClassRecursive that does the following:
1. It sees that the first character, 'w', is not in the character range ['/', '0'). This check corresponds to the '/' in the "[^\s/]" part of the regex.
2. It next tries CharInCategory which notes that 'w' is part of the "LowercaseLetter" UnicodeCategory. The magic number 0x64 in our set tells us to do a Char.IsWhiteSpace check on it. This too fails.
3. Although both checks fail, the interpreter sees that it needs to flip the result since it is a negated (^) set. This makes the character class match succeed.
Setloop - A "loop" instruction is like a "rep" one except that it isn't forced to match anything. In our case, we see that we loop for a maximum of Int32.MaxValue times on the same set we saw in "Setrep." Here you can see that the code generation phase turned the "+" in "[^\s/]+" of the regex into a Setrep of 1 followed by a Setloop. This is equivalent to "[^\s/][^\s/]*". The loop keeps chomping characters until it finds the '/' which causes it to call BackwardNext() which sets the current position to just before the final '/'.
CaptureMark - Here we start capturing group 1 by popping the "run stack" which gives us 18. Our current offset is 35. We capture the string between these two positions, "www.moserware.com", and keep it for later use in case the entire regex succeeds.
Oneloop - Here we do a loop at most one time that will check for the '/' character. It succeeds.
CaptureMark - We capture into group 0 the value between the offset on the "run stack", which is 11 (the start of "http://"), and the last character of the string at offset 36. The string between these offsets is "http://www.moserware.com/".
Stop - We're done executing RegexCode and can stop the interpreter.

Since we stopped with successful captures, the Match is declared a success. Sure enough, if we look at our console window, we see:

Full uri = 'http://www.moserware.com/'
Host ='www.moserware.com'

Backtracking Down Unhappy Paths

I can hear the cursing shouts of ^#!@.*#!$ from the regex mob coming towards me. They're miffed that I used a toy regular expression with a pathetically easy search text that didn't do anything "interesting."

The mob really shouldn't be that worried. We already have all the essential tools we need to understand how things work.

One common issue that you have to deal with in a "real" regular expression is backtracking.

Let's say you have a search text and pattern like this:

string text = "This text has 1 digit in it";
string pattern = @".*\d"; Regex.Match(text, pattern);

You'd recognize the parse tree:

The only thing new about it is that the '.' pattern was translated into a "Notone" node that matches anything except one particular character (in our case, a line feed). We see that the set follows the obscure, but compact representation. The only thing new to report is that '\x09' is the magic number to represent all Unicode digits (which the Turkey Test showed is more than just [0-9]).

It's painful to watch the regex interpreter work so hard for this match. The ".*" puts it in a Notoneloop that goes right to the end of the string since it doesn't find a line feed ('\n'). It then looks for the Set that represents "\d" and it fails. It has no choice but to backtrack by executing the "RegexCode.Notoneloop | RegexCode.Back" composite instruction which backtracks one character by resetting the "run track" to be the Set instruction again, but this time it will start one character earlier.

Even in our insanely simple search string, the interpreter has to backtrack by executing "RegexCode.Notoneloop | RegexCode.Back" and retesting the Set a total of thirteen times.

An almost identical process occurs if we had used a lazy match regular expression like ".*?\d". The difference is that it does a "Notonelazy" instruction and then gets caught up in a "RegexCode.Notonelazy | RegexCode.Back" backtrack and Set match attempt that happens fourteen times. Each iteration of the loop causes the "Notonelazy" instruction to add one more character instead of removing one like the "Notoneloop" instruction had to. This is typical:

In situations where the decision is between "make an attempt" and "skip an attempt," as with items governed by quantifiers, the engine always chooses to first make the attempt for greedy quantifiers, and to first skip the attempt for lazy (non-greedy) ones. Mastering Regular Expressions, p.159

If we had a little more empathy for the regex interpreter, we would have written "[^\d]*\d" and avoided all the backtracking, but it wouldn't have shown this common error.

Alternations such as "hello|world" are handled with backtracking. Before each alternative is attempted, the current position is saved on the "run track" and "run stack." If the alternate fails, the regex engine resets the position to what it was before the alternate was tried and the next alternate is attempted.

Now, we can even understand how more advanced concepts like atomic grouping work. If we use a regex like:

\w+:

to match the names of email headers as in:

Subject: Hello World!

Things will work well. The problem will come when we try to match against

Subject

We already know that there is going to be a backtracking since "\w+" will match the whole string and then backtracking will occur as the interpreter desperately tries to match a ':'. If we used atomic grouping, as in:

(?>\w+):

We would see that the generated RegexCode has two extra instructions of Setjump and Forejump in it. These instructions tell the interpreter to do unconditional jumps after matching the "\w+". As the comment for "Forejump" indicates, these unconditional jumps will "zap backtracking state" and be much more efficient for a failed match since backtracking won't occur.

Loose Ends

There are some minor details left. The first time you use any regex, a lot of work goes on initializing all the character classes that are stored as static variables. If you just timed a single Regex, your numbers would be highly skewed by this process.

Another common issue is whether you should use the RegexOptions.Compiled flag. Compiling is handled by the RegexCompiler class. The interesting aspects of the IL code generation is handled exactly like the interpreter, as indicated by this comment:

/* 
 * The main translation function. It translates the logic for a single opcode at 
 * the current position. The structure of this function exactly mirrors 
 * the structure of the inner loop of RegexInterpreter.Go(). 
 * 
 * The C# code from RegexInterpreter.Go() that corresponds to each case is 
 * included as a comment. 
 * 
 * Note that since we're generating code, we can collapse many cases that are 
 * dealt with one-at-a-time in RegexIntepreter. We can also unroll loops that 
 * iterate over constant strings or sets. 
 */

We can see that there is some optimization in the generated code. The down side is that we have to generate all the code regardless of if we use all of it or not. The interpreter only uses what it needs. Additionally, unless we use Regex.CompileToAssembly to save the compiled code to a DLL, we'll end up doing the entire process of creating the parse tree, RegexCode, and code generation at runtime.

Thus, for most cases, it seems that RegexOptions.Compiled isn't worth the effort. But it's good to keep in mind that there are exceptions when performance is critical and your regex can benefit from it (otherwise, why have the option at all?).

Another option is RegexOptions.IgnoreCase that makes everything case insensitive. The vast majority of the process stays the same. The only difference is that all instructions that compare characters will convert each System.Char to lower case, mostly using the Char.ToLower method. This sounds reasonable, but it's not quite perfect. For example, in Koine Greek, the word for "moth" goes from uppercase to lowercase like this:

That is, in Greek, when a "sigma" (Σ) appears in lowercase at the end of a word, it uses a different letter (ς) than if it appeared anywhere else (σ). RegexOptions.IgnoreCase can't handle cases that need more context than a single System.Char even though the string comparison functions can handle this. Consider this example:

string mothLower = "σής"; 
string mothUpper = mothLower.ToUpper(); // "ΣΉΣ"
bool stringsAreEqualIgnoreCase = mothUpper.Equals(mothLower, StringComparison.CurrentCultureIgnoreCase);  // true 
bool stringsAreEqualRegex = Regex.IsMatch(mothLower, mothUpper, RegexOptions.IgnoreCase); // false

This also means that .NET's Regex won't do well with characters outside the Basic Multilingual Plane that need to be represented by more than one System.Char as a "surrogate pair."

I bring all of these "cases" up because it obviously troubled one of the Regex programmers who wrote this comment twice:

// We do the ToLower character by character for consistency.  With surrogate chars, doing 
// a ToLower on the entire string could actually change the surrogate pair.  This is more correct 
// linguistically, but since Regex doesn't support surrogates, it's more important to be 
// consistent.

You can tell the author was fully anticipating the bug reports that eventually came as a result of this decision. Unfortunately, due to the way the code is structured, changing this behavior would take a hefty overhaul of the engine and would require a massive amount of regression testing. I'm guessing this is the reason why it won't be coming in a service pack anytime soon.

The last interesting option that affects most of the code is RegexOptions.RightToLeft. For the most part, this affects where the searching starts and how a "bump" is applied. When the engine wants to move forward or get the characters to the "right", it checks this option to see if it should move +1 or -1 character from the current position. It's a simple idea, but its implementation is with many "if(!runrtl)" statements spread throughout the code.

Finally, you might be interested in how Mono's regular expression compares with Microsoft's. The good news is that the code is also available online as well. In general, Mono's implementation is very similar. Here are some of the (minor) differences:

Mono's parse tree has a similar shape, but it uses more strongly typed classes. For example, sets such as [^\s/] are given their own class rather than encoded as a single string.
The Boyer-Moore prefix optimization is done in the QuickSearch class. It is calculated at run-time and is only used if the search string is longer than 5 characters.
The regex machine doesn't have a separate string table for referencing strings like "http://". Each character is passed in as an argument to the instruction.

Conclusion

Weighing in around 14,000 lines of code, .NET's regular expression engine takes awhile to digest. After getting over the shock of its size, it was relatively straightforward to understand. Seeing the real source code, with its occasional funny comments, provided insight that Reflector simply couldn't offer. In the end, we see that a .NET regular expression pattern is simply a compact representation for its internal RegexCode machine language.

This whole process has allowed me to finally connect with regular expressions and give them a splash of empathy. Seeing the horror of backtracking first hand in the debugger was enough for me to want to do everything in my power to get rid of it. Following the translation process down to the RegexCode level clued me into how my regex pattern will actually execute. Feeling the wind fly by a regex using the Boyer-Moore prefix optimization has encouraged me to do whatever I can to put string literals at the front of a pattern.

It's all these little things that add up to a blazingly fast regular expression.

Rebooting Computing: Why?

2009-02-03T12:15:00.000-05:00

Have you seen “The Most Famous Chart in Computer Science Education?” The exact numbers and data sources vary, but the curve always looks similar:

I used data from college bound seniors who indicated on their SAT that they intended to major in “Computer and Information Sciences and Support Services.” The curve tends peak between 1999 and 2001 and then you see a huge decline that has just begun to bottom out to numbers less than half their peak value.

Some people like to explain away this drop on another curve:

Although there was a correlation of computer science enrollment and the stock market, you'll see that the curves diverge around 2003. A popular belief is that the bursting dot-com bubble scared some potential students, but then by 2003 parents thought most software jobs were being offshored and encouraged their kids to pick a different field.

Some jobs did go to Bangalore, but the total number of jobs actually grew in the US, even beyond their 1999 levels. There are still excellent job prospects for the long term. Even in hard times like the 1970's recession, companies like Apple and Microsoft were founded. In 10 years, we'll know of a several great companies that got their start in the current financial crisis. It's unfortunate how students and their parents have been misled about the reality.

We're faced with a pipeline problem. The fresh-outs you'll be looking to hire in 10 years are in middle school right now. Are you doing anything to woo them to a career in computing? What do you say to a bright young girl to at least consider looking at computer science?

I could start with my story. As a kid, I was captivated by how I could think of an idea for a program and then have a computer execute it exactly. It was as if I could put part of my mind inside the computer. My parents and friends thought this was magic. It was magic, but it was a magic I could understand. There's always cool new things being computed. It was magical to see how Deep Blue beat Kasparov long before I began to understand the beauty of how it worked. Every day I listen to MP3s that were created by a compression algorithm that gets rid of sound that my ear can't hear. Companies like Walmart sift terabytes of data to predict market demand so they can send extra strawberry Pop-Tarts when hurricanes are approaching. On a personal level, new algorithms predict with a high accuracy what types of movies we'll like. But that's just one tiny sliver of what's out there. Each person can have their own unique experience. There's a lot of great computing going on and the demand is only increasing.

Sometimes you'll hear honest hesitations about a career in computing because of fears that they'll “sit in front of a computer all day.” The sad irony is that this thinking causes people to go into fields like accounting, graphic design, marketing, or hundreds of other fields where they spend just as much time in front of a computer. The difference is that they'll spend most of their time using applications like Outlook, Word, or Excel and often have less fun than the software developers that are creating these programs. Moreover, working in the computing fields will give someone a chance to create future interfaces that don't have everyone in front of giant screens all day.

This isn't to say that there aren't boring software development jobs, but there are also plenty of great jobs. It's a great career. I sometime feel a little guilty that I can work in a field that I enjoy. As a field, we create software that powers business communications and connects you with friends. Software will be a pivotal role in gene sequencing and analyzing that will usher in customized medical treatments and drugs. Software will drive many great innovations of the future.

It's sad that kids aren't even given a chance to see the breadth and excitement of our field. I don't blame them. On the whole, we're doing a terrible job broadcasting our image.

Professors often teach computer science as if it is some sterile thing with nothing new in it. This is just not true; we're in our adolescence. Sure, we bumble around and do silly things at times, but it also means we're growing. We're in an incredible time. Mehran Sahami captured this well at the conclusion of his intro class at Stanford:

“Think about the time that you're living in. Don Knuth, who is considered the father of Computer Science is still alive and he's in this department. It's sort of like you're geometers and you're living in the time of Euclid... It's all happening now. Don't think of this stuff as dead people who did this stuff and it just happened and now you're forced to do it. You're living in it.”

Mehran is one of the few teachers that do a great job of sharing the new and exciting possibilities of computer science. Too often you see teachers that claim that computer science is some small box that is exactly what they're teaching.

When I've had the honor of having conversations with computing pioneers like Alan Kay, I often hear how their teachers in the 60's would admit that they didn't understand the full possibilities of computing, and they wanted their students do better. The early ARPA community with J.C.R. Licklider at the helm is a great example of this style.

Licklider encouraged and funded wild and imaginative ideas that caused a huge boom in computer science back in the 60's and early 70's. Unfortunately, this slowed down in the 1980s as funders became more conservative, took fewer risks, and as a result got more incremental improvements rather than something big. I think this is why Alan Kay has difficulty finding significant new inventions in computing since 1980. Alan's statement sounds crazy until you see just how much of what we use was started before 1980. Some will point to the web and the browser as a huge new invention, but even Marc Andreessen, speaking on how he was able to create the first graphical web browser revealed:

“I was able to do it so quickly because it was the icing on the cake that had been baking for 30 years.”

Indeed he had. In the mid-60's, some of the baking started when Licklider funded Doug Englebart's amazing oN-Line System that amazingly had hypertext links and was operated by a mouse. Len Kleinrock's Ph.D. proposal on packet theory in 1961 gave him a great start that ultimately led to his team sending the first message over ARPAnet in 1969. Vint Cerf and Bob Kahn had already published a paper on TCP/IP, the bedrock of the Internet protocols, by 1974. All of these technologies were well refined and in production by the time Tim Berners-Lee created HTTP in the early 90's to which Andreessen would add a graphical front end.

Are we willing to fund long-term “wild” and “crazy” ideas today to create Internet-sized future results? We've been too focused on short term results. It's not just academia; most companies focus on short-terms results that dismiss the fact that computing is a young field and miss what really matters:

“Many HR departments haven't figured this out yet, but in reality, It's less important to know Java, Ruby, .NET, or the iPhone SDK. There's always going to be a new technology or a new version of an existing technology to be learned. The technology itself isn't as important; it's the constant learning that counts.” - Pragmatic Thinking and Learning, p.145

Bummer, Now What?

Last March, I was given the opportunity to be on a design team to start tackling some of these problems. We knew that we couldn't change the whole field and that some people would want to keep it the way it is. But we also knew that we had to do something; we didn't want to settle for the status quo.

Our primary task was to plan a “summit” of the best people from academia, government, and industry and get them all in one room so that we could get a good sample of the entire field. We didn't want to let people have the chance to point fingers outside and say it was somebody else's problem.

After working on the basic concept for the summit, we needed to give it a name. I had enjoyed many side discussions of the great days of Licklider, PARC, and the early culture that accomplished great things. Sort of as a joke, I thought that we needed to “reboot” computer science to get rid of the cruft that had accumulated over time and get back to the excitement when the field was brand new. After some discussion, we decided to change “computer science” to a broader field of “computing” and use the “magic and beauty” of computer science to be the driver of the “rebooting.”

Only later would I realize the rebooting metaphor could be stretched a bit further. We can “reboot” the field without throwing away the good parts just as an operating system can reboot and depend on its valuable non-volatile memory being preserved. Rebooting doesn't mean that we'll go down the same crufty path (e.g. perhaps we have better “drivers” now). Most importantly, the domain name was available so we ran with it.

After nine months of planning and inviting over 220 people, we had our summit in January at the Computer History Museum. It was the first time that such a broad representation of the computing field came to work together in the same room.

The summit was guided by the Appreciative Inquiry process. It's a technique that has you work in small teams to discover a positive core of what's giving the field life and then uses that to start dreaming of a better future. As the three days unraveled, we made it to the “design” phase where we kicked off several projects that fell into three rough categories:

Education
- K-8 Fundamentals (Creating engaging introductions of computing fundamentals at the elementary level)
- Project/Problem Based Learning for Grades 7-14
- CS in K-12: Essential Subject (Determining a path to get computing essentials introduced in the K-12 curriculum)
- Recruiting CS Teachers (Significantly increase the number of computer science teachers)
- National Curriculum for Multi-Disciplinary Collaboration
- International Educational Repository (that would include classroom activities and ideas for the K-16 level)
Outreach
- LabRats (Build learning communities that include after school activities focused on areas like computer science)
- Recruiting Women & Minorities into CS
- Image of Computing (Sort of like a marketing campaign to show how computing is changing the world)
- Tools for Fun and Beauty (Providing software tools for people sharing the fun and beauty of computing)
- Relevant Computer Science Intersecting with Socially Relevant Projects (e.g. providing infrastructure in third world countries or disaster response scenarios)
- Defining Future Computing Requirements for IT Service Verticals (e.g. Health Care, Financial, Government)
Internal Growth

Parallel Worlds Initiative (Leverage the boom in multi-core to drive new areas of thinking in computing)
Open Artifacts (e.g. create hardware and software systems that can easily be inspected, understood, assembled, disassembled and reused in new ways to allow for exploration)
Rediscovering Computing “Gems” (Revisit ideas from the past that might have been previously abandoned because they were infeasible but now might be possible)
Computing Field Guide (Create a resource to show the breadth of computing to both novices and experts)

I joined the Computing Field Guide team. I think it'll be fun to see if we can come up with a way to leverage many of the great existing resources out there and learn some of the breadth of the field as a result.

In the end, the three day summit was just the beginning of a long journey. It was a bit chaotic and some were disappointed we didn't fix everything right then or do more, but I think the summit gave a good context for the issues our field faces. My best memories include all of the great people that I met and being able to engage in some great conversations.

Steve Jobs said “you can't connect the dots looking forward; you can only connect them looking backwards.” I think that holds true for this summit. There are still a lot of dots between here and there; wherever “there” might be. With a lot of hard work, I'm confident that the dots will connect somehow. There's an interesting road ahead and I want to be a part of it. We need to start baking cakes for future generations to ice.

Your Turn

What do you think of the current state of computer science? What is your dream for the future? What are some things that we can start now to improve the current situation? Are you involved with any existing effort? Would you like to join ours?

I'd love to hear your thoughts.

P.S. There are several blog posts by fellow “Rebooters” ([1] [2] [3] [4] [5] [6] [7] [8] [9]). There are some pictures on flickr and a Rebooting Computing Community site that's starting to have follow-on discussion and might eventually have videos of highlights from the summit. In addition, you might watch this great talk by Dr. Peter Denning who has been leading this effort for over five years.

Wetware Refactorings

2009-01-02T12:15:00.001-05:00

Brain rot.

While others were enjoying the final months of their college senioritis, I was worried about brain rot. It hit me that in order to be bad or at best mediocre at something, all I had to do was... nothing. From a boring job to a bad marriage, it seemed that the secret to mediocrity was to coast along and not make any adjustments or actively work to make things better. Towards graduation, I knew that I had the option of going into the workplace and just let things happen, stop actively learning, and let my brain rot. It'd take awhile for people to realize that I'd stopped caring about learning. But by then, I'd be locked into a job where it didn't matter.

The alternative was to force myself to keep learning and accept the fact that it would never be easy. Fearful of brain rot, I decided to pick this second path. But I was on my own. Unlike school, there wouldn't be anyone forcing me to learn new things. Even with this decision, there was a slight feeling I was part of a losing game.

Throughout my school years, the consistent message about the brain was that you were given a limited number of brain cells at birth and you had to do your best to keep all the ones you could. At best, you could hope to somehow mature the ones that remained. Popular culture promoted this message and sometimes joked about it, such as Cliff's "Buffalo Theory" on Cheers:

"Well you see, Norm, it's like this... A herd of buffalo can only move as fast as the slowest buffalo and when the herd is hunted, it is the slowest and weakest ones at the back that are killed first. This natural selection is good for the herd as a whole, because the general speed and health of the whole group keeps improving by the regular killing of the weakest members. In much the same way, the human brain can only operate as fast as the slowest brain cells. Now, as we know, excessive drinking of alcohol kills brain cells. But naturally, it attacks the slowest and weakest brain cells first. In this way, regular consumption of beer eliminates the weaker brain cells, making the brain a faster and more efficient machine. And that, Norm, is why you always feel smarter after a few beers."

I kept this depressing view of brain cell scarcity until I learned about neurogenesis:

Fortunately, professor Elizabeth Gould thought otherwise. In a discovery that turned the field on its ear, she discovered neurogenesis -- the continued birth of new brain cells throughout adulthood. But here's the funny part. The reason researchers had never witnessed neurogenesis previously was because of the environment of their test subjects.
If you're a lab animal stuck in a cage, you will never grow new neurons.
If you're a programmer stuck in a drab cubicle, you will never grow new neurons.
On the other hand, in a rich environment with things to learn, observe, and interact with, you will grow plenty of new neurons and new connections between them.
For decades, scientists were misled because an artificial environment (sterile lab cages) created artificial data. Once again, context is key. Your working environment needs to be rich in sensory opportunities, or else it will literally cause brain damage. Pragmatic Thinking and Learning, p.67

Neurobics

While listening to a segment on Radio Lab, I finally realized that the brain doesn't have one central command structure that interprets the world. It's more likely that each sensory organ feeds in its own "note" to your mind and it's the combined musical "chord" that you perceive as a thought or memory.

In an attempt to take advantage of this discovery, I checked out the book "Keep Your Brain Alive: 83 neurobic exercises to help prevent memory loss and increase mental fitness." It was a bit odd for me to read since the book is targeted at people twice my age, but it highlighted the interesting concept of "neurobics" which are like neural aerobics. The book explains how neurobics take advantage of the decentralized nature of your brain:

Involve one or more of your senses in a novel context. By blunting the sense you normally use, force yourself to rely on other senses to do an ordinary task. For instance: Get dressed for work with your eyes closed.
Engage your attention To stand out from the background of everyday events and make your brain go into alert mode, an activity has to be unusual, fun, surprising, engage your emotions, or have meaning for you. (e.g. turn the pictures on your desk upside down)
Break a routine activity in an unexpected, nontrivial way. Novelty just for its own sake is not highly neurobic. Routine breakers include taking a completely new route to work and shopping at a farmers market instead of a supermarket.
- Keep Your Brain Alive, pp.33-34

Some of my favorite suggestions from the book include:

Shower with your eyes closed. (p.43)
Brushing roulette: brush your teeth with your nondominant hand. (p.44) This also works for other routine activities like using your mouse.
The sightless start: enter and get ready to start your car with your eyes closed. (p.55)
Take brain breaks: a walk or social lunch break can help invigorate the mind. (p.81)
Have an ongoing chess game.

The last was the most interesting, and had me involve coworkers:

We know of one office where a chessboard was left out near the water cooler. Any employee could come to the board (preferably during a break), assess the situation, and make a move. It was an ongoing game, with no known players, and no winners or losers.
Even a novice chess player will weigh dozens of possible moves, attempt to visualize the consequences of each one, then select the move that offers some strategic advantage. This type of "Random-player" chess game doesn't allow anyone to develop a long-term strategy. But it does require visual-spatial thinking that is different from what most of us do at work. The brief gear switching provides a break from verbal, left-brain activities and lets the "working brain" take a breather. - Keep Your Brain Alive, p.83

In my case, the chess game didn't work out exactly like the book described, but it has been fun. I set up a small magnetic chess board on my desk and encouraged anyone to come and make a move. I thought it'd be interesting to have clear winner and loser. This posed a challenge of how to keep track of the game that had no time limit or fixed set of players. I used a business card to track of whose turn it is. When the side with the printing on it is turned up, it means that it's black's turn; otherwise it's white's turn. This "protocol" has worked out well and has allowed several coworkers to play throughout the day. As a side benefit, it's caused me to actively work at getting better at chess.

Refactoring Your Wetware

Last week, I read through Andy Hunt's excellent "Pragmatic Thinking & Learning: Refactor Your Wetware" that has many more pragmatic brain tips that are written from a programmer perspective. The book is centered around the Dreyfus Model of skill acquisition where learning starts at a beginner stage where you need a lot of rules to function and then transitions all the way up to an expert level where you rely heavily on intuition. Here are just a few of the many ideas presented in the book:

Add sensory experience to engage more of your brain: continuing on the neurobics theme, Andy Hunt has some interesting ideas (pp.74-75):

Instead of UML diagrams, try toy blocks or Lego bricks.
Use physical CRC cards to engage your touch and spatial senses.
Draw a picture ("not UML or an official diagram; just a picture")
Describe your design verbally.
Act out your software design with coworkers.

Create a "Pragmatic Investment Plan" where you treat your skills and what you want to learn with at least as much care as you take with your finances and apply similar skills (e.g. diversify, have short and long term goals). Make sure your goals are Specific, Measurable, Achievable, Relevant, and Time-Boxed (SMART) (pp.154-156)
Consider starting a reading group with people in the office to help learn a skill from a book. (p.164)
Make sure you have freedom to explore ideas by having a "starter kit" infrastructure of version control, unit testing, and build automation. This gives you the safety to fail, which is often needed when learning. (p.192)
Unscaffolding: artificially make things harder than they need to be so that when you have to do it for real, it seems a lot easier (e.g. train for running by tying weights to your ankles). I like how the author claims that this is why Ruby programmers should at least spend some time working in C++ (p.206)
Develop Your Exocortex: Have a place outside your brain where you can store and organize thoughts. The author recommends a personal wiki. I personally prefer to use Google Notebook. (p.221)

Be the Query

I enjoyed the discussion in the book on changing your perspective, especially when it comes to feeling like you're inside the system you're creating:

Imagine yourself as an integral component of the problem you're working on: suppose you are the database query or the packet on the network. When you get tired of waiting in line, what will you do? Who would you tell? - (p.107)

I think that this approach can help lead to a richer Object Thinking in software designs. For example, if you can picture yourself as a database query, I think you'll have much more empathy for what's going on. This thinking might influence your design to avoid painful table scans and favor indexes.

Another way to change your perspective is to use oblique strategies:

These questions and statements force you to draw analogies and to think more deeply about the problem. They are a great resource to draw on when you' get stuck. - (p.108)

Some example strategies include:

Use fewer notes
Don't be afraid of things because they're easy to do.
What wouldn't you do?

I printed a bunch of cards with each strategy on them and keep them by my desk in a coffee mug. It's a new addition, so I don't have long term results, but it is fun to take one out and think of how it might relate to a problem I'm working on when I get stuck.

Keep Your Brain Cache Warm

Many brain changing ideas require you to focus. This is hard to do when our jobs often require us to multitask or our culture encourages us to check email frequently in order to respond quickly and look good among our peers. There are dangers to this:

Scientists agree that trying to focus on several things at once means you'll do poorly at each of them.
And if that wasn't bad enough, a controversial study done in the United Kingdom noted that if you constantly interrupt your task to check email or respond to an IM text message, your effective IQ drops ten points.
By comparison, smoking a marijuana joint drops your IQ a mere four points. - Pragmatic Thinking and Learning, p.228

This is really hard to overcome. Since reading this, I've tried to avoid checking Outlook more than once an hour. After each check, I shut it down to prevent the distraction. I've found that it's helpful to actually shut it down; otherwise it's too tempting to ALT+TAB to it or get lured in by a notification message.

If you replace "phone" with "email", you can see that Peopleware described over two decades ago why most people are working far below their potential of being in a state of "flow" where you actually get stuff done:

If the average incoming [email] takes five minutes and your reimmersion period is fifteen minutes, the total cost of that [email] in flow time (work time) lost is twenty minutes. A dozen [emails] use up half a day. A dozen other interruptions and the rest of the work day is gone. This is what guarantees, "You never get anything done around here between 9 and 5." - Peopleware 2nd edition, p.63

Therefore, for the sake of your sanity and focus, be careful before flushing your brain cache by doing a context switch. The time saved can be used for more creative thinking and getting things done.

Is this All a Bunch of Hooey?

I admit that some of these ideas sound silly. I haven't yet worked up the courage to bring Legos to a design meeting yet, but I can see how it would help use a different neural pathway and activate more gray matter. Surely that couldn't hurt, right? It'd probably bring a new perspective and overcome a road block. This is probably why some of the most creative companies encourage playful behavior at work. This might be seen as a horrible waste of time to traditional management (and shareholders for that matter), but it's much more likely to use more of your brain which in turn might create better solutions.

One alternative to all of this is to just coast along and not take thinking and learning into your own hands. Left on their own, your company is likely to put you through a sheep dip using a "training course" in an artificial environment that will easily wear off just like a farmer might dunk his sheep into a chemical bath to get rid of parasites which will also wear off and need to be repeated.

While sometimes uncomfortable at first, I've enjoyed incorporating some "wetware refactoring" into my daily life as a way to overcome brain rot and aid learning and thinking. It sure beats a sheep dip.

What do you do? Do you have specific wetware refactorings that you do? I'd love to hear them; the "crazier" they are the more likely they'll probably activate different neural pathways and probably lead to a better result. Let me know in the comments.

The Private Life of a Public API

2008-12-02T08:00:00.001-05:00

In college, I'd add "public" in front of my classes and methods without giving it much thought. Sure, I knew about "protected" and "private" and would use them where it made sense, but I had no pragmatic experience of designing my "public" code so that other people could easily use it.

Even a few years after graduation, I still didn't have to worry much about creating a public Application Programmer Interface (API). As it turned out, I was often the only "Programmer" that my code had to "Interface" with.

But I had a dream.

I knew that if I really wanted to get better as a programmer, I would have to write code that others could easily reuse. About two years ago, I started using Reflector to make some serious study of the internals of the .NET Framework. It was great to be able to do deep "reflectorings" on a real framework that is used by millions of people and see its good parts and its mistakes.

My next big step was following the recommendations of several blogs and reviews by buying a copy of Framework Design Guidelines by Krzysztof Cwalina and Brad Abrams. It's full of practical advice that explicitly points out how the .NET framework itself was intentionally designed. I found the book to be helpful enough that I really wanted to be a reviewer of the second edition. I didn't make the cut, but the publisher was kind and sent me a copy of it. I spent the past few days reading the new edition searching for updates. In the process, I also reflected on the older, but still relevant, guidelines from the first edition.

One of my favorite parts of the book is that it is full of annotations from the people in the trenches that actually designed the framework. For example:

"If you say what your library does and ask a developer to write a program against what he or she expects such a library to look like (without actually looking at your library), does the developer come up with something substantially similar to what you've produced? Do this with a few developers. If the majority of them write similar things without matching what you've produced, they're right, you're wrong, and your library should be updated appropriately." - Chris Sells, p.3

The book continues with many details of the work that goes into creating a public API and it helps shed some light an API beyond its short IntellSense description.

It's FileName, not Filename. Ok?

The design guidelines don't hide their goal:

"Consistency is the key characteristic of a well-designed framework... Consistency is probably the main theme of this book. Almost every single guideline is partially motivated by consistency..." - p.6

The problem with consistency is dealing with all the micro decisions that we have to make when we're programming. When writing a file open dialog class, how do you get the name of the file the user selects? You have at least 3 choices:

dialog.getFilename()
dialog.get_file_name()
dialog.FileName

There's nothing wrong with any of these names or styles from a general perspective. If you write Java code, option #1 is a good choice. Option #2 is reasonable for people writing C++ code that uses the STL. But on .NET, there is no choice: you need to go with #3.

Names in .NET libraries must follow a few simple rules. Almost all names in .NET are "PascalCased" except for method arguments which are "camelCased." Acronyms over two letters are treated as words (e.g. System.IO and System.Xml). There are also a few rules about compound words that I had to burn into my memory after I broke the rules too many times:

Pascal	Camel	Not
Canceled	canceled	Cancelled
FileName	fileName	Filename
Hashtable	hashtable	HashTable
Id	id	ID
Ok	ok	OK
UserName	userName	Username

(Subset of table from p.43)

The book hints at the naming process:

"In the initial design of the Framework, we had hundreds of hours of debate about the naming style. To facilitate these debates we coined a number of terms. With Anders Hejlsberg, the original designer of Turbo Pascal, and key member of the design team, it is no wonder that we chose the term PascalCasing for the casing style popularized by the Pascal programming language." - Brad Abrams, p.38

Ultimately, it doesn't matter how the name styles were chosen. The decision has been made. I once thought it didn't matter about these tiny details, but it really adds up over thousands of methods. Name things however you want on other platforms: use underscores, SCREAMING_CAPS, whatever, just not in .NET.

Hurling Programmers into a Pit of Success

It's sometimes humbling when you see people use an API that you worked hard on. Imagine that you've spent a week creating a class that hides all the database goo involved in getting employee information and puts it into an array. Then, to your horror, you see someone write this:

Company company = GetCompany(companyName);
for (int i = 0; i < company.Employees.Length; i++)
{
   Paycheck paycheck = CreatePaycheck(company.Employees[i]);
   SendPaycheck(paycheck);
}

Since you decided to expose things as a mutable array, you have to make a copy before returning it. The poor guy writing this simple code is going to have terrible performance because your code made it look like getting the employees array was "cheap." His code is doomed to 2n copies of the employee array because of your decision. The guidelines give guidance on how to avoid this problem: return a read-only collection or rename the property to a "GetEmployees" method so that programmers know the task isn't "cheap."

In addition to thinking about performance, you also have to keep in mind the context in which your code will be called. I've seen too many modern APIs that were designed by people who either didn't think about or care about their users. Methods that have boolean parameters are usually suspect. Methods with multiple boolean parameters are downright terrible.

Compare:

Stream stream = File.Open("file.txt", true, false);

with

Stream stream = File.Open("file.txt", FileMode.Open, FileAccess.Read);

Can you tell what the first one does? What about the second?

When I first read the "Member Design" chapter two years ago, I vowed I would never subject users to out-of-context boolean parameters again. A benefit of this has been that I'm able to read my old code months or years later and still understand what it does when I otherwise would have long forgotten the boolean parameters of a function.

There are many other, sometimes subtle things you can do to help make users successful with your code:

If you override .Equals on your class, you really should override .GetHashCode or your objects might do bad things when put in hashtables/dictionaries. (p.270)
If you need a specific time of day (e.g. when to unlock a door each day), use a TimeSpan rather than a DateTime with some random date or some arbitrary number. (p.263)
If you have an asynchronous method that invokes an event handler, make sure you do it on the proper thread (p.306). If you don't, you might scar a novice programmer for life with threading pains.
Don't forget that end-users need to unit-test their code that is built using your library (p.7). This might involve making key methods virtual or factoring them out to an interface that can be swapped out with a "mock" implementation.

Nobody's Perfect

Even when you have the best intentions, you'll make mistakes. For example, Path.InvalidPathChars is a mistake. It's a read-only field that is an array of characters that are invalid in filenames. Although the array reference is read-only, the array contents are not. This can lead to potential security issues if users depend on this array for safety and malicious code modifies the array contents.

Microsoft now recommends people use Path.GetInvalidPathChars() instead which returns a copy of the array instead. This is sort of ironic because it violates another type member guideline:

"DO NOT have properties that match the name of 'Get' methods" - p.69

This isn't too bad since Microsoft has marked the old method as obsolete, which gives them a chance to remove it in, ten years or so. In the meantime, novice users might continue to be confused as to why there are two ways for getting invalid path characters.

Public APIs: 21st Century Sewer Systems

I often think that public APIs are like sewer systems. They're the low-level "plumbing" that no one really cares about or notices when they're working well. In fact, being boring is a "feature:"

"Please don't innovate in library design. Make the API to your library as boring as possible. You want the functionality to be interesting, not the API." - Chris Sells, p.5

It's easy to look at guidance like the Framework Design Guidelines and think they're a bunch of minute details that don't really matter and that following them will turn you into a mindless drone. Maybe I'm brainwashed, but I've found that having a de-facto standard on details helps me concentrate on the bigger picture: designing the functionality that users care about.

In addition to the book, there are other good resources online:

The Framework Design Guidelines Digest
Framework Design Guidelines session from PDC 2008
FxCop is a tool that will automatically check your code for guideline "violations." It was especially helpful in helping me fix Turkey Test violations.

.NET is just one framework out there. There are great lessons from other platforms as well. Google's Chief Java Architect, Josh Bloch, has some great advice on developing good APIs, very little of it is specific to Java.

In The End...

Although it takes a lot of work to create a public API, it can be incredibly rewarding. It's exciting to hear about people you've never met before successfully using an API you've written.

Have fun, develop great code, and go public with care.

Boy Scout Check-ins

2008-10-31T08:40:00.003-04:00

I missed the Boy Scouts callout when I was kid. Perhaps that's why it took me 20 years to figure out a knot that keeps my shoes tied all day. My recent attempt at starting a campfire required a propane torch. Despite my shortcomings, I felt a connection to the Scouts while reading this:

It's not enough to write the code well. The code has to be kept clean over time. We've all seen code rot and degrade as time passes. So we must take an active role in preventing this degradation.
The Boy Scouts of America have a simple rule that we can apply to our profession.
Leave the campground cleaner than you found it.
If we all checked-in our code a little cleaner than when we checked it out, the code simply could not rot. The cleanup doesn't have to be something big. Change one variable name for the better, break up one function that's a little too large, eliminate one small bit of duplication, clean up one composite 'if' statement.
Can you imagine working on a project where the code simply got better as time passed? Do you believe that any other option is professional? Indeed, isn't continuous improvement an intrinsic part of professionalism? [Clean Code, p14]

While reading this, I was reminded of another gem:

Well-designed code looks obvious, but it probably took an awful lot of thought (and a lot of refactoring) to make it that simple. [Code Craft, p247]

Both sound great, but they have a sort of "Don't forget to floss" ring to them.

We've heard for years that refactoring helps improve code, but actually doing it can sometimes feel too daunting. It's just a fact that a lot of the code we deal with on a daily basis doesn't have enough test coverage, if there are any tests at all, to have us feel fully confident with many changes that we make to our code.

But a Scout wouldn't let the sad state of some parts of the code get him down. A Scout would always have his nose out for stinky code to clean up so that he could get a teeny bit of satisfaction knowing that he checked-in code that was better than when he checked it out.

This isn't a new idea; it's just a matter of realizing how easy it is.

Examples

There's a lot of low-hanging fruit in a typical code base. Over months of development, the top of a C# file might look like this:

using System.Linq;
using System;
using System.Collections.Generic;
using Moserware.IO;
using System.Diagnostics;
using System.Text.RegularExpressions;
using System.Text;using System.Threading;

This is a messy way to introduce your code. With just a simple click in Visual Studio, you can have it automatically remove clutter and sort things to get something nicer:

using System.Text.RegularExpressions;
using System.Threading;
using Moserware.IO;

For a three second time investment, you'll leave the file slightly better than you found it. With a free add-in, you can do this for your entire project in about the same amount of time.

Different team members can often work in the same class and you'll end up with member variable declarations that identify each person's style:

public class CircularBuffer<T>
{
  T[] m_array;
  private object syncRoot = new object();
  private int _HeadIndex;
  private int m_TailIndex;
...

This can easily be made consistent in few seconds:

public class CircularBuffer<T>
{
  private T[] _Array;
  private int _HeadIndex;
  private int _TailIndex;
  private object _SyncRoot = new object();
...

Changing a line like this:

if((i >= minAmount) && (i <= maxAmount))

to use number-line order:

if((minAmount <= i) && (i <= maxAmount))

makes the code slightly more visual and easier to read.

Introducing an explaining variable can turn:

private static DateTime GetElectionDay(int year)
{
  DateTime startDate = new DateTime(year, 11, 1);
  // Get the first Tuesday following the first Monday
  if (startDate.DayOfWeek <= DayOfWeek.Monday)
  {
     // Current day of the week is before Tuesday
     return startDate.AddDays(DayOfWeek.Tuesday - startDate.DayOfWeek);
  }
  else
  {
     // Current day of the week is Tuesday or after
     return startDate.AddDays(7 - (startDate.DayOfWeek - DayOfWeek.Tuesday));
   }
}

into a slightly more maintainable version that doesn't need comments:

private static DateTime GetElectionDay(int year)
{
  DateTime nov1 = new DateTime(year, 11, 1);

  int daysUntilMonday;
  if (nov1.DayOfWeek < DayOfWeek.Tuesday)
  {
     daysUntilMonday = DayOfWeek.Monday - nov1.DayOfWeek;
  }
  else
  {        
     daysUntilMonday = 6 - (nov1.DayOfWeek - DayOfWeek.Tuesday);        
  }

  DateTime firstMonday = nov1.AddDays(daysUntilMonday);
  return firstMonday.AddDays(1);
}

Along these lines, I tend to agree with Steve Yegge's observation:

The [Refactoring] book next tells me: don’t comment my code. Insanity again! But once again, his explanation makes sense. I resolve to stop writing one-line comments, and to start making more descriptive function and parameter names.

By themselves, each of these refactorings almost seems too simple. But each leaves your code in a slightly better place than you found it thereby qualify as a "Boy Scout Check-In."

Be Careful

We've probably all heard horror stories of some poor programmer who changed just "one little character" of code and caused rockets to explode or billion dollar security bugs. My advice is to not let that be you. Write more tests and use code reviews if that helps. Just don't let it be an excuse to not do something.

Boy Scout Check-ins should be short and measured in minutes for how long they take. Get in and out with slightly better code that fixed one small thing. Try hard not to fix a bug or add a feature while doing these small check-ins or you might face the wrath of your coworkers as Raymond Chen points out:

Whatever your changes are, go nuts. All I ask is that you restrict them to "layout-only" check-ins. In other words, if you want to do some source code reformatting and change some code, please split it up into two check-ins, one that does the reformatting and the other that changes the code.
Otherwise, I end up staring at a diff of 1500 changed lines of source code, 1498 of which are just reformatting, and 2 of which actually changed something. Finding those two lines is not fun.

Avoid Cycles

One subtle thing to realize is that you don't want to get lost in an infinite loop with a coworker of mutually exclusive changes. This is easy since good people can disagree. For instance, compare:

Use 'final' or 'const' when possible By declaring a variable to be final in Java or const in C++, you can prevent the variable from being assigned a value after it's initialized. The final and const keywords are useful for defining class constants, input-only parameters, and any local variables whose values are intended to remain unchanged after initialization. [Code Complete 2, p243]

and

I also deleted all the 'final' keywords in arguments and variable declarations. As far as I could tell, they added no real value but did add to the clutter. Eliminating 'final' flies in the face of some conventional wisdom. For example, Robert Simmons strongly recommends us to "... spread final all over your code." Clearly I disagree. I think there are a few good uses for 'final', such as the occasional 'final' constant, but otherwise the keyword adds little value and creates a lot of clutter. [Clean Code, p276]

Don't get bogged down with someone else on adding and removing 'final' or 'readonly'. Just be consistent.

I'm embarrassed to admit that in my earlier days, I might have "cleaned" code like this:

string headerHtml = "<h1>" + headerText + "</h1>";

into

string headerHtml = String.Concat("<h1>", headerText, "</h1>");

or even worse:

StringBuilder sb = new StringBuilder();
sb.Append("<h1>");
sb.Append(headerText);
sb.Append("</h1>");
string headerHtml = sb.ToString();

In this first case, I thought I was brilliant because I knew about the Concat method and thought it'd give me faster code. This is not true because the C# compiler special cases string concatenation to automatically do this. The second example is painful because it's uglier and slower and it isn't building a string in a loop where StringBuilders make a lot of sense.

After many dumb mistakes like this, I've finally decided that if I ever have a doubt on which option to use, I'll pick the more readable one:

Write your code to be read. By humans. Easily. The compiler will be able to cope. [Code Craft, p59]

Coda

Boy Scout check-ins are small steps that help fix the broken windows that we all have in our code. When you look at your code, try to find at least one thing you can do to leave it better. Eventually it becomes a game where everyone benefits. These check-ins can often be a small reward for checking-in a large feature or fixing a nasty bug.

If you're pressed for time and can't make the change now or you want to save it for when you can make the change across all your code, make a note to yourself. I create empty change-lists in my version control system for this purpose. This is also helpful if you find a bug and want to later complained that hand-washing took too long and "wasted" their precious time. We all have our own pressures that might cause us to think that we can neglect basic code hygiene. Over time, this snowballs into a mess that we've all had to deal with.

Only you can make a difference in your code campground.

How Do Locks Lock?

2008-09-29T08:26:00.007-04:00

When I was 9 or so, I was convinced I could write my own operating system in GW-BASIC. After all, I had written programs that played Mary Had a Little Lamb on the PC speaker while displaying CGA graphics. How much harder could an operating system be?

One thing had me stumped. How would I get my OS to multitask?

After giving it some thought, the best idea I could come up with was to write the programs for my "OS" in such a way that they would occasionally perform a GOSUB or GOTO to parts of other programs. By using a lot of mental handwaving to myself, I was convinced I could somehow make it work.

But the details came back to bite me. I never pulled it off. I put it aside and worked on other things. I just assumed that something magical happened under the covers. My bedtime reading of magazines like PC/Computing convinced me that the magical solution to the problem included buzzwords like "preemptive multitasking" and "multithreading." Both of these ideas were in the upcoming Windows NT 3.1 design. I didn't really understand what these buzzwords meant, but at least they sounded impressive.

Even though I've learned a bit more about writing programs that can do more than one thing at a time since those early days, I still have points where I don't understand exactly what is going on. Recently, I decided that I wanted to stop my handwaving about locks and do whatever it took to find out how they, well... lock.

A View from the Top

Locks let you express your belief that something bad might happen if two threads go through a section of code at the same time. Locks are present in many languages. Here's an example of one in C#:

object syncRoot = new object();

private void MyFunction()
{
 lock (syncRoot)
 {
     // only one thread can enter this locked gate at a time.
 }
}

The above lock creates a "gate" that only allows one thread at a time regardless of what that thread is doing. This is often too pessimistic and inefficient. In a lot of cases, it doesn't matter if multiple threads are reading a piece of data at the same time. However, we want to make sure that there is only one writer at a time. Furthermore, we want to make sure that the readers don't see corrupted garbage.

A lock that is optimized for allowing multiple readers at a time while still being consistent in the face of writers is called a reader/writer lock. Here's an example of some typical code you might see in an application that has to cache objects that take a long time to create:

private readonly Dictionary<string, ReallyExpensiveObject> expensiveObjectCache
 = new Dictionary<string, ReallyExpensiveObject>();

private readonly ReaderWriterLock rwl = new ReaderWriterLock();

public ReallyExpensiveObject GetExpensiveObject(string key)
{           
 ReallyExpensiveObject expensiveObject;

 rwl.AcquireReaderLock(Timeout.Infinite);

 try
 {
     if (this.expensiveObjectCache.TryGetValue(key, out expensiveObject))
     {
         // Cache hit
         return expensiveObject;
     }

     // Cache miss
     LockCookie cookie;

     cookie = rwl.UpgradeToWriterLock(Timeout.Infinite);
     try
     {
         expensiveObject = new ReallyExpensiveObject();
         expensiveObjectCache[key] = expensiveObject;
         return expensiveObject;
     }

     finally
     {
         rwl.DowngradeFromWriterLock(ref cookie);
     }
 }
 finally
 {
     rwl.ReleaseReaderLock();
 }
}

This code will allow more than one reader at a time and will handle the case of upgrading the read lock to a write lock if it needs to insert an item into the cache. The code is a bit long and tedious to write. [1] Even worse, it has a very subtle bug in it that we'll look at later.

We first need to understand what is going on inside a lock. Since reader/writer locks are usually more interesting than a normal lock, we'll focus on the details of a reader/writer lock implementation. [2]

Entering an Internal Lock

Locks themselves have internal data that they must protect from corruption by competing threads. This internal data includes the number of active readers and how many threads are waiting to write data. In order to provide this protection, locks must enter an internal lock.

For simplicity, locks usually have a single variable that indicates if a thread has acquired the internal lock. I'll illustrate this and other concepts by posting snippets from Vance Morrison's excellent reader-writer lock sample: [3]

 private void EnterMyLock()  {
 if (Interlocked.CompareExchange(ref myLock, 1, 0) != 0)
   EnterMyLockSpin();
}

In Vance's code, a member variable named "myLock" is set to 1 if the lock is held, otherwise it is 0. The Interlocked.CompareExchange function is interesting because it does two things. If "myLock" is 0, then it is set to 1. If "myLock" doesn't equal 0, then we know that someone else has the internal lock. The documentation says that "the compare and exchange operations are performed as an atomic operation." I was curious how this actually worked, so I looked at .NET's source code and eventually hit this wall:

[MethodImplAttribute(MethodImplOptions.InternalCall)]
[ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success)]
public static extern int Exchange(ref int location1, int value);

In my earlier .NET days, I would have given up at this point. The "InternalCall" attribute indicates that the CLR handles the call internally. It seemed like I would never quite know what happened inside this mysterious internal call.

And then I met Rotor.

Inside an InternalCall

Rotor lets you look at the CLR's internals that are mostly written in C++ with a small amount of assembly code. [4] If you navigate through several layers of function calls, you'll see that Interlocked.CompareExchange ultimately reaches this function in clr/src/vm/i386/asmhelpers.asm that is written in x86 assembly: [5]

FASTCALL_FUNC CompareExchangeMP,12
 _ASSERT_ALIGNED_4_X86 ecx
 mov eax, [esp+4]        ; Comparand
 cmpxchg [ecx], edx
 retn 4                  ; result in EAX
FASTCALL_ENDFUNC CompareExchangeMP

By far, the most interesting aspect of this is the "lock cmpxchg" line. Besides giving gamers power to play DOOM, the 486 chip introduced a "cmpxchg" instruction that will both compare a value and exchange it with a new value if the comparison succeeds. It does this in a single CPU instruction. This is how the documentation can claim that it is an "atomic" operation. We'll see why it's very important to do this in a single instruction a bit later. The "lock" prefix is used to tell the CPU to assert a physical signal so that no other core can access memory at the same time. [6] This hardware locking is how the "myLock" variable can remain safe from simultaneous access by other cores.

But now what happens if another thread already had the internal lock?

Spinlocks

When locks need to wait on the internal lock, they typically use a spinlock. This tells the processor to essentially spin around in circles in order to waste a little bit of time so that the thread that has the internal lock can possibly finish what it is doing and exit the lock.

Here's an example from Vance's code of how a spinlock is performed:

private void EnterMyLockSpin()
{
 for (int i = 0; ;i++)
 {
     if (i < 3 && Environment.ProcessorCount > 1)
         Thread.SpinWait(20); // Wait a few dozen instructions to let another processor release the lock. 
     else
         Thread.Sleep(0); // Give up my quantum.

     if (Interlocked.CompareExchange(ref myLock, 1, 0) == 0)
        return;
 }
}

It's a basic for loop that has a few interesting bits. The first thing to notice is that this loop will keep going until the CompareExchange succeeds. That is, until we acquire the internal lock.

On a multiprocessor system, it will try a Thread.SpinWait for 3 times. The documentation for SpinWait is a bit confusing about what it does with the "20" argument:

SpinWait essentially puts the processor into a very tight loop, with the loop count specified by the iterations parameter. The duration of the wait therefore depends on the speed of the processor.

What exactly is it doing? Looking at Rotor's clr/src/vm/comsynchronizable.cpp gives us the reality:

FCIMPL1(void, ThreadNative::SpinWait, int iterations)
{
 WRAPPER_CONTRACT;
 STATIC_CONTRACT_SO_TOLERANT;

 for(int i = 0; i < iterations; i++)
     YieldProcessor();
}
FCIMPLEND

Further diving shows that "YieldProcessor" is this macro:

#define YieldProcessor() __asm { rep nop }

This is a "repeat no-op" assembly instruction. It's also known in the Intel instruction set manual as "PAUSE - Spin Loop Hint." [7] This means that the CPU knows about the spin waiting that we're wanting to accomplish.

As the documentation hinted, the time spent waiting is dependant upon the clock rate of the machine. In my case, I have an EE6600 Core 2 Duo where each core runs at 2.4 GHz, and it's about 3.4 nanoseconds for each "YieldProcessor" call. [8] This means it takes approximately 70 nanoseconds for 20 iterations. Three unsuccessful passes through this loop will cost about 210 nanoseconds.

I'm sure that if reader/writer locks had cheerleaders inside of them, they would be shouting in hope that the spin wait used enough time so that the thread that had the internal lock that is protected by the "cmpxchg" will have released it.

Why does the lock try so hard to get by with only a spin wait? In a word: speed.

By not being able to satisfy the request with a spin wait, the thread gives up and goes to sleep. This requires intervention by the OS to potentially swap it out and run a different thread that that has been waiting. By letting another thread run, there is a chance that the CPU will have to toss out its onboard cache only to fetch it back when the thread gets swapped back in. All of this could potentially add up to hundreds of thousands of CPU cycles that aren't being used to get "real" work done. [9]

How Does a Thread Sleep? How Does it Know When to Wake Up?

Windows keeps track of the state of each thread in your system. [10] Here's a simplified thread state chart from the excellent Windows Internals book:

When your thread is "Running" and is interrupted because its time-slice ran out or it voluntarily gave up its time slice by using a Sleep(0) request, the OS will save the state of what it is doing by performing a context switch. The fact that this switch can occur at any time is why it was critical that the CompareExchange code execute in a single CPU instruction that cannot be interrupted. If it didn't, it would be possible to put the lock in an inconsistent state between the compare and the exchange.

When the Sleep(0) call is made, the thread is put in a "Ready" queue meaning that it's "ready" to run and not waiting on anything. [11]

While we're at this chart, it's important to note that one of the possible thread states is "waiting." Windows will keep track of the events that a thread is waiting on.

Events are useful for signaling between threads. For example, a reader/writer lock can "signal" other threads by informing the OS that an event has been "set." What happens next inside of the thread scheduler/dispatcher depends on the type of event that was set: [12]

AutoResetEvent: In this case, only a single thread that is waiting for the event will be put into the "ready" queue. Anyone else that is waiting for the event stays in the waiting queue. This is useful for releasing exactly one writer.
ManualResetEvent: When signaled, Windows will update all of the threads that are waiting on the event to be moved into the ready queue. Effectively, it releases them all. This is useful for releasing all waiting readers.

What's important to realize is that we have the cooperation of the thread dispatcher in the OS to obey the thread states. By simply being in the waiting queue, the threads aren't even considered to be scheduled to run and thus consume no real CPU time.

Putting It All Together

It's been a long journey, but we now have all the background information we need in order to understand how a reader/writer lock actually locks:

Acquiring a Read Lock:

Enter the internal lock (spin wait or sleep as necessary)
Look to see If there is anyone writing

If no one is writing and no writers are waiting, just increase the number of readers. This is the happy path.
If a writer is writing, tell the OS that we want to wait until the "ready for readers" event is set.

Exit the internal lock.

Exiting a read lock:

Enter the internal lock
Decrement the total number of readers.
Check the total number of readers remaining

If there are still readers remaining, then make sure that all waiting readers have been released so they can run.
If there are no readers left and there is at least one writer waiting, signal the appropriate event so that exactly one of the waiting writers wakes up and will get the lock.

Exit the internal lock.

Acquiring a write lock:

Enter the internal lock
Check the number of readers or if there is an active writer in progress. In addition, check to see if there are any in line waiting to do either.

If there are no readers or writers, record that we're writing. This is the happy path.
Otherwise wait for our turn in line on the write queue by waiting on the "ready for writing" event.

Exit the internal lock

Exiting a write lock:

Enter the internal lock
Check how many readers or writers are waiting

If there are no waiting writers, immediately signal all readers at once.
Alternatively, release one writer that has been waiting.

Exit the internal lock.

As it turned out, the locks themselves are fairly simple. They just had a few pieces that came together in interesting ways.

The Problem of the Upgrades

There's a subtle problem with reader/writer locks: Imagine that two threads are both in a read lock and then they both decide that they need to upgrade to a write lock. Because a writer must wait for all readers to finish before acquiring a write lock, there seems to be a deadlock scenario since neither one wants to give up its read lock.

The secret trick is that they indeed must give up their read lock if there are any other active readers. This forces a correct implementation to do something like this when performing an upgrade:

// Cache miss
LockCookie cookie;

int writerSeqNum = rwl.WriterSeqNum;

cookie = rwl.UpgradeToWriterLock(Timeout.Infinite);

try
{
    if (rwl.AnyWritersSince(writerSeqNum))
 {
     // Since another writer snuck in, we might no longer need
     // to create a new object. Let's check again to see if we
     // need to do this.

     if (this.expensiveObjectCache.TryGetValue(key, out expensiveObjectCache))
     {
         // The other writer(s) must have created it
         return expensiveObjectCache;
     }
 }

 // Other writers didn't sneak in, so we know we need to create
 // the object.

 expensiveObject = new ReallyExpensiveObject();

 expensiveObjectCache[key] = expensiveObject;

 return expensiveObject;

}
finally
{
 rwl.DowngradeFromWriterLock(ref cookie);
}

Each time a writer lock is acquired, the WriterSeqNum is incremented. The "AnyWritersSince" function will check to see if any writers have occurred since the moment just before we upgraded. If this is true, then it means that another writer might have come in and thus we need to recheck our assumptions.

This is just one way to handle the upgrade problem. [13]

As Joe Duffy explained on his blog, the new ReaderWriterLockSlim gets around the upgrade problem by introducing an "UpgradeableRead." When a thread enters an upgradeable read, the lock will force all subsequent readers to wait until the thread decides if it wants to upgrade. In the mean time, existing readers are allowed to finish. If an upgrade is requested, the lock will wait until no more readers are present. This preserves the integrity of the data.

Here's a full example:

private ReaderWriterLockSlim slimLock = new ReaderWriterLockSlim();

public ReallyExpensiveObject GetExpensiveObjectSlim(string key)
{
    ReallyExpensiveObject expensiveObject;

 bool upgraded = true;

 this.slimLock.EnterUpgradeableReadLock();

 try
 {
     if (this.expensiveObjectCache.TryGetValue(key, out expensiveObject))
     {
         // Cache hit
         upgraded = false;
         return expensiveObject;
     }

     // Cache miss
     this.slimLock.EnterWriteLock();

     try
     {
         expensiveObject = new ReallyExpensiveObject();
         expensiveObjectCache[key] = expensiveObject;
         return expensiveObject;
     }
     finally
     {
         this.slimLock.ExitWriteLock();       
     }
 }
 finally
 {
     slimLock.ExitUpgradeableReadLock();
 }
}

While showing the full syntax needed, it's a bad example of using a ReaderWriterLockSlim since it doesn't allow for multiple readers. The code might perform better by just entering a read lock if reads occur much more frequently than writes. If the a write is actually needed, then a subsequent write lock can be acquired and a double check can occur to see if a write is still needed. Alternatively, a classic Monitor style lock can be used.

Conclusion: Why Should I Care About the Details?

Our journey has taken us from the high level of using a reader/writer lock to the low level of a single signal on the processor bus. Knowing this low level "goo" is helpful for a few reasons:

Ideally, lock sections should be kept small so that no lock contention occurs in the first place so that we don't need to "spin wait" at all (to acquire the internal lock).
Since readers are released all at once via an event, it shows how a reader/writer lock gets its performance benefit over a normal Monitor lock that would force waiting readers to wait in a line to get released one-by-one.
We now can see that locks aren't magic at all. They just have a few moving parts.

With a better understanding of locks, I'll focus my handwaving on other concepts... like building a work-stealing thread pool.

UPDATE 30 Sep 2008: I fixed the footnote links and updated conclusion #1 based off comments.

UPDATE 3 Oct 2008: I updated the paragraph discussing why spin waits can be helpful based off some good discussion in the comments.

Notes

(This article had a few places where I made some claims. I'm sure I probably got some things wrong or might have misunderstood something in my explorations. I'm putting notes here to give background of what I was thinking when I wrote the post. Please feel free to correct me and keep me honest via comments for the benefit of others)

[1] If performance isn't insanely critical, you can create your own lock and have helper methods like "EnterScopedRead" that return an IDisposable object that will automatically release the lock when it's disposed. Then, you can use a C# "using" statement with it to reduce some of the code clutter.

[2] I still think that reader/writer locks are more interesting than normal Monitor type locks. However, if you have a relatively balanced number of readers and writers (e.g. no clear readers majority), then Monitors make more sense since they're slightly faster. However, the code that Monitors uses a lot more assembly code for performance reasons and thus is often harder to understand.

[3] Even a cursory look at the source code of .NET 3.5's new ReaderWriterLockSlim in Reflector shows that Vance's lock code was the basis for it. ReaderWriterLockSlim is slightly more complex to handle cases like a recursive lock (e.g. acquiring a read lock when you have a write lock), but the core ideas remain the same.

[4] To be technically correct, Rotor isn't exactly what the commercial CLR is. Some of the aspects like the garbage collector and the Just In Time (JIT) compiler are different due to trade secrets. However, I don't think the parts I'll be mentioning here are different between the reference implementation and the actual commercial implementation. For more details on Rotor, I recommend reading Joel Pobar and Ted Neward's new book on Rotor 2.0.

[5] Things aren't quite that simple. The first thing to realize is that the CLR has a Platform Adaptation Layer (PAL) that handles all architecture specific code. Thus, there can be equivalent assembly code for other chips like the PowerPC which is located in clr/src/vm/ppc. Furthermore, the actual x86 code can be one of these two functions:

FASTCALL_FUNC CompareExchangeUP,12
 _ASSERT_ALIGNED_4_X86 ecx
 mov eax, [esp+4]        ; Comparand
 cmpxchg [ecx], edx
 retn 4                  ; result in EAX
FASTCALL_ENDFUNC CompareExchangeUP

FASTCALL_FUNC CompareExchangeMP,12
     _ASSERT_ALIGNED_4_X86 ecx
     mov     eax, [esp+4]    ; Comparand
lock  cmpxchg [ecx], edx
     retn    4               ; result in EAX
FASTCALL_ENDFUNC CompareExchangeMP

If you look at cgenx86.cpp, you'll see that CompareExchangeUP is the default and the CompareExchangeMP is used if your system has more than one processor:

CmpXchgOps FastInterlockCompareExchange = (CmpXchgOps)CompareExchangeUP;

// Adjust the generic interlocked operations for any platform specific ones we
// might have.

void InitFastInterlockOps()
{
...

  if (g_SystemInfo.dwNumberOfProcessors != 1)
  {
   ...

   FastInterlockCompareExchange = (CmpXchgOps)CompareExchangeMP;

   ...
  }

...

From this, I was able to determine that "CompareExchangeUP" is for uniprocessor machines and "CompareExchangeMP" is for multiprocessor machines. If you look at the code carefully, you'll notice that the only difference is that the uniprocessor version doesn't bother locking the processor bus. This is safe because there is no chance of simultaneous memory access.

[6] The truth is a little bit more complicated, but more interesting. The Intel 64 and IA-32 Architectures Software Developer's Manual - Volume 3A: System Programming Guide, Part 1 tells us:

7.1.4 Effects of a LOCK Operation on Internal Processor Caches.
For the Intel486 and Pentium processors, the LOCK# signal is always asserted on the bus during a LOCK operation, even if the area of memory being locked is cached in the processor.
For the P6 and more recent processor families, if the area of memory being locked during a LOCK operation is cached in the processor that is performing the LOCK operation as write-back memory and is completely contained in a cache line, the processor may not assert the LOCK# signal on the bus. Instead, it will modify the memory location internally and allow [its] cache coherency mechanism to insure that the operation is carried out atomically. This operation is called "cache locking." The cache coherency mechanism automatically prevents two or more processors that have the same area of memory from simultaneously modifying data in that area. (emphasis added)

Here we learn that the P6 and newer chips are smart enough to determine if they really have to block off the bus or can just rely on intelligent caching. I think this is a neat optimization.

[7] I think the "PAUSE" instruction is an interesting example of how Intel allows for backwards compatibility. Its opcode of "F3 90" makes it identical to "REP NOP" which will cause older processors to still do nothing, however newer chips use this odd opcode as a clear hint to do more efficient things.

[8] If you're curious about where I came up with the numbers, look at this discussion on the Intel forums. It's a bit hard to measure since context switches might skew the results. My lowest run yielded numbers that indicate a nop took 0.34 clocks per instruction and that "PAUSE" took 8.21 clocks per instruction. I did (2,400,000,000 clocks / second) * (1 PAUSE / 8.21 clocks) to get 292,326,431 PAUSEs / second or 3.42 ns / PAUSE.

[9] UPDATE: The original statement made a statement that this was 100,000 times slower. After some good discussion in the comments, I'm not going to claim specifics since it depends a lot on the machine's workload and a thread's working set.

It's interesting to note that Vance's original code gives up after only three tries of around 70ns each. The ReaderWriterLockSlim that was ultimately derived from it keeps up the fight a little longer. It does something like "Thread.SpinWait(20 * (i + 1))" which leads to a geometric back-off over time for a total of up to 10 iterations which yields the equivalent of 1100 "YieldProcessor" calls or approximately 3.76 microseconds. This means it stays in the fight 1100 / 210 or 5.2 times longer.

(See the comments for more discussion on this)

[10] It's important to realize that processes don't run on Windows, but threads do. Although processes provide isolation boundaries, they require a thread to execute code.

[11] The Thread.Sleep(0) call ultimately reaches the SleepEx API that has this documentation:

A[n argument value of] zero causes the thread to relinquish the remainder of its time slice to any other thread of equal priority that is ready to run. If there are no other threads of equal priority ready to run, the function returns immediately, and the thread continues execution.

It's interesting that ReaderWriterLockSlim does a Sleep(0) for 5 times before finally doing Sleep(1) until it reaches success. I'm assuming it does the Sleep(1) in order to protect users from themselves in the event that the thread that has the lock and then goes into a state where it's waiting on something (e.g. I/O) to occur. Lock sensitive code should not be doing this, but it doesn't hurt to provide this forced 1 ms minimum delay. If they didn't do this, the thread that had the lock would remain on the waiting queue while waiting for I/O and this would potentially have the thread that needs the lock to immediately be put back on the run queue without burning much CPU time.

Finally, I'm assuming that SleepEx(0) performs a software interrupt. This is like a GOTO that jumps to a well known address that that handles the scheduling/dispatching of threads in the kernel.

[12] I'm simplifying things a bit here. Threads can wait on multiple events at one time. Therefore, setting one event might still mean that a thread is waiting on other events.

As an aside, it was only while researching this post that I realized why the WaitForMultipleObjects API is so useful. By using it, you can eliminate a very costly process of putting your thread back on the ready queue and getting scheduled only to find out that it still needs to wait and thus go back on a the wait queue.

[13] While the ReaderWriterLockSlim handles things properly, the early version that Vance posted will throw an error on a simultaneous upgrade. This is technically another way to handle the upgrade problem :-).

Meta-FizzBuzz

2008-08-25T06:58:00.007-04:00

By itself, solving the "FizzBuzz" problem won't get you a new job. If it does, you probably wouldn't want that job. It's a weed out type of question that doesn't say much about your skill if you get it right, but it hurts your credibility as a programmer if you can't do it. It asks:

Write a program that prints the numbers from 1 to 100. But for multiples of three print “Fizz” instead of the number and for the multiples of five print “Buzz”. For numbers which are multiples of both three and five print “FizzBuzz”.

By rearranging the words in the problem statement and adding a few programmer keywords, you can create this simple pseudocode solution:

for every number from 1 to 100                          
  if the number is a multiple of 3 and it is a multiple of 5 then
    print "FizzBuzz"
  else if it is a multiple of 3 then
    print "Fizz"
  else if it is a multiple of 5 then
    print "Buzz"
  else
    print the number

See? Simple and boring.

But what if the bar were raised in the future to be this "Meta-FizzBuzz" problem:

Create a language implementation and write a solution to the FizzBuzz problem using it.

It sounds crazy at first, but if you take it seriously, it is way more interesting than the original FizzBuzz problem. It forces you to have a deeper understanding of languages rather than just getting by with the basics. It also shows that languages are full of many design choices that often have several alternatives.

I decided to create a language implementation that would execute the above "pseudocode" solution. While working on the implementation, I discovered that needed to handle cases that I hadn't seen in "real" languages:

Variables can be prefixed by "the" to make the code more readable.
Instead of having a modulo operator (e.g. %), I picked the phrase "is a multiple of".
This language supports the special "it" variable that always refers to the last variable that was explicitly referenced.

These were just arbitrary decisions that I made to make the actual FizzBuzz program easy to read. Even though I'm still in the early stages of the development of OMeta#, it wasn't too difficult to write a complete "Meta-FizzBuzz" implementation in about 100 lines of code with generous use of comments and whitespace:

ometa MetaFizzBuzz : Parser {
    // Basic literals come first:

    // We override the Parser's version of "Number" which returns a string
    // to instead return the integer value of the string.
    Number ^= Spaces ('+'  '-'  Empty):prefix
              Digit+:ds -> { int.Parse(((prefix.Count > 0) ? prefix.As<string>() : "") + ds.As<string>()) },

    // Allow literal strings surrounded by quotes (e.g. "FizzBuzz")
    QuotedString = Spaces '"' (~'"' :c)*:inner '"' -> { inner.Count == 0 ? "" : inner.As<string>() },

    // For more natural sounding code, we allow "the" in front of a variable name.
    // In addition, we keep track of the last variable name used so that we can refer to
    // it as "it" later on.
    VariableName = ("the"  Empty) Spaces
                   FirstAndRest("Letter", "LetterOrDigit"):n
                   !{ Set("_it", n.As<string>()) } -> { n },

    // Expressions are functions that evaluate to some object.
    // We don't return the value directly since expressions can depend on
    // global variables that could be change while executing.
    Exp = AndExp
         BinExp
         NumExp   
         QuotedString:qs -> { (Func<object>) (() => qs.As<string>()) },

    // An "and" expression is the highest level of a function that returns
    // a boolean value. This left-recursive definition allows for an arbitrary
    // number of boolean expressions to be and-ed together.
    AndExp = AndExp:l "and" BoolExp:r -> { (Func<object>)(
                                              () => (
                                                     (bool)l.As<Func<object>>()()
                                                      &&
                                                      (bool)r.As<Func<object>>()()
                                                      ))
                                         }
            BoolExp,

    // This rule looks at what the expression returns and then tries to
    // convert non-boolean values by declaring that non-zero values and
    // non-empty strings are true and everything else is false.
    BoolExp = Exp:e -> { (Func<object>)(
                           () => {
                                      object o = e.As<Func<object>>()();
                                      return o is bool ? (bool)o
                                           : o is int  ? ((int)o) != 0
                                           : !string.IsNullOrEmpty(o as string) && (o != OMetaList<HostExpression>.Nil);
                           })    
                       },   

    // Binary expressions take two arguments (left and right).
    // Here we just have the one that is relevant to FizzBuzz
    BinExp = NumExp:left
             "is" "a" "multiple" "of"
             NumExp:right -> { (Func<object>)(
                                     () => {
                                               var l = (int)left.As<Func<object>>()();
                                               var r = (int)right.As<Func<object>>()();
                                               return (l%r) == 0;
                                           })
                               },              

    // Number expressions are functions that just return an integer.
    // Note that "it" resolves to the *value* of the variable that was last referenced by name.
    NumExp = Number:n        -> { (Func<object>) (() => n.As<int>()) }   
            "it"            -> { (Func<object>) (() => Get<int>(Get<string>("_it"))) }
            VariableName:vn -> { (Func<object>) (() => Get<int>(vn.As<string>())) },
   
    // Statements are the things that actually do work in this language.
    Stmt = "print" Exp:e -> { (Action) (() => { Console.WriteLine(e.As<Func<object>>()()); }) }  
          "if" AndExp:b "then" Stmt:t
           ("else" Stmt  Empty):f -> { (Action) (
                                            () => {
                                                     if((bool)b.As<Func<object>>()())
                                                       t.As<Action>()();
                                                     else if(f.Count > 0)
                                                       f.As<Action>()();
                                                  })
                                      }
         "for" "every" VariableName:n "from"
           Number:low "to" Number:high
           Stmt:s -> {  (Action) (
              () => {
               int lowerBound = low.As<int>();
               int upperBound = high.As<int>();          
               string iterationVar = n.As<string>();
               Action iterationStmt = s.As<Action>();
               for(int i = lowerBound; i <= upperBound; i++)
               {
                  Set(iterationVar, i);
                  iterationStmt();                
               }
              })
         },

    // A "block" is zero or more statements.
    Block = Stmt*:s -> { (Action) (
                          () => {
                           foreach(var currentStatement in s)
                           {
                              currentStatement.As<Action>()();
                           }
                          })
                         },
  
    // And finally, a "program" is just a series of statements, which is a "block"
    Program = Block
}

Full disclosure: It took some debugging to get this implementation to work right.

If I had been beamed into the future and had to write this solution on a whiteboard, I would have been a bit nervous that I wouldn't have gotten it right and would have taken noticeably more time than I now take to write a FizzBuzz solution.

In order to keep the code size down, I directly execute the "pseudocode" rather than convert it to an intermediate tree. I also simplified things by making all variables in this language global. The latest version of the source code has a slightly more elaborate version of Meta-FizzBuzz that also allows an alternative pseudocode implementation.

The current implementation of OMeta# uses C# 3.0 as the host language. This makes everything inside of the { }'s two to three times uglier and larger than it might have been if I had used a more dynamic host language like JavaScript, Python, Ruby, or possibly C# 4.0. As I mentioned in my last post, my hope is that eventually I'll be able to use clever techniques to make the host code appear more dynamic even though it might need to be strongly typed.

In the end, the Meta-FizzBuzz problem is just a thought experiment to guess what the low bar might look like in the future. That is, a future where it's so easy to create a language that perfectly fits your problem that people actually do. As an industry, we're not there yet, but it's fun to dream of the STEPS needed to get there.

Feedback: What do you think the low bar will be in an upcoming era of Moore's Law Software? What do you think of the Meta-FizzBuzz problem? Feel free to post your own solution (or outline of a path that you'd take towards a solution) in the comments. Comments are also encouraged about OMeta#'s current syntax in general.

Building an Object-Oriented Parasitic Metalanguage

2008-07-31T07:34:00.001-04:00

It's all about pattern matching. The rest is just details.

My last post on OMeta# focused on what it is and the vision I have for its future. Briefly, OMeta is a new language that makes it easier to design programming languages in an object-oriented fashion using very few lines of quite readable code. OMeta# is my attempt to support OMeta on the .NET runtime. My main strategy has been to base its design off of Alessandro Warth's JavaScript implementation of OMeta/JS. This post gets into the specifics of how I've done this so far, but my hope is that you might see some places where the design could use improvement and that you might be encouraged to leave a comment so that it could get better.

High Level Design

At its core, OMeta has a very simple design. The highest level of abstraction is a grammar. Here is a calculator grammar in the current implementation of OMeta#:

ometa Calculator <: Parser {
  Digit    = Super((Digit)):d         -> { d.ToDigit() },
  Number   = Number:n Digit:d         -> { n.As<int>() * 10 + d.As<int>() }
            Digit,
  AddExpr  = AddExpr:x '+' MulExpr:y  -> { x.As<int>() + y.As<int>() }
            AddExpr:x '-' MulExpr:y  -> { x.As<int>() - y.As<int>() }
            MulExpr,
  MulExpr  = MulExpr:x '*' PrimExpr:y -> { x.As<int>() * y.As<int>() }
            MulExpr:x '/' PrimExpr:y -> { x.As<int>() / y.As<int>() }
            PrimExpr,
  PrimExpr = '(' Expr:x ')'           -> { x }
            Number,
  Expr     = AddExpr
}

A grammar is composed of rules (which are sometimes referred to as "productions"). Both the grammar itself and the rules have the same form:

Going into the rule is a list of things of the input type (here they're represented by red circles) and coming out on the right is a list of things of the destination type (represented by purple triangles). As you can see from the diagram, the output list can have lists inside of it. In the calculator grammar, the circles are individual characters and the output is a single integer.

My "Ad Hoc, Informally-Specified, Bug-Ridden, Slow Implementation of Half of Common Lisp"

As an implementer of OMeta, you have to make several design choices. One of the first is how to represent grammars. Since OMeta is object-oriented, I decided that it made sense to represent grammars as a .NET class (a.k.a. "Type"). Grammars contain rules; the obvious choice for implementing rules is to use a method. This especially makes sense because rules can refer to rules in their base grammar. For example, the above calculator grammar has a rule called "Digit" which captures a single numeric digit. The "Digit" rule applies the "Digit" rule in its base grammar (Parser) that simply captures a digit character. It does this by applying the special "Super" rule which will use the base grammar to apply the rule that is specified by an argument. Since rules are implemented as methods and rules can "override" their definition from their base grammar, it made sense to make rule methods "virtual."

Another important decision is how to represent data going into and out of a rule application. An easy choice is to represent the data in a List<T>. This works out well except for the small detail that lists can contain other lists. This nested list idea has been around for at least 50 years in LISP and languages derived from it (like Scheme). Since it has worked out fairly well in those languages, I stole the idea of a LISP-like list in my OMetaList<TInput> class which is a list of other lists with a special case that makes lists of length 1 equivalent to the element itself.

These decisions get us started, but a problem comes up if you try to implement the factorial function using recursion in an OMeta grammar:

ometa Factorial {
    Fact 0                                               -> { 1 },
    Fact :n ?(n.As<int>() > 0) Fact((n.As<int>() - 1)):m -> { n.As<int>() * m.As<int>() }
}

If you look carefully at this grammar, you'll see that it only says two things:

If the next element of input matches a 0, return 1
If the next element of input is something greater than zero, store its value to "n" and then apply the "Fact" rule supplying it with the value of "n - 1" and capture that result to "m". Finally, return "n * m".

What might not be obvious at first is that any time you store something to a variable using an expression like ":n", the value stored must be of the destination type (e.g. a triangle in the diagram). This makes us need to update our mental model for how OMeta works. We need a place to store rule "arguments" which are already in the destination type.

One way of doing this is to create an argument stack that is separate from the rest of the input. Additionally, we'll need a place to store grammar-local variables as well as a place to remember previous results of rule applications for performance reasons. This gives us a much more complete picture of what really occurs:

When a rule needs to consume input, it will first attempt to grab pop an item from the argument stack. If the stack is empty, then next element from the input list can be read.

I decided to store all of these details into a single class which I call an OMetaStream<TInput> which internally uses an OMetaList<TInput> for input data and an OMetaList<HostExpression> for storing the argument stack. The arguments are actually stored in an OMetaProxyStream<TInput> which inherits from OMetaStream<TInput>, but this is just an implementation detail.

With the major data structures out of the way, one important choice remaining is how to handle going down the wrong path. If you look at the calculator grammar, you'll see that the "AddExpr" rule can be of the form "x + y", or "x - y", or a "MulExpr".

How does OMeta know which one to take? It makes a prioritized choice by trying each of the alternatives in the order specified. If it discovers that it has gone down the wrong path (e.g. the next item from the input is a "-" instead of a "+"), it needs to backtrack and reset itself to the condition it was in before the bad choice and then try the next option.

There are two obvious ways of doing this. The first approach is to leverage runtime support by using exceptions. This is exactly what OMeta/JS does. Using exceptions has an advantage of making the generated code simpler because there is no explicit code to "unwind the stack" in case you go down a bad path.

Although it makes the code easier to read, I decided against using exceptions and instead chose to use methods that return a boolean value to indicate if they succeeded. I did this for two important reasons:

.NET does a bit of extra work when an exception is thrown (e.g. getting a stack trace). Therefore, throwing an exception has a non-trivial performance penalty.
Rules have prioritized choice. This means that failing a single choice doesn't imply that the whole rule fails. Failing can be a very common occurrence (it's not exceptional) and this makes it very performance sensitive.

Here's a small glimpse of what the generated code looks like for attempting to apply the "AddExpr" rule:

OMetaList<HostExpression> x;
OMetaStream<char> addExprOut;

if(!MetaRules.Apply(AddExpr, inputStream2, out x, out addExprOut))
{
    return MetaRules.Fail(out result2, out modifiedStream2);
}

In this case, AddExpr is the name of the rule which is implemented as a method. Data is read from the "inputStream2" which is an OMetaStream (where the red circles are characters). The resulting list is saved to the "x" variable and the modified stream is stored in "addExprOut". In order to make back-tracking easier, OMetaStreams are mostly immutable, which means that they can't change. Instead of updating the stream itself, you get a fresh copy of the stream that contains what the result would be. If you need to back track, you can simply ignore the rule application output. As a side benefit, it makes it slightly easier to debug since you don't have to worry about the mutations that could otherwise occur.

Parasitic?

OMeta's creator likes to refer to OMeta as a "parasitic language" because it doesn't exist on its own. It always lives on top of a "host language." This makes an implementation usually defined in terms of its host language. That's why there is "OMeta/JS" which uses JavaScript as a host language. Although my ultimate goal for OMeta# is to have the host language be any .NET language, I decided to use C# as my first host language.

One of the first issues that came up was trying to recognize what exactly is C# code. As you can see from examples in my last post, my first attempt was to pick a really ugly pattern that wouldn't occur in normal use. I picked two consecutive @ signs as in:

@@/*This is C#*/@@

It worked out well, but it had the downside that it was, well... incredibly ugly. I have since written a rudimentary C# recognizer written in OMeta# itself that is aware of strings and comments. The upside is that the syntax looks a little nicer:

{ /*This is C#*/ }

Using C# as the host language had several implications. The most challenging was working with C#'s static type system. This was both a blessing and a curse. On the one hand, I had to constantly think about where the data came from and where it was going. This forced me to actually understand the overall design better. On the other hand, I had to spend so much time thinking about it. Late-bound systems with dynamic typing such as Smalltalk and JavaScript remove the need for people to spend so much time doing this.

I'm optimistic that over time a lot of the stronger annoyances will go away. For example, the current syntax forces type identification as in:

-> { n.As<int>() * 10 + d.As<int>() }

Where, OMeta/JS can just say:

-> { n * 10 + d }

I'm not exactly sure how to do this yet. My initial guess is that I might be able to write some sort of type inference algorithm (preferably written in OMeta#) that could do a reasonable job. My current ideas are tied too closely with the specific host language and would require a bit of work to port them to other host languages like Visual Basic. Another approach is to implement one or more helper classes that could enable duck typing (e.g. if it looks like a certain type, walks like that type, and quacks like the type, it's probably that type).

Being able to have strong static typing internally while having a very clean syntax would be ideal (e.g. sort of like the C# 3.0 "var" keyword). Static typing is usually harder to achieve, but if you can do it well, you get many benefits. C# designer Anders Hejlsberg said it well in a recent interview:

"I don't see a lot of downsides to static typing other than the fact that it may not be practical to put in place, and it is harder to put in place and therefore takes longer for us to get there with static typing, but once you do have static typing. I mean, gosh, you know, like hey -- the compiler is going to report the errors before the space shuttle flies instead of whilst it's flying, that's a good thing!"

Another issue that came up was properly handling inheritance. It makes sense to use "virtual" methods for rules, but this also requires you to emit the "override" directive to avoid warnings. Another warning cropped up from my use of the "base" keyword in the many delegates that makes it convenient from a code emission perspective, but frustrating from a verifiable security perspective. Both of these warning are being left for a latter phase.

Compiler issues were only one factor. The other significant piece was aesthetics. A notable number of rules yield specific lists as their result. C# doesn't quite have a good, clean way of expressing an OMetaList (that is, a list of lists). In order to get around this, I created the "Sugar" helper class which makes it slightly easier to write these lists. It's still far from perfect. Instead of having a nice way for expressing lists like that OMeta/JS:

-> ['add', x, y]

You have to do this instead:

-> { Sugar.Cons("add", x, y) }

This annoyance can probably be fixed by tricking the C# recognizer to act as if C# had a nice implicit way of expressing an OMetaList and then re-writing the expression to use the Sugar class.

Beyond C#, there is the "meta" "host language" which is the .NET common language runtime itself. For code to play nice on it, it should abide by the .NET framework design guidelines which dictate naming conventions and general practices. This had a parasitic effect in that it led me to name my rules after the naming guidelines for methods (e.g. they must be PascalCased). Thus, in OMeta# there is the "Digit" rule instead of the "digit" rule. OMeta/JS opts to prefix metarule method names with an underscore to make them not collide with other rules. I also wanted to hide metarules so that people would have to try harder to do the wrong thing; the best I could come up with to convey this idea was to implement them using an explicit interface exposed via a property (e.g. instead of "_apply", I have "MetaRules.Apply").

Being a Contextual Packrat

The last intriguing thing about OMeta is exactly how it implements parsing. It uses a technique called a Parsing Expression Grammar (PEG) that Bryan Ford introduced in 2004. It's just a fancy way to say you support the following features: (The table comes from the OMeta paper. I've also included how OMeta# implements them to prove its legitimacy):

expression	meaning	OMeta# Function
e₁ e₂	sequencing	Seq
e₁ e₂	prioritized choice	MetaRules.Or
e^*	zero or more repetitions	MetaRules.Many
e⁺	one or more repetitions (not essential)	MetaRules.Many1
~e	negation	MetaRules.Not
<p>	production application	MetaRules.Apply
'x'	matches the character x	Exactly

The most interesting aspect to me is the prioritized choice. This is in contrast to "Context-Free Grammars" (CFGs) which are the traditional way of defining parsers. To highlight the difference, consider parsing this line of C/C++ code:

if (condition1) if (condition2) Statement1(); else Statement2();

Is it the same as:

if (condition1)
{
    if (condition2)
    {
         Statement1();
    }
    else
    {
         Statement2();
    }
}

... or is it:

if (condition1)
{
    if (condition2)
    {
        Statement1();
    }       
}
else
{
    Statement2();
}

This is the classic "dangling else" problem. Context Free Grammars usually have this problem because they are free of any context when they are parsing (surprise!). In these situations, you often have to rely on something besides the grammar itself to resolve these ambiguities. Parsing Expression Grammars don't have this type of problem because you specify explicitly which one to try first. The prioritized choice therefore avoids ambiguity.

In order to make the performance relatively in line with the size of the input, a technique of "memoization" is used. This means the parser remembers what it has done previously; it does this as a space-time tradeoff. Keeping all those previous values have given them the reputation of being a "packrat" parser.

Let's say you have

  AddExpr  = AddExpr:x '+' MulExpr:y  -> { x.As<int>() + y.As<int>() }
            AddExpr:x '-' MulExpr:y  -> { x.As<int>() - y.As<int>() }
            MulExpr

and you try the first choice (AddExpr:x '+' MulExpr:y), but you get to where you're expecting a "+" and it isn't there. You'll notice that the second choice (AddExpr:x '-' MulExpr:y) repeats the first part (namely AddExpr:x). Instead of re-evaluating it, you can just retrieve the stored value that you remembered, or rather memoized.

Well, it's almost that simple. Note that the definition of an add expression (AddExpr) is left-recursive. This means that the left side is defined in terms of itself. A naïve implementation of the parser would try to evaluate "AddExpr" by applying the first choice which started with a AddExpr which would then cause it to try to apply AddExpr again and eventually cause a stack overflow.

It's not a trivial problem to fix. In fact, the paper that introduced Parsing Expression Grammars said that left-recursion should be avoided since you can rewrite the rule to avoid left-recursion. This is unfortunate guidance because the rewritten rule sometimes loses the clarity that the left-recursive version of the rule had.

At the start of this year, a paper came out showing a very clever trick that makes left recursion possible.

Say that we're parsing the expression "1+2+3" using the "AddExpr." At the start of the expression we look at our memoization table to see if we have a precomputed value for "AddExpr". Since it is our first time, we won't find anything. The first part of the trick is to immediately store the result of "Fail" as the memoized result for AddExpr when starting at offset 0. We do this before we attempt to apply the rule.

When the parser uses recursion and finds itself again asking for the value of "AddExpr" at position 0, it will find a result of "fail" and thus fail that choice. It will then continue down to "MulExpr" where it will eventually match "1". The second part of the trick is to treat this value of "1" for "AddExpr" at position 0 as a "seed parse." The parser will then attempt to "grow the seed" by starting over at the beginning of the input stream, but this time it will remember its previous successful match. This will cause it to match "1+2" for AddExpr and then start over again by growing the seed to finally match "1+2+3."

In hindsight, it's a very simple idea. However, I say that only after some serious debugging time where I kept finding problems in my poor implementation. Alas, the entire algorithm is implemented in only a few lines of code in the "MetaRules.Apply" function in OMetaBase.cs.

So there you have it, you now know all of the interesting ideas in OMeta#.

Where is This Going?

OMeta# is a hobby project that's been a labor of love for me. You might have already guessed that if you noticed that most check-ins occur late at night or on the weekends. It's been slow, but it's coming together. Probably the most exciting highlight in the development came when I got enough of OMeta# working that I could rewrite parts of itself in OMeta#. This has the benefit of being cool from a meta self-reproducing level, but it's also a bonus because the code becomes much more readable and introspective. For example, compare the C# recognizer that I wrote by hand to the OMeta# grammar version that implements the same idea.

This approach of writing more of OMeta# in OMeta# will continue. It's my hope that as much as possible will be written in itself. A significant next step would be to rewrite the code generator as an OMeta# grammar. This isn't a new design idea. Each subsequent version of Smalltalk has been bootstrapped by its previous version.

I'll be the first to point out that there are a lot of rough edges to my current implementation. If you look around the source code, you'll see several comments labeled "// HACK" where I admit a hacked version of an idea. One of the most glaring problems is that debugging is annoyingly difficult. I haven't yet implemented an optimizer for the generated code which causes a lot of unnecessary metarule applications. The second annoyance is that just stepping into so many methods that fail often takes a long time. Over time, I hope to add better hints to get more traditional error messages that you get from good compilers so that you don't have to step through the generated code to debug a grammar.

As mentioned earlier, the language recognizer could use some work to make the syntax cleaner as well inferring types so that grammar writers don't have to explicitly declare them. I have confidence that the work that would go into a good C# host language implementation would directly port to other languages such as Visual Basic.

There's also a great need cross pollination with other projects such as the Dynamic Language Runtime (DLR) which has already tackled some of the issues that OMeta# will face. Additionally, languages such as F# have similar data structures already built-in that OMeta uses. Boo and Nemerle have interesting extensibility points which could provide some good ideas. The problem for me is that there is so many different places to look. It'd be great if you know these languages (or others) and could tell me via a comment or better yet, by sending code of how they could help OMeta#.

As of right now, I plan on keeping the core functionality in C# rather than rewriting everything in another language or by using the DLR. The main reason is that C# is wide-spread in availability, both on .NET as well as on Mono. A second reason is that I would like to keep the outside dependencies on OMeta# as small as possible.

OMeta is a beautiful in the same sense that mathematics can have a simple beauty. LISP has been referred to by some as "The Most Important Idea in Computer Science" largely because its core ideas could be expressed on a half page of the LISP 1.5 manual (page 13 to be exact). This elegance is similar to mathematics of Maxwell's Equations describing electromagnetism.

It's my hope that I won't mess up the implementation to the point where this elegant beauty is lost. Currently it's way too ugly. I see some of the rough edges, but I'm sure you can help me discover others along with how to fix them. If this post sounds too complicated, it's not you, it's me. Let me know if something doesn't make sense and I'll try to provide clarification.

If you're interested in OMeta#, I highly encourage you to download the latest version of the source code from CodePlex and step through the unit test runner to see things get built up.

If you can, keep notes of all the places where you see me doing something and let me know about them either through comments or via email. In addition, I also highly recommend experimenting Alessandro Warth's great OMeta/JS implementation via your web browser.

Happy OMeta-ing!

OMeta#: Who? What? When? Where? Why?

2008-06-24T00:36:00.003-04:00

What if programming language implementations were object-oriented? What if you wanted to change one itty-bitty part of your favorite language? Say you wanted to add an exponentiation operator (^^). How hard would it be?

Wouldn't it be nice if you could "subclass" a language like C# and then add 5 lines of code to make it work and then use it? What if you could add Ruby-like method_missing support in 20 lines?

What if you could conceive of a new language and start experimenting with it in production code in an hour? What if it leveraged your knowledge of existing frameworks like .NET?

Let's imagine that it were possible. Let's say someone else created a basic calculator-like "language":

Even without knowing the syntax, you can probably figure out how it works since it's written very close to the standard way of describing a language. If you give this language "3*4", it will respond with 12. If you give it "2^(3*4)", it'd respond with a nice syntax error message like "I don't know how to deal with the '^' symbol. Sorry!"

But you could make it work by writing this object-oriented-like "subclass" of the language:

Now, giving this language "2^(3*4)" happily gives you 4096.

This worked using simple inheritance. What if you wanted to compose your language from several other languages? That is, something like "multiple inheritance" but without its problems? What if we took a simpler approach and allowed a language to attempt to match elements of any other language?

Let's say we want to build a scientific calculator that leverages some of the work we've already done. Instead of inheriting from it, we'll call out to it:

Now you can calculate expressions like "sqrt (1+2^3)!"

What if such a meta language (e.g. a language for describing other languages) existed? What would you do with it? How might it help you get things done while producing extremely small, but very readable code? What if creating a new language that perfectly fit a problem your software was trying to solve was as easy as writing a simple regular expression?

What if you could get all the whiz-bang, gotta-have tool support like syntax highlighting, interactive debugging, and a compiler for it came at almost no extra cost? What if the barrier to entry for a new language was so low, that almost anyone could do it quickly?

This is what I've been thinking about for the past month or so.

Who? & What?

When I was doing some research for my "Towards Moore's Law Software" series, I came across a very interesting language called OMeta which was created by Alessandro Warth and Ian Piumarta with some inspiration from Alan Kay. In their 2007 Dynamic Languages Symposium paper, the authors described OMeta as

".. a new object-oriented language for pattern matching. OMeta is based on a variant of Parsing Expression Grammars (PEGs) —a recognition based foundation for describing syntax—which we have extended to handle arbitrary kinds of data. We show that OMeta’s general-purpose pattern matching provides a natural and convenient way for programmers to implement tokenizers, parsers, visitors, and tree transformers, all of which can be extended in interesting ways using familiar object-oriented mechanisms. This makes OMeta particularly well-suited as a medium for experimenting with new designs for programming languages and extensions to existing languages."

To be honest, I didn't really understand the paper when I first read it. It sounded cool, but it used a few new terms I hadn't heard of before. However, I couldn't help but be fascinated by OMeta's readable syntax. OMeta doesn't try to solve every problem involved with writing a complete program. It makes no claims about being a good general purpose programming language. But it positions itself by doing just one thing really well:

Pattern matching.

If you look at modern programming languages that are good for developing other languages, you'll notice that they usually have good pattern matching capabilities. For example, in ML (which stands for meta-language), you can specify functions in terms of patterns. Here's how you can reverse a list:

This defines the function named "reverse." When it sees the "pattern" where the function is called with an empty list (nil), it just returns nil. However, when the function is passed in a list whose first element is "x" and the rest of the list is "xs", it will return the reverse of the rest of the list and then append the head of the list to the end.

If you think about it for a second, it's a really compact way of expressing how to reverse a list.

Streams of Anything

What I find interesting about OMeta is how it matches patterns. OMeta can operate on a stream of anything. This is useful because modern language implementations have several phases that work on different types of "things." Here's a simplified view of what a compiler does:

At the start of the process, you're working with individual characters from source code. The list of characters is converted to tokens by use of a scanner. This is how the characters 'i', 'n', and 't' become the "INT" token. The next phase combines tokens together to form a higher level view of the program, typically using a tree data structure. From that phase, several intermediate steps occur on the program (almost always in tree form), until it's finally pulled apart to make an executable program.

Often, you have to use different tools at each phase. You might use lex for the scanner (aka "lexer"), Yacc for the parser, and some sort of visitor pattern in your implementation language (e.g. C#) for many of the intermediate phases. With all of these different tools to learn, it's no wonder why most people don't even bother trying to create their own language.

OMeta is different in that lets you use the same syntax for all phases. The only thing that is different is what the input stream contains. At the start, the input stream is characters. In subsequent phases, it tokens, then trees, and then finally you produce your intended result. At each pass, your OMeta code has similar syntax.

Passing the Match Around

Another interesting bit about OMeta is how it goes about finding rules. Rules are defined in grammars which behave like classes in an object-oriented language. A grammar can "inherit" from another grammar. An added twist is that a grammar can call out to a "foreign" grammar. This makes it easier to build a language from many different reusable parts and allows for trivial "mashups" of several languages.

Additionally, if a rule has multiple "choices," then OMeta always tries to match the first choice, then the second, and so on until it achieves success. Although this seems obvious in hindsight, most parsers don't have prioritized choices and thus they make it easy to define ambiguous rules. For example, is "1-2-3" equal to "(1-2)-3" = -4 or "1-(2-3)" = 2? With prioritized choice, you make this explicit. If it successfully parses, then it has exactly one choice and therefore no ambiguities.

The last really interesting aspect of OMeta's design is what it does when it matches a pattern. A pattern might consist of several sub-components. Each of these components (e.g. rules) can be captured into a variable. OMeta then feeds these variables into a "host" language.

OMeta doesn't care what the host language is. It can be just about any language (e.g. JavaScript, LISP, C++, etc.). Typically, the host language is what the OMeta implementation itself was written in. The host language is free to do whatever it likes with the variables. OMeta is only responsible for getting them there. The OMeta paper describes an implementation where the host language is cola. Other early versions were written in Squeak and use that as the host language.

Alessandro has recently created a JavaScript version where you experiment with OMeta/JS (e.g. JavaScript is the host language) in your browser. It's a very interesting playground. Some of the demonstrations range from the basic calculator language, to a type checker, to LISP, to even the OMeta compiler and code generator itself and all of them are written in OMeta/JS. The playground website is neat to use because it shows the translated (generated) JavaScript code for the grammar (although the generated code needs to be put through a pretty printer to make any sense of it).

Why the "#" in OMeta#?

After understanding the basics of OMeta/JS, I thought it would be interesting to have the host language be any .NET language. I started to sketch out what this might look like by using my limited JavaScript ability and translating Alessandro's code to an equivalent functionality in C#. The result was the start of a project that needed a name. "OMeta#" seemed to fit the bill.

Besides, it just sounded better than other .NET-ism alternatives like "NOMeta", "OMeta.net", or "IronOMeta."

Some might ask, "Why .NET?" A subtle reason is that OMeta is useful for code generation. Code generation is a normal part of the .NET ecosystem even if people don't realize it. When people use the graphical designer in Windows Forms, there is a code generator working behind the scenes writing code for their host language (typically C# or Visual Basic). When people write ASP.NET ".aspx" files, there is a hidden process that takes that HTML-like "language" and compiles it to a real DLL.

For example, ASP.NET transforms this:

Into this generated code:

I wanted to bring a similar "it just works" illusion to the .NET world with OMeta#.

With the encouragement of Alessandro, I started working on some of the supporting "goo" that would be required to get OMeta working on the .NET's Common Language Runtime (CLR). This isn't trivial because the CLR has stricter type system than languages like JavaScript. Also, since I chose C# as the implementation language, I had to make sure that the code passed all of the static type checking it performs at compile time. It's been a slow start, but I have been able to make a few steps towards making it work.

One pragmatic question is why even bother adding another language, or rather, meta-language to the .NET world? Why not just get proficient at another toolset that is decent at creating language like ANTLR, Irony, NParsec, or IronRuby? What about using Parsing Expression Grammars in F# or writing Domain Specific Languages in Boo with its extensible compiler pipeline?

Ultimately, all of those tools are pretty good, but none of them did exactly what I was looking for. Some came close, but none of them seem capable of matching OMeta's power and simplicity.

Another reason was that I knew that writing an implementation of OMeta from the ground up would really help me "know" how it works.

More importantly, I thought it would be fun to work on. I'm not a language expert. I'll never reach the level of someone like Anders, but I was one of those odd kids that actually liked my compilers and programming languages classes. I also enjoyed the talks from this year's Lang.NET symposium (even if I didn't understand a lot of things).

The Grand OMeta# Vision

The grand vision for OMeta# is to make it really simple to create languages that "just work." It probably won't have the world's best performance, but it should be decent enough for almost all practical applications. It would be neat to have OMeta# (or something like it) be used to do the following:

Serve as a common, unified way for developing languages on the .NET platform — There are many helpful, yet often different "tools" out there for various stages of language design. I mentioned a few earlier, but some of the more advanced ones include the new Dynamic Language Runtime (DLR) and Phoenix compiler framework. It would be neat to have a language that abstracted away some of these tools into a clean syntax like OMeta. That way, you'd get the benefit of these tools without having to constantly learn different ways of manipulating the concepts that can be expressed simply.

Factor out the "goo" of language development — For a language to be taken seriously, it has to have things like syntax highlighting, interactive debugging, and a decent compiler. Each of these takes time to implement and often involves a high learning curve. It would be great if you could just make some minor annotations to your OMeta grammar and then these features would "just work."

Useful for teaching — One of my favorite textbooks in college was "Programming Languages: An Interpreter-Based Approach" by Ramsey (et. al.). Our class used a "draft" version of it (and it still hasn't been published yet). It took a very interesting approach towards teaching programming languages. In order to understand a language like Scheme, you had to implement an interpreter for it in C or ML. I really liked this approach because getting your hands dirty with implementing the language typically leads to a better understanding of it. I would love to have the ability to implement this type of approach in something like OMeta. You could understand the essence of a language by only having to understand a page or two of code. It would also let you learn by experimenting with adding small features to existing languages.

Practical for production use — For anything to really succeed at moving towards a Moore's Law increase in expressiveness, it has to have reasonable quality. I can imagine OMeta# being introduced into real production projects by first integrating a small amount of OMeta's "generated" a project and then over time implementing more and more parts of the application in this highly specific language. For this to occur, it has to be reliable and simple to use.

When? Where?

All of the parts of the vision are still in the future. To make them a reality will require more than just a single person or even a couple of people. I'm ~~naïve~~ crazy enough to think that it's actually possible. In an effort not to "go dark," I've decided to be fairly open about the design and implementation of OMeta#. The current state of the code isn't even alpha quality yet. Despite all of these shortcomings, I've posted what I have so far on CodePlex and will continue to make updates to it.

Keeping in the tradition of other OMeta implementations, I've licensed it under the MIT License so that you can use, experiment, play, and modify it without any licensing concerns.

The first interesting result is that I've been able to get a complete end to end demo working for an extremely simple grammar that matches numbers. I fed this input grammar written in OMeta/C#:

into my OMeta compiler/translator and successfully had it generate this output C# file.

There is still a ton of work left. It's quite possible that some of the design decisions I've made so far need to be challenged and redesigned. I'd love to get feedback from anyone that's interested.

What do you think? Do you think OMeta fills a unique niche? Do you think it would be useful to have as a tool in .NET? Would you want to help out making "The Grand OMeta# Vision" happen? If so, what parts can you help out with?

I'm curious to hear your thoughts. In my next post, I hope to cover some of the technical details for how my current implementation works "under the covers."

P.S. Many thanks to Alessandro Warth for creating this beautiful language and helping me get started!

Who Is This "Licklider" Guy?

2008-05-21T22:00:00.002-04:00

Who are they talking about? Why haven't I ever heard of him?

I was at SRI, a research institute by the Stanford campus. Around me was a lively group of some of the best minds in Computer Science, some of them have had their PhDs in the field for 40 years. I had the honor of being the least credentialed person in the room. As I listened to some of the discussions, I noticed that they seemed to keep bringing up the name "Licklider." Sometimes they'd just call him "Lick." Other times they'd mention projects along with his name that I hadn't heard about before like "Project MAC." Since the guys talked so much about him, I knew I had to find out more about who this "Lick" guy was. One of them suggested that I read the book "The Dream Machine: J.C.R. Licklider and the Revolution That Made Computing Personal" by M. Mitchell Waldrop.

My local library had the book. I was a bit worried when I saw that it hadn't been checked out for three years. "Hmm... maybe it's not that good?" I thought.

I was pleasantly surprised.

At about 500 pages, it's not a small book. Fortunately, I was able to finish it just before the library forced me to return it since I hit the maximum amount of renewals on it.

The book put me on a journey that filled in a lot of details about computing history that I didn't even know I was clueless about while weaving a story about a man from Missouri. Although his full name was Joseph Carl Robnett Licklider, just about everyone called him "Lick," a name he acquired in his fraternity days.

Lick's story is bigger than just one guy. It's a story that goes back to the dawn of computing right up to the personal computer. While reading the book, I had a lot of "Aha!" moments that helped fill me into the colorful history of computing. For example, I had heard a lot about DEC's PDP system, but it was interesting to know that they were specifically called "Programmed Data Processors" instead of "computers" because congress was pressured not to spend any more money on computers at the time. By itself, facts like these seem to be obscure trivia, but when you read about the politics of funding at the time, you can really understand that DEC had few alternatives.

I can't recall ever hearing Licklider's name before that meeting at SRI, but that's probably because I didn't try too hard. As a kid interested in computers growing up in the 1990's, I really focused my attention on learning about one person - Bill Gates. I read several books about him and had a reasonably good idea of his background and the history of Traf-O-Data, Microsoft and some of its products like BASIC, DOS, OS/2, Windows, and NT. Perhaps in the back of my mind I thought that learning about him would me emulate his success and make me ~~millions~~billions. Too bad that didn't work out.

In addition to the books, my other major source of information was when I watched Bob Cringely's Triumph of the Nerds on PBS in the summer before I started high school. In hindsight, after reading this book I really wish I would have watched the 1998 follow-on to the series called "Nerds 2.01: A Brief History of the Internet." I would have at least heard about Licklider and the computing days before Microsoft and Apple and not been so clueless back at that room in SRI.

What a story it is! It's not really just about Lick; it's about how he helped build a community that fostered the explosive computing growth in the 1960's right through the 70's and 80's.

Since I like to ask others what stuck out in books that they've read, I thought I'd share some things I found interesting:

22 Days of Beeps Can Change a Nation

Chapter 6 opens on a rocket launch pad in the early morning of October 1957 at a top secret Soviet Union location. When the rocket took off and deployed its payload, the world came to know Sputnik by its incessant beep beep beep transmissions.

Waldrop quotes this account:

"[Sputnik's] two transmitters would fail twenty-three days after launch - but their arrogant beeping would continue to sound in the American memory for years to come... Gone forever in this country was the myth of American superiority in all things technical and scientific." (p. 197)

Although the U.S. had rockets under development that were more sophisticated than the Soviet ones, it was a huge blow to American pride and there was a large public outcry. Everyone made the connection: if the Soviets could launch a satellite into space, they could probably launch a missile into any major U.S. city.

One famous result of this perceived threat was President Eisenhower's endorsement of "a plan to consolidate all the Pentagon's space research under a new civilian agency reporting directly to the secretary of defense. It would be called the Advanced Research Projects Agency, or ARPA."

Well it didn't quite work out exactly as planned.

Before ARPA opened for business, it had already been split up. The National Aeronautics and Space Administration (NASA) would handle all the non-military space projects and the services would get a large amount their funding back to handle most of their development projects. This left ARPA with "the kind of beyond-the-cutting-edge stuff that the services were willing to do without." (p. 198)

ARPA wasn't initially interested in computers. To them, they were really only helpful for things like accounting and payroll. This changed when ARPA was tasked to research new command and control ideas that would require a lot of data processing. This seemed like an ideal fit for computers. Licklider was asked to come over to ARPA and lead the new project.

He didn't want to take the job at first. He was already doing interesting things with computers and was so busy working on fleshing out his ideas of computer assisted "libraries of the future" to even think about burying himself in "the bureaucratic limbo of Washington." (p. 201)

Once he warmed up to the idea of going to ARPA, he began thinking that the command and control concept was ultimately a man-machine symbiosis, something he had been thinking about for years.

In March of 1960, he published his famous "Man-Computer Symbiosis" which began:

"The fig tree is pollinated only by the insect Blastophaga grossorun. The larva of the insect lives in the ovary of the fig tree, and there it gets its food. The tree and the insect are thus heavily interdependent: the tree cannot reproduce without the insect; the insect cannot eat without the tree; together, they constitute not only a viable but a productive and thriving partnership. This cooperative 'living together in intimate association, or even close union, of two dissimilar organisms' is called symbiosis.
'Man-computer symbiosis' is a subclass of man-machine systems. There are many man-machine systems. At present, however, there are no man-computer symbioses. The purposes of this paper are to present the concept and, hopefully, to foster the development of man-computer symbiosis by analyzing some problems of interaction between men and computing machines, calling attention to applicable principles of man-machine engineering, and pointing out a few questions to which research answers are needed. The hope is that, in not too many years, human brains and computing machines will be coupled together very tightly, and that the resulting partnership will think as no human brain has ever thought and process data in a way not approached by the information-handling machines we know today."

This might not seem radical in 2008, but it was revolutionary back in the 1960's when most people could only think of computers as batch processing machines. Lick saw computers in a symbiosis where humans could do the thinking and the machines would do the "algorithmic chores they were so good at" (p.148). In order to find out how much of a benefit they'd be, he did an experiment on himself and found to his horror that he spent 85% of his time just "getting into a position to think, to make a decision, to learn something I needed to know." The rest of the time was just clerical or mechanical. Computers would be a perfect fit to handle all the dreary stuff that got in the way of real thinking.

Lick knew that he could start making the man-computer symbiosis concept real and get the government to pay for it through his association with ARPA. Lick's view was "that the problems of command and control were essentially problems of man-computer interaction. I thought it was just ridiculous having command-and-control systems based on batch processing. Who can direct a battle when he's got to write a program in the middle of a battle?" (p. 202)

On the next page we see:

"Improbably, miraculously, through some once-in-a-lifetime alignment of all the right planets, ARPA was offering him a chance to turn his vision into a reality. He could reinvent the whole field of computing. He could transform those giant calculating machines into full-fledged partners in a human creativity. He could create 'information utilities' that spanned the continent. He could democratize information by opening up vast libraries of material to instant access by anyone. And he could do it all with the Pentagon's money." (p. 203)

And boy did he ever:

"[The professional bureaucrats] had a history of giving grants to individual people in twenty-thousand-dollar chunks. But Lick was talking about millions of dollars and whole teams of people. It was as though these folks had encountered this alien creature: friendly, but strange." (p. 206)

In addition to funding research organizations like SDC, RAND, and SRI, Lick is remembered for helping fund the new computer science departments at Berkeley, Stanford, Carnegie Mellon, and perhaps most famously, MIT. Lick's funding at MIT went towards a system that would put together several foundational ideas needed for his man-computer symbiosis. The goal was "Machine-Aided-Cognition," but since computer time was hard to come by and they had to invent a lot of the concepts for time-sharing to allow multiple people to access a computer at once, the project also went by the name "Multiple Access Computer." Regardless of which one you chose, the acronym was the same.

"So that's the Project MAC the folks in the room were talking about," I thought as I read about it.

Project MAC would lay a lot of the foundations for modern operating systems. Examples include technologies like multitasking and file systems to policies such as regular backups to protect themselves from their mistakes. They had to introduce passwords to stop some people from stealing computer time as well as ideas from unpublished academic papers. Unix and the C language it was written in was an offshoot of this project as an attempt to write a simpler version than what the Project MAC team was trying to accomplish.

And yet, Project MAC was just one of the many projects that Lick was funding and tracking. To the outside observer, all of the projects seemed like an ad hoc mess rather than a carefully crafted plan. Lick knew that his man-computer symbiosis dream would need to be maintained by more than just him. Waldrop writes:

"Lick realized, if this vision was ever going to outlast his tenure at ARPA, he would somehow have to forge all these groups into a self-reinforcing, self-sustaining community." (p. 225)

One such example of how he did this was his famous 1963 memo which began: "[to the] Members and Affiliates of the Intergalactic Computer Network." In his mind, Lick was referring to a human network. He continued: "It is evident that we have among us a collection of individual (personal and/or organizational) aspirations, efforts, activities, and projects." The challenge now was to exploit "the possibilities for mutual advantage". He went on to describe a connected system that would keep all the research projects together, a network focused on human thoughts but connected by wires. In essence, the early signs of the Internet.

But it took some time to materialize and didn't happen during Lick's ARPA tenure.

He did make progress. Due to the computing focus that Lick had caused, his ARPA division was given the title "Information Processing Techniques Office" (IPTO). After his two year tenure at ARPA, Lick handed the reins over to a young Ivan Sutherland (creator of Sketchpad, which launched the field computer graphics and computer aided design). When Sutherland finished his tenure, Bob Taylor would take over and proceed to actually make Lick's "Intergalactic Network" of people a real physical thing by linking ARPA people together into ARPANET, the direct predecessor of the Internet.

The first message went across it at 10:30 PM on October 29, 1969.

Two interesting things from the book stand out right around this period of time. The first was that the height of the Vietnam War was taking a huge toll on the nation, both in terms of people and dollars. In a reported attempt to limit spending on the war, Montana senator Mike Mansfield proposed an amendment that would prevent the Defense Department from "[carrying] out any research project or study unless such project or study has a direct and apparent relationship to a specific military function."

The practical effect of the "Mansfield Amendment" was that it diverted a large percentage of people's time into writing how their project had a "direct and apparent" relevancy. It's also one of the largest reasons why ARPA is now known as DARPA:

"In retrospect, moreover, [the Mansfield Amendment] came to be seen as the symbolic watershed for ARPA, the point at which it started its downhill slide from being a cutting-edge agency that was blessedly free to take risks to being an ordinary agency that was cautious and risk-averse." (p. 395)

The second big thing was that in May of 1969, Xerox was making a lot of money selling copiers. But their management knew they had to be more than a one product company. In an attempt to branch out and "go digital," they purchased Scientific Data Systems (SDS). However, they had a problem: the company was largely computer illiterate. They needed to go out and recruit the best computer people the world had. One of their first hires was none other than former ARPA IPTO director Bob Taylor. Taylor would go on to attract many from Lick's "Intergalactic Network" ARPA community who had been distressed by the Mansfield Amendment and its research cutting implications.

The resulting Xerox Palo Alto Research Center (PARC) was the place to be in the 1970's. It fostered freedom to explore ideas just like the early ARPA days since its backers were willing to invest in long-term innovation. Its anti-corporate culture included meetings filled with beanbag chairs which prevented people from leaping out of their chair to argue with someone. This 'helped' you hear them out. PARC would go on to create the foundations of personal computing as we know it with their Alto personal computer which was named after the city they were in. The Alto had new ideas like bitmapped displays, windows, an Ethernet network, WYSIWYG word processing, laser printing, and roots of modern object oriented programming. Unfortunately, Xerox's management didn't quite understand the business value of what their PARC guys were creating. Additionally, the guys inside PARC had a hard time creating a clear path and business model for getting their ideas to market. There was one notable exception. Waldrop writes:

"If [Jack Goldman] hadn't thrown a tantrum [in order to get the business guys to listen], they might just have rejected the laser printer itself - the one PARC-bred product that would eventually earn billions for Xerox and repay its investment in PARC many times over." (p. 392)

Steve Jobs, along with some other engineers, would visit PARC in December of 1979 for a demonstration of the Alto system. Jobs was so enamored by the graphical interface that he saw that he didn't even explore the object oriented programming and networking ideas. During the visit, Jobs reportedly exclaimed "Why hasn't this company brought this to market?" (p. 443) He didn't wait around for Xerox. Apple's first graphical computer, "Lisa," 'borrowed' several ideas from the Alto. When the Lisa and IBM PC hit the market in the early 80's, the guys inside PARC realized that Xerox had blown a huge opportunity. Many jumped ship. One example was Charles Simonyi, who took his ideas Bravo word processing ideas north to a relatively new company in Washington named Microsoft. It was a huge difference in culture. Simonyi's commented on the contrast:

"It was like going into the graveyard or retirement home before going into the maternity ward. You could see that Microsoft could do things one hundred times faster, literally, I'm not kidding. Six years from that point, we overtook Xerox in market valuation." (p. 449)

And that brought me full circle back to the pop culture history I was more familiar with. Throughout the years Lick would stay involved in some part with the research community, sometimes getting bogged down with management tasks which he despised. He would teach at MIT through the 80s with students that would only later realize all that he had done. Failing health caused him to pass away at the age of 75 on June 26, 1990: just before the world at large would come to use the "Intergalactic Network."

Lick was known for being quite modest about his contributions, often minimizing his role. When asked about what he did, he said:

"I think that I found a lot of bright people and got them working in this area. I got it moving. [And it was] a fantastic community. I guess that's the word. It was more than just a collection of bright people. It was a thing that organized itself into a community, so that there was some competition and some cooperation, and it resulted in the emergence of a field." (p. 258)

So that's why they kept talking about him. Now I get it.

Lick organized a community that would change the computing world. He realized that it's ultimately the people that matter. I think that our industry puts too much emphasis on technology and tends to marginalize people. I think that one of the first steps to reverse this trend is to understand the contributions of its founders like Lick.

"The Dream Machine" was a good book. I recommend it to anyone who might be curious about what happened in computing before the Microsoft, Apple, and especially Google days. From the early days of Von Neumann and Turing, right up to the 90's, Waldrop's detailed research helped the story come alive. The book appears to be out of print, but it is well worth a visit to your library or getting a used copy.

If you made it this far, I'd really love to hear your comments on a few related questions:

Had you heard of Licklider before? If so, where? What sticks out in your mind about Lick?
What do you think about Lick's funding and management strategy in the early days of ARPA's IPTO?
What do you think of Lick's comparison of the Fig Wasp and Fig Tree to a man-computer relationship? Do you think we've obtained the man-computer symbiosis he was referring to?
What about PARC? It could still be considered success since the laser printer paid for Xerox's investment in it. However, as Steve Jobs points out, they could have been the IBM of the 90's but blew their chance. What do you think?
What do you think about the Mansfield Amendment of the 1970 fiscal year? It's easy to criticize things in hindsight. If it was 1969 and you didn't know the future, which side would you have honestly taken? How would you have defended your position?
If you read this book or similar books, what is most memorable to you about the period from the 1930's through the late 80's that you think most people don't know about?

My "Better Know a Framework" Talk at IndyCodeCamp

2008-04-26T21:09:00.011-04:00

The podcast ".NET Rocks!" has a segment called "Better Know A Framework" at the start of every show. The point of the short segment is to simply raise awareness of perhaps lesser known areas of the .net framework. I've found that it's a great way to learn about some things that I simply haven't looked at before.

When Aaron Lerch asked for session proposals for the IndyCodeCamp that he and some others were organizing, I thought it'd be fun to have a "Better Know a Framework" session that had much of the same feel as the segment on the show.

In order to prepare for the talk, I went back through every segment and made a few notes on what parts of the framework was covered as well as documentation links for more information. In case that work might helpful to anyone else, I'm including it as an "appendix" to this post.

The actual talk went pretty well. There were around 30 people at the session (my session was concurrent with 3 other sessions). One of the highlights was the introduction where the hosts of .NET Rocks introduced me (via a recording). Another highlight was being able to throw out flip-flops with my company's logo on them to people in the audience that were first to answer some of the questions I asked.

In trying keep with the code camp manifesto, I intentionally had no slides. The presentation was basically me stepping through this C# solution.

I created it to show how to use some lesser known classes and namespaces. I also briefly mentioned the "Turkey Test" and its implications on code.

Feel free to download the solution and run through it. If you couldn't make it to the talk, feel free to ask questions via the comments. If you were able to attend the event in person, please fill out the evaluation form online or leave comments here as well.

Thanks to Aaron Lerch and many others who helped organize Indianapolis's first code camp! It was a privilege to get the chance to speak there.

Appendix

Here's a very brief recap of every "Better Know a Framework" segment since it started. If you'd like more information about it, I included a link to the show where you can listen to it. I also linked to the MSDN documentation for what was covered. I put an asterisk (*) by the show number if I covered that topic in my demo source file.

243* - System.BitConverter: Coverts value types like an int to bytes and back. Also determines endianness of the machine.
244* - System.Security.Cryptography.RandomNumberGenerator: Much better than System.Random at generating cryptographically strong random numbers.
245 - System.Net.NetworkInformation.Ping: which returns a System.Net.NetworkInformation.PingReply that has a System.Net.NetworkInformation.IPStatus which is useful in determining if a remote machine is available (assuming they respond to ping that is).
246 - System.Diagnostics.FileVersionInfo: Useful for getting detailed information EXEs and DLLs (such as the company that produced the file).
247* - System.Diagnostics.Process: Information about a process on the system such as how much memory it's using, its process ID, main window name, etc. Also includes methods to do things like kill the process.
248 - System.Net.Dns Useful for determining the IP address(es) for a given host name.
249* - System.Text.StringBuilder: Much faster at building a string than concatenating a string. Discussed in depth on show #87
250* - System.Threading namespace: Classes useful in synchronization of threads:

CPU: Interlocked - Operations performed atomically by the processor (e.g.
Interlocked.Increment)
CLR: Monitor and ReaderWriterLock
Kernel:
Semaphore,
AutoResetEvent,
ManualResetEvent,
WaitHandle (e.g.
WaitHandle.WaitAll)

251* - System.IO.FileSystemWatcher: Useful for getting notifications when something on the file system changes.
252* - System.IO.Compression namespace: Classes involved in compressing and decompressing files/streams.
253* - System.Collections.Stack for LIFO (last-in-first-out) and
System.Collections.Queue for FIFO (first-in-first-out). Also available are generic
Stack and Queue.
254 - System.ComponentModel.BooleanConverter: Type converter to and from booleans.
255 - Calendars in System.Globalization: Many utilities for manipulating dates in various calendar schemes:

256 - System.Web.Mail: Old (deprecated) way of sending an email.
257 - System.Net.Mail: .net 2.0+ way of sending emails
258* - System.ComponentModel.BackgroundWorker: Simplifies use of background worker threads that need to update a UI via use of the RunWorkAsync method and DoWork event.
259 - System.ComponentModel.BrowseableAttribute
: Can be used to disable a property's visibility in the properties window (e.g. windows forms control).
260* - System.Collections.Generic.Dictionary: Maps keys to values
261 - System.Windows.Input namespace: WPF classes used for input (e.g.
InputManager, KeyboardNavigation, Mouse)
262 - System.Reflection.Assembly: Useful for finding information about .net assemblies such as classes, interfaces, methods, properties, events, etc.
263* - System.Threading.Timer: Simple and lightweight timer. See comparison of timers.
264 - System.SerializableAttribute: Marks an object as serializable (able to create a persisted represention of it). A binary formatter/serializer is at
System.Runtime.Serialization.Formatters.Binary.BinaryFormatter
265 - System.Xml.XPath.XPathDocument: Provides a fast read-only in-memory representation of an XML document using the XPath data model. See also
System.Xml.XmlReader for read-only XML reading.
266 - System.ApplicationException: Intended for use of application specific exceptions, but if you read Best Practices for Handling Exceptions, you'll see that you shouldn't use it anymore.
267* - Global Assembly Cache: Otherwise known as the GAC. Provides a system-wide storage facility for assemblies. To put an assembly in the GAC, you need to use the
strong name tool (SN) to get it ready, and then use
GACUTIL on it.
268* - System.Console: Besides the obvious methods like WriteLine, there are many lesser-known ones:

CapsLock
NumberLock
ForegroundColor
WindowHeight
WindowTop
WindowLeft
WindowWidth
Title (sets what to display in the title bar)
CursorVisible
In (Stdin)
Error (Stderr)
Out (Stdout)
CursorSize
CursorLeft
CursorTop
BackgroundColor

269* - System.Environment: Contains many assorted details about your application's environment:

UserName: User name of the person currently logged in.
WorkingSet: Physical memory mapped to the process
GetFolderPath: Useful for finding file paths to things like the Program Files folder (which can be different depending on if you're running 64 bit Windows)

270 - System.Net.HttpWebRequest , HttpWebResponse , WebRequest classes: Lower level classes used to perform an HTTP request. See notes on show #275 for the much simpler WebClient class.
271* - System.IO.StreamWriter and StreamReader: Helper classes for dealing with text files/streams (contains methods like ReadToEnd() for returning a string of whatever is left in the stream)
272 - System.Windows.Forms.Splitter: Control that allows you to split parts of a UI in a way that allows the user to expand or shrink an area. This class can be hard to use, see show #273.
273 - System.Windows.Forms.SplitContainer: Much simpler way to provide a split UI.
274 - System.Windows.Forms.ToolTip: An
extender provider that allows you to add Tooltips to all items in a container's scope. It implements System.ComponentModel.IExtenderProvider. Similiar to how
System.Windows.Forms.ErrorProvider works.
275* - System.Net.WebClient: Provides a very easy way to perform common HTTP operations in 1 line of code (e.g. DownloadFile, DownloadData)
276 - System.Web.UI.Page: SavePageStateToPersistenceMedium and
LoadPageStateFromPersistenceMedium allows you to store viewstate in a different place besides sending it down to the browser each time. This can be useful as viewstate can account for a large (67%+) part of your page's size.
277 - System.Web.Management namespace: Classes that do all sorts of management of web servers and web farms. For example, WebAuditEvent allows you to audit web events.
278 - System.IO.IsolatedStorage: (In this show Carl thought that IsolatedStorage was used for storing things in a secret way. See show #278 )
279* - Christopher Loaf from Sweden pointed out that System.IO.IsolatedStorage is primarily used for storing and retrieving data in a partial trust environment (e.g. a web browser).
280* - System.Convert: Methods for converting items from one type to another (e.g
ToBoolean, ToChar, ToBase64String, FromBase64String). In addition, has IsDBNull to determine if an object is a database null value.
281* System.Globalization.CultureInfo: Used for ensuring that you retrieve, store, and process information according to a specific culture. For example, if you do DateTime.Now.ToString("D"), you'll get the date formatted in a culturally specific way as outlined by this class.
282 - System.Guid: Class used for handling global unique identifiers.
283 - System.IO.Packaging: Provides classes that support storage of multiple data objects in a single container. (Most notable example is Office 2007+ documents, see show #285 )

284 - System.Security.Cryptography.SHA1: Hash algorithm that has been
academically broken and therefore shouldn't be used anymore for safety reasons. The framework also has unbroken ones such as SHA512 which uses 512 bits instead of 160 bits, but is much more secure.
285 - Comments about the Guid class and how System.IO.Packaging is really useful for reading Office 2007 documents such as Word files)
286 - Microsoft.Windows.Themes: Classes used by WPF to provide visual appearance that is similiar to Vista, XP, and Window 2000 and lower (Luna, Aero, Royale, and Classic).
287* - System.IDisposable: Useful for controlling exactly when resources get released. An early Dotnetrocks show with Chris Sells talks about it in depth.
288 - No Better Know a Framework segment.
289 - System.ICloneable: Originally designed to provide a way of determining how to create a clone (copy) of an object. However, Brad Abrams recommends not to implement it in public APIs since its semantics are confusing.
290 - System.Security.Principal.WindowsPrincipal: Contains methods for determining information about the current user's Windows account information (e.g. use
IsInRole to determine if the user is an administrator)
291* - System.GC: Methods and properties pertaining to the built-in Garbage collector (see show #287 notes as to how this relates to System.IDisposable)
292 - System.CodeDom and System.CodeDom.Compiler namespaces: Classes for manipulating source code and their compiled forms.
293* - System.Math: Class containing many common math operations

Max
Min
Absolute Value
Tangent
Floor
Sqrt
Sine
Sinh
IEEERemainder
BigMul: returns full product of two 32 bit numbers (64 bit result)

294* - System.TimeSpan: Many methods and properties that are useful in working with a span of time (e.g. 30 minutes)
295* - System.WeakReference: Class that holds onto an object reference but gives clues to the garbage collector that the reference can be let go of if memory pressure arises.
296 - System.DataMisalignedException: Obscure exception that can be thrown if data is read from or written to memory that isn't aligned according to what the processor expected.
297* - System.Text.RegularExpressions.Match: Regular expressions are very useful for parsing and manipulating text. See this reference for a sampling of what types of patterns you can use.
298 - System.Resources.IResourceReader interface: You can use a ResourceReader or
ResourceWriter for using resources that can be stored elsewhere besides inside the assembly.
299 - System.Web.HttpResponse.TransmitFile: Provides a simple way to write a file to a stream.
300 - No Better Know a Framework segment
301* - System.Collections.IEnumerator and System.Collections.Generic.IEnumerator: Interfaces used for specifying how to enumerate (go one by one) through a collection.
302 - System.Speech.Synthesis namespace: Classes for creating speech from text
303 - Microsoft.VisualBasic.Compatibility.VB6 namespace: Classes for handling compatibility with VB6 semantics in .net.
304 - System.Drawing.Printing.PrintDocument: Class that has methods and events (e.g.
PrintPage) for easy use with printing.
305*- System.IComparable and System.IComparable: Has a
CompareTo method to determine how two objects relate to each other (Carl focused on equals, but you can also do greater than and less than).
306 - System.IO.Ports: Classes like SerialPort which are used for serial communications.
307* - Email from Thomas Betz about show #305 on System.IComparable discussing how it's most commonly used for sorting. The System.Object.Equals and System.IEquatable are better suited for determining equality.
308 - HTTP Handlers implementing System.Web.IHttpHandler: For example, you can register your code to be called when IIS processes a certain file extension.
309* - Discussion of C#'s yield keyword and how it can be used.
310* - Discussion of the new type inference feature in C# 3 and VB 9 so that you don't have to bother defining an object's type.
311 - System.Web.IHttpModule: Can be used to handle processing in the HTTP life cycle such as authentication, logging, and redirects. See Creating and Registering a Custom HTTP Module for more information.
312 - Discussion of the new anonymous types feature in C# 3 and VB 9.
313 - System.Collections.ObjectModel.ObservableCollection: Collection that has events for notification of when the collection has been modified.
314 - System.Windows.Converters: Classes like Int32RectValueSerializer which are used by WPF to persist objects to a string.
315* - System.IFormattable: Allows you to specify special string formatting options in
String.Format and ToString.
316 - System.Nullable: Generic wrapper for value types that allow for the possibility of a null.
317 - System.Net.PeerToPeer namespace: Classes providing access to peer network functionality such as how peers discover each other using the Windows peer to peer infrastructure (e.g. PNRP - peer name resolution protocol)
318 - System.Net.PeerToPeer.Collaboration namespace: Enhances the peer-to-peer networking functionality and provides capabilities for serverless, managed collaboration sessions.
319* - System.Linq.IQueryable: Used by LINQ to evaluate queries.
IQueryProvider creates and executes these.
320 - System.IO.Pipes namespace: Classes for working with interprocess communications using pipes.
321* - System.AppDomain: Encapsulates working with an application domain (a lighter weight than an process, but used by the CLR to provide isolation). See show 8 with Rocky Lhotka for a discussion on them.
322 - System.AppDomain.AssemblyResolve event: This method is raised if code in an AppDomain tries to find an Assembly and is not able to. See this knowledge base article for how to use it.
323 - System.AppDomain.DoCallBack method: Useful for executing a callback in another AppDomain.
324 - System.Web.Mobile namespace: Classes for use with mobile web devices.
MobileCapabilities class can be used to determine things like a client's screen size.
325 - System.Delegate: Class encapsulating a single method; sort of like a function pointer but better.
326 - More on delegates and how they are a combination of a code pointer plus the metadata including an invoke method.
327 - System.Configuration.IPersistComponentSettings: Defines standard functionality for controls or libraries that store and retrieve application settings.
328 - System.Windows.Xps namespace: Classes like
XpsDocumentWriter for saving XAML objects to a PDF like format.
329 - System.Data.IDbDataAdapater: Interface used by
System.Data.Common.DbDataAdapter and others built from it to fill a
DataSet
330 - System.Net.Sockets namespace: Classes for use with low-level socket communication. See DNR TV show (part part 1 and 2)
331 - No Better Know a Framework segment.
332* - System.String Compare method: Useful for performing a culturally sensitive string comparison. See System.Globalization.CompareOptions.
333* - System.Diagnostics.Trace: Class used to trace (record) what paths are executed in your code. If you've ever used Console.WriteLine, you'll find Trace.Write and Trace.WriteLine similar. They write to a listener.
334* - System.Diagnostics.TraceListener: Base class used to implement trace listeners (destinations/outputs for Trace.Write). For example TextWriterTraceListener writes to text files. You can use a config file to add/modify the listener without modifying code. In addition, you can do it dynamically in code via the Trace.Listeners.Add method.
335* - System.IO.FileInfo: Provides many details about a file:

336*: System.IO.MemoryStream: Provides an in-memory version of a
Stream. Much easier to work with than a byte array.