Please report any errors directly to us: cs61b@eecs.berkeley.edu
Navigation
A. Before You Start
- Everyone should now be registered (with us, that is; TeleBEARS is a separate matter) and have a repository.
- Make sure that you've finished Lab 1, and especially its introduction to git.
If you will be running things on your laptop, we suggest that you set things up using our
cs61b-software
package to supply the necessary .jar files, etc. (without including them in every assignment you submit). To do this (and you should only do it on your home machine, not in your instructional account), go to your home directory and executegit clone -b cs61b-software cs61b-ta@ashby.cs.berkeley.edu:shared cs61b-software
Then, on Unix or MacOS, add the line
source $HOME/cs61b-software/adm/login
to your
.bash_profile
file. When next you login (or after you execute source ~/.bash_profile by hand), this should set your PATH and CLASSPATH variables properly.
On Windows, see the README in cs61b-software (section 5B) for setting your CLASSPATH.
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 checkout -b lab2 shared/lab2
git push -u origin lab2
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
course.
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 ppinter
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
myList.head
returns 0myList.tail
returns 1 -> 2 -> 3 -> nullmyList.tail.tail.tail
returns 3 -> nullmyList.tail.tail.tail.tail
returns 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 the 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 still
intact.
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. IDE's like Eclipse 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.