Lab 2: IntLists and GJDB

Please report any errors directly to us: cs61b@eecs.berkeley.edu

A. Before You Start

B. Introduction

In this lab, you will learn about debugging, IntLists (which appear in HW1), and destructive vs non-destructive methods.

As usual, you can get the start files for this lab from git. Make sure you have committed and pushed any current work in your repo directory, and then use

git fetch shared
git merge shared/lab2 -m "Start lab2"
git push

C. IntLists

Introduction to IntLists

As discussed in Wednesday's lecture, an IntList is our CS61B implementation for a linked list of integers, which you will have already seen if you took 61A, 61AS, or other introductory programming courses.

As we saw in lecture, an IntList has a head and tail property. We named it IntList because a set of these objects can represent a list (sequence) of Java int values. The head of the first IntList object is the first element of the list. The tail (another IntList) represents the list of remaining elements (that is, it is a pointer to the IntList object whose head is the second item of the list.)

As a result of this correspondence between sets of IntList objects and lists, we often conflate pointers to IntList objects with the lists they head and use the term "IntList" to refer both to individual IntList objects and to the entire set of objects reachable by following the tail pointers. Usually, the distinction is clear from context.

See IntList.java in the IntList directory for a refresher. We've added a method called list, which makes it easier to create IntLists. For example, to create an IntList containing the numbers 0, 1, 2, and 3, we could use the method as follows:

IntList myList = IntList.list(0, 1, 2, 3);

which will create the IntList 0 -> 1 -> 2 -> 3 -> null

The IntList.list method makes it much easier to create IntLists compared to the naive approach:

IntList myList = new IntList(0, null);
myList.tail = new IntList(1, null);
myList.tail.tail = new IntList(2, null);
myList.tail.tail.tail = new IntList(3, null);

There is also a convenient toString method. As we'll see later in the course, this is a useful method, because among other things, the standard print... methods in System.out use it whenever they are asked to print a value of type IntList, so that

System.out.println(myList);

will print

[0, 1, 2, 3]

Likewise, the "+" (append) operation on values of type String will use the toString method to figure out what string to append when adding an arbitrary object to a String.

Destructive vs. Nondestructive

Let's consider a method dSquareList that will destuctively square every item in a list.

IntList origL = Intlist.list(1, 2, 3)
dSquareList(origL);
// origL is now (1, 4, 9)

Where dSquareList is defined as follows:

public static void dSquareList(IntList L) {
    while (L != null) {
        L.head = L.head * L.head;
        L = L.tail;
    }
}

This is a classic example of a destructive method. It iterates through the list and squares each item, causing the values linked by L to change. In other words, after calling this method once on L, every element in L will be squared.

Examining the code above, we see that the origL variable contains a reference to the created IntList. The value of this variable never changes. By contrast, the L variable in dSquareList moves around inside the method when the line L = L.tail is executed.

As we iterate through the method, origL always points to the beginning of the IntList, but L moves to the right until it reaches the null value at the end.

The reason we say that dSquareList is destructive is that we change the values of the original IntList objects, destroying the original data. As we go along, we replace each head value with its square.

By the end of the method, L is null, and origL is still pointing at the beginning of the IntList, but every value in the IntList that origL points to is now squared.

If these ideas don't yet make total sense, ask a TA or lab assistant to draw a diagram of the code execution. Pointers and IntLists might seem confusing at first, but it's important that you understand these concepts!

Now, look at at squareListIterative and squareListRecursive. These methods are both non-destructive. That is, the underlying IntList passed into the methods does not get modified.

Look at the recursive version—try to reason why this is non-destructive. If you don't understand this yet, you should make sure you do before proceeding.

Now look at squarelistIterative. The iterative version of a non-destructive method is often quite a bit messier than the recursive version, since it takes some careful pointer action to create a new IntList, build it up, and return it. Try to understand what this code is doing, but don't stress if it doesn't all make sense right away.

Finally, look at the test method testdSquareList in IntListTest.java. Notice that this test checks whether or not dSquareList is destructive by making sure that the original list is mutated.

You're done reading code for now. Phew! Create a test for squareListRecursive that checks that it is not destructive. You will probably also want to test whether or not squareListRecursive is correct.

D. GJDB

One way to better understand the methods you've examining is to use a debugger to step through them interactively. Here, we'll use the Java debugger GJDB. You'll find gjdb documentation here. Java IDEs generally have debuggers with similar capabilities, and you are welcome to use them as you wish.

To use GJDB on your IntList and IntListTest classes, you must first compile with the -g option (as our Makefiles do):

javac -g IntList.java IntListTest.java

You can use gjdb from the command line or through its Emacs interface (the latter is described in the documentation referred to above). Here, let's just start with the command-line interface.

Having compiled the classes, start GJDB with the command

gjdb IntListTest

You should eventually get a [-] prompt. At this point, you can run the main program in IntListTest with

[-] run

You should get the same output you'd get from running java IntListTest outside of GJDB.
Now try setting a breakpoint, a place where the debugger will stop the program:

[-] break IntListTest.testdSquareList

Now when you run the program, it should stop at line 23 of IntListTest.java. The prompt will have changed to main[0]. When it does, you can execute line 23 and stop at the next by typing

main[0] next

and the program will stop on line 24. The command n is equivalent.

Now you can look around to see what's going on. First, try printing the current value of L:

main[0] p L

