set_trace_func

I picked up a new machine this week to turn into a home media server, and had a small hoop to jump through with the Broadcom wifi card I picked up. Problem being, office and all my monitors were upstairs, wifi was downstairs, and it's difficult to install new drivers without net access.

But, Linux Mint popped up a "new hardware" dialog, saying it wanted to use b43-fwripper to set up the drivers. Good news, it gave me the url it failed to download from. Manually download the deb, open it up on my other machine using Archive Manager (rather than GDebi), and navigate through to the postinstall script, at data.tar.gz/./usr/share/b43-fwcutter/, and I find a reference to two other files.

After downloading those, copy all three files to the new box. Copy the .deb to /var/cache/apt/archives, and then apt-get install b43-fwripper. Ignore the failure, then go to the dir with the other two files, and manually run the 3 useful lines from the install script (don't forget to add sudo to the last one):

b43-fwcutter -w /lib/firmware wl_apsta-3.130.20.0.o
tar xfvj broadcom-wl-4.150.10.5.tar.bz2
b43-fwcutter --unsupported -w /lib/firmware broadcom-wl-4.150.10.5/driver/wl_apsta_mimo.o

Reboot, and voila - local wifi networks show up in the tray applet. I presume these steps will work for an Ubuntu install as well, since Mint is based on Ubuntu, but I haven't tried it as yet - in fact, the required .deb is on the Ubuntu 9.04 livecd. I also don't know if these files will work for other Broadcom wireless adapters, but if your modern linux system can do a hardware detect and tell you what driver it's trying to pull down, that should be a good starting point.

A little math can be a dangerous thing. Here's a quick benchmark for Fibonacci numbers (Y axis in seconds, 20,000 iterations):

The line on the left, marked A, is the typical naive recursive solution, based as directly as possible on the mathematical definition of the function:

def fib_r(n)
  return 1 if n <= 2
  fib_r(n-1) + fib_r(n-2)
end

Note the telltale exponential curve - this is what we call Very Bad. The line there stops at Fib(10).

A little jiggery lets us convert the recursive solution into an iterative one, line B:

def fib_i(n)
  x = y = 1
  (n-1).times do
    x, y = y, x+y
  end
  x
end

My personal favorite Fib function is (ab)using a hash's default value function to act as a memoizer. Line C is the fastest of the bunch (constant time of ~0.012s) but does have some extra memory overhead.

def fib_h(n)
  @h ||= Hash.new{ |h,k|
    if k < 2
      h[k] = k
    else
      h[k] = h[k-1] + h[k-2]
    end
  }
  @h[n]
end

If we were in an embedded system or something, the memory overhead would probably be bad, but fear not! Math can save us!

Line D is also constant time, but about 0.037s. It's a fun little bit of math mentioned in SICP, and turns Fibonacci numbers into a very simple (if unintuitive) bit of math:

SQRT5 = Math.sqrt(5.0)
PHI = (1 + SQRT5) / 2
PSI = (1 - SQRT5) / 2

def fib_m(n)
  ((PHI ** n - PSI ** n) / SQRT5).to_i
end

I've been trying to figure out a minimal way of getting the geoip_city gem installed on my mac, and having seen a few ideas on google, I'm gonna consolidate into a minimal solution. I originally wanted to work with the macports version of libgeoip, but had absolutely no luck with that, so here's something a bit more manual:

# we need to be root for the ARCHFLAGS later to stick
sudo su

mkdir -p /usr/local/src
cd /usr/local/src

# Download and install latest geoip
curl -O http://geolite.maxmind.com/download/geoip/api/c/GeoIP-1.4.5.tar.gz
tar -xzf GeoIP-1.4.5.tar.gz
cd GeoIP-1.4.5
./configure
make
make check
make install

# install the gem
export ARCHFLAGS='-arch i386'
gem install geoip_city

The main sticking point for me was that setting ARCHFLAGS doesn't continue through to a sudo gem install, so we need to do the whole thing as root.

But, now that we've done that, we can grab the GeoLiteCity database and point our app at it:

curl -O http://geolite.maxmind.com/download/geoip/database/GeoLiteCity.dat.gz
gunzip GeoLiteCity.dat.gz

So, some Hacker News users recently decided that it'd be a good idea to work through the SICP together and make a kind of book club out of the deal over irc.

When I heard of it, I thought it'd be a good excuse to work through the text myself (since it was just sitting on my bookshelf), and also stretch my brain a bit more teaching myself Clojure. I'm almost done the reading and exercises for section 1.1, and I'm already finding it a valuable exercise.

The third exercise asks us to "define a procedure that takes three numbers as arguments and returns the sum of the squares of the two larger numbers." At either extremity are two solutions. The straightforward solution a new programmer can generate based solely on the first 20 pages of the text looks something like this:

(defn sum-largest-squares [a b c]
  (cond (and (< a b) (< a c)) (+ (* b b) (* c c))
        (and (< b a) (< b c)) (+ (* a a) (* c c))
        (and (< c a) (< c b)) (+ (* a a) (* b b))))

Some tests to prove correctness, returning 2^2 + 3^2, or 13, are:

(sum-largest-squares 1 2 3)
(sum-largest-squares 2 3 1)
(sum-largest-squares 3 1 2)

An interesting (and enlightening) exercise is to take our naive function, and just start randomly refactoring, and see where it takes us. One step at a time, making sure we are always passing our handful of test cases. The goal is to decompose and abstract the function into more manageable pieces, with less repetition. To start:

(defn sum-largest-squares [a b c]
  (cond (and (< a b) (< a c)) (+ (square b) (square c))
        (and (< b a) (< b c)) (+ (square a) (square c))
        (and (< c a) (< c b)) (+ (square a) (square b))))

The square function is trivially pulling out (* x x), and conveniently is already present in Clojure.

Second step is to pull out the three conditional clauses into sum-of-squares:

(defn sum-of-squares [a b]
  (+ (square a) (square b)))

(defn sum-largest-squares [a b c]
  (cond (and (< a b) (< a c)) (sum-of-squares b c)
        (and (< b a) (< b c)) (sum-of-squares a c)
        (and (< c a) (< c b)) (sum-of-squares a b)))

Next, we can probably abstract the conditionals themselves, since what we're looking for is the smallest of three elements (min is also provided by clojure):

(defn sum-largest-squares [a b c]
  (cond (= a (min a b c)) (sum-of-squares b c)
        (= b (min a b c)) (sum-of-squares a c)
        (= c (min a b c)) (sum-of-squares a b)))

Now, we've got a much more parallel structure here, so we should be able to collapse the conditional, and process the values first.

I'll stop here, but there are a few different ways to get started with the next step - most involve transitioning our three arguments into a list at some point. I've found it instructive to play around with the different ways of decomposing the problem (including a few side steps along the way to the route I've followed above). I'm thinking that as I continue with the SICP exercies, I'll try and make a habit of not stopping with the first solution that springs out of my text editor, but to try and explore the structure of the code through refactoring.

Also, while I never managed to figure out refactoring steps that would produce it, I think the most straightforward functional solution (rather than the semi-iterative solution we started with above) winds up being this - it has a certain elegance to it, no?

(defn sum-largest-squares [a b c]
  (apply + (map square (rest (sort (list a b c))))))

The latest version of rubygems seems to be more gung-ho about trying to clean up old versions of gems. This is fine, except that OSX seems to be very protective of its bundled gem directory, refusing to uninstall gems located there even though I'm running the gem command via sudo.

As a result, while gem list tells me that I've got activerecord v 2.2.2 and 1.15.6 installed, gem cleanup fails miserably:

jamie@juliet ~> sudo gem cleanup
Cleaning up installed gems...
Attempting to uninstall activerecord-1.15.6
ERROR:  While executing gem ... (Gem::InstallError)
    Unknown gem activerecord = 1.15.6

I appreciate Leopard not wanting to break the bundled versions of gems, but having a functioning gem cleanup is helpful to me. Turns out it's pretty easy to just prevent rubygems from checking the Ruby.framework gem path, just create (or edit) ~/.gemrc and include the following:

gempath:
  - /Library/Ruby/Gems/1.8
  - /Users/jamie/.gem/ruby/1.8

Of course, you'll need to use your own username on the last line there, and you might want to double-check the existing GEM PATH values from gem env output so you don't accidentally clobber anything else. Also, if you've got a previously-generated .gemrc, the gempath key needs to be a string, not a symbol, or else it won't get picked up. Whee.