Archive

Help, this is driving me mad!

The Pragmatic Programmers have just started publishing an online magazine: PragPub. Among other things, it contains a quiz which in this issue tests your knowledge of programming languages.

I consider myself a bit of a languages geek, so I thought that I’d have no trouble with it. But it’s driving me mad!

The quiz consists of little snippets of code in different languages. The first letters of each language then spell out the name of another language.

I can get 5 of the 6, but one of them has me completely stumped. Even though I’m 99% sure what letter it’s name must start with.

Warning: Spoilers follow!

Continue reading ‘Help, this is driving me mad!’

Debug It! in beta

Debug It!

As you may know, I’ve been working on a book. It’s been a long process, but the finishing line is finally in sight – as of today, it’s available as a “Beta Book” from The Pragmatic Bookshelf:

http://pragprog.com/titles/pbdp/debug-it

This means that it’s available for purchase and download as a PDF and ebook, and the paper version can be pre-ordered. :-)

Blink versus The Decisive Moment

If, like me, you found Malcolm Gladwell’s Blink unsatisfying, I suggest that you take a look at The Decisive Moment by Jonah Lehrer.

Like Gladwell’s book, Lehrer gives several examples of instances where trusting our subconscious provides better results than thinking things through methodically and logically. And examples of the opposite, where our subconscious can be fooled and we need to be on our guard. So far, they have a great deal in common.

Where the books differ is that Lehrer delivers on the promise to tell you when to use one mode and when to use the other.

The iPhone 3G and Big Bangs

This article originally appeared upon on texperts.com

So the new 3G iPhone is here (for those of us lucky enough to win the O2 website lottery or patient enough to queue up on Friday morning, at least).

Although I’ve not yet had a chance to play with the 3G version, I’ve been very impressed with the version 2.0 software (apart from an annoying pause it seems to have introduced whenever I view my contacts).

But I am amazed! at the shambles that the launch has become.

One of the key insights of modern agile development methodologies (like Scrum, Extreme Programming and Crystal Clear) is that “big bang” releases are never a good idea. Instead, they use iterative, incremental releases. What Apple tried with the iPhone launch was the biggest of big bangs imaginable!

In one day, they tried to:

  • Release a new version of a handset globally
  • Release a new version of the desktop (Mac or PC) software which interfaces with that handset
  • Release a new version of the software running on existing handsets
  • Release a new version of the back-end server technology (MobileMe) supporting all the above

The upshot of all of this? Nobody could upgrade their handsets when O2’s systems collapsed under the load. Then people’s iPhones became bricks when upgrading to version 2.0. Then MobileMe was down for maintenance for much longer than intended and is still only limping along.

Anyone who has ever been involved in large software/IT projects could have worked out that this was guaranteed to happen. Big bangs don’t work. Why was Apple unable to forsee this?

The iPhone is a lovely device. But Apple have badly tarnished their reputation in my eyes.

Navigating the equality maze

This article originally appeared upon on texperts.com

Ruby Logo Ruby supports five (yes, five!) different ways to test for object equality. Why does Ruby need five different ways to test equality? What are they? How do they differ? How should they be used? When (and how) should they be implemented or overridden?

The actors take the stage

So, here are our choices:

  1. == (natural equality)
  2. equal? (object identity)
  3. eql? (hash equality)
  4. === (case equality)
  5. <=> (spaceship operator)

Object identity versus natural equality

Let’s start by looking at == and equal?. Object provides default implementations of both, both of which test for object identity (i.e. they return true if and only if an object is compared with itself) and both of which can be overridden.

So, what is the difference? The difference is entirely one of convention; by convention, equal? is not overridden whereas == is.

The intention is that == should be overridden to provide “natural” equality semantics (i.e. whatever you would naturally expect equality to mean in context). Normally this means value semantics in which == returns true if the two objects in question represent the same value, false otherwise. And this is exactly what most of the standard classes do; String for example:

s1 = 'test string'
s2 = 'test string'
 
