Real World Academia

Android development on Ubuntu 11.10 Oneiric

2011-12-20T23:23:00.002-07:00

I decided to play around with Android development but I had a hard time finding good instructions on how to set up the Android development environment on Ubuntu 11.10. With a little trial and error I've figured it out. I'm posting my notes in hopes that they will be useful to me in the future and possibly to others also. The aren't a complete step-by-step guide and they assume you're comfortable with the Linux command line, but hopefully they'll be useful.

Download and untar/gzip the Android SDK
Install the JRE

sudo apt-get install icedtea6-plugin openjdk-6-jre openjdk-6-jdk ia32-libs

Install ant

sudo apt-get install ant

Set your JAVA_HOME and CLASSPATH

export JAVA_HOME=/usr/lib/jvm/java-6-openjdk
export CLASSPATH=/usr/lib/jvm/java-6-openjdk/lib

Update the build tools

cd android*; ./tools/android update sdk --no-ui

Download eclipse (Helios release) (Note the one in the Ubuntu repositories doesn't seem to work)

google-chrome www.eclipse.org/downloads/

Untar eclipse

tar -xvf ./eclipse*.tar.gz

Install the eclipse Android plugin

eclipse : Help -> Install New Software ...
enter: "Android Plugin"
enter: "https://dl-ssl.google.com/android/eclipse/"
Select 'Developer Tools'
Click "Next"

Restart eclipse
Select the Android SDK

At this point you should have the Android SDK and eclipse installed and configured for Android development.

Here are some notes on doing Android development if you prefer to live on the command line instead of living in eclipse.

Create and Android Emulator

cd android*; ./tools/android -> Tools -> Manage AVDs

Start the Android Emulator

cd android*; ./tools/emulator -avd

Create a new Android project

cd android*; /tools/android create project --target android-14 --name HelloAndroid --path ../HelloAndroid.git --activity HelloAndroidActivity --package com.mydomain.helloandroid

Compile your project

cd ../HelloAndroid.git; ant debug

Push your project onto your running Android emulator

ant debug install

Why you should get a college degree

2011-08-23T22:48:00.000-06:00

Introduction
I've been thinking about why it's important to get a college degree for many years and have finally decided to write down why I think it's important. I've heard many arguments over the years both for and against college. I'll try and address those arguments here. I should point out that my arguments may only apply to those going into a technical field (Computer Science, Electrical Engineering, Mechanical Engineering), but many of the arguments may apply to non-technical fields. Since I don't fully understand these fields, nor do I fully understand the college experience for non-technical degrees, I am likely not qualified to discuss the related benefits or costs.

Background
Since many of my arguments will be based on empirical evidence, I believe my personal background is relevant. My career goals have been to be a Software Engineer. Computer Programming has been a long hobby and passion of mine. I started working as a Computer Programmer before I started college. Since I was working in my desired field, I didn't think that college would be that important. I did, however, decide to get my bachelors degree as career insurance in case I later needed or wanted to change careers. At the time, I didn't think there would be much educational benefit (I felt I already had many of the skills and knowledge that I would need for my career), but it seemed like a good idea. Many of the advanced CS courses I took showed me that I did have a lot to learn from college and I continue to use the knowledge I gained from my undergraduate studies at work.

A few years after getting my bachelors degree, I decided to go back to get my Masters Degree. Graduate school was more of a hobby than a career advancement strategy. I enjoyed reading papers and learning new things, and I wanted to get experience doing academic research and writing academic papers on my research. Just like with my Bachelors degree, I've been pleasantly surprised at how much I've learned while getting my Masters Degree. I've now graduated, and since my school work is done, I have had a lot of time to review my schooling and to think of the costs and benefits of my undergraduate and graduate work.

Addressing the Myths
Over the years I have heard repeated many arguments against college which I simply don't believe are valid. Here are the common myths that I've heard along with my counter argument.

1. A degree is just a piece of paper
This is simply not true. A degree is a certification from an educational institution that you have successfully completed an academic program. A degree is intangible, a diploma is tangible and is typically a piece of high quality paper.

2. A diploma is just a piece of paper

This is true, but the diploma is not really the goal of going to college. The diploma is a token that represents something of greater value. The diploma is nothing more than a certificate to show you have a degree. The concept of a token that represents something of value is not only limited to college diplomas. Cash, paychecks, car and house titles are all just pieces of paper, but their value is much greater than the cost of the paper that they're printed on. There is also a greater probability that you will be able to obtain the later pieces of paper such as cash, titles, paychecks if you have first obtained the first piece of paper a diploma.

3. Just because you have a degree doesn't mean you're smart.
This is certainly true. I have met and interviewed many degreed Software Engineers who managed to make it through college without retaining much of what they studied. Many of these unqualified Software Engineers were even able to pass their classes with good grades. So, I completely agree that the process of getting a degree will not guarantee competence. I have also met and interviewed non-degreed Software Engineers who were also incompetent and unqualified. So if a degree does not guarantee competence then why bother getting a degree? The answer is that a degree can help you become more competent, and therefore, a degreed individual is much more likely to be competent. My experience in talking and interviewing Software Engineers leads me to believe that there are a higher percentage of degreed Software Engineering that are competent than there are non-degreed Software Engineers that are competent. Just like safe driving habits won't guarantee you won't die in an auto accident a degree won't guarantee you'll be competent, but both will increase the likelihood of safety and competency respectively.

4. I don't have a degree, and I'm smarter than those that do.
This is entirely possible. As I mentioned before, I've met non-degreed Software Engineers who surpassed the average degreed counterparts in ability and competency. I do, however, think that this scenario is rare and unlikely. Of the non-degreed Software Engineers that I've known and interviewed, I have observed that there are many more who had an exaggerated perception of their abilities then those who's abilities we're above the average degreed Software Engineer. The idea that there are a lot non-degreed Software Engineers who erroneously think they are extra competent should not come as a surprise to those that are familiar with illusory superiority where people tend to overestimate their abilities or the Dunning-Kruger effect where the least competent tend to overestimate their abilities the most. If college degrees do in fact increase competency, then it would be expected that non-degreed individuals would not only be less competent, but would also not have the knowledge required to grasp the depth of their incompetence.

5. College is a waste of money. They don't teach anything that you can't learn on your own.
While I agree that college doesn't teach you anything that you can't learn on your own. I do not think that it is a waste of money. I believe that college provides several benefits over self learning. Namely:

A. Access to experts. Many of my classes were taught by professors who were considered experts in their fields. They kept up to date on the latest research and technology and shared that with their students. I remember discussing with a professor at the University of Utah an idea that I had for a research project for my Masters Thesis. He not only was able to quickly point out that my research topic had already been fully explored about 10 years earlier (a fact that I was not able to discover on my own despite several internet searches), he was also able to point me to that research. If I didn't have access to this professor, I would have spent a lot of time gaining knowledge that could have been gained in much less time by reading a handful of academic papers. This professor helped me to focus my research on areas that had not already been extensively explored.
B. Immediate feedback. More that once I've done an assignment, taken a test, or participated in a class lecture thinking that I fully understood a subject, only to find out the next week when the graded work was returned that I didn't. If you study on your own you may likewise misunderstand a topic, but you may not get the feedback that you need.
C. A well rounded curriculum. Both my Masters and Bachelors degrees surprised me at not only the depth of learning that I received but also the breadth. I think it would be possible (although much more difficult) for me to learn those topics on my own, but I'm less confident I would have known that some of those topics even existed or that they were important. I didn't know what I didn't know. It is impossible to study a topic that you don't know exists. A good example of this is big-O notation. Many un-degreed Computer Scientists have never heard of big-O notation or have shallow or incorrect understanding of what it is. In my job we use it all the time, if you don't know what it is you'll be left behind in the conversation or you'll require us to stop work and teach you about the topic (at work we pay you to be effective, we don't want to pay you to get an education). It's not a terribly difficult topic, but you won't learn it if you don't know it exists, and it's easy to get confused about what it really means. A good degree in Computer Science will guarantee the exposure to the topic and a good professor will give ample feedback to ensure a proper understanding.
D. Access to equipment and technologies. Somethings you just can't learn (adequately) from books. You need to get you hands dirty and work with it. Many of these equipment and technologies are out of the price range for many people. Colleges can provide access to these technologies at a cheaper cost than if you purchased all the technologies on your own.

