Mobile OS Wars: Upgrades

Right now Apple and Google are in the midst of major upgrades to the OS on their devices, the iPhone OS and Android. If you develop for these platforms, you need to make sure your applications have no issues on the new versions. The simplest first step is to upgrade your SDK and development tools, and re-compile. Neither OS updates remove (any?) APIs, they mostly add to them. So it is unlikely your application does not compile under the new SDK. You can also launch your application in the emulator provided with each SDK. Now there is a little more chance of a bug popping up.

Still, a lot of upgrades are only found when you run your app on the new OS on a device. Why is this? A lot of the bugs that come from these upgrades are memory management issues, multi-threaded issues, or networking issues. When you run on an emulator, many of these issues just never happen (memory/networking) or behave differently because of the difference in processor seed (multi-threading.) So you need to upgrade the OS on your test devices (you do have dedicated testing devices, not just your personal phone, right?)

Upgrading your iPhone OS is really quite easy. You download the new OS. You right-click on the "restore" button in iTunes, or you can use the Organizer in XCode. Either way, device is wiped, the new OS is installed, and then your data is reloaded from a backup (iTunes backs everything up automatically.) The only gotcha is that apps that weren't installed via iTunes, i.e. apps you developed and are testing, do not get backed up, so they disappear. This should not be a problem since you have the source code for such apps. However, in order to re-install from source code via XCode, your SDK must also be upgraded to the same version as the OS. Again, you probably upgraded the SDK first anyways, so no big deal.

Upgrading your Android device is not quite as straightforward. There are a lot of steps, so I won't repeat them all here. The upgrade is fundamentally different in that you replace parts of the system in place. Your device is not wiped. This is necessary because there is no automatic backup process on Android phones. On the iPhone, this is handled by iTunes. There is no analogous desktop software companion to Android. This is viewed by many as a pro, but in this case I consider it a con. Anyways, there are a lot of steps, but it is very smooth and very fast. In fact, it is much faster than the iPhone process because there is no delete/restore going on.

All of this points to some of the core differences between these platforms. Others have pointed to the Mac vs. PC scenario of the 80's as being similar to the iPhone vs. Android scenario of today. Apple went with a closed platform where they controlled everything, vs. the "open" combination of Windows plus Intel. Any manufacturer could slap an Intel chip in their machine and install Windows on there, with full freedom on what else went in to the machine. Same thing is going on here. Apple controls the OS and hardware of the iPhone. Android can go on many different types of hardware. Right now this is not making a big difference, since there are not yet a lot of Android phones. However, it seems likely that at some point you will see Android phones that are free with a contract or maybe $100 from Metro PCS or even pay-as-you-go carriers.

Ok so that was a tangent, what does it have to do with this issue? Well, by having a closed system, Apple can provide a lot of advantages. Upgrading is simple. For consumers, you get the upgrade from Apple directly. You might notice the Android link above is from HTC, the maker of the first Android phone. Most consumers will get the upgrade from T-Mobile. Notice that Google is not even in this conversation, even though not only do they make the OS, but it is open source. In addition, many developers I know are dreading the proliferation of Android. Currently development for Android is nice, in fact a lot nicer than for iPhone. The development/emulator scenarios are equivalent, but debugging on devices is much simpler. However, when more variants of Android appear, and those variants are more specific to the devices they run on, then right once / run anywhere fades away. Again, notice that the OS upgrade came from the handset manufacturer already. That is very significant.

Tail Recursion in Scala

Earlier this week, I gave a talk about Scala with Bill Venners and David Pollak. In my slides, I had an example of a factorial function in Scala and in Java. I made that point that not only is Scala usually almost as fast as Java, but sometimes it is even faster. One reason for this is that the Scala compiler can perform tail recursion optimizations on your code. This is something that has been proposed for Java as well as other languages, but has its downside as well.

