Archive for July, 2006

If you’ve just upgraded to Amarok 1.4 on Gentoo Linux and it keeps crashing on startup, try installing sqlite:

emerge --oneshot dev-db/sqlite

It looks as if this is a runtime dependency of Amarok that emerge fails to install.

I’ve raised this issue as bug #142340 on Gentoo’s bug tracker.

Update: This might just be required if you’re upgrading a collection from 1.3.x.

Continuing my look into language features, today I’m asking why are we still using arrays? Or more specifically why does Java have C-style arrays? An array is essentially a list, an ordered collection of things. Lists are a vital data structure in programming but why is there this first-class array primitive in Java?

Let’s first look at C. Arrays in C are nothing more than syntactical sugar for pointer arithmetic. Consider the following example.

int[] a = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
a[1]; /* equals 2 */

int *a = malloc(10 * sizeof(int));
for (int i = 0; i < 10; i++) {
    *(a + i) = i;
}
*(a + 1); /* equals 2 */

These two bits of code are, for all intends and purposes, the same. Since they are the same there are some limitations placed on arrays in C, i.e. they are fixed length, and things need to be next to each other in memory because of the way pointer arithmetic works.

We don’t really want these restrictions on lists, I may want to change the number of elements, and where they’re located in memory should be an implementation detail. For the second point in particular, Java does make it an implementation detail when you decide to use ArrayList or LinkedList.

