A Python puzzle for Python newbies

(August 2006)

I first met Python 4 years ago.

My initial reaction was "where are the braces?". Horror of horrors, it didn't have any block delimiters. Code blocks were defined based on indentation! Yikes. I immediately returned to my C++/Perl/awk and vowed never to look at this toy again.

No matter how hard I tried though, I stumbled on it, again and again. An alarmingly large number of programs were being written with it... and to my bewilderment, whenever I chanced a look at Python code, I figured things out effortlessly, quickly - and I didn't speak the language! The first time this happened I attributed it to the competence of the programmer and the nice comments he had written. The second time there were no comments - and yet I figured things out just as easily. The third time, I googled for Python and stumbled on Eric Raymond's "Why Python".

That was it. One of the high priests was raving about this language - just like me, he had also been bitten by the indentation fright but had gotten over it, and persisted to quickly realize that this was a true gem. I followed suit.

4 years later, I am writing Perl only for quick'n'dirty text-processing, the...

process data | perl -ne 'm/([a-z]*) goo/ && print $1;'

...kind. Anything bigger, it's a no brainer: if it's going to be a script, it's in Python. Incredible effort to gain ratio - compared to any other language I've used. Notorious ease of learning; I have only read the tutorial over a weekend, and that never got in the way of writing really large scripts. In fact, for enthusiasts like me, that can be a problem! It is so easy to write in Python, that I get carried away - I end up writing really large scripts before I know it... I then have to stop and FORCE myself to refrain from writing code and to plan it out first!

So where's the puzzle? you ask.

This year's "lab rat" is Lisp. I read the gospels of Paul Graham and decided to check this language out - the high priests seem to agree that this is the be-all and end-all of computer languages. I'm almost there myself, having written just a couple of Lisp macro's and been thoroughly impressed by the "code is data, let your code do the coding" revelation. Lisp isn't Python, you need a good book and a lot of effort to understand it, so I'm reading Paul's "ANSI Common Lisp". On page 52, I ended up on an old acquaintance, the "find the shortest path in a graph" problem. I vaguely remembered having met it 14 years ago, in the university exercises... Before attempting to think of it in Lisp, I smirked to myself: "How much time would it take me to think up a recursive algorithm and write it in Python?". And 20 minutes later I had this:

neighbours = {
    "A": {"B": 3, "C": 4},
    "B": {"D": 2},
    "C": {"D": 1, "E": 1, "F": 6},
    "D": {"H": 1},
    "E": {"H": 7},
    "F": {"G": 1},
    "G": {},
    "H": {"G": 3}
}


def FindShortestPath(begin, end, shortestPath):
    print "From %s to %s" % (begin, end)
    if begin == end:
        shortestPath = [end]                           # (1)
        return 0
    currentBestLen = 1e10
    currentBestRoute = []
    for neigh in neighbours[begin].keys():
        aiResult = []
        cost = FindShortestPath(neigh, end, aiResult)
        if cost + neighbours[begin][neigh] < currentBestLen:
            currentBestLen = cost + neighbours[begin][neigh]
            currentBestRoute = [begin] + aiResult
    shortestPath = currentBestRoute                    # (2)
    print "FindShortestPath from %s to %s has cost %d for %s " \
        % (begin, end, currentBestLen, shortestPath)
    return currentBestLen

bestRoute = []
FindShortestPath("A", "G", bestRoute)
print "Best path is", bestRoute

Resist the temptation to skip the code - have a look at it. It's a simple, nice, recursive implementation: in order to compare alternate paths, use recursion to find the paths and costs from the neighbours to the target, and then check the costs from the source to each of the neighbours. When you identify the best path, return it to the caller via the 'shortestPath' function argument (points 1 and 2).

Er... it didn't work.

When I sprinkled the code with debug printing of the paths, it turned out that the resulting paths in (1) and (2) were not propagated to the callers. Why? I was passing mutable arguments, plain old lists, they ought to have been changed! I checked some other scripts I had written, and I was doing similar things there (sure enough) passing lists as arguments to functions, modifying them and returning them to the caller.

That was a first - the obvious thing appeared not to work (until then, Python had been 100% successful in reading my mind and doing whatever I desired).