Back to Scala... Bill also had a slide that showed a factorial function in Scala, though it was much simpler as it made use of Scala's implicit conversions between integers and BigInts. Afterwards, Bill and I were talking, and he pointed that he did not think the Scala compiler would be able to optimize either my code or his code. Here is code that is very similar to Bill's code (I don't have the exact code handy, so I recreated it from memory):

def factorial(n:BigInt):BigInt={
 if (n == 0) 1
 else n*factorial(n-1)
}

Why can't this be optimized as a tail call? Instead of explaining it myself, I will introduce the hero of this story, Daniel Spiewak (check out his blog or follow him on Twitter.) Bill emailed Daniel about his suspicion, and Daniel confirmed it :
You're quite correct: this version of factorial is not tail recursive.
I find it sometimes helps to split the last expression up into atomic
operations, much as the Scala parser would:

else {
 val t1 = n - 1
 val t2 = factorial(t1)
 n * t2
}

It is possible to devise a tail-recursive factorial. In fact, it
might be possible to convert any recursive function into a
tail-recursive equivalent, but I don't have a proof for that handy.
Back to factorial:

def factorial(n: Int) = {
 def loop(n: Int, acc: Int): Int = if (n <= 0) acc else loop(n - 1, acc * n)
 loop(n, 1)
}

I'm cheating a bit by taking advantage of the fact that multiplication
is commutative, but this is the general idea. Some functions are
naturally tail recursive, but for those which are not, this
"accumulator pattern" is a fairly easy way to achieve the equivalent
result. Technically, the accumulator must be combined with an
inversion of the computation direction (bottom-up rather than
top-down) to generate a truly-equivalent tail-recursive function, but
it is not necessary for examples like this one.
This accumulator pattern is a great tip. To drive home the difference this produces in the behavior of the Scala compiler, it is useful to use our good 'ol friend javap. For the original code, here is the output:

public scala.BigInt factorial(scala.BigInt);
  Code:
   0: aload_1
   1: iconst_0
   2: invokestatic #27; //Method scala/runtime/BoxesRunTime.boxToInteger:(I)Ljava/lang/Integer;
   5: invokestatic #31; //Method scala/runtime/BoxesRunTime.equals:(Ljava/lang/Object;Ljava/lang/Object;)Z
   8: ifeq 21
   11: getstatic #36; //Field scala/BigInt$.MODULE$:Lscala/BigInt$;
   14: iconst_1
   15: invokevirtual #40; //Method scala/BigInt$.int2bigInt:(I)Lscala/BigInt;
   18: goto 40
   21: aload_1
   22: aload_0
   23: aload_1
   24: getstatic #36; //Field scala/BigInt$.MODULE$:Lscala/BigInt$;
   27: iconst_1
   28: invokevirtual #40; //Method scala/BigInt$.int2bigInt:(I)Lscala/BigInt;
   31: invokevirtual #45; //Method scala/BigInt.$minus:(Lscala/BigInt;)Lscala/BigInt;
   34: invokevirtual #47; //Method factorial:(Lscala/BigInt;)Lscala/BigInt;
   37: invokevirtual #50; //Method scala/BigInt.$times:(Lscala/BigInt;)Lscala/BigInt;
   40: areturn

I know this looks scary if you have not used javap much, but if you have then you will recognize that this is a straightforward compilation. You can see the de-sugaring (try scalac -print for a better way to view the de-sugaring that the compiler performs) like the implicit conversions being made (#15 above) and the operators as method invocations (#31 and #37.) Especially important is that you can see the recursive call to factorial on #34, and then a call to BigInt.$times, i.e. multiplication for BigInts.

Now let's rewrite the method using Daniel's suggestions:

def factorial(n:BigInt):BigInt={
 def loop(n:BigInt, acc:BigInt):BigInt = if (n <= 0) acc else loop(n-1,acc*n)
 loop(n,1)
}

And now when we run javap, things are a lot different (make sure you use the -private flag with javap to get all of the details):

private final scala.BigInt loop$1(scala.BigInt, scala.BigInt);
  Code:
   0: aload_1
   1: getstatic #26; //Field scala/BigInt$.MODULE$:Lscala/BigInt$;
   4: iconst_0
   5: invokevirtual #30; //Method scala/BigInt$.int2bigInt:(I)Lscala/BigInt;
   8: invokevirtual #36; //Method scala/BigInt.$less$eq:(Lscala/BigInt;)Z
   11: ifeq 16
   14: aload_2
   15: areturn
   16: aload_1
   17: getstatic #26; //Field scala/BigInt$.MODULE$:Lscala/BigInt$;
   20: iconst_1
   21: invokevirtual #30; //Method scala/BigInt$.int2bigInt:(I)Lscala/BigInt;
   24: invokevirtual #40; //Method scala/BigInt.$minus:(Lscala/BigInt;)Lscala/BigInt;
   27: aload_2
   28: aload_1
   29: invokevirtual #43; //Method scala/BigInt.$times:(Lscala/BigInt;)Lscala/BigInt;
   32: astore_2
   33: astore_1
   34: goto 0

public scala.BigInt factorial(scala.BigInt);
  Code:
   0: aload_0
   1: aload_1
   2: getstatic #26; //Field scala/BigInt$.MODULE$:Lscala/BigInt$;
   5: iconst_1
   6: invokevirtual #30; //Method scala/BigInt$.int2bigInt:(I)Lscala/BigInt;
   9: invokespecial #51; //Method loop$1:(Lscala/BigInt;Lscala/BigInt;)Lscala/BigInt;
   12: areturn

At the bottom is the decompilation of the factorial function. Notice that it calls something called loop$1. That is the compiled version of the inner function loop. It is shown at the top of the decompiler output. The most important thing to notice here is the #34 -- the goto statement. This is a goto-loop. Notice that there is no recursive call back to the loop$1 inside the function, just as there is no call back to factorial inside the factorial function. The compiler removed the tail recursion and replaced it with a goto loop, just as Daniel said it would.

For more proof, you can run the code. On my MacBook, the original loop will blow up in a stack overflow when trying to calculate 60,000! I'm sure it blows up well before then, but you get the point. The optimized version of the code has no problems with 60,000! though it does take a while to calculate.

The one last mystery in all of this for me, goes back to my slides on Scala. In the slides, I used tail recursion as the reason why the factorial code ran faster in Scala than in Java. Clearly I was wrong. The code definitely ran faster on Scala, but I do not know why exactly. Perhaps javap can shine some light on this, too...

ActionScript Quickie: Check for Required Params

You ever need to test that a bunch of variables are not null/empty/true? Here is a quick and dirty way to do it in ActionScript 3.0:

private function validArgs(...args):Boolean{
 return args.every(function(arg:Object, ...crap):Boolean {
  return arg ? true : false; });
}

Usage:

var firstName:String = ...
var lastName:String = ...
var iq:int = ...
var friends:Array = ...
validArgs(firstName, lastName, iq > 100, friends.length);

Properties Survey

The object-oriented programming tenet of encapsulation can lead to some ugly looking code. Objects should not expose their internal state, but instead provide access through methods. The related ugliness is most commonly seen in the Java programming language:

public class User{
   private String name;

   public String getName(){
       return this.name;
   }

   public void setName(String name){
       this.name = name;
   }

   public static void main(String[] args){
       User user = new User();
       user.setName("Michael");
       System.out.println(user.getName());
   }
}

I suppose ugly is a subjective term. Perhaps verbose is the better term. Many other languages offer syntax that is simplified, but without losing encapsulation. For example, here is similar code in Ruby:

class User
   attr_accessor :name
   def name=(name)
       puts "setter called"
       @name = name
   end
end
user = User.new
user.name = "Michael" #setter called
puts user.name #Michael

In the above code, the getter and setter are both generated by the attr_accessor method. The syntax makes it seem like the internal state is exposed directly, but there really are methods being generated and invoked. To demonstrate this, I chose to override the setter and added in some extra code to let you know it had been called. Ruby is a very powerful language, and its meta-programming (i.e. code that writes more code for you, like the attr_accessor method above) are renowned. However, it is hardly the only language that does properties like this. Good 'ol Python can do it too:

class User(object):
   def getname(self):
       return self.__name
   def setname(self, name):
       print "setter called"
       self.__name = name
   name = property(getname, setname)

user = User()
user.name = "Michael" #setter called
print user.name #Michael

Not quite as succinct or as elegant as Ruby, but it works. Slick properties were added to Objective-C not too long ago as well:

@interface User:NSObject{
   NSString* name;
}
@property (copy) NSString* name;
@end

@implementation User

@synthesize name;

- (void) setName:(NSString *)name{
   [self.name autorelease];
   self.name = [name copy];
}
@end

The header file makes this more verbose, as well as the memory management. Objective-C has a garbage collector, but only for its desktop profile. You have to manually manage the memory if you are writing Objective-C for an iPhone application.

ActionScript 3.0, which is based on the now defunct EcmaScript 4.0 specification also has properties. The syntax is a little verbose

class Person{
  private var _name:String;
  public function get name(){
    return _name;
  }
  public function set name(name:String){
    trace("Setter called");
    _name = name;
  }
}

Note that you have to define both the get and set functions. This gives you the "dot syntax", i.e. you can do something like myPerson.name = "Michael". Scala is similar:

class Person{
  private var _name:String = null

  def name:String = _name
  def name_=(name:String){
    println("setter called")
    _name = name
  }
}

object App{
  def main(args:Array[String]){
    val person = new Person
    person.name = "Michael"
    println(person.name)
  }
}

Scala can generate the getter/setter for you, but you cannot override them. So if all I wanted was the default behavior, nothing extra, I coudl just do

class Person{
  var name:String=null
}

object App{
  def main(args:Array[String]){
    val person = new Person
    person.name = "Michael"
    println(person.name)
  }
}

There is no way to override the methods that Scala generates for you. Even if you subclass Person, you cannot alter the generated getter/setter methods.

The Java App Engine

One of the worst kept secrets in the tech world was revealed on Wednesday night when Google announced Java support on the Google App Engine. Everyone knew this was coming, but it was still very exciting news. Last night I went to a Google Technology User Group meeting where folks from Google went into more detail on GAE/J as some folks are calling it. Here are a few of my thoughts:

1.) First of all, kudos to Google for supporting a lot of the standards in Java. They did the same thing with Python on GAE, but there are a lot more standards to deal with in Java and those standards tend to be harder to implement.

2.) Also major props to Google for working so well with partners. They had big partners like IBM, but also smaller ones like ThoughtWorks. The ecosphere around GAE/J is off to a great start. Of course reaching out to partners is probably a big reason for the lack of secrecy about GAE/J, but it is certainly worth it.

