a+bi

A new version of dwm has been released so I have updated the Fibonacci spiral patch. I’m still working on the movestack patch. The updated dwm patch can be found here. I have also created a Fibonacci layout patch for dvtm – the dynamic virtual terminal manager. The dvtm patch can be found here.

In order to install an Android Application onto the emulator or the phone you must first cryptographically sign it. When you do a debug build (using “ant debug”) ant will automatically sign the binary with an auto-generated debug key.

This key is set to expire 365 days after it was auto-generated (the first time you did a debug build). If a debug build fails due to an expired key, you simply need to delete the current debug key and a new one will be auto-generated. To do this, navigate to where the debug key is located and delete it. On Linux and Mac OS X this is ~/.android and the key is the file “debug.keystore”.

Signing your application with a debug key is fine for testing purposes but for release the application should be signed with a unique key that you have generated just for that purpose. If you plan on release the application on the Android Market then the key should also contain correct identifying information (your name or company) and should expire no earlier than October 22, 2033.

To generate a key you need to have the keytool application that come with Java. You need to specify the key-store (the file name), the alias for the key, which algorithm to use (we want RSA) and how long it should be valid for. Let’s create a key stored in the file “release.keystore” with the alias “release” that will be valid for 10,000 days:

niki@redblacktree:~/.android$ keytool -genkey -v -key-store release.keystore -alias release -keyalg RSA -validity 10000

Keytool will then ask you a bunch of questions:

Enter keystore password:
Re-enter new password:
What is your first and last name?
[Unknown]: Niki Yoshiuchi
What is the name of your organizational unit?
[Unknown]: aplusbi
What is the name of your organization?
[Unknown]: aplusbi
What is the name of your City or Locality?
[Unknown]: New York
What is the name of your State or Province?
[Unknown]: NY
What is the two-letter country code for this unit?
[Unknown]: US
Is CN=Niki Yoshiuchi, OU=aplusbi, O=aplusbi, L=New York, ST=NY, C=US correct?
[no]: y

Generating 1,024 bit RSA key pair and self-signed certificate (SHA1withRSA) with a validity of 10,000 days
for: CN=Niki Yoshiuchi, OU=aplusbi, O=aplusbi, L=New York, ST=NY, C=US
Enter key password for
(RETURN if same as keystore password):
[Storing release.keystore]

And you’re done! You’ll notice that I ran keytool out of the ~/.android directory so that release.keystore is located in the same place as debug.keystore.

Now onto signing applications. Let’s go back to our Hello Android project and do a release build:

niki@redblacktree:~/projects/android/hello$ ant release

Once this has finished there should be a new apk located in the bin directory called “HelloAndroid-unsigned.apk”. We need to sign it with the key we created earlier using jarsigner:

niki@redblacktree:~/projects/android/hello$ jarsigner -keystore ~/.android/release.keystore HelloAndroid-unsigned.apk release

And now “HelloAndroid-unsigned.apk” has been signed. It can now be installed using adb.

Android’s developer guide has a section on Developing in other IDEs for those who don’t want to use Eclipse. However the documentation leaves out a few details and all of the examples use Eclipse with perhaps a token paragraph discussing the CLI. The rest of this post will assume that you have already installed the SDK and properly configured it (added the SDK to your path and installed the appropriate SDK components).

The first thing to do is to figure out which version of Android you want to target. Version 1.6 (aka – “Donut”) is a pretty good lowest-common-denominator. Using the Android tool we will figure out the ID for 1.6:

niki@redblacktree:~$ android list targets

Which will give you a list of all the targets available (this depends on which SDK components you have added). My output looks like this:

Available Android targets:
id: 1 or "android-3"
Name: Android 1.5
Type: Platform
API level: 3
Revision: 1
Skins: QVGA-L, QVGA-P, HVGA (default), HVGA-P, HVGA-L
id: 2 or "android-4"
Name: Android 1.6
Type: Platform
API level: 4
Revision: 1
Skins: WVGA854, QVGA, HVGA (default), WVGA800
id: 3 or "android-7"
Name: Android 2.1
Type: Platform
API level: 7
Revision: 1
Skins: WVGA854, WQVGA400, QVGA, HVGA (default), WVGA800, WQVGA432

The target ID for version 1.6 is 2. Knowing that, let’s set up an Android Virtual Device (AVD) for our emulator using the android tool, specifying the target with the –target option and giving it a name with the –name option. We will use the default hardware configuration:

niki@redblacktree:~$ android create avd --name donut
Android 1.6 is a basic Android platform.
Do you wish to create a custom hardware profile [no]
Created AVD 'test' based on Android 1.6, with the following hardware config:
hw.lcd.density=160


Finally, let’s setup a project. Again well use the android tool, this time to create a new project. I’m going to create the project in the directory ~/projects/android/hello:

niki@redblacktree:~/projects/android/hello$ android create project --name HelloAndroid --activity HelloAndroid --path ./ --package com.examples.helloandroid --target 2

