PostgreSQL and PL/Pythonu

Beside SQL PostgreSQL has support for creating functions in many other so called procedural languages. We just need to install them and they are available within database. Standard distribution includes those four languages PL/pgSQL, PL/Tcl, PL/Perl, and PL/Python. There are other externally maintained languages like Java, Scheme, PHP, Unix shell and so on. If that is not enough it is possible to write procedural language handler, it is open source and consequently fully customizable.
Hosted Python is very interesting option. It is quite powerful, versatile language and code is very concise. If it is executed within PostgreSQL it enjoys very fast communication avoiding overhead of DB calls which external programs suffer. Both Python 2 and Python 3 are supported. If you are using, for example, Ubuntu then postgresql-plpython-9.x is Python 2 and postgresql-plpython3-9.x is Python 3. It needs to be installed, server restarted and language created.

createlang plpythonu [dbname]

If we do not specify db, then it will be created on db to which are we currently connected. That u suffix have meaning that we are dealing with unrestricted/untrusted language. Power is given to us and it is our responsibility to use it to our benefit without causing damage. Once everything is in place we can write Hello World function in Python.

CREATE OR REPLACE FUNCTION lumberjack() RETURNS text AS $BODY$ a = "I'm a lumberjack, and I'm okay. " return a + "I sleep all night and I work all day." $BODY$ LANGUAGE plpythonu

From psql we try it

testpgdb=# select lumberjack(); lumberjack ----------------------------------------------------------------------- I'm a lumberjack, and I'm okay. I sleep all night and I work all day. (1 row)

Or if you prefer GUI, then use pgAdmin III start Query tool and execute it there.
To enjoy full comfort of Python one need to import modules. How do we use modules in PL/Pythonu? It is no different to ordinary Python code:

create or replace function get_response() returns text as $BODY$ import httplib2 h = httplib2.Http(".cache") resp, content = h.request("http://example.org/", "GET") return resp $BODY$ language 'plpythonu'; select get_response();

we should see response. If we see:

ERROR: ImportError: No module named httplib2 CONTEXT: Traceback (most recent call last): PL/Python function "get_response", line 2, in <module> import httplib2 PL/Python function "get_response"

That is sign that httplib2 is not in path, we can place it in path or if we do not want to reload server we can append to function:

from sys import path path.append('/path to httplib2')

There is significant quantity of examples on Internet to help you further. With some knowledge of Python one can do really huge amount of work directly from PostgreSQL without overhead of DB connection. In role of mailer of monthly report PL/Pythonu function beats Java Application Server and even C/C++ application connecting from outside to DB.

Homework: Towers of Hanoi

This puzzle was popularised in Europe by French mathematician Edouard Lucas. There are three poles, 64 disks of different sizes and number of monks trying to move those disks from first to third pole, respecting the following rules:
1) You can move only one disk at the time.
2) You can pick only top disk and place it on top of other disks on different pole.
3) You can place disk only on bigger disk.
When monks finish moving those 64 disks and puzzle is solved, end of the world will come. According to Lucas all that takes place in Vietnam. Now, this puzzle is known in India as Towers of Brahma and there could be other versions of it, for example Chinese, over last seven thousands years they invented many puzzles. One may be under impression that end of the world is near but to solve 64 disk puzzle, 2^64-1 moves are required and that is quite big number 18446744073709551615. Though end of the world may come before puzzle is solved for many other reasons.
Puzzle is quite interesting because it allows to develop simple algorithm. Now we will name poles start, aux and end. With single disk, we take it from start and place on end. With two disks, we take small to aux, big to end and finally smal from aux to end. Now with three disks we already see that we should move top two to aux, big disk to end and after that top two to end. So, moving top two to aux is like previous case, but aux and end are swapping places. Moving top two from aux to end is again the same as previous case, but start and aux are swapping places. We can even write moves, so it is easy to see what is going on:

One disk: start to end
Two disks: start to aux, start to end, aux to end
Three disks: (start to end, start to aux, end to aux), start to end, (aux to start, aux to end, start to end)

We can generalize and say that solution is moving n-1 disks to aux, moving bottom disk to end and moving n-1 disks from aux to end. So we got self algorithm for solving puzzle. Turning it into code is more than simple:

def towers(n, start, aux, end): if n>1 : towers(n-1, start, end, aux) print 'moving disk {} from {} to {}'.format( n, start, end ) towers(n-1, aux, start, end) elif n==1 : print 'moving disk {} from {} to {}'.format( n, start, end )

