Beautiful Code: Code == Data

I found this in an exercise in SICP. Instead of the original Scheme, which IMHO is a little difficult to read, I’ve translated it to Haskell.


pair x y = \acc -> (acc x y)
first pair = pair (\x y -> x)
second pair = pair (\x y -> y)


Haskell tends to look a little discouraging at first, but its actually quite straightforward. \x -> expr is how you create a lambda in Haskell. Even though Haskell is statically typed, note that we haven’t specified any types at all. This is because Haskell’s system of type inference is quite powerful.

That said, what does the above do? The function names should make it clear that we’re somehow providing a function that creates a pair, and the first and second functions are accessor methods for the elements of the pair. For instance, they’d be used like this:


*Main> let n1 = pair 10 20
*Main> first n1
10
*Main> second n1
20


Question is: how does this work? Lets look at at the pair function carefully. It’s returning a function that accepts a single parameter acc, and calls acc with the parameters x and y.

The function first accepts a single argument pair as input, and calls pair with an argument that is a function. This function accepts two arguments, and returns the first of those two arguments.

It should all make sense now. pair 10 20 returned a function that would accept a function as parameter, and call that function with the parameters 10 and 20. The functions first and second second call this function (the returned value of pair) with a function as a parameter such that this passed function (the lambda’s in definitions of first and second) returns the appropriate element of the pair.

Pretty cool, no?

blog.hibernate()

It turns out the anonymous commentor from IISc was right. I can’t keep a blog and keep up with course work at IISc. So, somewhat unfortunately, I will have to put this blog into a hibernate mode. 

I will try and post interesting things as and when possible, but I don’t see that happening too often in the near future.

Before I go, here is an interesting way of finding fibonacci numbers that I found in SICP.

The trick is to think of calculating one fibonacci number from the previous as a transformation of a vector in . We’re going from (a b) -> (b a+b). But this can be expressed as f’ = Af, where A is a 2×2 matrix and f is a vector. The trick now is to chain many of these transformations together, and then use the method of exponentiation by squaring to calculate the n-th power of A, giving us a method to calculate the n-th fibonacci number in O(log n) time.

Pretty cool, eh?

Hello, World!

This post is an attempt to dispel all rumors suggesting that I’m dead, have lost the ability to write, and/or have given up writing this blog. All three assertions are baseless; I’m alive, kicking and have some interesting posts coming up over the next few weeks.

It all started when I decided to interview for the M.S programs at IIT Madras, and IISc. So I had to spend a few weeks preparing for the interviews. Then I went to the interviews and found out that what I thought I knew was a lot lesser than what I thought it was! Eventually, I ended up being accepted at both places and have now joined the M.Sc (Engg) program at SERC, IISc. Between preparing for the interviews, doing some background research on what I want to do in grad-school, and keeping up with work at NI, I couldn’t find any time at all to blog. I am hoping that the move to IISc will give me some more time to focus on this blog.

In between, I bought a Dell Vostro 1510. I wanted a machine that had a decent processor, lots of RAM and HDD space – this one has all three – a Core 2 Duo T8100, 4 GB of RAM and a 250 GB hard drive. I decided to run Ubuntu 8.04 on this, and had a lot of trouble getting the network card to work. It turns out you have to remove the r8169 driver that is installed by default, download the Realtek r8168 driver from their website, compile it from source and install it. The worst part of the driver nightmare was that the default shipping driver randomly works, instead of not working at all, and because of this I got fooled into thinking that passing pci=nomsi to the kernel at boot time fixes this. It doesn’t. You have to do the r8168 compile and install thing. See here for details.

Anyway, that’s all for now. I promise to get back to the functional programming series very soon. Ciao!