You'll get a line such as

$1 = instance of IntList(id=571)

This is how GJDB prints pointer values (the $1 lets you refer to the value later, if needed). To see what's actually in the object pointed to, you can ask GJDB to print the object itself:

main[0] p/1 L

You should see something like

$2 = instance of IntList(id=571) {
  head: 1
  tail: instance of IntList(id=572)
}

(the "id"s may be different; they simply distinguish one pointer value from another). As you can see, the tail of this list prints as a pointer. We can ask instead to print "two deep"; that is, to print the contents of the object plus the contents of any object it points to:

main[0] p/2 L

giving

$3 = instance of IntList(id=571) {
  head: 1
  tail: instance of IntList(id=572) {
    head: 2
    tail: instance of IntList(id=573)
  }
}

Because there is a toString method in IntList, we can also see a prettier version of this:

main[0] p L.toString()

or

main[0] p L + ""

will print

$4 = "[1, 2, 3]"

Indeed, the debugger can evaluate and print just about any Java expression. For example, the contents of the second int in L would be

main[0] p L.tail.head
$5 = 2

You can even create new IntList objects:

main[0] p new IntList(13, new IntList(42, null))
$6 = instance of IntList(id=637)
main[0] p $6 + ""
$7 = "[13, 42]"

This last example illustrates the use of the $ identifiers to refer back to previously displayed values.

At this point, we are stopped on line 24. Use next (or n) again to proceed to line 25, and then see what has become of L. You'll notice that the id number displayed by p L.tail has not changed, although the contents of the object pointed to by L.tail has.

At any time, you can continue normal execution of the program with the commands continue, cont, or just c. Try that now.
Suppose that you'd like to see dSquareList in action. You can set a breakpoint there, of course, but let's try something different. Run the program again, use next to get to line 24. Now to "step inside" of dSquareList, rather than "stepping over" it, use the command

main[0] step

(or just s). The program will stop on the first line of dSquareList in IntList.java. At this point, try stepping through one iteration of the while loop (so that L changes). Now execute the command

main[0] up

You'll find yourself back in testdSquareList, and you'll find that printing L gives you the value it has in that method, not in the dSquareList method you just left. The commands up and its partner down move the focus of the debugger "up and down the call chain", the sequence of functions that are currently executing. You can see the entire chain (or call stack or stack trace or backtrace) with the command where. Because we are running JUnit, you'll find the output of this command to be long and full of mysterious method names. Only the top few are of any interest. When executing ordinary programs outside of JUnit, you'll generally find the call stack much simpler.

Return the debugger's focus to dSquareList with the down command, which leaves you at the top of the stack (hey; I didn't invent this terminology).
Try the command

main[0] finish

and see if you can figure out what it does.

Recursion

Write a JUnit test testSquareListRecursive (as suggested by the comment in IntListTest.) Compile it and run GJDB on it again, this time stepping through the testSquareListRecursive method. Use step when going through squareListRecursive. When you reach the return null statement (the base case), use the commands you've learned to go up through the recursive calls and examine the values of L. Also, use where to see what a recursive call stack looks like. Finally, try out the command finish a couple of times to see how it behaves when in a recursive program.

A bug

Of course, GJDB is called a "debugger" because it's supposed to help with bugs. Let's see if we can tickle one. It turns out that there is an error in the IntList.equals method. It will be best if we do so outside of JUnit for now. For this purpose, we've put a main method in IntList (normally, you wouldn't expect one in a class that implements a data type like IntList). Write some statements that create lists, and then compare them with statements like this:

System.out.println(L1.equals(L2));

(which will print "true" or "false"). See if you can come up with a tests that causes .equals to "blow up" (throw an exception) when run in the usual way:

$ java IntList

Now run with GJDB:

$ gjdb IntList
$ run

Now when the program throws an exception, you should find the debugger stopped on the statement causing the problem. Use the print (p) command to see what is causing the exception.
Fix the bug in 'IntList.equals' and convert your tests in IntList into new JUnit tests in IntListTest.

Other features

There's a great deal in GJDB we haven't touched on, but you've got the basics. From time to time, you'll find the need for one of the many other features. For example, you can cause a breakpoint to stop only when certain conditions are met. Also, you can attach commands to a breakpoint so that when hit, these commands execute. You can arrange to print the value of a certain expression automatically whenever you step through a program. You can even ask Java to stop as soon as particular field of an object changes value (although admittedly, this feature really slows down your program). How do you do these things? Well, you can find out the same way I did: RTFM.

Emacs

Using the debugger from the command line is tedious. I much prefer the Emacs interface myself. IDEs like Intellij likewise allow you to avoid the command line. I suggest that you redo this lab (now or later), trying out the Emacs interface or that of your favorite IDE. It will pay off in future assignments.

E. Closing Thoughts

In the real world, the process of writing tests and debugging probably consumes most of time in a project. Never think that because you have "finished coding", you are anywhere near being finished! The debugger is therefore an important tool—one that you should learn and become comfortable with. Many students simply rely on "print" statements, which mess up one's program, produce incomprehensible volumes of output, and somehow never manage to get removed.

In this course, when you come to us with a stubborn bug in your program, we'll expect you to have made some reasonable attempt to have tracked down the problem. We'll ask pointed questions such as "What did the debugger show you had happened at such-and-such a point in the program?" With a little practice, you can be ready with an answer.