6. But if you did learn it all on your own and you are competent why don't employers just interview you so you can prove that you're qualified? They could but interviewing is expensive. I believe the right way to interview for a technical position is to have your most qualified employees ask candidates technical questions. This process is likely to result in hiring a qualified candidate. First of all, your most qualified employees are also likely your highest paid employees, so you're paying them a lot of money to interview. They are also likely to be overworked as they can perform the most tasks (hence the most qualified) and if they weren't overworked you wouldn't be hiring. If you interview every candidate you will spend a lot of money paying your existing employees to interview and it is likely that your employees will get tired of interviewing and they may leave for another job where they can do real work and not perform job interviews. Because interviewing is expensive you must be selective with who you interview, so it makes sense to only interview those candidates that are most likely to be qualified. In my experience degrees individuals are most likely to be qualified and so it may make good business sense to toss the resumes of the candidates that don't have degrees. An obvious exception to this rule is if you simply do not have enough candidates, in which case, you may end up interviewing all candidates, but you should start with those who are most likely to be qualified first.

7. What about professors who live in their ivory towers and know nothing about the real world? This is a common criticism about professors, and one that I've probably uttered a time or two. Such professors do exist, but I've found that often what they teach isn't applicable to today's real world problems but it often becomes applicable in the future. I remember learning about closures while working on my Bachelors degree. At the time I didn't think I'd ever use them as C/C++ Java ruled the industry. Since then Perl, Python, Ruby, JavaScript, Google Go have all become more predominant and all support closures. Even C++ recently added support for lambdas which in C++ are close to full grown closures. Had I ignored this topic, I would have had a more difficult time learning these languages and taking advantage of the power of closures. Additionally many of the students that are complaining about ivory tower professor do not have any real experience in the "real world" either. They are college students, who haven't spent a lot of time working in the "real wold," and, therefore, likely unqualified to determine what knowledge will have real world significance.

Conclusion

While I don't think college is perfect, I do believe the vast majority of people entering technical fields would greatly benefit from obtaining a college degree. I've talked to many who don't have degrees who feel that they aren't useful, but very few who have earned a technical degree who question the benefit. If there are additional augments against earning a college degree in a technical field that I haven't addressed, I would love to hear them.

Using gnuplot to make simple line graphs.

2011-07-14T15:31:00.000-06:00

