split-s

Helping javac infer generic return types

2007-08-22T15:16:00.000-07:00

One of my pet peeves with Java generics is that you can't pass the result of a method that returns a generic type whose bounds cannot be inferred from actual arguments directly to another method. This is particularly useful when passing an empty list obtained from Collections.emptyList() to a method:

class Test
{
   static void foo(List<String> list) {}

   public static void main(String[] args)
   {
     foo(Collections.emptyList()); // doesn't compile
   }
}

Unfortunately, that doesn't compile. It can be worked around by doing:

List<String> list = Collections.emptyList();
foo(list);

It beats me why the compiler cannot infer the appropriate type for the list returned by Collections.emptyList() in the first example above. I understand why it would fail when 'foo' has multiple overloads, but it should work for the simple case when the method resolution is unambiguous.

I recently came across an obscure (yes, ugly and unintuitive) way of getting the first example to work. It consists in telling the compiler explicitly what to bind the return type to. This is the BNF definition, per the JLS 3.0:

MethodInvocation:
   MethodName ( ArgumentList? )
   Primary . NonWildTypeArguments? Identifier ( ArgumentList? )
   super . NonWildTypeArgumentsopt Identifier ( ArgumentList? )
   ClassName . super . NonWildTypeArguments? Identifier ( ArgumentList? )
   TypeName . NonWildTypeArguments Identifier ( ArgumentList? )

And here's a concrete example:

foo(Collections.<String>emptyList());

rubydbc

2007-02-25T16:05:00.000-08:00

Design by Contract for Ruby is now a Rubyforge project. Version 1.0.0 is available as a gem:

gem install rubydbc

Creative commercials

2006-11-11T21:27:00.000-08:00

For your enjoyment, here's a site I've built recently: Creative Commercials -- a (growing) collection of creative tv ads.

Here are a couple I like:

Extensible mod_rewrite with Lua

2006-11-07T16:51:00.000-08:00

I was running an experiment with apache + mod_rewrite that required rules that cannot be expressed with regular expressions. mod_rewrite has the notion of rewrite maps, which let you choose from a couple of built in functions (int:tolower, int:toupper, etc.) or a key-value pair map backed by a text or dbm file.

Unfortunately, there's no way to plug in arbitrary mapping functions*, so my first thought was to extend mod_rewrite by adding a new built in function. This lets me write:

LoadModule rewrite_module modules/mod_rewrite.so
RewriteEngine on
RewriteMap foo int:foo

RewriteRule (.*) ${foo:$1} [L]

It works great, but this approach requires forking mod_rewrite.c, which is obviously not a good thing.

Inspired by Brian's mod_wombat, which allows you write http handlers in Lua, I thought "wouldn't it be nice to be able to extend mod_rewrite with custom Lua scripts?". Say, something like:

LoadModule rewrite_module modules/mod_rewrite.so
RewriteEngine on
RewriteMap foo lua:/usr/local/apache2/rewrite-rules.lua

RewriteRule (.*) ${foo:$1} [L]

30 lines of code later, my lua-enabled mod_rewrite prototype is able to do exactly that. Mind you, this is a very crude implementation and doesn't check for errors, cache compiled scripts, etc. But all those details can be improved.

Anyway, this is all becomes somewhat irrelevant with the latest version of mod_wombat, which allows you to define transform_name hooks in Lua, as well.

It was a interesting experiment, nonetheless :)

* To be fair, there is actually a way to do this, but I consider it to be too clunky and non-scalable to be of any value in a real production system. The mechanism consists on mod_rewrite talking to an external process that does translations via its stdin/stdout streams. As a result, a global mutex is required to guarantee correctness in the face of multiple simultaneous requests.

application/atom+xml content type workaround for Firefox

2006-04-29T22:09:00.000-07:00

Here's a Firefox extension that will let you view Atom 1.0 feeds inside your browser. Currently, Firefox does not understand the application/atom+xml content type and will treat the feed as a download and prompt you to save it or to open it with an external application.

Once you install this extension, Atom feeds will be displayed in your browser like any other xml document.

Get it here!

Shoot Profiles

2006-04-22T14:20:00.000-07:00

If you are into Shoot and games, you may appreciate this application for uploading and sharing Shoot profiles.

I uploaded the profiles from the old site and added a few that I hadn't got around to posting. Feel free to share yours!

Atom 1.0 parser for Ruby

2006-04-06T19:41:00.000-07:00

I've been looking for a Ruby library for parsing Atom 1.0. The only one I could find was FeedTools. Unfortunately, it's intended to be a universal feed-parsing library and not quite what I need.

As a result, I decided to build my own. The project is hosted at RubyForge and the source code is available under the MIT license.

It is still in its early stages, so don't expect much at this point. So far, it understands most atom:* elements and attributes but doesn't perform validation.

The interface is fairly simple. For example, you can do this:

require 'atom'
require 'net/http'
require 'uri'

str = Net::HTTP::get(URI::parse('http://blog.ning.com/atom.xml'))
feed = Atom::Feed.new(str)

feed.entries.each { |entry|
puts "'#{entry.title}' by #{entry.authors.first.name} on #{entry.published.strftime('%m/%d/%Y')}"
}

Give it a try, play with it. Comments are welcome!

Where am I?

2006-03-15T16:22:00.000-08:00

Need to get the name of the current method in Ruby?

module Kernel
def current_method
caller[0].sub(/.*`([^']+)'/, '\1').to_sym
end
end


irb(main):006:0> def test
irb(main):007:1>    p current_method
irb(main):008:1> end
=> nil
irb(main):009:0> test
:test
=> nil
irb(main):010:0>

If you want to get fancier, you can get get a reference to the method itself:

module Kernel
def current_method
method(caller[0].sub(/.*`([^']+)'/, '\1').to_sym)
end
end

Design by contract for Ruby

2006-02-21T23:30:00.000-08:00

Here's a nice little module Brian and I hacked together a few weeks ago. It adds basic design by contract capabilities to classes with a fairly clean syntax (yay for Ruby's flexibility!)

Take a look for yourself:

class Foo
   include DesignByContract

   pre(:sqrt, "value must be >= 0") { |v| v >= 0 }

   pre("divisor must be != 0") { |dividend, divisor| divisor != 0 }
   post { |result, a, b| a - b * result < 1e-3 }
   def div(dividend, divisor)
      dividend / divisor
   end

   def sqrt(value)
      Math.sqrt value
   end

   post(:sqrt, "error is greater than expected") { |result, value|
         result * result - value < 1e-3
   }
end

When the DesignByContract module is included in a class, the pre and post methods become available. The parameters to these methods are a symbol representing the method to add the pre or post condition to, the message to print if the condition fails and a block that implements the condition.

The method name and message are optional, though. If the method name is missing, the condition will applied to the first method definition following the pre/post declaration. Note that if the method name is present, the condition can be defined anywhere in the class definition, as shown in the example above.

The condition block receives all the arguments passed to the method it applies to. They must return a boolean value indicating whether the condition succeeded. A minor difference between pre and post blocks is that the post block receives the result returned by the method as the first argument. This makes it possible to validate the results against the inputs such as in:

post { |result, dividend, divisor| dividend - divisor * result < 1e-3 }

Get it here!

How it works

