Archive for November, 2009

Not At PDC

Monday, November 23rd, 2009

I was saddened when I was unable to attend PDC this year. One project is winding down, we're staffing up for the next, and I cannot be spared at this particular time. I was not present when Scott Hanselman dragged and dropped his way through a data binding demo. Nevertheless, I was groaning from afar.

I did, however, have the chance to participate in the Not@PDC conference. It was quickly organized via Twitter and blogs to be an online get together for folks who were not lucky enough to be in LA. (Lucky to be in LA? Did I really say that?) It turned out to be a wonderful substitute. OK, not really a substitute; more like consolation.

I presented Data Binding Without INotifyPropertyChanged, a 70-minute demo of Update Controls in WPF, Winforms, and Silverlight. In the video, I show you the most awesome application ever: Microsoft Excel. Excel is awesome because you can use the MVVM pattern. It's true.

As you watch, please forgive the poor video quality and even poorer jokes. I'll be polishing the demo and taking it on the road. My first stop will hopefully be the North Dallas .NET Users' Group. I'll keep you posted.

Fibonacci solution

Sunday, November 8th, 2009

The question is how bad the recursive Fibonacci algorithm.

To calculate fib n, how many times does this method evaluate fib m, where m < n and both m and n >= 0.

The answer, as you might expect, is pretty bad.

Let’s look at the code again:

let rec fib n = 
  if n < 2 then 1 
  else fib (n-1) + fib (n-2)

When would fib n be called recursively? When fib (n+1) or fib (n+2) is called.

How many times would fib n be called? Count of fib n is count of fib (n+1) plus count of fib (n+2). Look familiar?

The count is the Fibonacci sequence in reverse.

Fibonacci inefficiency

Wednesday, November 4th, 2009

The Fibonacci function is often the first code that someone writes to learn a new functional language. Ironically, it's not always the best example of functional programming. Here's the Fibonacci function in F#:

let rec fib n =
  if n < 2 then 1
  else fib (n-1) + fib (n-2)

The code matches the mathematical definition, which is a strength of functional programming. However, it performs poorly unless the language has a feature called "memoization". F# does not have this feature.

Can you spot the difference between these two statements?

  • Each Fibonacci number is the sum of the prior two Fibonacci numbers.
  • To calculate Fibonacci of n, add Fibonacci of n-1 to Fibonacci of n-2.

They might seem to say the same thing, but in fact they are different. The first is a definition. The second is an algorithm.

Memoization is a memory/time tradeoff wherein the results of a function are stored in the expectation that the same function will be called with the same parameters. It helps us get across the gap between definition and algorithm.

Your homework
Nevertheless, F# does not have built-in memoization. So when you execute this Fibonacci function, it will execute recursively and redundantly. It will call fib for smaller numbers multiple times. Your homework is to find out how many times.

To calculate fib n, how many times does this method evaluate fib m, where m < n and both m and n >= 0.

Email or post your answers. Code is good, but proof is better.