Gnu plot is an amazing tool. It's great for generating quick plots from bash. I've had my programs generate statistical data and then thrown it into gnuplot so I can better understand how my program is behaving. Unfortunately every time I use it I end up having to go back to the web to relearn the basic syntax of creating a line graph. I'm going to try and save myself some time by documenting the basic usage here.

To draw a simple line graph first place the points to draw in a separate file in this case named "gnuplot.data"

Now create the gnuplot script:

The pause line at the end keeps the gnuplot from flashing the graph and then immediately exiting. When you execute gnuplot you'll see the following:

There is a ton more you can do with gnuplot like generate png files, create different types of graphs, but I've found that as a simple programming tool this gets me 90% there. For more information checkout the gnuplot homepage. Happy plotting

Test Second Development

2011-06-08T21:44:00.000-06:00

Let me start off by stating that I'm a big fan of test-first development. I think that a (the?) major benefit of writing unit-tests is the fact that the first person to use a new API is the developer herself/himself. By first writing tests against the API before it has written you increase the likely hood of creating a unable, testable and bug free code. Test-first development is valuable even if you never ran any of the unit-tests that you wrote. The purpose of this post is not to extol the virtues of test-first development but to share a scenario where I feel it may be better to not write the unit-tests right away.

Several weeks ago I started to work on a simple command line utility. Nothing fancy but just something to scratch an itch that I've had for a while. I had a vague idea of what I wanted it to do but hadn't quite worked out all of the details. Additionally I wasn't sure how the utility would involve. Finally I was writing the utility in Google Go, which I have done a bit of development but I certainly haven't played with it long enough to fully think in the language. In short I simply didn't know what I was doing and I knew it would be some time before I fully understood the problem I was trying to solve. I started to write the code and neglected to start by writing unit-tests. After some time of hacking on the utility I finally got to the point where I had a working prototype and I finally understood the problem. At that point I reviewed the code of my program and I realized that I had (not surprisingly) got the architecture of the program wrong. I figured out the right architecture of the program and started on the refactor. During the refactor the majority of the original code and internal API's was radically changed. If I had written any unit-tests they would have been discarded as the code and API's they would have tested simply did not exist in the refactored program. I could have preserved end-to-end tests but not any unit-tests. During the refactor I wrote unit-tests and I now have a program that has good unit-test coverage. I'll call this development process "Test Second Development". I'd like to propose the following criteria for when test-second development may be appropriate.

You don't understand the program you are writing.
You don't understand the language you are writing the program in.
You will have the luxury of refactoring the program once you understand it, and before it "ships".
You're disciplined enough to write unit-tests when you do your rewrite/refactor.

In other words I think it may be OK to delay writing unit-test when you are writing a true *prototype.

My thoughts on test-second development are still immature and evolving, but I thought I'd jot them down for future reference. In my case I don't think that I would have gained any benefit to using test-first development and I can definitely see how test-first development would have slowed down the discovery process.

* If you are writing code for your job and anyone else will know about your project, then I really doubt you will ever write a prototype. As soon as someone sees or hears about your project they'll want to ship it. I once worked for a company that shipped a simple utility that I had written to aid in testing my code. I only found out that they had shipped it after my manager came and talked with me about the utility and told me that I needed to pretty up the GUI. When I told him that it was a testing utility and was never meant to be shipped he told me that since it was shipped we'd have to support it. I started prettying up the GUI and started on a new testing utility. The new testing utility had a big banner across the front stating that it was for internal testing only. I later learned that calling testing tools something like "The enema tester" was a good strategy for ensuring that internal testing tools never got shipped.

Cross Compiling Google Go Code

2011-04-23T21:23:00.000-06:00