3.) The Eclipse tooling is outstanding. I know some folks were a little dismayed that they would have to use Eclipse instead of IntelliJ or NetBeans, but what can you do? Eclipse is king, and the developer experience with the Google tools is second to none.

4.) Speaking of standards, support for JPA is great. So you can't do joins or aggregates, but did you really think you could or should be able to do that on GAE? After all, you have a non-relational store (BigTable) behind all of this.

5.) On the other hand, support for JDO is ... surprising and a little puzzling to say the least. Heck, I thought Gavin King put a wooden stake through the heart of that would-be standard a long time ago. At least you can eschew it in favor of a standard that people actually use (JPA.)

6.) No threading is not entirely suprising, but it lights the way to a bigger issue. The GAE road map has talked about task queues/background processing for awhile now. Google announced cron jobs this week as well, but those are limited to 30 seconds of execution time, only 10/day, and are schedule at a specific time. Here is another Java standard for you: JMS. I think GAE/J needs this, as well as some kind of thread pool (or substitute) for processing. BigTable (as a backing store for a queue) and cron tasks are not enough. Heck, even one of the App Engine success story/presenters talked about how they simulated (quite cleverly I might add) batch processing.

All Your Pages Are Belong To Us

Remember back when people realized that the Internet was a valuable way to reach customers and potential customers? You would see all of these television or print ads where they would print the URL of a website, or even radio ads would have somebody read the URL of a website. Oh wait, I guess this is still done a lot. Whatever, a while back this really became unnecessary. Whatever the name of your brand or product, you could just search for it in the search engine of your choice and find the same link that was being advertised. Who wants to try to remember a URL anyways?

