Knowing .NET

The long-term success of every operating system is tied to the progress of hardware, which has taken a 90-degree turn from “faster every generation” to “more parallel every generation.” For the better part of a decade, the chips in new machines have run no faster, but there have been more processors living side-by-side. Many of us run “octocore” desktops and Santa will be delivering 16-core systems to good little programmers this year.

The days of single-threaded programming is over. Done. When someone complains about performance and find out out that your code uses 1/16 or 1/32 of the power available, there’s going to be a lot of trouble. But nevermind *your* problems, think about the OS vendors looking at a future with dozens of cores inside a single machine. And not just dozens of cores, but the absolute certainty that the entire hardware infrastructure will be parallelized. The next decade will bring the wholesale reinvention of the PC architecture and I’ll bet dollars to donuts that at least one major operating system is going to screw up and lose years of performance improvements. At this point, with Windows still recovering from the Vista debacle and still trying to get its mobile feet firmly planted, it’s not at all certain that the Windows hegemony will last through 2025.

WinRT, the runtime used for the new “Metro-style” programs of Windows 8, gives Microsoft a new system-level interface that is designed for highly-parallelized programs. Every function that is expected to take more than 1/20th of a second to execute has been recast in an asynchronous form: developers will certainly be able to screw up and write programs that block/freeze, but they will have difficulty blaming that problem on the OS.

A highly asynchronous system-level API gives Microsoft the top-down leverage it needs to squirrel around at the lowest levels, reworking the OS incrementally to work with more-and-more side-by-side processing. The dramatic break in UI appearance is both a powerful aesthetic incentive and a subtle indicator of compliance — you want the Metro UI and, if you have it, your code is built on a foundation that has firm asynchronous roots.

Given the development tempo and lifespan of enterprise applications, it is not a moment too soon for this change.

As the sun falls, the seagulls, which have been the only birds I’ve seen, are joined by some swifts darting into the facade of nearby buildings and a trio of hawks or maybe kites: rather drab, but with that athletic sharp-banked twisting flight.

…

The wide beach has a cold-looking tumbling surf but there are no surfers, at least tonight. Finally I see some seabirds beyond gulls — a trio of pelicans riding the ground-effect of the waves and an ill-defined flock of diving seabirds I can’t see well in the heavy glare.

…

I have beheld a Peruvian booby! I love boobies! And not just because of the name; they are elegant flyers (but mostly because of the name). I have now seen every booby but one — the blue-footed.

…

As we leave Choros, an Ibis lifts heavily out of the grass and flies alongside the bus for a hundred yards. It’s head is a lovely complex of curves.

…

I saw a seagull near the supermarket that looked like it was cross-bred with an albatross. It had long thin pointed wings like an ocean cruiser. I’m pretty sure it was just a seagull, but a fine Antipodean gull cut out for scavenging dumpsters off Cape Horn.

…

Condors ride thermals, and thermals are bad for seeing, so when the condors are at the observatory, the astronomers curse.

…

It’s funny how shorebirds seem to be globally distributed. I’ve seen phalaropes, curlews, plovers, and what looked like an oystercatcher — whether they are local species or the same as California I don’t know.

…

A bay at Isla Dama is named after a “scissor bird” which sounds like a skimmer — a bird that flies at high speed with its beak splitting the ocean surface, trying to spear a sunning fish. I’ve always wanted to see a skimmer. I don’t on this trip.

A Game of Thrones by George R.R. Martin

My rating: 4 of 5 stars

Dynamite, the most compellingly complete “world” I’ve read in I-can’t-remember. The world is brilliant, a gritty and “realistic” medieval-ish place with slowly-introduced fantastical elements — summers and winters last for years (and even decades), there were once dragons, there are zombies (wights… same thing). Martin’s tone is pitch-perfect, too, with vivid descriptions that never overstep into the sentimental.

The characters are the weak point, but that’s only noticeable because one character (Tyrion the Imp) is fully realized, complex, and the flatness of the others is apparent in contrast. On the other hand, there’s a certain amount of “people are the way they are because they’re duty-bound and locked into roles,” so maybe those characters will flower in later books.

View all my reviews

On my recent trip to Chile, I used the following iPhone apps:

