Python Homework

At work, Python is one of many languages we utilize. In fact, Python is one of the APIs we offer for accessing our services.

We generate our Python SDK using our (sort of) open source SDK generation system, which is hosted by our friends at osmosoft. You can find the SDK generation code here.

Anyway, there has been much debate about langauge proliferation within our group. As one of the most enthusiastic exponents of a polyglot programming, I perform quite a bit of evangelism within our group. Most recently, I've started the work of setting up a Python focus group, and in the course of doing so, have begun setting some "homework" for some of my keen fellow engineers.

Always ahead of the game, Kerry has already started blogging about some of these exploits. The second exercise is an interesting one. I'll discuss the thinking behind the exercise, followed by my solution.

Here's the exercise itself:

Write a recursive function that calculates the value of Fibonacci numbers. These are your acceptance criteria:

• Calculating fib(250) must return 7896325826131730509282738943634332893686268675876375
• The function must use recursion. No intermediary data structures, etc.
• The implementation must be written in pure python – no C extension modules, that's cheating.
• The function must calculate the 250th Fibonacci number in under one second. You will get extra points if:
• You can also demonstrate a proof for the Reciprocal Fibonacci constant, meeting the following conditions
  • Your proof must also run in under one second
  • Your proof must not duplicate any of the concerns addressed by your original Fibonacci function implementation.
  • Your proof is allowed to call into the Fibonacci function though!

The reciprocal Fibonacci constant is defined here. Here's a couple of hints about things to look for:

• Memoization
• Function decorators

Well now. What's the point of this exercise?

The point here is to get people thinking about function composition. Re-use is so often quoted as being important in our work, and yet in our industry at large, we often see developers failing to apply even basic functional (de!)composition, let alone OOP and other high level programming paradigms.

Properly composed functions are a basic unit of abstraction in most languages, and Python is no exception.

Implementation

The performance requirements of the spec are really a red herring. The key to this exercise is to avoid duplicating the performance enhancing code, which is required to avoid the slowdown (and possible program failure) resulting from excessive recursion. I decided to abstract a simple caching algorithm as a function decorator, which is then applied to both recursive functions (fibonacci and the fib' constant implementation). You could use the 'memoized' decorator anywhere you have a function that is referentially transparent. Here's the code:

#!/usr/bin/env python

def memoized(fun):
  target = fun
  cache = {}
  def memoized(*args, **kwargs):
      if cache.has_key(args[0]):
          return cache[args[0]]

      result = target(*args, **kwargs)
      cache[args[0]] = result
      return result
  return memoized

@memoized
def fib(n):
  if n < 2: return n
  return fib(n - 1) + fib(n - 2)

@memoized
def fibConstant(n):
  if(n == 1):
      return (1.0 / fib(n))
  else:
      return (1.0 / fib(n)) + fibConstant(n - 1.0)

if __name__=='__main__':
  import profile
  profile.run('print fib(250)')
  profile.run('print fibConstant(93.0)')