That was Python implementation. If you do not know Python, here is Java implementation:

public class Towers { public static void main(String[] args) { towers(5,1,2,3); } static void towers(int n, int start, int aux, int end){ if(n>1){ towers(n-1, start, end, aux); System.out.println("moving disk "+n+" from "+start+" to "+end); towers(n-1, aux, start, end); }else System.out.println("moving disk "+n+" from "+start+" to "+end); } }

Very simple. There are many other ways to solve this puzzle but recursion is simplest and most logical. Also excellent interview question, if candidate is not capable of developing simple algorithm and understanding recursion, then candidate is not really programmer.

Recursion in Python

And now something completely different. During last week I was busy polishing my Python skills or rather removing rust from them. I went through book Think Python: How to Think Like a Computer Scientist by Allen Downey. Mentioned book is available for download from http://www.thinkpython.com. My impression is that book is intended for army of different bookkeepers and alike trying to learn programming. So author is threading rather gently and slowly. It reminds me of joke from Monty Python where accountant, Palin, wants to go directly into taming lions, but career consultant, Cleese won’t let him, he must do that gradually, first investment banking. Now I will be kind and let accountant do lion taming without going first into investment banking.
In one of introductory chapters recursion is introduced and stack transition is explained. For example we can use factorial:

def fac(n): if n <= 1 : return 1 else: return n*fac(n-1)

It is easily readable and looks good. If we call it with n=6 this will happen:

6*(5*(4*(3*(2*1))))

CPU pushes on stack value for n and * operation and dispatches call to the same function but with n-1 parameter, when right brace is closed, pops frame from stack and finishes multiplication. Problem with recursion and Python is that depth of stack is rather small, only thousand frames. If you try to calculate factorial for 2^10 using this function it will cause stack overflow. So instead of doing recursive calls one can rewrite factorial and use iterations:

def fac(n): res = 1 while n>1: res *= n n-=1 return res

Still simple and shallow stack problems are avoided, but that is so investment banking. What else could be done? We can use binary splitting. Story about binary splitting comes from Xavier Gourdon and Pascal Sebah and you can find it here. Instead of multiplying accumulator with all numbers in range we do recursive preparation similar to binary search and build tree like flow to multiply partial products between themselves. We define product like this:

P(a, b) = P(a, (a+b)/2)*P((a+b)/2, b)

Then we divide each range in half until distance between upper and lower bound is small. Here is the code:

def product(a, b): d = b - a m = (a+b)/2 result = 0 if d > 1 : result = product(a,m)*product(m,b) elif d == 1 : result = b else : result = 1 return result

If we say a is 0 we will get factorial b as result. I tested it for b up to 2^16 and it went through without stack overflow as expected. While it theoretically could be used for values up to 2^1000, try not to exceed 2^16 unless your box have really good cooling and plenty of time to wait for result. Tree is not tall, but there is quite few branches. Python is partly functional language and that bring us to yet another idea. Functional languages have compilers which will optimize recursive calls into so called tail calls if function is written in certain way. For example this could be optimized:

def fac(n, a=1): if n<2 : return a else: return fac(n-1, n*a)

But Python compiler is not that much functional and it will not generate tail calls. Through the years people are bothering Guido with tail call optimisations but he just doesn’t want to implement it. When gccpy front-end is released, there will be tail call optimisation since GCC is doing it anyway. Instead of waiting for gccpy we can help ourselves with generators and so called trampolining. We should also switch from factorial to Fibonacci numbers, due to size of result. Plain Fibonacci looks like this:

def fibo(n): if n<2: return n else: return fibo(n-1)+fibo(n-2)

In order to get generators we will replace return with yield and rewrite function so it ends with single function call:

def fibo(a, b, c):
    if c==0:
        yield b
    else:
        yield fibo(a+b, a, c-1)

and one would like to call it like this fibo(1, 0, n). Now we just need trampoline to execute those tail calls and we can calculate first thousand or so Fibonacci numbers:

import types

def trampoline(func, *args, **kwargs):
    f = func(*args, **kwargs)
    while isinstance(f, types.GeneratorType):
        f=f.next()
    return f

def fibo(a, b, c):
    if c==0:
        yield b
    else:
        yield fibo(a+b, a, c-1)

for x in range(1024):
    print "F(", x, ") =", trampoline(fibo, 1, 0, x)

There is user friendly version of trampoline where decorator is used, so no need to replace return with yield and normal function call is used, but is more difficult to understand, you can download it from here.