Word Lens: Realtime translation. You point the iPhone at a sign or menu and you see live video, but the Spanish words are translated into English. It not only provides a “Wow!” experience, it’s actually by far the most useful translator, since it can be used with relatively little fanfare on, for instance, a menu. The words sometimes swim in and out of translation and only the words, not the grammar, is translated, but you definitely get the sense of what’s going on.

Photosynth: Panoramic photos. You click “start” and the camera takes a photo, bordered with a dash. As you move the camera around, more photos are added automatically … *click* *click* *click* and a panorama is built up in no time. When you are done, the stitching of the images is completed and you have a panoramic image. The stitching is not perfect (take a look at this quite-poor job of the Gemini South telescope, which I thought would be an excellent candidate, given the strong lines of the telescope’s struts), but the image-capture is lightning fast and on landscapes it seems to do a better job.

Camera+: Photography. There are a few things I like about this application over the iPhone’s built-in camera app. First, it has a “stabilizer” mode which only takes a photo when your hand has steadied; obviously, you can’t use this in all situations, but I prefer it when trying to take a landscape. Second, it has built-in sharing for Facebook. Third, you can crop and do basic adjustments in the app. Pretty simple to use and adds some real functionality.

Trip Journal: Note-taking. A limited, but useful, product that allows you to keep together your photos, notes, and locations. If you actually want to put together a travelogue, you want to organize your stuff by time, which can be difficult if you keeo your notes in one program, your photos in another, and GPS waypoints in a third. Trip Journal ties together these things, *but* cannot import notes or photos from other applications and has very limited editing capabilities. It turns out, though, that it’s export format (.tjz) is just a zip file that contains an XML document and the photo JPEGs, so if you’re the type of person who says “Oh! Well, that makes it easy,” it’s a good product.

Night Stand: Alarm Clock I use this as my alarm clock. Some reviews complain of the alarm not working, but I use this app every day and it work for me. What people *may* be complaining about is that if you set the alarm clock to a song that is subsequently removed from the phone, the app will not complain (e.g., I have a “smart playlist” that puts highly-rated and “not recently played” music on my phone; if I set Night Stand to wake to some song on that playlist and subsequently sync the iPhone and that song gets removed, Night Stand will silently fail). So instead, I just make sure that the song I choose to wake to is on the phone and won’t get bumped (on this trip, I chose to wake to “Drunken Sailor,” by the Blaggards. Hey ho and up she rises!)

Tom Tom Chile: Navigation A few years ago, I drove around for 45 minutes in what couldn’t have been more than an 8-block area looking for my hotel. I swore that I would never rent a car without turn-by-turn navigation again. This app is probably the most expensive thing I’ve ever bought for my iPhone, but for me, in a foreign country, with extremely limited Spanish, and no 3G Internet (I actually didn’t bring my SIM-card with me on this trip), it was worth it. The street maps seemed quite accurate *but* were very, very bad about 1-way restrictions, which were extremely common. So “Ms. Garmin” would often be commanding me to move towards an impossible route. But, at some point she’d give up and reroute me through something manageable. I used this with a vent mount that I brought with me, but I neglected to bring an in-car recharger, which would have been a mistake had I not been primarily in the city. The Garmin app *sucks* power, even when it’s in the background (I think what drains the power is the real-time navigation; pressing *Clear Route* when you don’t need it seems to help quite a bit).

The Ice Limit by Douglas Preston

My rating: 4 of 5 stars

A fun thriller concerned with the recovery of a meteorite on the frozen islands off Cape Horn. There’s a good deal of nonsense: engineering that would take months or years is done in a matter of days (to the point of being confusing: “What? Where did a *road* come from?”), the crazy career-ruining theory that just happens to be redeemed, and an epilogue that takes the over-the-top ending to a new level. But, y’know, not every twist is telegraphed, the character’s fates are somewhat surprising, and the story plays itself out within the rules it lays out for itself. The action is paced well and builds to a series of fun and increasingly implausible climaxes, which is I think exactly what you want in this kind of book. The next time I take a 6-hour flight, I’d read another book by these authors.

View all my reviews

My first in-water shark encounter was in San Diego, in La Jolla Cove. I was snorkeling in the cove, out near “Alligator Rock” when I saw a Gray Smoothhound, an entirely harmless shark maybe 3’ long. But, hey, it’s a shark that looks like a shark and I wanted to share the moment with my friend Dave, who was maybe a hundred yards away. So I called out to him.