Well the days of remembering a URL may be coming back, sort of. Earlier tonight I was watching UNC beat down Villanova. During a TV timeout, there was an ad for a movie. I honestly do not remember the name of the movie. At the end of the commercial, they put up a URL. Only this time the URL was something like http://www.facebook.com/name_of_movie. That's right, if you wanted to know more about this product, you needed to go inside the proverbial walled garden that is Facebook.

Now if you just searched for the name of this movie, would you get the link to the Facebook page? Maybe, but maybe not, or maybe it would depend on the search engine. Of course, if you were already on the Facebook site, and searched there, then you surely would find this page. So what does this mean? Do we need to start remember and typing in URLs? Or do we just need to do all of your search inside Facebook?

Statistically Useless

One of the nice things about living in the Bay Area is that we have a lot of major professional sports teams: two NFL teams, two MLB teams, one NBA team, and one NHL team. Never you mind that they all stink currently, except for the Sharks. With so many teams, sports radio is a lot of fun. Today I was listening to Fitz & Brooks as they fielded a question from a listener about the Golden State Warriors and their lack of defense. They made the case that the Warriors have a lot of defensive talent because they are 6th in the league in steals and 1st in the league in blocked shots. They argued that the Warriors just needed to allow less "blow-bys." I looked around, but could not find this statistic.