s1.equal? s1
=> true
s1.equal? s2
=> false
s1 == s2
=> true

Just about every standard class overrides ==. Array, for example, overrides == to return true if and only if two arrays contain the same number of elements and each element is equal according to its own definition of ==. But it isn’t always as simple as this; the various numeric classes, for example, define == to return mathematically sensible results when comparing values of different types:

1 == 1
=> true
1.equal? 1
=> true
1.equal? 1.0
=> false
1 == 1.0
=> true

Hash Equality

Whereas == normally tests that two objects represent the same value, eql? should always do so. For example:

1 == 1.0
=> true
1.eql? 1.0
=> false

Hash uses eql? to compare values used as hash keys. Why not use ==? Because natural equality isn’t necessarily apropriate for a hash. There are two reasons for this, one philosophical and one practical.

To understand the philosophical issue, consider the following:

h = {}
h[1] = 'an integer'
h[1.0] = 'a float'

If Hash used ==, the second assignment would override the first, which almost certainly isn’t what we meant.

The practical issue relates to how hashes work. For the implementation to work correctly a.eql? b must imply that a.hash == b.hash. How could we possibly guarantee this if Hash used ==, when potentially several unrelated classes are involved?

Object provides a default implementation of eql? which compares object identity. This is almost certainly not what you want.

Although the primary use of eql? is within hashes, because hashes are used extensively throughout Ruby code you can easily end up using it indirectly without necessarily realising that you are doing so. Set, for example, is implemented using a hash internally so comparison for set membership is performed with eql? instead of ==. This can lead to surprising behaviour if you rely on the default implementation provided by Object:

class Foo
  attr_accessor :x
  def initialize(x)
    @x = x
  end
  def ==(other)
    @x == other.x
  end
end
 
f = Foo.new(1)
g = Foo.new(2)
h = Foo.new(1)
 
f == g
=> false
f == h
=> true
 
Set.new [f, g]
=> #<set:><foo @x="2">, #<foo @x="1">}>
s.add h
=> #<set:><foo @x="1">, #<foo @x="2">, #<foo @x="1">}>
s.size
=> 3

Case equality

Our next equality operator is ===, the case equality or “threequals” operator. This is the power behind the nice syntactic sugar supported by Ruby’s case statement.

For most objects, === works just like ==, but certain classes modify it to return true for a wider ranger of comparisons. One such class is Range:

(1..10) == 4
=> false
(1..10) === 4
=> true

Which means that you can write this kind of code:

kind = case lines
  when 1..10: "Short"
  when 11..25: "Medium"
  when 26..50: "Long"
  else "Too long!"
end

Regular expressions can play the same kind of trick:

/foo/ == 'foo'
=> false
/foo/ === 'foo'
=> true
 
kind = case moment
  when /dd:dd:dd/: 'time'
  when /dd/dd/dd/: 'date'
  else 'other'
end

As can classes

String == 'foo'
=> false
String === 'foo'
=> true
 
case thing
  when String: # Handle strings here
  when Numeric: # Handle numbers here
  # etc...
end

Note that this means that, unlike the other methods we’re considering here, this means that === won’t in general be commutative:

String === 'foo'
=> true
'foo' === String
=> false

Object provides a default implementation of === which returns true if its arguments are identical and otherwise calls ==:

class Foo
  def ==(other)
    puts '== called'
    super
  end
end
 
f = Foo.new
g = Foo.new
 
f === f
=> true
 
f === g
== called
=> false

The Spaceship operator

The spaceship operator does a lot more than simply check for equality. It defines an ordering on your objects, returning -1, 0 or 1 depending on whether the first argument is less than, equal to or greater than the second.

It’s relevant to our discussion here not only because it can be used to test for object equality as follows:

(f <=> g) == 0

But also because via the Comparable mixin, it provides us with an alternative method of implementing the == operator (although note that, as with the default implementation of ===, it short-circuits if the two objects are identical):

class Foo
  include Comparable
  def <=>(other)
    puts '<=> called'
    0
  end
end
 
f = Foo.new
g = Foo.new
 