In my head, what I called out was along the lines of “Dave! A carcharhinid! Certainly a Mustelus, most likely californicus!” (I’d convinced myself that my career in Marine Biology would be aided by memorizing scientific names) But since I was snorkeling and couldn’t quite get all that out, what I shouted was, instead, “Shark! Shark!”

Which, it turns out, is not the most appropriate thing to shout out in a cove crowded with casual swimmers.

Damon Tucker, probably the Big Island’s most prominent blogger, was given a pretty solid roughing-up by Big Island police on Friday night, while videotaping police arresting people after a concert in Pahoa. The photos on Tucker’s site clearly indicate that excessive force was used against Tucker, who probably weighs 150 pounds soaking wet. As for Tucker’s “crime,” it is not against the law to photograph and videotape police in Hawai’i (or most states), and such records are an important check on the possibility that police will occasionally overstep their authority and, say, rough up a guy who’s obeying the law and weighs 150 pounds soaking wet.

Of course, police have a hard job, I wasn’t there, etc., but I have a hard time imagining him interfering with the police or disobeying their instructions on crowd control. What I don’t have a hard time imagining is him standing with a good view, with his camera up, recording the scene. “Standing around taking photos” is what Damon does and has been doing for the past half-decade or more.

Project Daytona: Iterative MapReduce on Windows Azure – Microsoft Research.

Prime numbers are not my thing, but generating them is a common task in the early Project Euler problems. The one algorithm I know for generating primes is the Sieve of Eratosthenes, which I defined in Scala as:

def successor(n : Double) : Stream[Double] = Stream.cons(n, successor(n + 1))

def sieve(nums : Stream[Double]) : Stream[Double] = Stream.cons(nums.head, sieve ((nums tail) filter (x => x % nums.head != 0)) )

val prime_stream = sieve(successor(2))

The first function is the only function that I’ve ever written that I’m sure is properly “functional.” It’s stuck in my head from circa 1982 LISP. It uses Scala’s Stream class, which is like a List but is “lazily evaluated,” in other words, it only calculates the next value in the List when it’s needed (the Stream pattern is to create a List whose head is the next value and whose tail is a recursive call that, when executed will produce the next value).

The 2nd function sieve is my take on the Sieve of Eratosthenes. It too returns a Stream of primes. (By the way, the reason I use Double rather than an Int or Long is that one of the early Project Euler problems involves a prime larger than LONG_MAX.)

In case you’re not familiar with the algorithm, the Sieve is conceptually simple. Begin with a list containing all positive integers starting at 2 (the first prime) [2, 3, 4, ...] . Remove from the list every multiple of your current prime. The first number remaining is the next prime. For instance, after removing [2, 4, 6, ... ], the first number remaining is 3. Prime! So remove [3, 6 (already removed), 9, ... ]. Since 4 was removed as a multiple of 2, the next available is 5. Prime! Remove [5, 10 (already removed), 15 (already removed), ...] …

The 7th Project Euler problem is “What is the 10001st prime number?” Unfortunately,

scala> prime_stream take 10001 print
2.0, 3.0, 5.0, 7.0, ...SNIP ... 29059.0, 29063.0, java.lang.OutOfMemoryError: Java heap space
 at scala.Stream$cons$.apply(Stream.scala:62)
 at scala.Stream.filter(Stream.scala:381)
 at scala.Stream$$anonfun$filter$1.apply(Stream.scala:381)
 at scala.Stream$$anonfun$filter$1.apply(Stream.scala:381)
 at scala.Stream$cons$$anon$2.tail(Stream.scala:69)
 at scala.Stream$$anonfun$filter$1.apply(Stream.scala:381)
 at scala.Stream$$anonfun$...

That will never do. Obviously, I could run Scala with more heap space, but that would only be a bandage. Since a quick Google search shows that the 1000th prime number is 104,729 and I’m running out of heap space near 30K, it seems that “messing around with primes near the 10Kth mark” requires some memory optimization.

Converting the Sieve

If I really wanted to work with very large sequences of primes, I should certainly move away from the Sieve of Eratosthenes. But I’m not really interested in prime number algorithms, I’m interested in the characteristics of the Scala programming language, so I’m going to intentionally ignore better algorithms.

