 |
Welcome to the third episode of the Software Carpentry lecture on program design using invasion percolation as an example. In this episode we’ll look at aliasing, and some bugs that can arise when your programs depend on it. |
 |
As you recall, we’re implementing a 2D grid using a list of lists. |
 |
A single list serves as the “spine” of the structure… |
 |
…and then each of the sublists stores actual values. |
 |
Here’s some code that creates an N×N grid containing 1′s. |
 |
Here’s some other code that is almost identical, but has a bug. |
 |
The only change we’ve made is to introduce a variable called EMPTY so that we can say “grid dot append EMPTY” inside our outermost loop. |
 |
How can this be a bug? Aren’t meaningful variable names supposed to be a good thing? |
 |
Well, let’s trace the execution of this program. We start by assigning an empty list to the variable grid. |
 |
We then assign another empty list to the variable EMPTY. |
 |
In the first pass through our loop, we append the empty list pointed to by EMPTY to the list pointed to by grid to get the structure shown on the left. |
 |
We then go into our inner loop and append a 1 to that sublist. |
 |
Going around the inner loop again, we append another 1… |
 |
…and another. |
 |
We then go back to the outer loop and append EMPTY again. The structure shown on the left is now broken: both cells of the list pointed to by grid point to the same sublist, because EMPTY is still pointing to that list, even though we’ve changed it. |
 |
So now, when we go into the inner loop, we’re appending 1′s to the same list that we were using last time. |
 |
You see the problem… |
 |
Any time we use indirection, it allows aliasing, i.e., it allows us to have two or more references to the same object. |
 |
This can be very useful… |
 |
…in fact, in some situations it’s absolutely essential… |
 |
…but it can also be a rich source of bugs. |
 |
Whenever you’re in doubt about what your data structures are supposed to look like, draw a picture and check it against the code. |
 |
There are some tools that can do this for you automatically… |
 |
…but so far, none of them has been widely adopted. |
 |
|