So what is an array in Java? It’s not an instance of the Array class, but it is an object. It has a field named ‘length’ (public final), and it implements the Cloneable interface. int[].class.getName() is [I. That doesn’t tell us much, but IMHO it’s a hack in the language to implement C-style arrays. It is fast, according to Peter Norvig’s IAQ on Java, accessing an array is 15-30 times faster than accessing an element of a Vector. But that could just be synchronization overhead, and Vector is probably implemented with arrays anyway. There should be some low level language feature that allows us to access that speed.

So what’s my gripe? Arrays in Java should be so much more than copies of the things in C. The Java Collections API which is one of the best Java APIs, and the List type should have the array syntax. Take a look at Arrays in Ruby, which are essentially a good list implementation with array syntax.

a = [1 ,2, 3, 4, 5]
a[1] » 2

b = [6, 7, 8, 9, 10]
a + b » [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

N.B. this produces a new array, but you can use the ‘concat’ method to append them to the same array

c = [2, 4, 6, 8, 10]
(a + b) - c » [1, 3, 5, 7, 9]

Ruby’s Array class also does a lot more.

The concept of C-style arrays need to be dropped. We don’t handle pointers any more, we shouldn’t be bound by the limitations. The concept we’re using is the list data structure, we should make that, along with all of its potential features, our first class type.

Update: I simplified the way to get the int[] class name (Thanks Shai).

Disclaimer 2: I know Vector’s methods are synchronized, and ArrayList is essentially the same thing without the synchronization overhead, hence faster. The performance numbers I pulled up are old and it used Vectors, thanks Shai for providing up to date numbers.

How cool is this?

You can control your ThinkPad by hitting it.

You can find out more at:

• Knock-based commands for your Linux laptop
• http://www.thinkwiki.org/wiki/HDAPS

Sadly my ThinkPad is too old, so I’ll have to stick to boring keyboard based commands.

Update: Wordpress’ WYSIWYG editor doesn’t let me embed the YouTube flash player, disabling it allowed me to embed the video.

One nice feature of Ruby that I wish I had with Java is the able to change the standard classes. For example, Ruby’s Array class has a map function, but no reduce function. So we simply add methods to the class:

class Array
  def reduce(n)
    each do |value|
      n = yield(n, value)
    end

    n
  end

  def sum(initial = 0)
    reduce(initial) { |n, value| n + value }
  end

  def product(initial = 1)
    reduce(initial) { |n, value| n * value }
  end
end

[ 1, 2, 3, 4, 5 ].sum   »  15 
[ 1, 2, 3, 4, 5 ].product   »  120

(Example from Programming Ruby, where the method is called ‘inject’ and is defined in a separate Mixin so it can be included in other classes, e.g. Range)

In the above example we add the reduce method to the Array class and two additional methods, sum and product, which make use of reduce. The reduce method takes an initial value for the reduction and a code block to act on each element of the array.

We can’t replicate this elegance in Java because the classes are closed. Extending the class only gets us halfway there because only instances of the sub class have the method, i.e. others methods that return the original class won’t have it. Therefore we tend to end up abandoning OO and sticking the function somewhere else, e.g.:

public interface Functor {
  Object function(Object acc, Object value);
}

public class ArrayUtils {
  public static Object reduce(Object[] array, Object initial, Functor f) {
    Object result = initial;
    for (Object o : array) {
      result = f.function(result, o);
    }

    return result;
  }

  public static Integer sum(Integer[] integers) {
    return reduce(integers, 0, new Functor() { 
      public Object function(Object acc, Object value) { return ((Integer) acc) + ((Integer) value); }
    });
  }

  public static Integer product(Integer[] integers) {
    return reduce(integers, 1, new Functor() { 
      public Object function(Object acc, Object value) { return ((Integer) acc) * ((Integer) value) }
    });
  }
}

ArrayUtils.sum(new Integer[] {1, 2, 3, 4, 5});   »  15 
ArrayUtils.product(new Integer[]{1, 2, 3, 4, 5});   »  120

The Java version does the same thing, but just looks wrong to me. Sure autoboxing cleans it up a bit and generics would do more (at the expensive of having to instantiate ArrayUtils), but you can’t get around defining the methods outside of the class, and having code blocks passed around as anonymous classes.

Since I switched to using Eclipse for my Java developer I also switched to use its built in debugger. In the past I’ve used JSwat, which is a great open source Java debugger, but I’ve had some troubles with recent versions with getting it to pick up my source path. This made the switch easier.

Having your debugger integrated with your editor is great, but so far I haven’t played with hotswapping. I’m debugging everything in isolation with JUnit, which makes tracking down bugs a lot quicker.

But this article is called ‘Eclipse Debugger Gripes’, so here are the moans:

Variable Names Disappear

Every so often, normally as I’m just about to track down a tricky bug, all the variable name information disappears. See the screen shot to see what I’m talking about. You can see the variable values, but you don’t know what the value is for. The only way to fix this is to restart Eclipse. Easy fix but annoying.

At first I thought it was the Sun JVM not playing nice with IBM’s IDE, so I switched to their JVM. Initially it seemed better, but every now and again the names disappear. I have no idea what this is the case, but it’s very annoying.

Jad

This isn’t a gripe about Eclipse so much but JadClipse. It has the option to synchronize the lines of the decompiled file with the line information in the class. This allows you to set breakpoints in binaries. Very useful, but doesn’t always work, sometimes it just doesn’t sync them up. This is where the problem with Eclipse comes in, it only allows you to set a breakpoint by highlighting the line in editor that contains the source, you can’t set one manually. So if Jad can’t create a source file where the lines don’t match up, I can’t set a breakpoint.

Source Paths

I came across this one when Jad wouldn’t do its thing. You can assign a source path to each library you import. But this only takes affect after you restart Eclipse. I thought it was broken and almost started tearing out my hair when it wouldn’t stop bringing up the incorrect decompiled source. A restart corrected this. I’m including this one to save others of this grief.

Otherwise, if you’re using Eclipse and haven’t already, I highly recommend you give the debugger a go.

I’ve been wondering what language to learn next for a while. Scala caught my eye. I really should spend more time with Ruby since Rails programming hasn’t taught me much about the dynamic aspects of the language, which is what makes it interesting. I also want to pick up Scheme at some point. So what language did I go for? Prolog.

Not the most practical language in the world, but it’s one of those languages I liked at university but haven’t played with since. It’s not the most popular language either, in fact I think they’ve dropped the advanced Prolog course from the Computing degree at Imperial, which is a shame.

Since I’ve done some Prolog programming before I avoided a beginner’s tutorial and went for Clause and Effect: Prolog Programming for the Working Programmer, which is a terse introduction and series of exercises. I’ve worked through the first two chapters, which is a refresher on lists and backtracking, and remember why I like it so much. You just state what the program is supposed to be rather than how it’s supposed to do it. I remember going from the Prolog labs to Java programming and getting annoyed that just writing a pre and post condition wasn’t enough, you actually had to manipulate your data.

I’m not sure how learning Prolog again will improve my programming, but I’m certain it will, at very least it’ll make me consider backtracking as another form of control flow.

On a slight tangent, IBM DeveloperWorks has an interesting article on how you can use continuations in Scheme to implement Prolog style backtracking. They also show how to implement Python’s generators and Java’s exceptions. I really must learn Scheme so I can understand it.