For a project I'm working on, I'm implementing a linked-list data-structure, which is based on the idea of a pair, which I define as:

class Pair:def __init__(self, name, prefs, score):self.name = nameself.score = scoreself.preferences = prefsself.next_pair = 0self.prev_pair = 0

where self.next_pair and self.prev_pair are pointers to the previous and next links, respectively.

To set up the linked-list, I have an install function that looks like this.

def install(i, pair):flag = 0try:old_pair = pair_array[i]while old_pair.next_pair != 0:if old_pair == pair:#if pair in remainders: remainders.remove(pair)return 0if old_pair.score < pair.score:flag = 1if old_pair.prev_pair == 0: # we are at the beginningold_pair.prev_pair = pairpair.next_pair = old_pairpair_array[i] = pairbreakelse: # we are not at the beginningpair.prev_pair = old_pair.prev_pairpair.next_pair = old_pairold_pair.prev_pair = pairpair.prev_pair.next_pair = pairbreakelse:old_pair = old_pair.next_pairif flag==0:if old_pair == pair:#if pair in remainders: remainders.remove(pair)return 0if old_pair.score < pair.score:if old_pair.prev_pair==0:old_pair.prev_pair = pairpair.next_pair = old_pairpair_array[i] = pairelse:pair.prev_pair = old_pair.prev_pairpair.next_pair = old_pairold_pair.prev_pair = pairpair.prev_pair.next_pair = pairelse:old_pair.next_pair = pairpair.prev_pair = old_pairexcept KeyError:pair_array[i] = pairpair.prev_pair = 0pair.next_pair = 0

Over the course of the program, I am building up a dictionary of these linked-lists, and taking links off of some and adding them in others. Between being pruned and re-installed, the links are stored in an intermediate array.

Over the course of debugging this program, I have come to realize that my understanding of the way Python passes arguments to functions is flawed. Consider this test case I wrote:

def test_install():p = Pair(20000, [3, 1, 2, 50], 45)print p.next_pairprint p.prev_pairparse_and_get(g)first_run()rat = len(juggler_array)/len(circuit_array)pref_size = get_pref_size()print pref_sizeprint install(3, p)print p.next_pair.nameprint p.prev_pair             

When I run this test, I get the following result.

0
0
10
None
10108
0

What I don't understand is why the second call to p.next_pair produces a different result (10108) than the first call (0). install does not return a Pair object that can overwrite the one passed in (it returns None), and it's not as though I'm passing install a pointer.

My understanding of call-by-value is that the interpreter copies the values passed into a function, leaving the caller's variables unchanged. For example, if I say

def foo(x):x = x+1return xbaz = 2
y = foo(baz)
print y
print baz

Then 3 and 2 should be printed, respectively. And indeed, when I test that out in the Python interpreter, that's what happens.

I'd really appreciate it if anyone can point me in the right direction here.

In Python, everything is an object. Simple assignment stores a reference to the assigned object in the assigned-to name. As a result, it is more straightforward to think of Python variables as names that are assigned to objects, rather than objects that are stored in named locations.

For example:

baz = 2

... stores in baz a pointer, or reference, to the integer object 2 which is stored elsewhere. (Since the type int is immutable, Python actually has a pool of small integers and reuses the same 2 object everywhere, but this is an implementation detail that need not concern us much.)

When you call foo(baz), foo()'s local variable x also points to the integer object 2 at first. That is, the foo()-local name x and the global name baz are names for the same object, 2. Then x = x + 1 is executed. This changes x to point to a different object: 3.

It is important to understand: x is not a box that holds 2, and 2 is then incremented to 3. No, x initially points to 2 and that pointer is then changed to point to 3. Naturally, since we did not change what object baz points to, it still points to 2.

Another way to explain it is that in Python, all argument passing is by value, but all values are references to objects.

A counter-intuitive result of this is that if an object is mutable, it can be modified through any reference and all references will "see" the change. For example, consider this:

baz = [1, 2, 3]def foo(x):x[0] = x[0] + 1foo(baz)
print baz
>>> [2, 2, 3]

This seems very different from our first example. But in reality, the argument is passed the same way. foo() receives a pointer to baz under the name x and then performs an operation on it that changes it (in this case, the first element of the list is pointed to a different int object). The difference is that the name x is never pointed to a new object; it is x[0] that is modified to point to a different object. x itself still points to the same object as baz. (In fact, under the hood the assignment to x[0] becomes a method call: x.__setitem__().) Therefore baz "sees" the modification to the list. How could it not?

You don't see this behavior with integers and strings because you can't change integers or strings; they are immutable types, and when you modify them (e.g. x = x + 1) you are not actually modifying them but binding your variable name to a completely different object. If you change baz to a tuple, e.g. baz = (1, 2, 3), you will find that foo() gives you an error because you can`t assign to elements of a tuple; tuples are another immutable type. "Changing" a tuple requires creating a new one, and assignment then points the variable to the new object.

Objects of classes you define are mutable and so your Pair instance can be modified by any function it is passed into -- that is, attributes may be added, deleted, or reassigned to other objects. None of these things will re-bind any of the names pointing to your object, so all the names that currently point to it will "see" the changes.