I was almost really impressed by Fitz & Brooks. It seemed like they were on the verge of saying "NBA statistics are meaningless" but they could not go that far. The NBA keeps a lot of statistics, but they really are mostly meaningless. Points, rebounds, assists, steals, blocks, etc. None of these are particularly good at determining if a player will make his team more or less likely to win a game. That is why you see guys like David Lee, Troy Murphy, Jose Calderon, and Mario Chalmers as statistical leaders. Look at the league leaders in blocks. Their teams are ranked 8th, 18th, 25th, 30th, and and 20th in the league in points per game. In terms of team field goal% allowed, the ranks are 3rd, 4th, 25th, 23rd, and 19th.

The NBA is hardly the exception. Most sports have a lot of meaningless (from the standpoint of predicting team success) statistics. Baseball has terrible stats like batting average, runs batted in, stolen bases, and fielding percentage. Football is not quite as bad mostly just because there are less stats. Still things like rushing touchdowns and even passing yards are pretty worthless.

Of course baseball has seen a statistical renaissance and it is known as sabremetrics. Michael Lewis's Moneyball is a popular work that discusses the value of sabremetrics. It uses the success of the Oakland A's and their GM Billy Beane as proof, but if it was written today, then the success of the Boston Red Sox would be (more?) compelling. Lewis expanded this "nerdy numbers leading to unexpected success" plot to basketball recently by writing an article about the Houston Rockets' Shane Battier. Basketball is tougher sport to measure though. Maybe there will be sabremetrics in basketball eventually, who knows.

It was definitely easier in baseball, where some of the statistical ingredients for more meaningful sabremetrics were already measured (like number of walks, total bases, etc.) What would similar stats in basketball be? Certainly making shots is good, missing shots is bad. How do you measure a three point play vs. a three point field goal? If a player takes a shot and misses, but somebody else gets an offensive rebound and an easy field goal, how is this measured?