This will create a new project in the current directory (–path ./) with the name “HelloAndroid” (–name HelloAndroid). It will be targeted towards Android 1.6 (–target 2). It will create a Java source file containing an Activity “HelloAndroid” (–activity HelloAndroid) and will be in the namespace “com.examples.helloandroid” (–package com.examples.helloandroid).

We can now use Apache Ant to build our project:

niki@redblacktree:~/projects/android/hello$ ant debug

This will build a debug version of our project and place the “HelloAndroid-debug.apk” in the bin directory. This application has been signed using a default debug key and is ready to be installed on a device. To do that, let’s fire up the emulator, using the virtual device we created earlier:

niki@redblacktree:~$ emulator -avd donut

Once the emulator has finished booting, we can get a list of attached devices using the Android Debug Bridge or adb:

niki@redblacktree:~/projects/android/hello$ adb devices
List of devices attached
emulator-5554 device


If there is only one device attached, then you can install the application using ant:

niki@redblacktree:~/projects/android/hello$ ant install

Which will automatically remove any previous versions installed on the device and install the current build. Alternatively you can use adb to install the application:

niki@redblacktree:~/projects/android/hello$ adb install bin/HelloAndroid-debug.apk

This will fail, however, if you have already installed a previous version of the application on the device. If that is the case, you need to uninstall it first:

niki@redblacktree:~/projects/android/hello$ adb uninstall com.examples.helloandroid

Note that you must specify the application by the name of its package.

Finally if you have more than one device attached, (say, a phone and an emulator) then you must specify which device (using the name returned from adb devices) using -s:

niki@redblacktree:~/projects/android/hello$ adb -s emulator-5554 install bin/HelloAndroid-debug.apk

Now you can just navigate to the application on the emulator or on your phone and run it! You’ll notice by default it says “Hello World, HelloAndroid!”

That’s the basics of setting up, building and running an application using the CLI instead of eclipse. In the next post I’ll go over release builds and signing your applications.

I have owned an Android-based phone (the G1) for awhile now and have been meaning to develop applications for it since day one. I have finally gotten around to learning how. So far it hasn’t been easy for me: I don’t know Java and I don’t use Eclipse which are the primary development tools for Android.

Fortunately Google released the Android NDK, or Native Development Kit which can be used to program applications in C or C++ and be compiled for the ARM architecture. This introduces new complexities however. The NDK still requires some Java as the compiled code is executed using JNI. In other words I still need to learn a minimal amount of Java and learn how to interface it with native code.

Finally, most of the information online assumes the use of Eclipse. Google provides some tools for creating ant build files but I have found the documentation to be lacking a bit. Through some trial and error I have figured out how to compile the NDK samples and in my next post will present a tutorial for doing so.

Topics so far:
* Creating an Android project from the Command Line
* Signing Android applications

A game that I worked on during my time at Powerhead Games was just released: Glow Artisan! It’s a puzzle game for the Nintendo DSi and it is quite addictive. It has already received a number of glowing (groan) reviews:

Nitendo Life 9/10
Game Set Watch

If you have a DSi I highly recommend forking over the $5 to buy it.

After becoming increasingly fed up with Ubuntu I decided to reinstall Debian. I had used Debian for a number of years but eventually left it in favor of Ubuntu as I initially saw Ubuntu as Debian with more complete repositories. At first Ubuntu was quite promising however as I diverged from the default install I became annoyed at some of the idiosyncrasies of the system. After attempting to upgrade from Hardy to Intrepid (which requires a graphical installer – and all the directions/tutorials I found online assume you are using gnome/xfce/kde) I realized that what I really wanted was Debian with some additional external repositories.

In the process of setting up my system I decided to update dwm to the latest version (5.6.1). There have been some significant changes to dwm since 5.2 including better multi-head support. Even though I’m not currently using a multi-head system the changes affected my patches and they needed updating. The new diff files can be found on the dwm projects page.

I have added a new project to the projects page: Prime number storage. When I was in college a friend of mine and I came up with a method for compressing and storing prime numbers. While doing research on our method we discovered that it was already in use.

However I recently decided to implement it anyway, as it was (and still is) interesting to me.

Last night I watched the movie 21, based on the book Bringing Down the House, about the MIT blackjack team. There is a scene in the movie in which math professor Mickey Rosa poses the Monty Hall problem to a student, Ben Campbell. Predictably enough Ben is able to figure out the correct strategy and realizes that switching doors yields a 2/3s probability of winning the car (which is roughly the same chance you’ll predict the entire plot of the movie within five minutes). The problem is, he’s wrong.

At first the error is subtle. There is not enough information about the behavior of the host to determine whether the best strategy is to switch or not. The problem is not constrained enough. This is made glaringly obvious when Mickey Rosa asks “how do you know he’s not trying to play a trick on you?” If there is the possibility that the host is trying to play a trick on you, then there is the possibility that the host only allows you to switch if you have already chosen the car. In that case, switching doors would result in a 0% chance of winning the car.