My first thought was “OK, I’ll allocate a chunk of memory and every time I find a prime, I’ll set every justFoundPrime-th bit to 1.” But that would depend upon my allocated memory being sufficient to hold the nth prime. With my Google-powered knowledge that the 10001st prime is only 100K or so, that would be easy enough, but (a) it seemed like cheating and (b) it would require a magic number in my code.

My next thought was “OK, when I run out of space, I’ll dynamically allocate double the space– no, wait, I only need justFoundPrime-(2 * justFoundPrime) space, since I’ve already checked the numbers up to justFoundPrime.”
My next thought was “And really I only need half that space, since I know 2 is a prime and I can just count by 2…And, y’know, I know 3 is prime too, so I can check–” At which point, I engaged in a mental battle over what was appropriate algorithmic behavior.

On the one hand, I didn’t want to change algorithms: if I moved from the Sieve to a slightly better algorithm, then wasn’t it Shameful not to move to at least a Quite Good algorithm? On the other hand, the instant I opened the door to allocating new memory, I committed to keeping around the list of already-discovered primes, since I would have to apply that list to my newly-allocated memory. But if you have a list of numbers, checking if your candidate number is a multiple of any of them can be done without consuming any additional memory. But is it the same algorithm? Isn’t the Sieve fundamentally about marking spots in a big array?

Finally, I decided that checking a candidate number against the list of already-discovered primes was the Sieve algorithm, just with a smallest possible amount of memory allocation — one number. (By the way, did you read the article in which scientists say that rational thought is just a tool for winning arguments to which you’re already emotionally committed?)

Here then, is what I wrote:

def multiple_of = (base : Long, target : Long) => target % base == 0;

val twoFilter = multiple_of(2, _ : Long)
val threeFilter = multiple_of(3, _ : Long)

println(twoFilter(4))
println(twoFilter(5))
println(twoFilter(6))
println(threeFilter(4))
println(threeFilter(5))
println(threeFilter(6))

The first function multiple_of is a function literal (?) that returns true if the target is a multiple of the base. The next two lines, where I define twoFilter and threeFilter are  an example of the functional idiom of partial function application (I think — “currying” is the use of partial function application to accomplish a goal, right?).

This is an undeniably cool feature of functional languages. Without any fuss, these lines create new functions that require one less argument to have their needed context. Once you have a twoFilter, you don’t need to keep the value “2″ around to pass in. Which might not seem like a big win, since a function named twoFilter or threeFilter is no more compact than calling multiple_of(2, x) or multiple_of(3,x). But…

def filter = (x : Long) => multiple_of(x, _ : Long);

val fs = List(filter(2), filter(3))
for(f <- fs){
   println("Eight is a multiple of this filter: " + f(8))
}

OK, now that’s nice and compact! Now we have a new tk function literal? tk called filter and rather than have a bunch of variables called twoFilter and threeFilter and fiveFilter, we just have a List of filters. With such a list in hand, it’s easy to figure out which numbers in a list are relatively prime:

def relatively_prime(fs : List[(Long)=>Boolean], target : Long) : Boolean = {
 for(f <- fs){
    if(f(target)){
      return false;
    }
 }
 return true;
}

println("4 is prime? " + relatively_prime(fs, 4))
println("5 is prime? " + relatively_prime(fs, 5))

val list = List[Long](2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
println(list.map(relatively_prime(fs, _)))

Which leads to a simple recursive function to find the next prime:

def next_prime(fs : List[(Long)=>Boolean], x : Long) : Long = {
 if (relatively_prime(fs, x)) {
    return x
 }
 return next_prime(fs, x + 1)
}

println(next_prime(fs, 4))
println(next_prime(fs, 8))

Which leads to our solution:

def primes(fs : List[(Long)=>Boolean], ps: List[Long], x : Long, nth : Long) : List[Long] = {
   if(ps.size == nth){
      return ps;
   }

   val np = next_prime(fs, x)
   val sieve = fs ::: List(filter(np));
   primes(sieve, ps ::: List(np), np + 1, nth);
}

println("Missing 3 because its in fs" + primes(fs, List[Long](2L), 2, 8))
println((primes(List(filter(2)), List(2L), 2, 8) reverse) head)

def nth_prime(nth : Long) : Long = {
   (
      primes(
         List(filter(2)),
         List(2L),
         2,
         nth
     ) reverse
   ) head
}

println(nth_prime(8))
println("The 10001st prime is " + nth_prime(10001))