f == g
<=> called
=> true
 
f == f
=> true

Object does not provide a default implemenation of <=>, but many standard library classes do provide one of their own.

Which method to use?

So, given this smorgasbord of equality methods, which should we use, and when?

In the vast majority of cases, you will either want to test for “natural” equality (==) or object identity (equal?). Only very rarely (possibly never) should you ever need to call === or eql? directly.

Of course, you will use both indirectly whenever you use a case statement or a hash. But there should be very few occasions where you need to use them directly.

You will notice that quite a bit of code “out there” doesn’t necessarily follow the above recommendation. In particular, it has become idomatic to test the class of an object with ===; the standard libraries in particular use this idiom heavily. Personally speakiing, however, this strikes me as excessively “cute” and I would prefer to use is_a? instead:

Integer === 1
=> true
1.is_a? Integer
=> true

Implementing and overriding equality methods

A number of obvious recommendations arise naturally from the above.

  1. Do not override equal?.
  2. eql? should return true if and only if the two objects represent the same value. This means that if you derive directly from Object, you almost certainly should provide your own implementation of eql?.
  3. If you implement eql? you will normally also have to implement hash and must ensure that x.eql? y implies that x.hash == y.hash.
  4. Under most circumstances, == should be an alias for eql?. If, however, a broader definition of equality makes sense, feel free to alter it to provide sensible natural semantics.
  5. If you do decide to broaden the definition of ==, you should ensure that it still behaves mathematically “sensibly”. As a minimum this means ensuring that it remains commutative.
  6. Under most circumstances, you will not need to implement ===. If, however, your class can benefit from the flexibility of Ruby’s case statement, feel free to create your own version of ===.
  7. If you implement <=>, you normally should not need to implement == as it comes “for free” with Comparable. If you do decide to implement both, however (which can be a reasonable choice for reasons of efficiency) you should ensure that (x <=> y) == 0) implies that x == y and vice-versa.

Oddities

Most of the standard Ruby classes follow these rules. There is one exception we’ve come across though. Hash’s implementation of eql? appears to test for object identity, not equal values. Contrast its behaviour with Array which does behave as we expect:

x = {:a => 'foo'}
y = {:a => 'foo'}
 
x == y
=> true
x.eql? y
=> false
 
x = ['foo', 'bar']
y = ['foo', 'bar']
 
x == y
=> true
x.eql? y
=> true

If anyone can cast any light on the reason for this discrepancy, we’re all ears!

Escape from Zurg

This article originally appeared upon on texperts.com

Ruby Logo “Escape from Zurg” is a puzzle (featuring characters from the movie “Toy Story”) which has been used to teach students Logic Programming (in, for example, Prolog). Recently I came across a very interesting paper which presents an elegant Haskell solution to the riddle. This got me wondering about whether I could come up with a similarly satisfying solution in Ruby.

After a few false starts (mainly a result of me trying to transliterate the Prolog or Haskell solutions rather than come up with something which worked well in Ruby) I’ve come up with something that I’m pretty happy with. Not only is it (I think) concise and clear, but it’s also efficient. Given that Ruby doesn’t have built-in searching (like Prolog) and and doesn’t support lazy evaluation or list comprehension (like Haskell), the fact that the Ruby implementation is as straightforward as it turns out to be is, I think, a testament to the power of the language.

Here’s the puzzle:

Buzz, Woody, Rex, and Hamm have to escape from Zurg. They merely have to cross one last bridge before they are free. However, the bridge is fragile and can hold at most two of them at the same time. Moreover, to cross the bridge a flashlight is needed to avoid traps and broken parts. The problem is that our friends have only one flashlight with one battery that lasts for only 60 minutes (this is not a typo: sixty). The toys need different times to cross the bridge (in either direction):

Buzz: 5 minutes
Woody: 10 minutes
Rex: 20 minutes
Hamm: 25 minutes

