24 March 2009

walk score -- measuring pedestrian friendlyness

As I've mentioned before, I don't have a car, don't want one, and don't think that people should have an unquestioned right to drive a car. I'm an urbanist, and I believe that people should be able to walk to all of their life's necessities, or in the worst case, ride a bike or public transportation. Since I've moved to Princeton, one of my major complaints has been how inconvenient it is for someone without a car.

Today, I discovered WalkScore (via the Freakonomics Blog). It is a google maps mash-up which tries to quantify how walkable an area is according to distance from common necessities, such as grocery stores and bars. Very clever. And for comparison:

  1. My old neighborhood in Charlottesville: 85/100 - very walkable
  2. My old neighborhood in Brooklyn: 88/100 - very walkable
  3. My current neighborhood in Princeton: 29/100 - car-dependant
  4. Washington Square Park, NYC: 100/100 - walker's paradise.
It's nice to have some external validation on my opinion of Princeton ;)

In all fairness to Princeton, if I were to live on Witherspoon at Spring St, I'd live in Walker's Paradise 95/100, but what grad student can afford that?

05 March 2009

Bjarne Stroustrup is so metal!

Bjarne Stroustrup is so metal!On Wednesday, Bjarne Stroustrup made a visit to Princeton, and the Liberty Research Group scheduled a private meeting with him before his colloquium. We spent a little over an hour discussing the C++0x and the future of C++. Overall, Bjarne is a cool guy, and I had an excellent time talking with him.

The wikipedia article about C++0x is painfully out of date. Bjarne mentioned some upcoming features that are hardly mentioned, if at all. Of these, the ones which took my interest the most were Concepts, Axioms, and the future of static typing in C++.

I'll disclaim that I haven't read any C++0x standardization documents, not even drafts, so take everything here as a grain of salt. These are simply my take-away points from the talk.

Bjarne is concerned that the template feature of C++ does not allow programmers to sufficiently constrain template parameters. For instance, a sort algorithm may be implemented to operate on a random-access iterator. However, recall that iterators in the C++ STL do not share a common inheritance (and there are fair arguments that they shouldn't). C++ templates cannot capture the notion that one of its formals must be a iterator-like type, and so specializing the template against, say a string, will likely yield hundreds of uninformative type errors instead of a simple error stating that we expect an iterator.


One solution to this problem would be to create base iterator classes in order to ensure an interface (this is the approach taken by Java, for instance). However, one could argue that this is an inappropriate use of inheritance---it's not code re-use, and although we give many concepts the name iterator, they really have little in common.

Some languages use a notion of structural equivalence (or, less formally, duck typing) to capture these constraints. I think this is the appropriate technique. The earlier example of a sorting algorithm simply requires some object which can provide random access to a data structure, and the most direct test for compatibility is whether the interface is a satisfied. In C++0x, Concepts are an implementation of structural equivalence (from the high-level, language view). In the low-level view, concepts are a special case of templating, and produce multiple implementations of the same code according to the specific type.

In a C++0x Concept, one can specify the methods which must be supported. For instance, one may have a Concept named TotalOrder, which must support a less-than-or-equal-to operator. Many types satisfy the TotalOrder concept, such as int, double, std::string, yet they are not required to have a common ancestor. In this sense, a concept allows you to communicate many of the traits to a type, without paying the penalty of multiple inheritance.

But Concepts get cooler. Although I describe them as a mechanism for structural equivalence in C++, they can also be viewed as mixins, since they allow a programmer to specify a default implementation for many methods. With the prior example of TotalOrder, one could also add default implementations of greater-than, equal-to, etc, operators as functions of less-than-or-equal-to. In this way, it becomes very easy for programmers to bootstrap support for all operators while writing minimal code.

Suppose that I implement some class that satisfies TotalOrder. This information simply means that my class supports comparison operators. One wonders, however, if these operations actually behave as a total order. As a counter example, I could write a random number generator to produce the result of the less-than-or-equal-to comparison---can a language be made to disallow this? Or, can a compiler be taught to rely upon deeper qualities of total orders, without having a special case for total orders?

Axioms allow the programmer to specify additional qualities of operations that transcend simple typing. For instance, one could write axioms that signify that the less-than-or-equal-to relation is transitive, or that it is always the logical inverse of the greater-than relation. With axioms, we can state that a sort algorithm not only requires a random-access-iterator, but also that there is a total order of the elements which satisfies transitivity. The use of concepts and axioms allows us to specify all of the constraints of the sort algorithm.

But how can the compiler use axioms? It is unlikely that any compiler will ever be able to verify that the listed axioms are true for a given implementation. Instead, axioms will provide additional transformations to the compiler's arsenal of optimizations. With support for axioms, many compiler optimizations including constant-folding (especially with associativity), reduction in strength, and common-subexpression elimination can be lifted from the compiler and expressed at the language level. I think this is really cool.

I think the notion of concepts and axioms struck home with me because they resemble some of my thinking on one of my side projects. I've been working on a language for years now (never enough time, alas!) in which I plan to feature structural equivalence in typing for reasons similar to those outlined by Bjarne. The axioms are a natural extension which I now realize I would like to support as well.

Finally, before the meeting was over, I had to ask a question about type safety. Throughout his book The Design and Evolution of C++, Bjarne laments the type (un)safety of C. Repeatedly, and with each new language feature, he attempts to make C++ more typesafe, but is repeatedly foiled by inherited features such as void pointers and unrestricted casting. So, I asked: are you ever going to take the plunge and drop support for pointers in C++? His answer was intelligent, and showed a great understanding of not simply the technical considerations of C++, but also the political considerations.

Mr. Stroustrup suggested that he hopes to add more and more features to C++ until type-safe alternatives are available for each and every unsafe aspect of C++. Once that has happened, he hopes to define a safe subset of C++. At that point, all existing C++ tools could be given a flag to provide warnings of unsafe features. This safe sub-C++ will immediately have rich toolchain support, but will be able to provide strong guarantees, such as those provided by ML. Excellent plan.

Bjarne is a very interesting person indeed; I recommend you talk with him if you ever have the chance.

01 March 2009

A quick thought...

The other day, Daya and I rode our bikes to the local grocer to buy some groceries. At the checkout line, we stuffed our groceries into our bags, when the teller asked, "Did you guys ride your bikes here?"

"Yes," I responded, "How else does one buy groceries?"

She deducted a dollar from our total, and told us the store offers a ride your bike discount. The guy in line behind us muttered something to the effect of "I'm glad you're doing your part."

It's at times like these that I want to say "No! I'm not being a responsible person; rather, you are being irresponsible!" Honestly, I think they should add a fee for driving to the grocer, perhaps charge for parking, or make you wear an "I hate the environment" shirt.

But, I bit my tongue.

On an unrelated note, Bjarne Stroustrup is visiting Princeton CS on the 4th for a 4:15 colloquium. If you're in the area, you should check it out. It will be packed.