Only when you constrain the problem does it make sense to switch doors. If (and only if) the host always opens a door, the door always reveals a goat, and the host always offers the player the option of switching does switching result in winning the car 2/3s of the time. Wikipedia has a good analysis of this constrained version using Bayesian products. (The short answer, the host is essentially giving you the option of switching from your initial choice of one door, to the two remaining doors and if the car is behind one of those two, you win).

Of course if the host only gives you the option to switch when you’ve chosen the car it won’t take long for people to catch on, and everyone will win all the time. It makes more sense for the host to offer a switch when you’ve selected the car with probability p, and offer a switch when you’ve selected a goat with probability q. Thus the host opens the door with probability: .

Borrowing from the analysis on the wikipedia page, we see that:

We can now use this new piecewise function to determine the probability of winning the car by switching:

So:

If we let p = 1 and q = 1 (in other words, the host always opens a door) then the probability of winning the car by switching is 2/3s, which is what we should expect.

Update:
It makes the most sense for the host to always offer the switch when you’ve chosen the car (p=1), and to offer the switch when you’ve selected the goat with probability q. By solving the inequality:

We find that we should switch when q > 1/2.

I first tried to learn OCaml after hearing about it in my Programming Languages course in college. I didn’t get very far beyond the basics at the time for a variety of reasons involving both the language itself and the resources available to me. The problems I had that did not involve the language were not unique to OCaml (except perhaps the lack of available learning material) and were not particularly exceptional. The problems I had understanding the language however were, and the worst offender was without a doubt the semi-colon.

I had a lot of trouble understanding when to use semi-colons and when I needed one of them or two. I’m pretty sure my difficulty with this was not unique either. It seems to me that very few OCaml tutorials or books go into enough detail with this…err…detail and leave it as an exercise for the reader.

Ultimately the problem comes down to the difference between statements and expressions and their relationship to OCaml. There are a few different definitions of both statements and expressions, so for the sake of this post statements are going to refer to stand-alone elements of a programming language that do not return values (that is, they are evaluated solely for their side-effects) and expressions are combinations of values, variables, functions, etc . that are evaluated and return a value.

In an imperative language like C it’s easy to see the difference between the two. An assignment is a statement, an operation is an expression. It follows from this that statements can contain expressions (such as assigning a variable to the result of an operation) and that expressions can also contain expressions (chaining together operators or using the result of a function as the argument to another).

With OCaml it’s not so easy at first. OCaml is a multi-paradigm language and one of those paradigms is imperative programming. A lot of its syntax resembles the syntax of imperative languages like C, but it does not behave like an imperative language. In OCaml there are no statements. Everything is an expression. Everything has a return value. Sometimes that return value is of type unit (as in the case of assignment to a reference). For example, and if…else block in C does not return a value. However in OCaml it does – it’s value is the last expression evaluated within the block. This is why the value of the expressions in both the if and the else block much have the same type.

This brings us back to the semi-colon. The single semi-colon is an operator that behaves similarly to the comma operator in C. It evaluates the expression on the left side of the semi-colon, then evaluates the expression on the right side of the semi-colon and returns the result of the right-side expression (effectively ignoring the value of the left-side expression). So (a;b) would evaluate to b. Since the left-side value is ignored, this is only useful when the left-side produces side-effects (the corollary being that side-effect free OCaml programs shouldn’t use the semi-colon operator).

The only book I’ve seen this in is A Concise Introduction to OCaml which I unfortunately did not come across during my first attempt at learning the language.

A few months ago I was having a discussion with a few friends of mine and the subject of social awkwardness as it applies to telephone conversations arose. I am in many ways a stereotypical nerd and I am no stranger to social awkwardness. I have grown out of the worst of it, but telephone calls are still difficult for me.

One of my friends could not believe that anyone could have trouble making a phone call or talking to someone on the phone. At the time he worked in tech support and answered phones for a living. It came very naturally to him and he had trouble believing that he had some special skill that made him good at his job.

Eventually I came to realize how his attitude mirrored my own, albeit about entirely different subjects. I often have trouble understanding how some people are unable to understand basic logic or simple math. It’s frustrating to encounter an otherwise intelligent person who barely understand a concept as simple as say, division. There are certain skills that I possess that are “innate” (I don’t know if it’s genetic or environmental but it doesn’t matter either way) and that I take for granted. These skills are so simple for me that I have to fight the temptation to write off as stupid people who have difficulty with the same tasks.

I call this the “pocketknife paradox” – I have a lock-back pocketknife that I typically carry on me. I have observed that somewhere around half (and I believe it to be greater than half) of the people that I have lent it to are unable to figure out how to close it. The mechanism to lock the knife in the open position is so intuitive to me that I forget that many people don’t observe things the same way I do.