Since there can be only two toys on the bridge at the same time, they cannot cross the bridge all at once. Since they need the flashlight to cross the bridge, whenever two have crossed the bridge, somebody has to go back and bring the flashlight to those toys on the other side that still have to cross the bridge.

The problem now is: In which order can the four toys cross the bridge in time (that is, in 60 minutes) to be saved from Zurg?

Like the Haskell solution, the Ruby solution depends on a SearchProblem class which looks after the task of generating candidate solutions:

SearchProblem = Struct.new(:initial) do
  def each_candidate(&proc)
    step [], initial, &proc
  end
 
  def step(history, state, &proc)
    if state.terminal?
      yield history
    else
      state.each_successor do |move, state|
        step history + [move], state, &proc
      end
    end
  end
end

SearchProblem takes an initial State which provides two methods; terminal? returns true if the state is terminal (i.e. in our case, all the toys are on the right hand side of the bridge) and each_successor calls a block with each valid move from that state, together with the new state after that move.

SearchProblem provides an each_candidate method which calls the provided block with each candidate solution in turn. Crucially, candidate solutions are generated as needed, so we don’t have to hold the entire search tree in memory (not a big deal for a problem of this size, but definitely an issue for a “real world” problem!). The Haskell solution achieves a similar effect through lazy evaluation (contrast with this Erlang solution which does have to generate the entire search tree).

To define the particular problem at hand, we first define our Toys:

Toy = Struct.new(:name, :time)
Toys = [
  Toy.new(:buzz, 5),
  Toy.new(:woody, 10),
  Toy.new(:rex, 20),
  Toy.new(:hamm, 25)]

Next, we define Move which we will use to represent transitions between states. In this case, a move consists of a direction (right or left) and a group of toys (two toys for a move to the right, one toy for a move to the left):

Move = Struct.new(:direction, :who) do
  def cost
    who.collect(&:time).max
  end
end