With Python, when you are in doubt, you never look at the manual - you fire up the interpreter and try things to make sure you got it right (it's so much easier than reading manuals). Well, it was working! (see below):

Python 2.3.4 (#1, Apr 30 2005, 19:57:58) 
[GCC 3.2.3 20030422 (Gentoo Linux 1.4 3.2.3-r1, propolice)]
Type "help", "copyright", "credits" or "license" for more info.
>>> def f(x):
...    x[1]=2
... 
>>> a=[0, 0, 0, 0]
>>> f(a)
>>> a
[0, 2, 0, 0]
>>>

The function indeed changed the list I was passing in, why didn't it work in the shortest path code?

I looked, and looked, and huffed and puffed - to no avail. I tried various alternatives (the most hideous one was using a global list to pass the returned results back to the callers - I almost choked from disgust and removed it immediately). What was happening?

Ah, the joy of programming.

It took me a while to notice that the test I did was not doing exactly what the shortest path code did. When I tried it in the same form...

Python 2.3.4 (#1, Apr 30 2005, 19:57:58) 
[GCC 3.2.3 20030422 (Gentoo Linux 1.4 3.2.3-r1, propolice)]
Type "help", "copyright", "credits" or "license" for more info.
>>> def f(x):
...   x=[2]
... 
>>> a=[0,0]
>>> f(a)
>>> a
[0, 0]
>>>

... it failed, just like the shortest path code! At least the thing was reproducible. Obviously something else was happening - if the x=[2] assignment didn't change the passed-in data, what was it changing?

At that point I decided to bite the bullet and have a look at the language docs. After a fair amount of searching I got to this part:
"The execution of a function introduces a new symbol table used for the local variables of the function. More precisely, all variable assignments in a function store the value in the local symbol table; whereas variable references first look in the local symbol table, then in the global symbol table, and then in the table of built-in names.
The actual parameters (arguments) to a function call are introduced in the local symbol table of the called function when it is called; thus, arguments are passed using call by value (where the value is always an object reference, not the value of the object). When a function calls another function, a new local symbol table is created for that call."

There was the answer to the mystery - inside the tutorial, by Guido himself. Assignments are handled in a - special - way. In the first test I did, I was "referring" to the passed-in argument, and invoking the 'x[1]' accessor to get to one of its data. In the second test, I am assigning - and as Guido says, assignments store the value in the local symbol table!

The problem probably only exists in the mindsets of C++ programmers - when I originally read that paragraph of the tutorial, what I understood was the last part: that the value passed in is always an object reference. In the C++ world, this is equivalent to:

returnType functionName(argumentType& arg)
{
}

...which in my mind meant, that if I do anything on arg, the caller will see the changes in the data. Not so, in Python: all variable assignments in a function store the value in the local symbol table. It is more like this C/C++ code:

returnType functionName(argumentType* arg)
{
}

...so by assigning to arg (arg = "foo";) you won't be changing the data passed in; the caller will never see the change, because the assignment is simply re-assigning the local symbol.

So how do I pass the results back to the caller?

I need to somehow "refer" to the variable, but I want to assign data to it... In a moment of inspiration, I tried:

	shortestPath[:] = [end]			(1)
and
	shortestPath[:] = currentBestRoute	(2)

...and to my intense satisfaction, I saw my code work:

From A to G
From C to G
From E to G
From H to G
From G to G
FindShortestPath from H to G has cost 3 for ['H', 'G'] 
FindShortestPath from E to G has cost 10 for ['E', 'H', 'G'] 
From D to G
From H to G
From G to G
FindShortestPath from H to G has cost 3 for ['H', 'G'] 
FindShortestPath from D to G has cost 4 for ['D', 'H', 'G'] 
From F to G
From G to G
FindShortestPath from F to G has cost 1 for ['F', 'G'] 
FindShortestPath from C to G has cost 5 for ['C', 'D', 'H', 'G'] 
From B to G
From D to G
From H to G
From G to G
FindShortestPath from H to G has cost 3 for ['H', 'G'] 
FindShortestPath from D to G has cost 4 for ['D', 'H', 'G'] 
FindShortestPath from B to G has cost 6 for ['B', 'D', 'H', 'G'] 
FindShortestPath from A to G has cost 9 for ['A', 'C', 'D', 'H', 'G'] 
Best path is ['A', 'C', 'D', 'H', 'G']

Yes, it happens a lot with Python - things tend to work on the first or second attempt. When they don't, it's because I'm lazy and expect to use a language without properly reading a manual! Shame, coder, shame.

Index

Updated: Fri Aug 9 22:48:30 2013