Debugging a Python script

The other night I wrote a Python script to group my ScriptEd students into 5 tables. I wanted the groupings to be random, but I wanted both males and females to be equally distributed at each table—or at least, as close as possible, since we have a few more males than females.

My first iteration of the script looked like this:

from random import shuffle

NUM_GROUPS = 5

MALES = [
  'M1',
  'M2',
  'M3',
  'M4',
  'M5',
  'M6',
  'M7',
  'M8',
  'M9',
]

FEMALES = [
  'F1',
  'F2',
  'F3',
  'F4',
  'F5',
  'F6',
  'F7',
]

shuffle(MALES)
shuffle(FEMALES)

groups = [ [] ] * NUM_GROUPS

for i in range(len(MALES) + len(FEMALES)):
  if i % 2 == 0 and FEMALES:
    groups[i % NUM_GROUPS].append(FEMALES.pop())
  else:
    groups[i % NUM_GROUPS].append(MALES.pop())

print(groups)

Nothing too complicated—loop through the total number of students, and if the current index is even and there are unplaced females, place one of them in the current group. Otherwise, place a male in the current group.

This script breaks when the number of groups to assign is even, since the assignment logic uses modular arithmetic that will always assign the males and females to separate groups. But, since I was using an odd number of groups, I didn't have to worry about that problem.

Aside from that, though, I had introduced a separate bug. The output from running that script looks something like this (newlines and indentation added for clarity):

[
  [ 'F7', 'M4', 'F3', 'M7', 'F4', 'M6', 'F5', 'M3', 'F1', 'M2', 'F2', 'M5', 'F6', 'M8', 'M1', 'M9' ],
  [ 'F7', 'M4', 'F3', 'M7', 'F4', 'M6', 'F5', 'M3', 'F1', 'M2', 'F2', 'M5', 'F6', 'M8', 'M1', 'M9' ],
  [ 'F7', 'M4', 'F3', 'M7', 'F4', 'M6', 'F5', 'M3', 'F1', 'M2', 'F2', 'M5', 'F6', 'M8', 'M1', 'M9' ],
  [ 'F7', 'M4', 'F3', 'M7', 'F4', 'M6', 'F5', 'M3', 'F1', 'M2', 'F2', 'M5', 'F6', 'M8', 'M1', 'M9' ],
  [ 'F7', 'M4', 'F3', 'M7', 'F4', 'M6', 'F5', 'M3', 'F1', 'M2', 'F2', 'M5', 'F6', 'M8', 'M1', 'M9' ]
]

Each group had all the students in it! I combed through each line of code several times, unable to figure out how this was happening. Because the code is simple—the main looping and assignment logic is only 5 lines —I started thinking truly farfetched thoughts: had I somehow corrupted my Python build?

Stumped, I set the script aside and left to cycle my laundry. As it often happens, while walking to the laundromat, an idea popped into my head. As soon as I got back, I tested my idea and it worked. Here's the problematic line:

groups = [ [] ] * NUM_GROUPS

I expected [ [] ] * NUM_GROUPS to create a list containing 5 different empty lists. Instead, that line of code creates a list containing 5 references to a single list. When adding a member to the first list, all lists received the member, because there was only a single underlying Python object for that list.

Curious to understand the underlying implementation responsible for this behavior, I dug into the source code for the Python interpreter. Since the problematic line of code involves multiplying a list by a number, here's the routine Python uses for multiplying two things (excerpted from abstract.c):

PyObject *
PyNumber_Multiply(PyObject *v, PyObject *w)
{
    PyObject *result = binary_op1(v, w, NB_SLOT(nb_multiply));
    if (result == Py_NotImplemented) {
        PySequenceMethods *mv = v->ob_type->tp_as_sequence;
        PySequenceMethods *mw = w->ob_type->tp_as_sequence;
        Py_DECREF(result);
        if  (mv && mv->sq_repeat) {
            return sequence_repeat(mv->sq_repeat, v, w);
        }
        else if (mw && mw->sq_repeat) {
            return sequence_repeat(mw->sq_repeat, w, v);
        }
        result = binop_type_error(v, w, "*");
    }
    return result;
}

It attempts to multiply the two objects using binary_op1. If that returns Py_NotImplemented (and it will for a Python list object), it tries using sequence_repeat. For a list object, sequence_repeat maps to list_repeat. Here's the relevant part of the implementation for list_repeat (excerpted from listobject.c):

items = np->ob_item;
if (Py_SIZE(a) == 1) {
    elem = a->ob_item[0];
    for (i = 0; i < n; i++) {
        items[i] = elem;
        Py_INCREF(elem);
    }
    return (PyObject *) np;
}

A couple quick definitions:

• a is the list that will be repeated.
• np is the new, repeated version of a.
• items is a reference to the objects contained by np.
• elem is a reference to the first (and only) object in a.
• n is the number of times to repeat the list.

You can see in the line items[i] = elem; that each slot in the new, repeated list points to the same singular elem. The Py_INCREF line says it all: each time the repeated element is added to the new list, Python increments the reference count for that object.

Fixing the behavior required ensuring that groups contained a list of separate lists, rather than a list of references to the same list.

groups = [ [], [], [], [], [] ]