In a nutshell, the pre and post methods intercept the existing method using the technique I described a few weeks ago (i.e., no poluting the class' namespace with aliased methods). The new methods test the provided condition before or after delegating the call to the original method and raise an exception if the condition fails.

There is a small caveat, though. If pre/post are called before the method is first created, it cannot be intercepted. To get around this the module uses an alternative trick. Whenever the module is included, it hooks into the method_added callback of class it's included into. If pre/post are called and the corresponding method does not exist, the interception is scheduled until the method is added.

Duplicate Message Remover for Thunderbird 1.5

2006-01-25T00:15:00.000-08:00

I've updated the Duplicate Message Remover extension to make it compatible with Thunderbird 1.5. Grab it here.

Replacing methods

2006-01-20T22:43:00.000-08:00

Let's say we want to replace a method instead of just throwing it away. But we want the new method to be able to call the old implementation.

The standard way of doing this is by aliasing the old method and making the new one call the aliased version:

class Foo
  def method
    ...
  end

...

class Foo
  alias :method :old_method

  def method
    ...
    old_method
  end
end

This solution works perfectly for most situations, but what if we want to remove all traces of the old method?

Here's a simple trick to do exactly that:

class Foo
   old_method = instance_method(:method)

   define_method(:method) { |*args|
       # do something here ...
       old_method.bind(self).call(*args)
   }
end

It shouldn't take much to understand how it works, but let's analyze it in more detail. The first line gets a hold of the old implementation of method. instance_method returns an UnboundMethod object that wraps it.

Next, we redefine method and pass it a block with the new implementation. One thing worth mentioning is that the old_method variable inside the block is bound to the variable assigned to outside of the block. The binding is maintained even after the execution reaches the end of the class definition. As a result, the new method has a direct reference to the old one... and nobody else does.

After doing whatever it has to do, the new method calls the old one after binding the UnboundMethod to the current object (i.e., the object on which method was invoked).

If you have a keen eye, you'll notice that there's something special about self. At first glance, it looks like a standard variable that just happens to hold a reference to the current object. If that were true, it would follow that the reference to self inside the block would be bound to the self representing class Foo. That is not the case, though. The binding of self is established when the block gets called.

Removing methods from a module

2006-01-17T20:59:00.000-08:00

How do we remove a method from one of Ruby's built-in modules (Kernel, etc)? It should be easy and obvious, right? The following snippet should be enough, right?

#remove system from module Kernel
Kernel.send :remove_method, :system

Well, not quite. While that prevents you from calling system() in the context of the current object, you can still invoke it like this:

Kernel::system('date')

What's going on?

It turns out that they way Kernel (and other built-in modules) are defined is analogous to doing the following:

module Kernel
  def system (...)
    ...
  end

  module_function :system
end

Thus, system() is a method that will be added to instances of classes that include the given module (in our case, instances of any object, since Kernel is included by Object), but it is also a method in Kernel's singleton class (bear with me for a moment), or a module_method as the PickAxe book calls them. In Java parlance, they are simply static methods.

Looking at Ruby's source code, we can see that all of Kernel's methods are defined by way of the rb_define_module_function function, whose definition is:

void
rb_define_module_function(module, name, func, argc)
  VALUE module;
  const char *name;
  VALUE (*func)();
  int argc;
{
  rb_define_private_method(module, name, func, argc);
  rb_define_singleton_method(module, name, func, argc);
}

So, what does it mean that "system" is a method of Kernel's singleton class? Let's recap what happens when we create a class and add a method to the singleton class of one of it's instances.

class A
end

V1 = A.new    # creates an instance of A and assign it to constant V1
V2 = A.new    # ... and V2

# now we add method x() to V1's singleton class
class << V1
   def x
     puts "hello"
   end
end

V1.x    # will print "hello"
V2.x    # will fail ... V2 does not have a method x()

Clear?

Ok, now, remember that all Ruby modules are instances of a class called Module? Say we replace A by Module, V1 by Kernel and x() by system(). What we get is the following:

Kernel = Module.new

class << Kernel
   def system
     ...
   end
end

And that's essentially what's going on behind the scenes.

Going back to the question that started this post, how do we remove a method from one of the built-in modules, anyway? The answer is easy, if not as obvious as we might have expected:

module Kernel
remove_method :system
end

class << Kernel
remove_method :system
end

Or, more concisely,

Kernel.send :remove_method, :system
class << Kernel; self; end.send :remove_method, :system

Flying dog

2006-01-10T14:35:00.000-08:00

LOL!

http://video.google.com/videoplay?docid=2978884470072026171&q=flying+dog

Ruby's executable class definitions

2005-12-22T16:19:00.000-08:00

If you're coming to Ruby from Java, remember that class definitions are executable code. I can think of at least one situation where this has practical implications and if you're not clear about it you'll spend a couple of hours banging your head against the wall.

Consider this simple Java class:

class A
{
  int a = 10;

  public int getA()
  {
    return a;
  }
}

If you create an object of type A and call it's method getA(), you'll get 10. No surprises here.

Now, knowing that member variables in Ruby are prefixed with @ we go ahead and translate our little java class to Ruby like so:

class A
  @a = 10

  def a
    return @a
  end
end

We then create an object of class A and call its a() method:


irb(main):001:0> class A
irb(main):002:1>   @a = 10
irb(main):003:1>   def a
irb(main):004:2>     return @a
irb(main):005:2>   end
irb(main):006:1> end
=> nil
irb(main):007:0> A.new.a
=> nil

"WTF!!" you say. Well, if you remembered what I said, class definitions are executable code. In our case, this means that the @a = 10 is executed when the class is defined, not when an instance of the class is created. As a result, this statement defines a member variable of the instance of class Class that represents class A.

To prove the last statment is true, let's make a() a class method:

class A
  @a = 10

  def A.b
    return @a
  end
end

When we call it we get what we expected:


irb(main):001:0> class A
irb(main):002:1>   @a = 10
irb(main):003:1>   def A.a
irb(main):004:2>     return @a
irb(main):005:2>   end
irb(main):006:1> end
=> nil
irb(main):007:0> A.a
=> 10

Simple color effects

2005-12-22T08:32:00.000-08:00

RGB is the most widespread method for representing colors. HTML, CSS, Java's java.awt.Color constructors, and countless more, all expect color to be described in terms of their RGB components.

But RGB is not the best choice for doing common operations such as desaturation and certain types of gradients (e.g., shades of a color and fade to black or white). There's a much more natural way of manipulating colors for that purpose without going crazy with interpolation in the RGB color space. The trick is to work with the HSV representation, instead. In the HSV space, a color is defined by it's hue (the "rainbow" of colors), it's saturation and it's brightness or value.

For any given color, change the brightness to get a darker or lighter shade. If you want to desaturate it (without changing it's brightness), simply reduce it's saturation value.

Here's a simple example, and the relevant Javascript code:

function RGB(r, g, b)
{
   this.r = r
   this.g = g
   this.b = b
}

RGB.prototype = {
   toHSV: function()
   {
     var max = Math.max(this.r, this.g, this.b)
     var min = Math.min(this.r, this.g, this.b)

     var s = (max - min) / max

     switch (max) {
       case this.r: return new HSV(60 * (this.g - this.b) / (max - min), s, max)
       case this.g: return new HSV(60 * (this.b - this.r) / (max - min) + 120, s, max)
       case this.b: return new HSV(60 * (this.r - this.g) / (max - min) + 240, s, max)
     }
   },

   toHex: function()
   {
     var r = Math.floor(this.r * 255).toString(16)
     var g = Math.floor(this.g * 255).toString(16)
     var b = Math.floor(this.b * 255).toString(16)

     return "#" + (r.length == 1? "0" : "") + r
       + (g.length == 1? "0" : "") + g
       + (b.length == 1? "0" : "") + b
   }
}

function HSV(h, s, v)
{
   this.h = h
   this.s = s
   this.v = v
}

HSV.prototype = {
   toRGB: function()
   {
     var sextant = Math.floor(this.h / 60) % 6

     var f = this.h / 60 - sextant
     var p = this.v * (1 - this.s)
     q = this.v * (1 - f * this.s)
     t = this.v * (1 - (1 - f) * this.s)

     switch (sextant) {
       case 0: return new RGB(this.v, t, p)
       case 1: return new RGB(q, this.v, p)
       case 2: return new RGB(p, this.v, t)
       case 3: return new RGB(p, q, this.v)
       case 4: return new RGB(t, p, this.v)
       case 5: return new RGB(this.v, p, q)
     }
   },

   toHex: function()
   {
     return this.toRGB().toHex()
   }
}

function desaturate(box, color)
{
   box.style.backgroundColor = color.toHex()

   color.s -= .01
   if (color.s >= 0) {
     window.setTimeout(function() { desaturate(box, color), 50 })
   }
}

function fadeToBlack(box, color)
{
   box.style.backgroundColor = color.toHex()

   color.v -= .01
   if (color.v >= 0) {
     window.setTimeout(function() { fadeToBlack(box, color), 50 })
   }
}

function fadeToWhite(box, color)
{
   box.style.backgroundColor = color.toHex()

   var v = 1 - color.v
   var distance = Math.sqrt(color.s * color.s + v * v)

   color.s -= 0.01 * color.s / distance
   color.v += 0.01 * v / distance

   if (color.v <= 1 && color.s >= 0) {
     window.setTimeout(function() { fadeToWhite(box, color), 50 })
   }
}

Internationalized GET parameters with Tomcat

2005-12-21T16:22:00.000-08:00

One tiny, oft overlooked detail when working with internationalized web apps is that the Content-Type header specifies the type and encoding of the body of the http request.

Say you want to add searching to your site, which is implemented as a form that submits using method="GET", and your target audience is Japanese people. How do you deal with internationalized query parameters, considering that GET requests do not have a body?

Historically, query strings were expected to contain characters in the ISO-8859-1 character set, with anything but a subset of ASCII encoded using the %xx notation. In discussions a few years ago it was agreed that using UTF-8 encoding for international characters was the best alternative. This is reflected in RFC 3986 (which is backed by the W3C):

When a new URI scheme defines a component that represents textual data consisting of characters from the Universal Character Set [UCS], the data should first be encoded as octets according to the UTF-8 character encoding [STD63]; then only those octets that do not correspond to characters in the unreserved set should be percent-encoded. For example, the character A would be represented as "A", the character LATIN CAPITAL LETTER A WITH GRAVE would be represented as "%C3%80", and the character KATAKANA LETTER A would be represented as "%E3%82%A2".

If you're running Tomcat, watch out! If your URL contains unicode characters, the browser will properly encode them as UTF-8 and then do the %xx magic for each byte. Tomcat will treat each encoded byte in the UTF-8 representation as a single ISO-8859-1 character and make your Japanese users very unhappy.

Unfortunately, this is Tomcat's default behavior. Fortunately, there is server configuration option that will force it to treat URLs as per RFC 3986. To enable it, edit server.xml and add the following parameter to the connector element:

BTW, I've tested this in Tomcat 5.5.12. I don't know whether it will work in previous versions.

ANTLR for Ruby

2005-12-15T20:28:00.000-08:00

The latest release of ANTLR v3 adds support for Ruby as a target language, courtesy of yours truly. Let's look at an example to see what's possible.

The following grammar generates a parser that can evaluate simple arithmetic expressions involving integer numbers, +, -, *, /, ( and ).

grammar Calculator;
options {
  language = Ruby;
}

@members {
  @stack = []

  def result
    @stack[0]
  end
}

parse: expression;

expression: mult (
    '+' mult {
      @stack.push(@stack.pop + @stack.pop)
    }
  | '-' mult {
      a = @stack.pop
      b = @stack.pop
      @stack.push(b - a)
    }
  )* ;

mult: atom (
    '*' atom {
      @stack.push(@stack.pop * @stack.pop)
    }
  | '/' atom {
      a = @stack.pop
      b = @stack.pop
      @stack.push(b / a.to_f)
    }
  )* ;

atom: n=NUMBER { @stack.push($n.text.to_i) }
  | '(' expression ')';

NUMBER: ('0'..'9')+;

WS: (' ' | '\n' | '\t')+ { channel = 99 };

First, we need to process the grammar with ANTLR. You'll need to have Java installed in order to do this. ANTLR will generate two files: Calculator.rb and CalculatorLexer.rb.

You'll also need the ANTLR ruby runtime library (just a small .rb file) which you can get here. Just drop into the same directory as the two .rb files created above (in the future I may package it as a gem).

We got our parser, so let's try it out. Create another ruby file with the following:

require 'Calculator'
require 'CalculatorLexer'

lexer = CalculatorLexer.new(ANTLR::CharStream.new(STDIN))
parser = Calculator.new(ANTLR::TokenStream.new(lexer))
parser.parse

puts parser.result

Now, run the program, type an expression and press CTRL-D (or CTRL-Z if in Windows) to see the results, like so:


(5 + 4) * (10 - 2) / 3
^Z
24.0

Simple... but cool, eh?

ANTLR v3 is still in pre-alpha stage, and the Ruby backend is a work in progress. So far, it can handle syntactic and semantic predicates, token labels, etc. and I'm planning to add support for scopes and token/rule parameters and return values next. AST creation will come after that.

ANTLR-based Ruby grammar

2005-11-26T01:03:00.000-08:00

It looks like other people are showing interest in replacing the YACC-based Ruby parser by one based on ANTLR. This hits close to a project I've been working on in my spare time.

When I looked at JRuby's source code a few weeks ago, I thought I'd start trying to understand how the parser works. I had a few ideas I wanted to experiment with, but...

The YACC-based parser is too hard to fathom. There are too many scattered pieces with no clear dependencies. Making changes without breaking things should be even harder.

So I decided to start working on ANTLR-based grammar to replace the current implementation -- pretty much what MenTaLguY is trying to do. I'm still in experimentation mode and trying to figure out how I'll deal with some of the features of Ruby that are not usually found in other languages.

One of the hardest aspects, I think, is how to parse %Q-delimited strings. Here's how they work (from the Pickaxe book):

Following the type character is a delimiter, which can be any nonalphabetic or nonmultibyte
character. If the delimiter is one of the characters (, [, {, or <, the literal
consists of the characters up to the matching closing delimiter, taking account of nested
delimiter pairs. For all other delimiters, the literal comprises the characters up to the
next occurrence of the delimiter character.

Additionally, %Q strings can contain #{} constructs, whose contents should be parsed as Ruby expressions. These can probably be handled in a manner similar to how this grammar for the E language implements what they call quasi-literals.

I haven't yet decided on how to deal with delimiters but I have the feeling it may require writing a custom lexer for string contexts.

Firefox search plugins for Ning

2005-10-08T16:06:00.000-07:00

If you're using Firefox, you can get a few search plugins for Ning here:

http://utils.ning.com/plugin/

It's aliiiive!

2005-10-05T10:07:00.000-07:00

A couple of days ago we launched Ning, a playground for building social applications. Lots of work in the past few months -- that's my lame excuse for not having posted this long :) --, working with a great team (and others that don't have a blog to link to).

The next few months are going to be exciting!

Goodbye Texas, hello California

2005-03-25T14:44:00.000-08:00

split-s has been silent lately. A lot has been happening in recent weeks, and my mind has been elsewhere.

I'm leaving my current job in Plano and moving to the Bay Area. I can't say what I'll be doing, yet. Stealth-mode and all that :). All I'll say for now is that I'll be working with Diego and a few other great people.

Now, to start planning for the move. It's gonna be very hectic for the next few weeks, but I'm excited!

const_missing

2005-03-08T08:58:00.000-08:00

There's an ongoing weekly quiz in the Ruby mailing list. This week's theme is roman numerals -- writing a program that can read roman numerals from the standard input and print out their arabic representation. A few solutions have been posted, standard stuff. But Dave Burt complemented his with a very neat hack. He makes it possible to treat integers and roman numerals interchangeably, and to perform arithmetic operations with them:

VII + 3 -> X
XIV / 2 -> VII
VIII.divmod(III) -> [II, II]
etc.

Part of this is achieved by redefining the const_missing method of the Object class, which kicks in whenever the interpreter finds reference to an unknown constant.

def Object.const_missing sym
    # verify that the constant is a roman numeral
    raise NameError.new("uninitialized constant: #{sym}") unless RomanNumerals::REGEXP === sym.to_s
    # define the constant and return it
    const_set(sym, RomanNumeral.get(sym))
end

The arithmetic operations are made possible by redefining RomanNumeral's method_missing method with code that delegates unknown operations to the it's integer representation.

Take a peek at the complete solution.

Stealth fighter jet unveiled

2005-03-02T10:21:00.000-08:00

See for yourself...

I had a good laugh with these, too. Enjoy!

1 2 3 4 5 6 7 8

Ruby-style iterators in Java

2005-02-24T09:05:00.000-08:00

Loop abstraction is probably the most common application of blocks in Ruby. The idea being that the programmer should not have to deal with the iteration code itself and concentrate on what needs to be done at each step, instead. And it's typically a good idea.

This is what a standard pre-Java 5 iteration looks like:

Iterator i = collection.iterator();
while (i.hasNext()) {
Object obj = i.next();
...
}

Or, for iterating over an array:

for (int i = 0; i < array.length; ++i) {
Object obj = array[i];
...
}

These are cleary prone to cause programming errors. Forget to call i.next(), call it twice, use <= instead of <, forget ++, and all goes to hell.

Iterators have gotten significantly better in Java 5 with the introduction of the for each construct, but they are still a long way from Ruby's internal iterators:

for (String str : listOfStrings) {
...
}

A little bit of nomenclature here. External iterators are those where the client code controls how the iteration takes place (e.g., the Java way). Internal iterators, on the other hand, abstract that logic and only require the client code to supply the action to perform at each step of the iteration (e.g., the Ruby way).

Take a look at the iterator idiom in Ruby:

array.each { |value|
...
}

Much cleaner, and no need for so much boilerplate, don't you think?

In the majority of cases, what a program really needs are internal iterators. From a code reuse perspective, why replicate the same construct over and over? But make no mistake, there are some legitimate cases for where external iterators are necessary, such as when looping over several collections in parallel (try doing that with internal iterators).

Ruby provides a way for externalizing internal iterators. Using the Generator class, an Enumerable object (i.e., that which exposes a method each) can be transformed into an external iterator:

generator = Generator.new [1,2,3,4,5,6,7]

while generator.next?
puts generator.next
end

Internal iterators in Java

So, how about internal iterators for Java? The first thing we need to look at is how to encapsulate a chunk of code in a form that can be passed around (a la Ruby blocks).

The closest we can get are anonymous inner classes, but it's not even fair to compare them with Ruby blocks. The latter a lot more flexible, without the clunky syntax. Here's an how we could emulate a general-purpose block in Java 5:

interface Block {
     Object call(Object... items);
}

...

void methodThatTakesBlock(Block block)
{
     block.call("hello", "world");
}

...

Block block = new Block() {
     Object call(Object... items) {
         return items[0].toString() + items[1].toString();
     }
}

methodThatTakesBlock(block);

First, you'll notice we're declaring a Block interface. This is needed in order to be able to invoke the "call" method on the block (it would be possible to do via reflection, too, but that's another story).

The use of varargs helps avoid having to declare a block class or method for each possible combination of arguments and return values, but places the burden of extracting the arguments from the array on the implementer of the block.

For what we're trying to achieve here, we're going to stick with non-vararg arguments. In fact, our block only needs one argument, namely, the element that's being iterated over at each step. Here it goes:

interface IterationCallback<E>
{
     void call(E element);
}

interface EnumerableCollection<E>
    extends Collection
{
     void each(IterationCallback<E> callback);
}

class EnumerableArrayList<E>
     extends ArrayList<E>
     implements EnumerableCollection<E>
{

     public void each(IterationCallback<E> callback)
     {
         for (E element : this) {
             callback.call(element);
         }
     }
}

And here's how to use it:

EnumerableCollection<Integer> list = new EnumerableArrayList<Integer>();

list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);

list.each(new IterationCallback<Integer>() {
     public void call(Integer element) {
         System.out.println(element);
     }
});

So, it is possible, but nobody said it would be pretty. Better language support would be needed to make internal iterators as developer-friendly as they are in Ruby. And we're not even considering the performance implications. The above code instantiates an extra object compared to using Java's iterator idiom, and requires an extra method call. It could have significant impact if used in the wrong place.

Do-not-call registry loophole?

2005-02-20T13:40:00.000-08:00

I received a call last Friday at home. I was at work, but the answering maching picked it up. The message said:

... This is not a sales call or a solicitation. Unfortunately, due to the nature of this matter, I am not able to provide additional information in this format. I, or one of my associates, can be reached at 1-800-XXX-XXXX. Please return this call..."

I used to get marketing calls every day, even Saturdays at 8 am. Really annoying. When I registered my phone number with the FCC do-not-call list over a year ago, the calls stopped. The rule does not limit some kinds of calls, though. To quote from the FCC site:

calls from organizations with which you have established a business relationship
calls for which you have given prior written consent
calls which are not commercial or do not include unsolicited advertisements
calls by or on behalf of tax-exempt non-profit organizations

It seems to me that by saying "this is not a sales call or solicitation" they are attempting to cover themselves (see the 3rd item above). And if I call them back, then it would be me who's contacting them, so they would be exempted from the rule and free to try to sell me anything.

I'm not calling them back, of course. But I hope this is not the beginning of a trend, or I may have to start shutting off my phone every Friday night... again.

building blocks

2005-02-19T17:47:00.000-08:00

One of the features I like best in Ruby is the support for blocks. Blocks are, essentially, chunks of code that can be passed around as objects and invoked at a later point in the program (also known as lambdas in other languages). But they are more than just code. When a block is defined, the context in which it is defined (variables, constants, etc) goes with it.

You define a block like this:

b = lambda { |value| puts value }

c = lambda do |value|
puts value
end

Either {} or do...end can be used as delimiters. The names between | are the arguments to the block. Any number of arguments can be specified by separating them with comma: |value, i, j|

To call the block:

b.call("hello")

The need for call may go away, though.

A little syntactic sugar allows us to pass blocks to methods implicitly. As far as I know, this syntax originated as a way to abstract looping behavior, one of the key applications of blocks in Ruby.

This is how it works:

methodThatTakesBlock { |value| puts value }

Sweet, eh?

A method that takes a block can refer to it implicitly or explicitly. Implicitly:

def methodThatTakesBlock
yield "hello"
end

The key here is the yield keyword, which calls the provided block with one or more values as arguments. yield can be called any number of times, for example:

def methodThatTakesBlock
yield "hello"
yield "world"
end

But what if you need to keep a reference to the block, or pass the block around from within that method? Easy. If the last parameter in a method declaration is prefixed with &, the provided block will be assigned to the parameter. Take a look for yourself:

class BlockContainer
     def initialize
         @blocks = {}
     end

     def addBlock(name, &block)
         @blocks[name] = block
     end
end

container = BlockContainer.new
container.addBlock("a") { puts "a" }
container.addBlock("b") { puts "b" }

Going back to what I said about blocks taking the context they were defined in with them... it is true! I swear!

Ok, to illustrate the idea, look a this code:

def methodThatTakesBlock
yield
end

a = 1
methodThatTakesBlock { puts a }

Your first reaction might be "that won't work, a will not be available from within methodThatTakesBlock". In fact, it will, simply because a is part of the context where the block is defined.

astronaut monkeys?

2005-02-10T08:00:00.000-08:00

Cedric suggests that the inconsistencies in Java 5 collections are there to preserve compatibility. Until I see an example, I won't be conviced (nudge, nudge...) ;)

Unless I'm way off base, binary compatibility wouldn't be broken. For an inside look, see Euxx.

After all, the runtime signature for
boolean remove(E element) is boolean remove(Object element) and for E[] toArray() it's Object[] toArray()

Source compatibility is not broken, either. If you're doing stuff like:

List list = new ArrayList();
list.add("hello");
list.remove(new Integer(1));

your code will still compile in Java 5.

And if you want to take advantage of generics, well, you have to abide by the new rules. Is that too much to ask for?

I'm starting to think astronaut monkeys may be the culprits ;)

Java 5 Collections inconsistencies

2005-02-07T11:28:00.000-08:00

Generics are one of the Cool New Features™ in Java 5. The collections framework has been ported to make use of the new syntax and semantics. So now it's possible to do the following:

List<String> list = new Array<String>();

list.add("hello");
list.add("world");

String hello = list.get(0);
String world = list.get(1);

for (String str : list) {
System.out.println(str.length());
}

There are definite advantages to the generics-enabled syntax. It looks *much* cleaner for starters. And we can combine them with the new for each syntax for a nicer looking loop construct. Compare the above with pre-Java 5 code:

List list = new ArrayList();

list.add("hello");
list.add("world");

String hello = (String) list.get("hello"); // downcast needed here!
String world = (String) list.get("world");

// this is plain ugly...
Iterator i = list.iterator();
while (i.hasNext()) {
String element = (String) e.next();
System.out.println(element.length());
}

But a couple of aspects of the new generics-enabled collections framework annoy me. For example, the Collections interface is declared as Collection<E> and the add method, for example, is correctly declared as:

boolean add(E object)

So I cannot help but wonder why, then, is remove declared as:

boolean remove(Object object)

This declaration makes it possible to call remove with an element of the wrong type. While it won't trigger an exception, it could hide a coding error. For example, in the snippet below we "forget" to call toString() on x. Yet, we don't get a compilation or runtime error. We can only realize there's a mistake when the program does not produce the expected results.

List<String> list = new ArrayList<String>();

list.add("hello");
list.add("1");
...
Integer x = new Integer(1);
list.remove(x);

Similarly, the toArray() method should be declared as follows:

E[] toArray()

Instead of:

Object[] toArray()

Othewise, we need to downcast the result of the call, as shown in the example below... yuck! But most importantly, it allows invalid down casts, which is one of the things generics try to help avoid in the first place.

List list = new ArrayList();

list.add("hello");

Object[] elements = list.toArray();

String string = (String) elements[0]; // downcast needed
Integer intValue = (Integer) elements[0]; // accepted by compiler, but fails at runtime.

Lastly, there's another variation of the toArray method, which has been defined as:

<T> T[] toArray(T[] type)

Here the method uses generics, but there's a caveat. If T is not a supertype of E, an ArrayStoreException will be thrown at runtime. It would be nice to be able to capture the relationship between T and E as in the example below. Unfortunately, such syntax is not allowed:

<T super E> T[] toArray(T[] type)

I don't know what were the reasons behind these choices, and I certainly hope it wasn't a case of "oops, I missed it"-itis. For performance, maybe (the compiler would save a downcast)? If that was it, it wasn't a good trade-off, IMO.

Update: fixed an error in one of the code snippets. Thanks for the observation, Diego.

Duplicate Message Remover 0.1

2005-02-04T11:31:00.000-08:00

Here's the extension for Thunderbird I was working on. It removes duplicate messages in any given folder and moves them into the Trash (the operation can be undone). The function can be accessed by right clicking on a folder and selecting "Delete Duplicate Messages".

Installation instructions

Download the extension to your computer (Right-click on the link, and choose "Save Link As" if you're using Firefox. Otherwise, Firefox may try to install it itself)
In Thunderbird, go to Tools->Extensions and click on the Install button. Browse to the file you just downloaded and click on Open.
Restart Thunderbird... and you're done!

By the way, the extension requires Thunderbird 1.0

Known Limitations

The extension works on folders only. Executing the function on an account will do nothing.
It does not recurse into folders. If a folder contains subfolders you'll need to run it on each subfolder manually.
Since the extension analyzes each folder independently, messages duplicated across folders won't be detected.

Thanks to the anonymous poster for the suggestion regarding the message IDs. It turned out that the IDs can be obtained via Thunderbird APIs (they are stored in the metadata database). There's no need to parse the emails at all.

Update: a new version compatible with Thunderbird 1.5 can be found here.

two of each

2005-02-02T14:29:00.000-08:00

[He] held one finger up directly in from of Yossarian and demanded, "How many fingers do you see?"
"Two", said Yossarian.
"How many fingers do you see now?" asked the doctor, holding up two.
"Two", said Yossarian.
"And how many now?" asked the doctor, holding up none.
"Two", said Yossarian.
The doctor's face wreathed with a smile. "By Jove, he's right," he declared jubilantly. "He does see everything twice."

In Catch-22, by Joseph Heller.

For some mysterious reason, Thunderbird occasionally downloads my emails twice from the POP server. I think it may be related with the fact that I use to email clients (home and office) to suck emails from the server. But I also remember seeing this happen in Outlook in a previous life. So maybe it the server's fault rather than Thunderbird's.

Aaanyway, I decided to create an extension for Thunderbird that would delete duplicate emails automatically. Something that could be triggered from the context menu of a folder or account (and why not, as soon as an email arrives).

So the approach goes like this. The program iterates over every email in a folder or account and computes a hash for each email, using some function such as MD5. It then stores the hash in a map, associating it with the email (or rather, a reference to the email. We don't want to store the contents of every email in memory). But, if the map already contains an entry for that hash, it means we're probably facing a duplicate email. So the program compares the contents of both emails to rule out any chance of them having the same hash by coincidence (very unlikely, but possible).

So far so good. After a few cycles of writing and testing the Javascript code (writing mozilla extensions is messy, I tell you) I got to a point where it could detect duplicate emails (no deletion yet).

To my surprise, when I ran it the browser locked up for a few seconds. I eventually discovered what the problem was and I'll get to it after I describe how to program is structured.

There's a main function, deleteDuplicateMessages() that is invoked when the menu item is clicked on. This function iterates over the set of message headers (Thunderbird objects that contain metadata about each email) and invokes an asynchronous method to stream the contents of the email. The function takes an callback object as an argument. I believe they had to implement it like that to support IMAP, where getting the contents of an email could take a while.

The callback object gathers all the pieces of the email as it is streamed, strips out the headers and computes the MD5 hash. It then makes sure the entry does not exist in the hash map and exits.

The reason for the lockup is two-fold. First, there's the issue with the MD5 library I'm using, which takes a few seconds to compute the hash for really long strings.

The second issue seems to be that Javascript code in Mozilla executes in the UI thread, regardless of whether it's a callback function being invoked by a native component. So what's happening here is that the computation of the MD5 hash executes in the UI thread and prevents the Thunderbird from responding to user events.

I've been trying to find how to make that callback run in a separate thread, without much luck.

Another alternative would be to write the callback object in C++ as an XPCOM component, but I wanted to make the extension as portable as possible. Creating a native XPCOM component would mean that I'd have to compile it for every platform I wish my extension to support. Too bad.

The quest goes on.

Default initializer for Hash entries

2005-02-02T11:11:00.000-08:00

zenspider made an interesting observation in a comment to my conditional initialization post. He suggests to use the following construct instead:

def initialize
@map = Hash.new { |hash, key| hash[key] = [] }
end

def addToList(key, val)
@map[key] << val
end

Yes, this is definitely more readable. This goes to show, as I mentioned in my reply to his comment, that when switching between languages we need to *think* in the new language. Performing direct "syntax translation" results the kind of code I posted earlier. The ability to think in a new language comes with practice, just like it does when switching "speakable" languages such as Spanish and English.

In the code above, we're passing a block to the new method of Hash. This block is invoked by the hash object whenever an entry that doesn't exist is requested, and the item returned is the value returned by the block (in this case, the result of evaluating hash[key] = [], that is, []).

The only disadvantage here is that any time we try to get the value associated with a key, an entry is created in the hashmap. So it really depends on how the hash is going to be used in the larger context of the program.

Anyway, it's a cool feature that I'm adding to my bag of tricks.

Quack, quack

2005-02-01T13:49:00.000-08:00

If it walks like a duck and quacks like a duck, then it must be a duck.

The type systems of Java and Ruby are very different. First and foremost, Java is more statically-typed than Ruby. Then there or other features that pull them appart, such as the fact that in Ruby everything (or almost) is an object, while in Java there are some things that don't qualify as such (primitive types, functions). But there's a more more fundamental, philosophical, difference; namely, the intention behind the type systems.

First of all, let me make a subtle but important distinction that will help understand what comes next. When I refer to the class of an object, I'm talking about the class it was created from. For instance, in Java, new String() creates an object of class String, just like String.new does in Ruby. The type of an object is the set of roles the object can play. Thus, the type of a class is not the same as the class, but typically includes it.

Java uses inheritance (loosely speaking) as the mechanism for defining the type of an object. An object "is a" X if it implements X. While Ruby also supports inheritance, establishing "is a" relationships is not its main purpose. In Ruby an object is of a certain type if it behaves as that type. Thus the saying "if it walks like a duck and quacks like a duck, then it must be a duck" or as it is commonly called, Duck typing. It must be noted, however, that while Ruby has classes, objects are not explicitly declared of to have a certain type.

So, what, concretely, defines what type an object is in Ruby? Well, that's the wrong question to ask. But if you'd still like to hear an answer, an object, conceptually, is of N! types (made of the subsets of all the combinations of methods exposed by the object), where N is the number of methods exposed by the the object,

In a sense, Ruby shifts the notion of type to the client (the client being the code that uses a given object). Thus, an object is (or not) of the type required by client if it implements the operations required by the client.

Ruby types are more granular as well, with the method being the atomic component of the type. In contrast, Java types are defined class by class, interface by interface.

Of course, this is all possible because Ruby is dynamically typed. That, together with the executable definitions concept I posted about before also allows type to vary by object. In Java, all objects created from the same class have the same type, and that type includes the class. In Ruby that may not be so. Look at this piece of code:

class SomeClass
    def method
        puts "within method"
    end
end

value = SomeClass.new
value.method # prints out "within method"

class << value
    private :method
end

value.method # fails with "NoMethodError: private method `method' called for ...

Definition-time, execution-time, anytime!

2005-02-01T12:37:00.000-08:00

From "Programming Ruby", by David Thomas and Andrew Hunt:

The important thing to remember about Ruby is that there isn't a big difference between “compile time” and “runtime.” It's all the same. You can add code to a running process. You can redefine methods on the fly, change their scope from public to private, and so on. You can even alter basic types, such as Class and Object.

To this, I would like to add that Ruby blurs the distinction between definition-time and runtime. While definition-time may resemble, and frequently overlap, compile-time, there's a subtle difference.

In Java and other compiled languages, it is the compiler who interprets the class definition and produces an internal representation that the runtime portions will use. In contrast, in Ruby, it is the interpreter the one who does this. But more importantly, the class and method definitions are executed. As opposed to being parsed to extract the definitions before the code starts to execute.

In that sense, a class and method definition is part of the executable code, and the line between definition and actual code begins to fade.

It is this simple concept that enables Ruby to programs to create classes, add methods and attributes to classes and objects at runtime.

To illustrate these points, consider this piece of code:

c =
     class SomeClass
         attr :value
         self
     end

Before analyzing the code, remember that in Ruby every statement returns a value. In the case of a class definition, the value returned is the result of the last evaluated line.

When the Ruby interpreter sees this above code, it defines a class named SomeClass, creates an getter and setter for an attribute named value and assigns the result of evaluating self(i.e., a reference to SomeClass itself) to c.

And then we can also do the following:

obj = c.new
def obj.aMethod
puts "Custom-made method"
end

This example reinforces the notion that definitions are executable code, and can intermingled arbitrarily with regular code(emphasized because in Ruby there's no such thing as regular code).

Executable definitions is a simple, but powerful concept. I'm still trying to understand all its implications and possibilities it opens.

Strong/Weak vs Static/Dynamic typing

2005-02-01T11:23:00.000-08:00

During the past week, while imbuing myself with Ruby knowledge, I came across a few discussions about the nature of Ruby vs that of other languages such as Java, Python, Perl, etc. Most of those discussions centered around the type systems in each language.

It seems quite common for people to mix the concepts of strong/weak and static/dynamic language typing. Let me clarify, these are two different categories, almost orthogonal to each other. A language can be strongly-typed and dynamically-typed at the same time.

Static vs Dynamic

Informally, a statically typed language enforces type consistency at compilation time, whereas a dynamically typed language defers this until runtime. In reality, there's a wide gamut of "typing dynamism" so it would be incorrect to say that every language falls into either category. At one end of the spectrum lie languages such as ML or Haskell; at the other end, languages like Lisp. Java and C++ lie close to the statically-typed end, whereas Ruby and Python lie close to the opposite end.

Here's an example of dynamic typing, in Ruby:

class Car
     attr :price
end

class Apple
     attr :price
end

def calculateTotalPrice(item, quantity)
     item.price * quantity
end

car = Car.new
car.price = 300
calculateTotalPrice(car, 2)

apple = Apple.new
apple.price = 2
calculateTotalPrice(apple, 12)

The type of the arguments to calculateTotalPrice are not bound or even checked at compile type. That determination is left till the moment the method is actually called.

With a statically typed language, on the other hand, the type of the actual parameters must match those of the formal parameters in a call. The example above could be rewritten in Java as:

class Item {
     float price;
}

class Car extends Item { }

class Apple extends Item { }

class Calculator {
     float calculateTotal(Item item, int quantity)
     {
         return item.price * quantity;
     }
}

The difference here is the introduction of the Item superclass and typed arguments for calculateTotalPrice. Trying to call that function with anything that is not an Item will fail at compile time. Disclaimer: this is not a good way to use inheritance, since it involves bringing two unrelated classes under the same hierarchy just for interface compliance. It's just an example to illustrate static typing without excesive boilerplate.

Here's a simpler example. In Ruby it we can do:

class Car; end
class Apple; end

obj = Car.new
obj = Apple.new

The type of obj is determined at runtime, based on what object it points to.

The Java equivalent would be:

class Car {}
class Apple {}
...

Car car = new Car()
Apple apple = new Apple()

car and apple are variables of type Car and Apple, respectively. Attempting to assign new Car to apple would fail at compile-time.

Of course one could replace the type of all variables with Object, effectively turning the language into a dynamically-typed one. That's one of the reasons why Java is not at the end of the spectrum, but close to it.

Strong vs Weak

It is a little harder to define what a strongly vs weakly typed language is, but it revolves around the notion of how much effort does the language put into checking type consistency (either at runtime or compile time). In this sense, Java and Ruby are both strongly typed, whereas Javascript is weakly typed.

In Ruby, it is possible to access only to methods and attributes that have been defined in a class or added to an object at runtime:

def ColoredObject
attr :color
end

obj = ColoredObject.new
obj.color = "blue"

Attempting to access a method or attribute not defined explicitly for the class or object will cause a runtime error.

On the other hand, in weakly typed languages such errors will go unnoticed. For example, in JavaScript it is possible to access an attribute that doesn't exist in an object (it will be created on the fly):

var obj = new Object();
obj.color = "blue";

Some may say this is a feature. But it has its dangers (a simple typo can be very hard to detect and find).

Ruby seems to capture the best of both worlds. While being a strongly typed language, it has a mechanism for adding methods and attributes to objects at runtime (whether even compile time exists in Ruby is the topic of another discussion :) ):

class Car
end

car = Car.new
car.color = "blue" # fails with "NoMethodError: undefined method `color=' for #"

# let's add an attribute named "color"
def car.color= (value)
@color = value
end

car.color = "blue" # succeeds

Breaking the code

2005-01-29T23:09:00.000-08:00

As a follow-up to my previous post, I'd like to describe how the I broke the GCHQ code. All it took was a bit of luck, some detective work and some programming.

The first time I saw the challenge, I skimped over the names to get a feel for it, without any intention of actually trying to solve it. It was pretty obvious to me, though, that the names had been encrypted with some kind of substitution cypher.

And then I saw the tip-off... BZGZD A'GAANZ. That had to be an irish-like name, so the A would be and encrypted O. Consequently, the last name would have to have the form O'xOOxx. Peter O'Toole immediately came to mind, although I didn't initially remember who he was. But the name sounded so familiar. I googled for it and it turned out he was an actor. Then I remembered :), and I was hooked.

I looked at the other names carefully, trying to spot easy ones, like KHP FNWHQBEV. With three distinct letters in the first name, I couldn't think of anything else than "Kim". Kim Basinger came to mind, and it fit nicely.

It was then that I decided to write a program to automate the discovery. I needed the program to take a name as input and match it to each name in the list. The question was how to do this efficiently. I realized that when dealing with substitution cyphers, an unencrypted string has the same form as the encrypted version. For example, PETER could be described as a sequence of characters [a, b, c, d, e] where a = P, b = d = E, c = T, e = R. It can be rewritten as [a, b, c, b, e], or "abcbe". In a sense, this sequence is a canonical form for the string. This (Ruby) code snippet will do the transformation:

def canonicalForm(chars)
     map = {}
     currentIndex = 64
     result = ""
     chars.each_byte { |char|
         if not Regexp.new("[' ]") =~ char.chr
             index = map[char] ||= (currentIndex += 1)
         else
             index = char
         end
         result << index
     }
     return result
end

A string and its encrypted version will both have the same canonical form. For instance, for PETER O'TOOLE and BZGZD A'GAANZ, the canonical form is ABCBD E'CEEFB.

The original version was quite primitive... if you fed it a name it would tell you which, if any, encrypted names matched. I discovered a few names with this approach. At first I thought the actors and actresses were Oscar winners, but I quickly dropped that hypothesis when I encountered "Kirsten Dunst". Given that she performed in Spiderman, I decided to try "Tobey Maguire". Direct hit! So my new theory was that an actor and actress that had performed in the same movie would be paired together. But I had to test it.

That's when I came up with the second version of the program, one that would build the cypher given a string and its encrypted version. For example, if I provided it with TOBEY MAGUIRE and DYFJN WCLEQPJ, it would produce

CF..J.L.Q...W.Y..P.DE...N.
The dots represent unknown substitutions. If I did the same with Kirsten Dunst, I'd get

...HJ...Q.U..X...PIDE.....
If you take a close look at the cyphers, you'll notice that they look awfully similar (the J, Q, P, D, and E are in the same positions). If you merge them, you get

CF.HJ.L.Q.U.WXY..PIDE...N.
Also, you'll note that the merged cypher is very regular and that the letters seem to be, up to a point, in alphabetical order. We can confidently fill in some of the missing spaces, for only one letter seems to fit:

CFGHJKL.Q.UVWXY..PIDE...N.
The last portion is suspiciously close to Spiderman, the name of the movie. That was one of the tell-tale signs that confirmed that the cyphers were unique to each pair, and that they were built from the name of the movie. Completing the cypher with the missing letters from Spiderman we get

CFGHJKL.Q.UVWXY.SPIDERMAN.
That leaves only a few letters left, which, again, we can detemine unequivocally:

CFGHJKLOQTUVWXYZSPIDERMANB

Some names were still missing their pair. I was able to infer a few by applying the cyphers of the still-unpaired names to the remaining encrypted names. For example, the cypher for Sean Connery produced .ONOR...AC..AN when decrypting one of the names. .ONOR could be nothing else than "Honor", so I queried www.imdb.com for all the people named that way. The first entry in the list was "Honor Blackman". Another direct hit!

At this point I was out of luck. I had no idea how to decrypt the remaining names and I had tried with all the actors and actresses I could remember. That's when I decided to investigate if IMDb had a programmatic interface. It did not, but it was possible to download the list of all known actors and actresses in a text file. Oh yeah, baby!

The third incarnation of the program would parse the text files and attempt to decrypt each of the remaining names with each of the names in the file. Surprisingly, some names produced unambiguous translations, but others resulted in dozens of alternatives. And I was not going to try one by one.

During the few minutes I spent thinking about how to best tackle the problem ahead I contemplated a couple of alternatives and I made an interesting discovery: if I picked any name (with Ae and Ad being the encrypted and decrypted versions, respectively) and another name B (with Be and Bd following the same rule as A), such that A and B are encrypted with the same cypher, the concatenation of Ae with Be has the same canonical form as the concatenation of Ad with Bd. If you stop to think about it for a second it, it makes perfect sense. Just consider what happens within a name. The encrypted and decrypted versions of the first name have the same canonical form. If we add the last name, which is written in terms of the standard alphabet in the decrypted version, and in a non-standard alphabet resulting applying the cypher on the standard alphabet, the strings are still isomorphic (i.e., they have the same canonical form). Thus, it follows that if we add a full name to each of the strings, each in their respective alphabet, the result will still be two isomorphic strings.

In the fourth incarnation, the program would pair up all the alternatives for the names that I hadn't been able to decrypt and make sure that their concatenation was isomorphic with the contatenation of the encrypted versions. Amazingly, the program produce one and only one pairing for each name! I was done with the first step.

Next, I had to figure out what were the names of the movies, since I had a hunch that the hidden quotation would be buried somewhere within the cyphers. I could've written a program to extract this information from the IMDb text files, but they are not well structured and I considered that it would take me longer to figure out how to parse them than to query IMDd. It did take some going back and forth in IMDb, but it wasn't that bad. Plus, I had already figured out most of the names, anyway.

Finding the hidden quotation took me a while, though. I tried everything I could possibly think of, to no avail. Then, it simply clicked. I looked at the release dates of the movies and noticed they were all different, and ranged from the 40's up to the present day. That could imply only one thing: they were meant to be sorted! And so I did. I sorted the cyphers based on the release date, in ascending order. And it didn't take me long to realize that the quote was in the diagonal of the matrix formed by the cyphers.

no that protected, it seems

2005-01-29T12:36:00.000-08:00

During a conversation with Diego today, he pointed out that the protected qualifier in Java does not prevent access to classes within the same package.

That was news to me. I always thought protected limited the access to subclasses of the class that contains the protected member.

As Diego points out in his weblog, it seems the Java Language Specification is incomplete. The ambiguity is actually cleared up in section 6.6.1 of the spec:

A member (class, interface, field, or method) of a reference (class, interface, or array) type or a constructor of a class type is accessible only if the type is accessible and the member or constructor is declared to permit access:

If the member or constructor is declared public, then access is permitted. All members of interfaces are implicitly public.
Otherwise, if the member or constructor is declared protected, then access is permitted only when one of the following is true:

Access to the member or constructor occurs from within the package containing the class in which the protected member or constructor is declared.
Access is correct as described in §6.6.2.

Amazon Gold Box ... gone

2005-01-29T09:03:00.000-08:00

I just realized that Amazon has yanked the Gold Box feature from their site.

In the past two or so years I occasionally opened the gold box in search of a good deal. And never was I offered anything I may have remotely wished for. Items such as power tools, kitchen appliances and jewelry were common.

One would think the gold box would offer deals for items that were in one's wish list or related to stuff bought in in the past. Quite the opposite, items I had never even browsed for showed up.

I say, good riddance.

Solution to the GCHQ challenge

2005-01-27T21:09:00.000-08:00

As promised, here's the solution to the challenge.

The names in the two lists are those of actors and actresses. They are encoded using a simple substitution cypher. There's one cypher for each pair of men and women, built from the name of the movie they performed in together. These are the translations:

Men
QJAMDU WWVDU	MICKEY ROONEY
KCRVKXHL EUJDXZ	HUMPHREY BOGART
XCT GSXXJYUQ	REX HARRISON
JRFJWRI XFCS	GREGORY PECK
NRIKUSL UIQORMDB	CHARLES LAUGHTON
QFDX ORNQTP	TONY CURTIS
UFIV WKXXZY	JACK LEMMON
HYUE WREEYCS	SEAN CONNERY
WKNJVWL GSWOXU	RICHARD BURTON
BZGZD A'GAANZ	PETER O'TOOLE
VTWMAC UEIIML	ALBERT FINNEY
ZGRT BPDIIRNN	ALEC GUINNESS
XIVL VFBD	JOHN HURT
GMTHYL IKUBGMFPTPSSPM	ARNOLD SCHWARZENEGGER
OFIIPTYX LYIJ	HARRISON FORD
RNBTCNP TCOSHNM	ANTHONY HOPKINS
KEZHQ WSNIEC	KEVIN SPACEY
LVZD CONKLNFK	EWAN MCGREGOR
DYFJN WCLEQPJ	TOBEY MAGUIRE
PZSS TEBBMJ	BILL MURRAY

Women
LRNU FHZOHVN	JUDY GARLAND
MTJXMG EHXJRDT	INGRID BERGMAN
OSXFSXCZ XBZGCXDUXA	MARGARET RUTHERFORD
YAERFI KFXBARV	AUDREY HEPBURN
AIKUSBS EHSMKHNR	MARLENE DIETRICH
CZNTBXD CFDNFE	MARILYN MONROE
AQSEWKC XFIWFSYK	SHIRLEY MACLAINE
ORERC VIUWFNUE	HONOR BLACKMAN
BQKDVGBOJ OVIQXW	ELIZABETH TAYLOR
OUGEUDLRZ EZBVJDR	KATHARINE HEPBURN
TVFAMI WVYVTT	LAUREN BACALL
TZMMDR WDNCRM	CARRIE FISHER
CWUIFBLSK HSOGSB	SIGOURNEY WEAVER
YVTLG UGZVYNHT	LINDA HAMILTON
RKUUC VHMPUUPT	KELLY MCGILLIS
ECWHX YCMBXA	JODIE FOSTER
KHP FNWHQBEV	KIM BASINGER
DGOFBL AGUCZD	NICOLE KIDMAN
UQPIDJX HEXID	KIRSTEN DUNST
CQMBSVDD LNYMICCNI	SCARLETT JOHANSSON

And here's how they relate to each other and the name of each movie:

STRIKE UP THE BAND	MICKEY ROONEY	JUDY GARLAND
CASABLANCA	HUMPHREY BOGART	INGRID BERGMAN
BLITHE SPIRIT	REX HARRISON	MARGARET RUTHERFORD
ROMAN HOLIDAY	GREGORY PECK	AUDREY HEPBURN
WITNESS FOR THE PROSECUTION	CHARLES LAUGHTON	MARLENE DIETRICH
SOME LIKE IT HOT	TONY CURTIS	MARILYN MONROE
THE APARTMENT	JACK LEMMON	SHIRLEY MACLAINE
GOLDFINGER	SEAN CONNERY	HONOR BLACKMAN
WHO'S AFRAID OF VIRGINIA WOOLF	RICHARD BURTON	ELIZABETH TAYLOR
THE LION IN WINTER	PETER O'TOOLE	KATHARINE HEPBURN
MURDER ON THE ORIENT EXPRESS	ALBERT FINNEY	LAUREN BACALL
STAR WARS	ALEC GUINNESS	CARRIE FISHER
ALIEN	JOHN HURT	SIGOURNEY WEAVER
THE TERMINATOR	ARNOLD SCHWARZENEGGER	LINDA HAMILTON
WITNESS	HARRISON FORD	KELLY MCGILLIS
THE SILENCE OF THE LAMBS	ANTHONY HOPKINS	JODIE FOSTER
LA CONFIDENTIAL	KEVIN SPACEY	KIM BASINGER
MOULIN ROUGE	EWAN MCGREGOR	NICOLE KIDMAN
SPIDERMAN	TOBEY MAGUIRE	KIRSTEN DUNST
LOST IN TRANSLATION	BILL MURRAY	SCARLETT JOHANSSON

The cyphers are created by taking the name of the movie, capitalizing it, removing duplicate letters and completing the string with the missing letters from the alphabet, in alphabetical order. The string is then shift-rotated by a certain number of positions.

For example, if the movie is "The silence of the lambs", we get "THESILNCOFAMB" after the first two steps. We then add the missing letters and obtain "THESILNCOFAMBDGJKPQRUVWXYZ". The cypher is then shift-rotated to produce "RUVWXYZTHESILNCOFAMBDGJKPQ".

You may be wondering how is that used to encrypt the actor name. Simple, replace each letter in the name with the letter that appears in the cypher in the position that corresponds to the original letter's position in the alphabet. For instance, to encrypt an F we look at the 6th position in the cypher (F is the 6th letter of the alphabet) and find a Y.

To find the hidden quotation we first listing all cyphers to form a matrix (26x20). They should be sorted according to the movie release date, in ascending order. The hidden quotation can be read from the diagonal of the matrix, starting top-left corner and going down and to the right. The phrase reads "Here's looking at you, kid", a quote from Casablanca.

HBANDCFGJLMOQVWXYZSTRIKEUP	STRIKE UP THE BAND
DEFGHIJKMOPQRTUVWXYZCASBLN	CASABLANCA
SPRACDFGJKMNOQUVWXYZBLITHE	BLITHE SPIRIT
YBCEFGJKPQSTUVWXZROMANHLID	ROMAN HOLIDAY
ITNESFORHPCUABDGJKLMQVXYZW	WITNESS FOR THE PROSECUTION
ZSOMELIKTHABCDFGJNPQRUVWXY	SOME LIKE IT HOT
FGIJKLOQSUVWXYZTHEAPRMNBCD	THE APARTMENT
UVWXYZGOLDFINERABCHJKMPQST	GOLDFINGER
VGNLBCEJKMPQTUXYZWHOSAFRID	WHO'S AFRAID OF VIRGINIA WOOLF
UVXYZTHELIONWRABCDFGJKMPQS	THE LION IN WINTER
VWYZMURDEONTHIXPSABCFGJKLQ	MURDER ON THE ORIENT EXPRESS
ZSTARWBCDEFGHIJKLMNOPQUVXY	STAR WARS
OPQRSTUVWXYZALIENBCDFGHJKM	ALIEN
GJKLPQSUVWXYZTHERMINAOBCDF	THE TERMINATOR
FGHJKLMOPQRUVXYZWITNESABCD	WITNESS
RUVWXYZTHESILNCOFAMBDGJKPQ	THE SILENCE OF THE LAMBS
NFIDETBGHJKMPQRSUVWXYZLACO	LA CONFIDENTIAL
ZMOULINRGEABCDFHJKPQSTVWXY	MOULIN ROUGE
CFGHJKLOQTUVWXYZSPIDERMANB	SPIDERMAN
MPQUVWXYZLOSTINRABCDEFGHJK	LOST IN TRANSLATION

Here's a Ruby script to automate the decryption process. You'll also need to get the list of movies and the actors.list and actresses.list files from IMDB's text database.

Conditional initialization in Ruby

2005-01-26T14:49:00.000-08:00

Exploring Ruby further, I came accross the || operator. It behaves like the boolean or operator in other languages (Java, C++) but with a catch: it returns the value of the last evaluated term. Since evaluation is lazy (from left to right), the last evaluated term is either the first non-false (I'll qualify this later on, bear with me) term or the last term in the expression.

More concretely, the expression d = a || b || c will assign the value of a to d if a is non-false, the value of b if a is false and b is non-false, or the value of c otherwise.

A non-false value in Ruby is anything that's neither nil, nor false. Thus, values such as true, 1, 0, "a", [] are all non-false.

The || operator can be combined with the = operator in a self-assignment statement: a ||= expression, which is a shorthand for a = a || expression.

A statement of that kind is essentially a conditional initializer: if a is nil (i.e., not initialized), initialize it with the value of expression. Otherwise, leave it untouched.

The conditional initialization idiom has at least one interesting usage. Before we get to it, it is important to note that in Ruby every statement returns a value, which means that any statement can be used in place of an expression. For example, one could conceivably do:

(if true then 8 end) + 3

Ok, on to the example now...

It is common to have to keep track of lists of items associated with certain key values. The obvious way to implement that is with a map of keys to lists of values. In Java, the code for adding an element to such structure would typically look like this:

void addToList(Object key, Object value)
{
    List list = (List) this.map.get(key);
    if (list == null) {
         list = new ArrayList();
         this.map.put(key, list);
     }

     list.add(value);
}

In Ruby, using the conditional initialization idiom, it could be written more compactly as:

def addToList(key, value)
(@map[key] ||= []) << value
end

The @map[key] ||= [] piece performs the conditional initialization of the list associated with key and the (...) << value part adds the value to the existing or newly created list.

Ok, ok... you might be thinking, while the Java syntax is more verbose, is certainly more readable. That may be true, but in that case you could still write:

def addToList(key, value)
list = (@map[key] ||= [])
list << value
end

Which is still more compact than in Java but in my opinion does not sacrifice readability.

Pretty neat, eh?

Babbler

2005-01-25T20:25:00.000-08:00

Here's a useless cute little program I wrote yesterday, called "Babbler", which creates new text based on how patterns of characters appear in a piece of text used to train the program. It is a Markov generator, which means that it uses the last N (N being the order) produced characters to determine which character comes next.

During training, Babbler analyzes all sequences of 1, 2, ... N characters and records the number of times each shows up in the original text.

To generate a character, it picks one at random from the set of all characters that may follow the sequence of the last N-1 output characters. The random function honors the frequency distribution of the characters in the source text. If the sequence of N-1 characters hasn't been seen in the source text, the program falls back to a N-2 sequence and so on.

Let's see an example. Using the book "The Prince" by Nicolo Machiavelli as training data, here's a fragment generated by an order-1 Babbler:

"gstkln tyeannioi rfa iaeafalrtutficbah tat eri de oesowaitpt neeff p odhi nn .ett borege r susnhsardlreneftgbnwauihn"

This is garbage. Essentially, an order-1 Babbler generates random characters based on their frequency in the source text. It gets better with higher order Babblers:

Order 2: "pom so owins ase is ibend antusirty hothlest r t nnd cthoath we wnt ony as y sizistaul, cos."
Order 3: "sse mays ing per bringet beforgeopers to st yound thus en of wily pir i same of cousembing of the vin to came they caussuccul is much aggrands"
Order 4: "runnibaldo, whers, count, and in had the for of meason thirds heles, markable in ought a luccion of france cound seat to blus, on of his rose they againtate trodus, he prince them will for have thing thould by have he abilitated the prince fro"

Here you can see that words start taking a definite english-like form -- they can be pronounced in english -- even if they are meaningless. Compare this to an order-4 Babbler trained with Don Quijote, by Cervantes (a well-known Spanish writer):

"no la tale pensigida, porque vaya ena gana, sea desto, y, aun llencio que durmino a mayor de su mores quelevas ciel tien del me dar locura razos mucho malano que alma: no hacer punto de me de sea; pensaminea quijo me hartida"

Lastly, here's an order-5 Babbler for The Prince:

"oned again they always or maste; and not. in 1510. thing except down they have saw the duke, and was defend when case helples. fifteen very were admitted by those offerent him outral; and intered himself anothing his notwith him near again"

The input to Babbler is a tokenizer object, which must implement the each() method. This allows for babbling randomly selected characters (what I've shown you so far) or words. Here's an example of an order-4 Babbler that uses entire words as tokens:

"should now take part; but nothing being concluded, Oliverotto da Fermo was sent to propose that if the duke wished to undertake an expedition against Tuscany they were ready; if he did not wish that the fortresses, which he did not recognize any need for doing so, he begged Castruccio to pardon the other members of his family by reason of the wrongs recently inflicted upon them."

If you're interested, here's the source: babbler.rb. It's written in Ruby, but may contain many Javaisms due to the fact I'm still getting used to the language (I started learning Ruby this weekend and this is my version of a "Hello World" -- on steroids)

Emulating keystrokes in Windows

2005-01-21T21:58:00.000-08:00

One of the core functions in Shoot, a voice command program I wrote a couple of years ago, is the ability to emulate key presses programmatically.

There is a fairly straightforward way to do this in Windows 2000/XP, via the SendInput Win32 function. In Windows 98/ME things are somewhat more complicated: SendInput inserts the keystrokes in the Windows event queue, but DirectInput bypasses it and hooks directly into the keyboard driver.

As a result, any keystroke sent via SendInput is completely ignored by DirectInput applications. Pretty much every modern Windows-based game uses DirectInput, the main target for Shoot. The solution is to implement a Virtual Device Driver (VxD) that inserts the keystrokes directly into the keyboard driver buffer, and that is what I ended up doing for Shoot.

Here's how to use the SendInput function from C#. I stripped all the Win98/ME-related code. Not only would it make the code below significantly more complex, but it's probably useless by now. Who's using Win 98, anyway? Not even Microsoft supports it anymore :)

[StructLayout(LayoutKind.Sequential)]
private struct KEYBOARD_INPUT {
public uint type;
public ushort vk;
public ushort scanCode;
public uint flags;
public uint time;
public uint extrainfo;
public uint padding1;
public uint padding2;
}

[DllImport("User32.dll")]
private static extern uint SendInput(uint numberOfInputs, [MarshalAs(UnmanagedType.LPArray, SizeConst=1)] KEYBOARD_INPUT[] input, int structSize);

void press(int scanCode)
{
  sendKey(scanCode, true);
}

void release(int scanCode)
{
  sendKey(scanCode, false);
}

private void sendKey(int scanCode, bool press)
{
   KEYBOARD_INPUT[] input = new KEYBOARD_INPUT[1];
   input[0] = new KEYBOARD_INPUT();
   input[0].type = INPUT_KEYBOARD;
   input[0].flags = KEY_SCANCODE;

   if ((scanCode & 0xFF00) == 0xE000) { // extended key?
     input[0].flags |= KEY_EXTENDED;
   }

   if (press) { // press?
     input[0].scanCode = (ushort) (scanCode & 0xFF);
   }
   else { // release?
     input[0].scanCode = scanCode;
     input[0].flags |= KEY_UP;
   }

   uint result = SendInput(1, input, Marshal.SizeOf(input[0]));

   if (result != 1) {
     throw new Exception("Could not send key: " + scanCode);
   }
}

Java tip #1

2005-01-21T08:23:00.000-08:00

Working with Swing JTables can be tricky. Working with custom cell editors is even trickier. Here's a tip that may save you some time and frustration.

This is a custom cell editor (based on a text field) that will automatically highlight its contents as soon as it is becomes active and save the user from having to select the text with the mouse or with the all-too-common "home - shift+end" key sequence.

The trick is to select the text after the editor gets focus. Otherwise, the JTextField object will ignore the request.

Here's the code:

private class CustomTableCellEditor
    extends DefaultCellEditor
{
  public CustomTableCellEditor()
  {
     // use a JTextField as the actual editor
     super(new JTextField());
     final JTextField editor = (JTextField) getComponent();

     editor.setName("Table.editor");
     editor.setBorder(new LineBorder(Color.black));

     // listen for focusing events
     editor.addFocusListener(new FocusListener()
     {
       public void focusGained(FocusEvent e)
       {
         // now is the time to select the text in the JTextField
         editor.selectAll();
       }

       public void focusLost(FocusEvent e) { }
     });
   }

   public Component getTableCellEditorComponent(JTable table, Object value, boolean isSelected, int row, int column)
   {
     final JTextField textField = (JTextField) super.getTableCellEditorComponent(table, value, isSelected, row, column);

     Runnable task = new Runnable() {
       public void run()
       {
         // set the focus on the JTextField
         textField.requestFocusInWindow();
       }
     };
     SwingUtilities.invokeLater(task);

     return textField;
   }
}

GCHQ challenge

2005-01-20T15:10:00.000-08:00

The GCHQ posted the following challenge a couple of months ago:

What is the connection between the men in the first list and the women in the second list? Which man pairs with which woman? And what is the hidden quotation?

MEN

KCRVKXHL EUJDXZ

WKNJVWL GSWOXU

HYUE WREEYCS

QFDX ORNQTP

VTWMAC UEIIML

OFIIPTYX LYIJ

ZGRT BPDIIRNN

XCT GSXXJYUQ

RNBTCNP TCOSHNM

XIVL VFBD

NRIKUSL UIQORMDB

UFIV WKXXZY

DYFJN WCLEQPJ

LVZD CONKLNFK

PZSS TEBBMJ

BZGZD A'GAANZ

JRFJWRI XFCS

QJAMDU ZWWVDU

GMTHYL IKUBGMFPTPSSPM

KEZHQ WSNIEC

WOMEN

TVFAMI WVYVTT

KHP FNWHQBEV

MTJXMG EHXJRDT

ORERC VIUWFNUE

AIKUSBS EHSMKHNR

UQPIDJX HEXID

TZMMDR WDNCRM

ECWHX YCMBXA

LRNU FHZOHVN

YVTLG UGZVYNHT

YAERFI KFXBARV

OUGEUDLRZ EZBVJDR

CQMBSVDD LNYMICCNI

DGOFBL AGUCZD

AQSEWKC XFIWFSYK

RKUUC VHMPUUPT

CZNTBXD CFDNFE

OSXFSXCZ XBZGCXDUXA

BQKDVGBOJ OVIQXW

CWUIFBLSK HSOGSB

I've already solved it, but I'm not going to tell you the answer yet. I'll post it here after the window for submitting the solution to GCHQ has closed.

What are you waiting for, get those brain cells working!

Garmin iQue 3600a

2005-01-19T12:52:00.000-08:00

Garmin has unveiled a new GPS gadget, the iQue 3600a. It's a Palm device with GPS capabilities and a bunch of aviation-related software. It looks great, if you ask me, although it's a little bit pricey at $1100.

I've been on the lookout for a GPS device lately, and the best candidate so far was the Garmin GPSMAP 296. The iQue has all the functions a regular Palm has, such as adress book and calendar, which, in my opinion tilt the balance against the 296 (plus the fact that the latter costs $1700).

From the specs I couldn't see anything significant in the 296 that's missing in the iQue. In fact the iQue features a nifty 16-bit color screen (65536 colors) vs. 296's 8-bit (256 colors) screen.

For in-cockpit and outdoors use the 296 may be more robust (better shock resistance, weather-proof, longer battery life), but for regular day-to-day use, the iQue seems like a great contender.

Finally, I'm sure Garmin will make an SDK available for the 3600a soon. It's available for the 3600, and I'd be surprised if it doesn't already support the 3600a, so it may just be a matter of certification. The device runs PalmOS and the iQue 3600 page claims that all GPS-related functions are available to third-party software. Sweeeet!

out for a spin

2004-12-12T20:36:00.000-08:00

I took a couple of friends flying yesterday. It was a beatiful day, after a few weeks of bad weather. That meant, of course, that everybody had to come up with the same idea.

The airport was extremely crowded. We were 3rd in the takeoff sequence, with at least 4 airplanes waiting after us. 3 airplanes landed in the short period before our turn came up.

We left the airport to the north and got a "traffic 9 o'clock, 1 mile" advise from the tower before leaving Addison's airspace. Figuring the friendly skies would be as crowded as the ground, I turned my radio to the approach frequency to listen for nearby traffic as soon as we were clear of Class D airspace.

We cruised around for a bit, keeping a watchful 3 sets of eyes (it's always a good idea to have your passengers look out for traffic as well) on the space around us. When flying under VFR (visual flight rules), it's the pilot's responsibility to see and avoid other aircraft, even when talking to ground-based controllers. The may occasionally advise about nearby traffic, but they are not required to do so. After all, they are not liable if you have an intimate encounter with another plane.

We did, indeed, come across a few other airplanes and had to maneuver to avoid getting too close to them. Other than that, our short trip was peaceful and uneventful.

As always, I really enjoyed the flight, which was a welcome break from the more demanding aerobatic training I've been working on for the past couple of months.

learning to cherish

2004-12-09T14:35:00.000-08:00

I took this picture a few months ago. Needless to say, it's one of my favorites.

backing up digital pictures

2004-12-09T11:28:00.000-08:00

I have a 6 megapixel digital camera. Each picture I take uses up around 6 mb of disk space (at the highest quality, RAW format) and I've already shot almost a thousand.

Backing up that amount of data is becoming a royal pain in the butt. CDs are already too small. DVDs will soon be, too, at the rate at which I'm taking pictures. As a temporary measure, I'm storing all the images in my iPod and I will probably have to get an external drive.

My main concern is that soon I'm not going to be able to keep all my pictures in my puny laptop hard drive. I may need to get two external drives, instead, for primary and backup storage.

Or how does a RAID-5 disk array sound?

the great playlist meme of '04

2004-12-08T14:56:00.000-08:00

Here are the instructions:

Open up the music player on your computer.
Set it to play your entire music collection.
Hit the "shuffle" command.
Tell us the title of the next ten songs that show up (with their musicians), no matter how embarrassing. That's right, no skipping that Carpenters tune that will totally destroy your hip credibility. It's time for total musical honesty. Write it up in your blog or journal and link back to at least a couple of the other sites where you saw this.
If you get the same artist twice, you may skip the second (or third, or etc.) occurrences. You don't have to, but since randomness could mean you end up with a list of ten song with five artists, you can if you'd like.

Here's my list:

Down To The Waterline - Dire Straits
Cerca De La Revolución - Charly García
Entre Caníbales - Soda Stereo
I Can't Tell You Why - The Eagles
Englishman In New York - Sting
Stuck In A Moment You Can't Get Out Of - U2
Quizas Porque - Sui Generis
Big Shot - Billy Joel
Que Hago Ahora (Dónde Pongo Lo Hallado) - Silvio Rodriguez
Pennyroyal Tea - Nirvana

via Diego

Stack trace translation using annotations

2004-12-08T12:10:00.000-08:00

Code generators and compilers that use Java as an intermediate language (e.g, JSP compilers) can take advantage of the new Java annotations feature for translating stack traces.

Why is this necessary? Any runtime error in the form of an exception will have its stack trace expressed in terms of the intermediate java code. Troubleshooting the problem could become a nightmare, unless the line and number information is presented in the context of the components and methods originally written by the developer.

In simple terms, the idea is to place line number information in metadata blocks in every class generated by the compiler. This information is accessed during runtime to interpret and translate stack traces back into something the developer will understand.

Let's consider a hypothetical component called "MyObj" that has two methods: "methodA" and "methodB". Here's an example of what the intermediate Java code might look like:

@TranslationTable(lines = {
  @Entry(line=11,component="MyObj",method="methodA",sourceLine=241),
  @Entry(line=12,component="MyObj",method="methodA",sourceLine=247),
  @Entry(line=13,component="MyObj",method="methodA",sourceLine=249),
  @Entry(line=18,component="MyObj",method="methodB",sourceLine=340)
})
public class AutogeneratedObject
{
  void autogeneratedMethod1()
  {
     int a = 1;
     int b = 2;
     autogeneratedMethod2();
  }

  void autogeneratedMethod2()
  {
     throw new RuntimeException();
  }
}

The metadata block is made of a tag (@TranslationTable) that contains a list of sub-tags (@Entry). Each entry represents a line of significant code in the generated class. Information about the line number in the generated class and the name of the original component, method and line number it maps to are stored in each entry.

Here's the definition of the Entry tag:

import java.lang.annotation.*;

@Retention(RetentionPolicy.RUNTIME)
public @interface Entry
{
  int line();

  String component();
  String method() default "[unknown]";
  int sourceLine();
}

And here's the TranslationTable tag:

import java.lang.annotation.*;

@Retention(RetentionPolicy.RUNTIME)
@Target(ElementType.TYPE)
public @interface TranslationTable
{
Entry[] lines();
}

The stack trace translator takes each stack frame, obtains the associated class, queries the class for it's TranslationTable metadata and looks up the TranslationTableEntry for the line reported by the stack frame.

This is what the stack trace translator might look like. I know, I know, the implementation very inefficient (linear traversals of the translation tables, no caching)... I'm just trying to make a point here :)

StackTraceElement[] translate(StackTraceElement[] elements)
{
  List result = new ArrayList();

  for (StackTraceElement element : elements) {
     try {
       Class clazz = Class.forName(element.getClassName());
       TranslationTable table = (TranslationTable) clazz.getAnnotation(TranslationTable.class);

       boolean found = false;
       if (table != null) {
         for (Entry line : table.lines()) {
           if (line.line() == element.getLineNumber()) {
             result.add(new StackTraceElement(line.component(), line.method(), line.component(), line.sourceLine()));
             found = true;
             break;
           }
         }
       }

       if (table == null || !found) {
         result.add(element);
       }
     }
     catch (ClassNotFoundException e) {
       e.printStackTrace();
     }

  }

  return result.toArray(new StackTraceElement[0]);
}

If you're not in the mood for trying out the code, I already did it for you :). Here's a regular Java stack trace:

java.lang.RuntimeException
  at AutogeneratedObject.autogeneratedMethod2(Test.java:18)
  at AutogeneratedObject.autogeneratedMethod1(Test.java:13)
  at Test.main(Test.java:25)

And the translated version:

MyObj.methodB(340)
MyObj.methodA(249)
Test.main(25)

split-s

2004-12-08T08:16:00.000-08:00

... just make sure you're high enough

Photo by SSgt Bennie J. Davis III
Still Photographer, USAF