This is more of a note to self, so I can look up this information in the future as needed. Google Go makes it really easy to cross-compile. Here is how you an compile your Go project for another architecture. The first step is to compile the cross compiling compilers (I can't believe I just typed that). So lets checkout the source code for the go compiler.

hg clone -r release https://go.googlecode.com/hg/ go

Now to compile the Go compiler for the architecture of your machine, simply cd into the go/src directory and run the all.bash script

cd go/src; ./all.bash

If you want to create compilers for a different architecture you set the GOARCH environment variable and then run the make.bash script.

GOARCH=arm ./make.bash

GOARCH=386 ./make.bash

GOARCH=amd64 ./make.bash

The all.bash script compiles the compiler and runs the unit tests, the make.bash script just compiles the compilers.

This will create separate compilers, linkers and assemblers for each of the three architectures. Because each compiler, linker and assembler have a different name you can have support all architectures simultaneously.

Once you have the Go compilers compiled you can now compile your project for different architectures by creating a Go Makefile and setting the GOARCH environment variable before typing make.

GOARCH=arm make

GOARCH=386 make

GOARCH=amd64 make

That's it! You can now cross compile your Go code. More information on the Go compilers, creating a Go Makefile and getting started with Go can be found here, here, and here respectively. Happy Hacking!

I'm back

2011-04-22T21:17:00.000-06:00

Last year I decided that it was time to finish up my Masters degree. I recognized that in order to finish in a timely manner I would need to forgo all hobbies for a while and so this blog has been on hold. I'm now done, or at least I'm at the stage where I'm waiting for the final announcement that I'm done and so I'm now returning to normal life. After having dropped out more than a year ago I'm finding that it's taking some time to get adjusted to normal non-academic life. I'm also slowly starting to remember all the non-homework activities that I used to participate in. I wonder how long it will be before I become as busy as I was before.

Developer Etiquette

2010-03-16T22:41:00.000-06:00

I created a list of etiquette guidelines for Software Engineers. These etiquette guidelines are not for social interactions, but are instead for writing code. Like most etiquette guidelines these are designed to minimize the discomfort for others. So here they are.

Before committing I will:

Review the patch.
Review the list of files that are not being committed, but have been modified or are new.
Compile the code.
Run any affected unit-tests.
Test the code to make sure it does not break core functionality.

The reason behind #1 is simple. It's very easy to accidentally commit code that's not ready, or that contains printf debug code. It's quite obnoxious to have your terminal sprayed with hundreds of "XXX Hey I'm executing function foo()." By following guideline number #1 you will rarely accidentally commit half-baked code. The git add --patch command makes this really easy.

Guideline #2 saves you from forgetting to commit some critical patch, or more commonly forgetting to add a new file to the repository. I've found that most of the time when code compiles on the developer's computer but not anyone else's, it's because they forgot to add a file. The git status command helps here.

Guideline #3 is simple. Committing code that doesn't compile turns a O(1) problem into a O(n) where n is the number of developers on your team. Don't ever check in code that doesn't compile.

Guideline #4 ensures that you don't accidentally break the unit-tests. It is much easier to fix bugs earlier rather than later. So if you break the tests it's better to find out before you commit.

Guideline #5 is similar to #4 but assumes that not all of your code is covered by unit-tests. Even if you test every line of code with unit-tests, your unit-tests won't tell you that you just made your GUI look like puke. So run the code and make sure nothing broke.

If you follow these guidelines you can still write horribly broken code and be a terrible developer, but at least you won't prevent your co-workers from being competent.

Easy to Use

2010-01-20T22:42:00.001-07:00

I've noticed that when choosing a tool for software development one of the criteria that's often proposed is the tool should be "easy to use". While I agree that ease of use should be a criteria for choosing a tool I've come to realize that I have a different opinion on what "easy to use" means than others. When I say a tool is "easy to use" I mean it literally. A tool that is easy to use should make it really easy for me to do what I want. Here are some of the development tools that I use that I consider easy to use:

vim
git
The command line (bash)

All three of these tools let me do my job as quickly and painlessly as possible. If you asked others for a list of similar tools that are easy to use you may get the following:

notepad
svn
GUI's

By my definition the above tools are not easier to use than my list (they don't allow me to do my job as quickly or painlessly) but they are easier to learn. I'm not sure if easy to learn and easy to use must be mutually exclusive but I can't think of any tools that I use frequently that have both qualities. There is nothing wrong with choosing a tool that's easier to learn over one that's easier to use as long as you use the tool infrequently. Investing years to fully learn vim is a waste of time if you only edit text files for a few minutes every month. If your going to use a tool frequently over a long period of time then you should spend the time to learn the tool that's easy to use even if it isn't easy to learn.

Recursion and Inductive Proofs

2010-01-05T21:34:00.000-07:00

I've discovered that programmers frequently stumble when writing recursive algorithms. There are some simple rules that programmers can steal from mathematics to make writing recursive algorithms easy. I should point out that I'm only talking about writing recursive algorithms for interacting with recursive data-structures (lists, trees, etc.). Let's get started by reviewing some basic steps for proving a statement holds for all natural numbers n using an inductive proof.

Base case: Show the statement holds for a value of n (usually n=1 or n=0).
Inductive step: Assuming the statement holds for any value of n then show it also holds for a value of n+1

Rule 2.5 would be to make sure that the inductive step reduces the problem space. Using a base case of n=0 and then and inductive step of n-1 wouldn't be a valid proof because the inductive step does not really reduce the problem space (remember we're talking about natural numbers for this example). So let's use an inductive proof to show that 0+1+2...n=(n(n+1))/2.

Base case: Show the statement holds for n=0

0=0(0+1)/2

This equation clearly holds.

Inductive step: Assuming the statement holds for any value of n then show it will also hold for n+1.

0+1+2...n+(n+1) = ((n+1)((n+1)+1)/2

If we assume that the statement holds for n then we can reduce the expression.

(n(n+1))/2 + (n+1) = ((n+1)((n+1)+1)/2

Using some basic algebra we can reduce both sides and discover that the inductive step holds.

Now we can apply same (perhaps slightly tweaked) rules to writing a recursive algorithm for finding the length of a linked-list (a recursive data-structure).

Let's start out with the function signature.

int length(Node *node)
{
  // Do stuff here
}

Base case: Write the algorithm for n=0 (the linked-list with 0 nodes).

int length(Node *node)
{
  if (NULL == node)
  {
    return 0;
  }
  // Do more stuff here
}

Congratulations! If you've make it this far you're above average. You've solved the base case without dumping core.

Now onto the inductive step: Assume that your length function will work for lists of length n now write code to make it work for lists of length n + 1.

int length(Node *node)
{
  if (NULL == node)
  {
    return 0;
  }
  else
  {
    return 1 + length(node->next);
  }
}

Notice that if we assume that "length(...)" works for lists of length n then for lists of length n + 1 all we need to do is add 1 to the length. You should also notice that we passed node->next to the "length(...)" function not just node because rule 2.5 states that the inductive step must reduce the problem space and just passing node would not reduce the problem space. Congratulations! If you've make it this far you're now well above average. Now not only will your algorithm not core dump, but it won't hang either.

So let's review what we've done. We've used the rules for inductive proofs to guide us in writing a recursive algorithm. Does this mean we've proved that this algorithm is correct? The answer is, not really or at least, not formally. Even though we haven't proved this algorithm is correct we can be much more confident that it will work.

If we were to write unit-tests for this algorithm (which you should *always* do before writing the algorithm) we could use the rules of induction to guide our unit tests. We could write a test for testing the base case and another test for testing the inductive case.

Since math has been around longer than computers, it makes sense that we could borrow a few ideas from it to make our jobs easier.

Google's Go trying to be too clever.

2009-11-27T22:27:00.000-07:00

I've discovered a couple of cases where Google's Go is trying to be too clever. There are two expressions who's behavior changes based upon what is done with evaluated results. Lets look at a bit of code.

package main

import . "fmt"

// Define a simple struct
type foo struct {
        a int;
}

// Define an interface
type plus1 interface {
        add1() int;
}

func any(a interface{}) {
        v := a.(plus1).add1();
        Printf("%v\n", v);
}

func main() {
        f := foo{1};
        any(f);
}

So this code defines a simple struct "foo" with a single member a. It defines a "plus1" interface that says that any struct that implements the interface must implement an add1 method that returns an int. The main function instantiates a "foo" and passes it onto the any function. Because "foo" doesn't implement the "plus1" interface the first expression in the function "any" will fail with a runtime exception. the "a.(plus1)" is called a type assertion and it fails if the "a" doesn't implement the "plus1" interface. Now we can switch this code so the type assertion won't assert by assigning the results of the type expression to some variables. Consider the following:

package main

import . "fmt"

// Define a simple struct
type foo struct {
        a int;
}

// Define an interface
type plus1 interface {
        add1() int;
}

func any(a interface{}) {
        a1, ok := a.(plus1);
        if ok {
                v := a1.add1();
                Printf("%v\n", v);
        }
 }

func main() {
        f := foo{1};
        any(f);
}

The only difference in this code is that the type assertion will not assert but instead return two values (yes Go can return multiple values!). The second value is of type bool which indicates whether the first value is "a" cast to "plus1". If "a" isn't of type "plus1" then instead of asserting the type assertion will just return false for the second parameter. While this is clever, it feels like assigning the return value to a variable magically alters the behavior of the expression. I think this will just make the language too difficult to learn. The second operation has to do with go-routines and I'll talk about it next time.

Letting the compiler find the bugs

2009-11-18T15:06:00.001-07:00

Lets start by looking at a bit of contrived C/C++ code. See if you can spot the (hopefully obvious) bug.

#include <stdio.h>

int main()
{
    float fieldLength = 120; // yards
    float fieldWidth  = 48.77; // meters
    float yardsInAMile = 1760; // yards per mile

    printf("You must run around the perimeter of an American football field %f times to run a marathon\n", 
            26.2 * (yardsInAMile / ((fieldLength * 2) + (fieldWidth * 2))));

    return 0;
}

It probably shouldn't take you too long to realize that in the above code I'm mixing units. I'm adding yards to meters. While bugs like this are obvious in trivial code they can be difficult to track down in more complex software. What can we do to prevent bugs like this from creeping into code? One solution is to use coding standards to reduce ambiguity. For example you could decide to use metric units for all data in your project. You could also use 'typedefs' and variable naming conventions to make errors even more obvious. Consider the following:

#include <stdio.h>
typedef float yards;
typedef float meters;

int main()
{
    yards fieldLengthYards = 120; // yards
    meters fieldWidthMeters  = 48.77; // meters
    float yardsInAMile = 1760; // yards per mile

    printf("You must run around the perimeter of an American football field %f times to run a marathon\n", 
            26.2 * (yardsInAMile / ((fieldLengthYards * 2) + (fieldWidthMeters * 2))));

    return 0;
}

By including the units in the variable names and types it makes the programmers intentions clear. It's also easier to spot bugs in code audits. For even more safety you could define Meters and Yards classes that encapsulate the floats and prevent mixing of types. The advantage of defining new types/classes is the compiler can now ensure that you don't mix types. The disadvantage is that you'll end up writing a class for each type, with lots of overloaded operators. Writing a class for every unit feels to burdensome for all but the most critical code (nukes, airplane firmware, surgery robots, etc.). The problem with the above 'typedef' solution is that C/C++'s 'typedef' really only defines an alias for the type. Both the type-checker and the compiler will treat 'meters' the exact same way it treats 'yards', we want the type-checker to treat 'meters' and 'yards' as distinct types and the compiler to treat them both as floats. Google's new system language Go lets you do just that. Lets reproduce the original bug in Google Go.

package main

import "fmt"

func main() {
    var fieldLength float = 120; // yards
    var fieldWidth  float = 48.77; // meters
    var yardsInAMile float = 1760; // yards per mile

    fmt.Printf("You must run around the perimeter of an American football field %f times to run a marathon\n", 
            26.2 * (yardsInAMile / ((fieldLength * 2) + (fieldWidth * 2))));
}

This has the same bug as the C/C++ code above. The code should be readable to a C/C++ developer, the only really "weird" thing is that the type follows the variable name. Now let's use Go's strong typing to let the compiler catch the bug for us.

package main

import "fmt"

type yards float
type meters float

func main() {
        var fieldLength yards = 120;
        var fieldWidth meters = 48.77;
        var yardsInAMile float = 1760; // yards per mile

        fmt.Printf("You must run around the perimeter of an American football field %f times to run a marathon\n",
                26.2*(yardsInAMile/((fieldLength*2)+(fieldWidth*2))));
}

Notice that all we did is define two new types 'yards' and 'meters' all which should act like 'floats', but should be treated differently by the type-checker. When we compile we get the following error:

invalid operation: fieldLength * 2 + fieldWidth * 2 (type yards + meters)

The most important part of the error is at the end where it tells us we're trying to add 'yards' with 'meters'. The type checker found the bug for us! So how do we fix it? We need some conversion routines. So lets add some methods to the types and fix the bugs.

package main

import "fmt"

type yards float
type meters float
type miles float

func (m meters) toYards() yards { return yards(m * 1.0936133) }
func (y yards) toMiles() miles  { return miles(1760.0 / y) }

func main() {
        var fieldLength yards = 120;
        var fieldWidth meters = 48.77;

        fmt.Printf("You must run around the perimeter of an American football field %f times to run a marathon\n",
                26.2*((fieldLength*2)+(fieldWidth.toYards()*2)).toMiles());
}

With the corrected program we see that you only have to run around the field 133 times instead of 136.6 times!

Go isn't the first nor the only programming language that allows you to encode units as types, but it's close enough to C/C++ for a good comparison. So what's the runtime overhead of the change? Well there are a couple of method calls (toYards(), toMiles()) where the original version did the conversions inline. The error checking happens at compile time because Go is statically typed so there's no runtime performance hit. Personally I'd much rather wait for my program to call a couple of functions than to run around an American football field 3.6 more times.

By carefully using Go's (or any other language with a good type system) type system you can spend more time writing code and less time tracking down bugs.

More fun with C/C++

2009-11-09T22:34:00.002-07:00

In order to write a program it's useful (but not necessary) to have an accurate mental model of how the language works, so you can mentally interpret your code before handing it off the compiler. So if you're a C/C++ programmer take a look at the following code and see if you can correctly identify the output:

#include <stdio.h>

int foo(int a, int b, int c, int d)
{
    if (a>b)
    {
        return c;
    }
    else
    {
        return d;
    }
}

int main(int argc, char * argv[])
{
    int x = 2;
    int y = 1;

    printf("Result: %d\n", foo(x+=y, y+=x, x+=y, y+=x));

    return 0;
}

In this case the output is non-deterministic. While C/C++ specify what order arguments will be pushed onto the stack it doesn't specify what order they'll be evaluated in. So there are several possibilities for the output. This flexibility allows compiler writers to order the evaluation of operations in the most efficient way. If you want to avoid confusing/broken code don't mutate variables in argument positions. The person that ends up maintaining your code will thank you for it.

Coding Challenge

2009-10-21T22:33:00.008-06:00

Here is a little coding challenge. Learning how to solve this probably won't make you a better programmer (it may make you worse) but it's fun anyway. You are given a file named "helloworld.cxx" that contains the following code.

#include <stdio.h>
#include "muck.h"

int 
main(int argc, char **argv)
{
    printf("%s\n", "Hello World!");
}

You can't edit this file! Your job is to write the "muck.h" header file. When you're done compile "helloworld.cxx" and run it and the output should be "Goodbye!" followed by a newline. Nothing more nothing less. Remember you can only modify "muck.h" and you must compile "helloworld.cxx" unmodified. My solution and it's Makefile.

The Essence of Scheme (part two)

2009-10-06T12:56:00.001-06:00

This post is a continuation of part one. You probably want to read that post first. So in my previous post I walked you through a nifty little though experiment on why Scheme is so expressive, and why those pesky ('s and )'s are actually useful. In this post I hope to provide some concrete examples of using Scheme's macros to do interesting things. So lets start with a simple example. The Scheme programming language (R5RS) doesn't have a built in "while" loop. It does have a "do" loop which is kind of like a "for" loop but I don't think it gets used much. Most Schemers use recursion instead. Lets say you're just learning Scheme and recursion hurts your brain and you really really just want to use a "while" loop just this one time and you promise that you'll pay better attention when you CS professor talks about recursion. It turns out it's quite easy to implement a "while" loop as a Scheme macro¹.

;; A while loop
(define-syntax while
  (syntax-rules ()
    [(_ (cnd ...) body ...)
     (letrec ([tmp (lambda () (if (cnd ...) (begin body ... (tmp)) (void)))])
       (tmp))]))

If you want to try it out here is a bit of code that uses the while loop to count from 10 down to 1.

(define count 10)
(while (> count 0)
       (printf "~a\n" count)
       (set! count (- count 1)))

So in 10 lines of code you can define a "while" loop that works just like the "while" loops built into C/C++/Java/Python/Insert_Your_Favorite_Language_Here.

So that doesn't seem to hard. If C didn't have a built in "while" loop you could always create you're own with a C style macro as follows.

#define WHILE(cond) for(;cond;)

Lets try something more difficult. Scheme also doesn't have a C/C++ "#include" directive. So lets write our own.

;; Define include
(define-syntax include
  (lambda (stx)
    (define (read-all port)
      (let ([exp (read port)])
        (if (eof-object? exp)
            '()
            (cons exp
                  (read-all port)))))
    (define read-file
      (lambda (fn ctx)
        (let ([port (open-input-file fn)])
          (begin0
            (datum->syntax ctx (read-all port))
            (close-input-port port)))))
    (syntax-case stx ()
      ((ctx filename)
       (with-syntax ([(exp ...) (read-file (syntax->datum #'filename) #'ctx)])
         #'(begin exp ...))))))

Once you've defined this you can use it as follows.

(include "extern.ss")

Once you've defined the "include" macro any include expression will get evaluated at compile time which opens up the included file reads in the text and injects it into the the source file at the location of the "include" call. Spend a little time thinking about that. A Scheme programmer can write code that gets evaluated at compile time and that code can open, close, and read from files. So if Scheme's macro language allows you to read from files what else can it do? It turns out anything that a Scheme program can do. The above macro can read from files because any old PLT-Scheme program can read from files. A Scheme macro is just a chunk of regular old Scheme code that gets executed at compile time. If your Scheme allows you to open up a TCP/IP socket then you can write a macro to do this at compile time². If your Scheme allows you to rotate images then you can do it at compile time. If your Scheme allows you to play music then you can play music at compile time³. OK so lets look at some more examples.

(define current-catch 
  (make-parameter 
   (lambda (exn) 
     (printf exn) 
     (exit 1))))

(define (throw exn)
  ((current-catch) exn))

(define-syntax try
  (syntax-rules (catch throw)
    [(_ body ... (catch exn cbody ...))
     (let/cc k
       (parameterize ([current-catch (lambda (exn) cbody ... (k (void)))])
         (begin body ...)))]))

This chunk of code allows users to throw and catch exceptions using "try", "catch" and "throw"⁴. Scheme doesn't have a built in exception mechanism, but in 13 lines of code you can write your own. The following code will use the above macro and functions.

(try 
 (printf "Yes\n") 
 (throw "Error\n")
 (printf "No\n")
 (catch exn 
   (printf exn)))

It will print "Yes" followed by "Error" the "No" will not be displayed because of the "Error" exception will be thrown. OK lets look at one more.

(define-syntax define-generator
  (lambda (stx)
    (syntax-case stx ()
      ((_ (name args ...) body ...)
       (with-syntax ([yield (datum->syntax #'name 'yield)])
         #'(define (name args ...)
             (define yield-k #f)
             (define return-k void)
             (define (yield retval)
               (let/cc k
                 (set! yield-k k)
                 (return-k retval)))
             (lambda ()
               (let/cc ret
                 (set! return-k ret)
                 (if yield-k
                     (yield-k '())
                     (begin
                       body ...
                       (set! yield-k (lambda (x) (void)))))))))))))

This allow you to define Python style generators. Here is a simple example that defines a "range" generator that will reuturn 0 he first time it's called and 1 the next.

(define-generator (range init limit)
  (let loop ([i init])
    (yield i)
    (when (< i limit)
      (loop (+ i 1)))))

(define foo (range 0 1))
(foo)
(foo)

I hope these examples give some insight at how expressive and malleable the Scheme programming language is. There is one more issue I'd like to address. If you're a Python programmer you may be thinking to yourself. "Hey Python has loops, exceptions, generators and import which is kind of like #include. If python has these built in then why should I use Scheme?" That is a valid but slightly myopic question. The point of Scheme's macro system is not to create another Python with funnier syntax. The real point is that you the developer can extend and grow the language to meet your needs. You may extend the language by adding features that are found in other programming languages, but you may also add features that don't exist in any language, and that don't have a name, and that may not be generally useful but really make the current program you're working on really really easy to write. In Python, Perl and Java users have the power to create and extend libraries, in Scheme users have the power to create and extend languages⁵. Power to the people!

[1] All examples tested in in PLT-Scheme 4.1.3.
[2] Implementing "http-include" is left as an exercise for the reader.
[3] Playing music at compile time is possible but not recommended by the author.
[4] Anyone want to try implementing exceptions in C?
[5] There is one major downside to learning Scheme. Eventually you'll find yourself writing a program in C/C++/Python/Java and you'll realize that you could solve some problem really elegantly if you could just extend the language just a little bit. Then you'll realize that you can't and you'll spend the next hour wishing you we're never enlightened.

The Essence of Scheme

2009-09-28T14:25:00.000-06:00

Note that throughout this post "Scheme" could be replaced with "Lisp" without changing it's meaning.

My Introduction to Scheme
My first exposure to Scheme was in college at the University of Utah. At that time they taught a Programming Languages course that was based on the book Structure and Interpretation of Computer Programs, and the Dr. Scheme programming environment. While I enjoyed the class I never understood why some people thought Scheme was so special. In my defense the class really didn't teach us Scheme they just used a small subset of the language to teach us about programming language features such as exceptions, continuations, closures, loops, recursion, conditionals, first class functions etc. It really was a great class, you learned about these features by writing and modifying interpreters that implemented these features. The only problem is that many students including myself left that class thinking they knew Scheme, but we didn't. I didn't get re-introduced to Scheme again until a few years later when I was learning Perl. I kept on learning about features of Perl that I really liked, and then I realized that all of these features were also in Scheme. I decided that I needed to go back and tinker with Scheme.

Learning Scheme
I started learning Scheme by writing programs and reading a lot of blogs, and articles in an attempt to get my brain wrapped around the programming language. Almost everyone talked about how powerful Scheme is, but it took me a long time before I really understood why Scheme is such an expressive language. Because it takes a lot of work and study to reach Scheme enlightenment, many developers simply give up on the language, before they really understand it. I don't know if it's possible to reach Scheme enlightenment, without all the hard work, but I hope this post will at least will give you a peek at why Scheme is so expressive, and why those that really learn it have a tendency to turn into Smug Lisp Weenies. In short this is the blog post that I wish I could have read when I was working towards Scheme enlightenment.

A shortcut to Scheme enlightenment
Lets get started. Consider the following snippet:

(if val
  0
  1)

Now if you're an experienced programmer or a Schemer you were probably tempted to just glance at the above snippet and move on, but take a minute and really think about what you're looking at. As a Schemer I can see three different interpretations of the snippet.

The most obvious interpretation of the above snippet is an 'if' expression. The expressions condition is the 'val' value, the consequence is the integer '0' and the alternate is the integer '1'.

The second interpretation that I see is a linked-list¹ of 4 elements. The first elements in the list are the symbols² 'if' and 'val' followed by the integers '0' and '1'.

The third interpretation is a tree data structure. A linked-list can represent a tree structure by putting the first element in the list as the root and all other elements in the list as child notes of the root. Because Scheme allows a linked-list to have another linked-list as an element arbitrary tree structures can be represented using linked-lists. So the above snippet could also represent the following tree:

This tree also happens to be the Abstract Syntax Tree for the previously mentioned 'if' expression. At this point you may be wondering why this is important, and we'll get to that but for know just consider that every expression in Scheme is an expression, a linked-list and the AST for that expression. Now lets explore the consequences of that fact.

Scheme and linked-lists
Scheme is one of many dialects of Lisp. The name List is short for "List Processing". Although Lisp dialects do support other data-structures, they have very powerful constructs that make them an ideal language for processing linked-lists³. Because every Scheme expression is also a linked-list and Scheme is an ideal language for processing linked-lists we can conclude that Scheme is an ideal language for processing Scheme expressions⁴.

Compilers and AST
When you write a compiler for a language one of the first things you may do will be to build an AST for the tokenized and parsed text. An AST is a simplified representation of the code that is in a format that is easily to manipulate. When the code has been transformed to an AST it is easy for the compiler to perform optimizations, static analysis and transform complex language features into more basic language features.

Bringing it all together
So we've discussed that all Scheme expressions are linked-lists and Scheme is a great language for manipulating linked-lists. We've also discusses that all Scheme expressions are also the AST for that expression, and AST's are a great data-structure for compiler writers to do complex transformations. It shouldn't be too hard to see that Scheme is an excellent language for performing complex transformations on Scheme expressions. In fact Scheme allows you to easily extend the programming language in ways that are only reserved for language designers and compiler writers in other languages. When I learn about some new programming language feature in Python that I wish was in C++, my only choices is to hope that the great C++ language design committee will include the feature in some future version of the C++ spec and that g++ will implement that feature quickly, and my distro will ship the updated version, and ... If I want to use that same feature in Scheme, I can simply implement it and I don't need to ask the language design committee for permission, I don't need to modify the Scheme compiler/interpreter, I don't need to modify any Makefiles, I just implement the feature and start using it immediately! That IMHO is the feature that makes Scheme such a powerful tool! In my next post we'll look at some examples of how easy it is to grow your own language with Scheme.

[1] I know that for this to be treated as a list in code it would need to be quoted, but if it was simply read in from a file with a 'read' call it would come in as a list.
[2] Scheme symbols are like read-only strings that can be efficiently compared for equality by simply comparing their pointers. Symbols are often used like enums in C++.
[3] A proof of this statement is left as an exercise for the reader.
[4] Yep, you should prove this one too while you're at it.

A(nother) counter intuitive C++ (mis)feature

2009-09-16T22:08:00.005-06:00

I've been using C++ for about 12 years now. Which means I don't know if very well. Early on in my C++ career I thought I had a good grasp of the language, but C++ is one of those languages that the more you learn the more you understand how hopeless it is to fully understand it. Every month or so I'm confronted with some new corner case that I didn't know about. Last months mis-feature had to due with overloading and overriding.
Consider the following code:

class Bar
{
    public:
        virtual void method(int a)
        {
            std::cout << "Bar " << a << std::endl;
        }
};

class Baz : public Bar
{
    public:
        virtual void foo(std::string a)
        {
            std::cout << "Baz " << a << std::endl;
        }
};
int main()
{
    int i = 9;
    std::string s = "9";

    Baz *b1 = new Baz();

    b1->method(i);
    b1->method(s);
}

If you compile this code (with g++) you'll get the following errors:

error: invalid conversion from ‘int’ to ‘const char*’
error:   initializing argument 1 of ‘std::basic_string<_CharT, _Traits, _Alloc>::basic_string(const _CharT*, const _Alloc&) [with _CharT = char, _Traits = std::char_traits, _Alloc = std::allocator]’

This caught me by surprise. I had assumed that the compiler would match the method signatures after the method names were mangled, and thus method(std::string) would not hide method(int). It turns out that methods are matched only by the name, and after the match has been found (in this case finding the method(std::string) the type checker validates the parameter types. While I can understand this could make the compiler more efficient, it seem that by default the C++ compiler does the wrong (non-intuitive) thing.

So how do you make the compiler do what you want? You just need to add a "using" line right before Baz's method as follows:

...
using Bar::method;
virtual void method(std::string a)
{
...
}
...

Of course you could have guessed that. Right?