Move provides one method, cost which returns the time taken to complete the move (the implementation of which makes use of the Symbol#to_proc trick).

Most of the heavy lifting is performed by the State class:

State = Struct.new(:pos, :group) do
  def terminal?
    group.empty?
  end
 
  def each_successor
    case pos
      when :left
        group.each_pair do |pair|
          yield Move.new(:right, pair), State.new(:right, group - pair)
        end
      when :right
        (Toys - group).each do |toy|
          yield Move.new(:left, [toy]), State.new(:left, group + [toy])
        end
    end
  end
end

A State comprises two attributes, pos which represents the current flashlight position and group which represents the toys remaining on the left-hand side of the bridge (so the toys on the right-hand side will be Toys - group).

The implementation of State#terminal? is obvious — if group is empty (i.e. if there are no toys on the left-hand side) then we’re done.

State#each_successor has to deal with two cases, depending on the position of the flashlight. The implementation utilises a small utility method on Array which allows all unique pairs of elements of the array to be generated:

class Array
  def each_pair
    each_with_index do |x, i|
      self[i + 1 ... length].each {|y| yield [x, y]}
    end
  end
end

Finally, we create an instance of SearchProblem with our initial state and print out the first candidate solution we find in which the time taken is no more than 60 minutes:

problem = SearchProblem.new State.new(:left, Toys)
puts problem.each_candidate {|history|
  break history if history.inject(0) {|acc, move| acc + move.cost} <= 60
}

As it happens (by sheer fluke) with the Toys array initialized in the natural order, the very first solution generated turns out to be the correct one, so the amount of work performed is the bare minimum. Clearly we can’t always rely on being so lucky in general, however!

To my mind, this solution is at least as easy to understand (and as flexible) as the Haskell equivalent (and both are a significant improvement on the Prolog). I would very much welcome comments and suggestions, however!

The complete source code can be downloaded here.

Update (2007-09-11)

There’s an interesting discussion about this problem on the ruby-talk mailing list.

Hidden feature in Ruby’s Struct

This article originally appeared upon on texperts.com

Ruby LogoThe Ruby core library contains a nice little utility class called Struct, which provides a convenient way to bundle a number of attributes together, using accessor methods, without having to write an explicit class. So this:

class Customer
  attr_accessor :name
  attr_accessor :address
 
  def initialize(name, address)
    @name = name
    @address = address
  end
end

is (broadly) equivalent to this:

Customer = Struct.new(:name, :address)

Much nicer (and DRYer)!

But what if you want to define methods on the new class that you’ve just created? The Pickaxe Book says:

Ruby 1.9 and later allow you to pass a block to a Struct’s constructor. This block is evaluated in the context of the new struct’s class and hence allows you conveniently to add instance methods to the new struct.

Unfortunately most of us haven’t (yet) moved to Ruby 1.9, but there is good news! It turns out that this functionality has actually been present ever since 1.8.3 (here’s the relevant ChangeLog entry, although note that when it refers to [ruby-talk:02606], it should really refer to [ruby-core:02606]).

Imagine, for example, that we wanted to add a custom to_s method to our Customer class:

Customer = Struct.new(:name, :address) do
  def to_s
    "A customer called '#{name}' living at '#{address}'"
  end
end

Sweet!

Update (2007-09-05)

It turns out that there is another commonly used idiom which achieves much the same effect:

class Customer < Struct.new(:name, :address)
  def to_s
    "A customer called '#{name}' living at '#{address}'"
  end
end

However, it also turns out that both of these idioms may have problems when combined with Rails. For further information see this discussion on the ruby-talk mailing list.

Race conditions in Rails sessions and how to fix them

This article originally appeared upon on texperts.com

rails We’ve finally managed to track down and fix a bug in our system which has been bothering us for a while. It turns out to be related to a race condition in Ruby on Rails’ session management code. We would like to share our analysis of the problem, and our solution, with you.

Continue reading ‘Race conditions in Rails sessions and how to fix them’

Well, that’s that then…

Last weekend was the first race meeting of the year at Silverstone. It didn’t go well…

The first piece of bad news was that sticking with my venerable 8-year-old engine for this season was a bad move. A lot of drivers have upgraded to the Suzuki GSXR, and it has a *lot* more power. On one occasion I exited the hairpin right underneath Frazer’s rear wing and by the end of the straight he was a good 5-6 car lengths ahead.

The second piece of bad news was that the car was handling terribly, and chewing up front-left tyres. After a lot of head-scratching, we came to the conclusion that the problem was most likely a result of the chassis not being straight after the accident at the end of the season at Snetterton.

All of that was made moot by what happened in the second race on Sunday – at the start of lap 2, Kat Impey spun on the exit of Copse (very fast – taken in a continuous 4-wheel drift in fifth gear at around 120mph). I was unable to avoid Kat and ended up hitting her very hard indeed. Two further cars then went into the back of us, and the debris hit a couple of other drivers.

The marshalls and paramedics had lots of fun getting me onto a back-board and neck brace and carted me off to the medical centre to be checked over. Luckily there wasn’t any serious damage – although I’m definitely feeling it now!

The car is a complete write-off (as is Kat’s). There are a few bits that I might be able to salvage, but basically it’s a “start from scratch” job.

So, that’s it for a while at least.

Drat.

Is Ruby on Rails a Silver Bullet?

This article originally appeared upon on texperts.com

Here at 82ASK, we’ve been using Ruby on Rails for well over a year, and we love it. We switched to Rails because we believed that we would see dramatically better productivity, and (in the main) that’s how things have turned out.

Something’s been bothering me about this though. Back in 1986, Fred Brooks wrote his brilliant paper No Silver Bullet (included in the Anniversary Edition of The Mythical Man Month). It was, and remains, one of the most influential papers ever written about software engineering. In it he argues that there will be no more techniques or practices that will serve as “silver bullets” and massively improve programmer productivity.

So, how do we square this circle? Was Brooks wrong? Has David Heinemeier Hansson (the creator of Rails) uncovered something that invalidates his argument? Or are we fooling ourselves, and Rails isn’t really giving us the kind of productivity boost we think it is?

Continue reading ‘Is Ruby on Rails a Silver Bullet?’