archive.tex

\section{The first bug}

In the old days, computer scientists had to deal with real bugs flying into their systems.
You probably won't have that problem, but you will need to think creatively when unexpected errors happen.

\begin{figure}[!ht]
\begin{center}
\includegraphics[height=2.2in]{figs/firstbug.jpg}
\caption{The first computer bug, taped to Grace Hopper's log book in 1947.
\\ She discovered the moth in an electromagnetic relay of the Mark II.}
\end{center}
\end{figure}

% ABD: I don't love this particular piece of mythology, partly because it's not accurate, and partly because stories about the old days bore students.


\section{Formal languages}

\index{natural language}
\index{language!natural}

Learning a programming language is very different from learning a {\bf natural language} such as English, Spanish, or German.
The languages that people speak evolved naturally over time.
%They were not designed by people, although we try to impose order on them for practical reasons.

\index{formal language}
\index{language!formal}

In contrast, {\bf formal languages} are designed by people for specific applications.
For example, the notation that mathematicians use is a formal language that is particularly good at denoting relationships among numbers and symbols.
Chemists use a formal language to represent the chemical structure of molecules.
And most importantly:

\index{programming language}
\index{language!programming}

\begin{quote}
{\bf Programming languages are formal languages that have been designed to express computations.}
\end{quote}

\index{syntax}
\index{semantics}

Formal languages have strict rules about both the {\bf syntax} (structure) and the {\bf semantics} (meaning) of statements.
For example, $3 + 3 = 6$ is a syntactically correct mathematical statement, but $3\ + = 3\ \$\ 6$ is not.
$1 + 2 = 4$ uses correct syntax, but is semantically incorrect.
$H_2O$ is a syntactically correct chemical formula, but $_2Zz$ is not.

%\subsection{Tokens and grammar}

\index{token}

Syntax rules come in two flavors, pertaining to tokens and grammar.
{\bf Tokens} are the basic elements of the language, like words, numbers, and chemical elements.
One of the problems with $3\ + = 3\ \$\ 6$ is that $\$$ is not a legal token in mathematics.
Similarly, $_2Zz$ is not legal because there is no element with the abbreviation $Zz$.

\index{grammar}

The second type of syntax rule pertains to the {\bf grammar} of the language, or the way tokens can be arranged.
The statement $3\ + = 3$ is structurally illegal, even though $+$ and $=$ are legal tokens, because you can't have one right after the other.
Similarly, in a chemical formula the subscript comes after the element name, not before.

\index{parse}

When you read a sentence in English or a statement in a formal language, you have to figure out its structure.
This process is called {\bf parsing}, and in a natural language you learn to do it unconsciously.
As you learn to program, you will learn to parse Java code.

%For example, when you hear the statement ``the penny dropped,'' you understand that the penny is the subject and ``dropped'' is the predicate.
%After you have parsed the statement, you can begin to figure out what it means.
%Assuming that you know what a penny is and what it means to drop, you will understand the general implication of this statement.

%\subsection{Reading source code}

Beginning programmers, who are used to natural languages, often have a hard time adjusting to formal languages.
Although formal and natural languages have features in common---tokens, grammar, and meaning---there are some differences:

\begin{description}

\term{ambiguity}
Natural languages are full of ambiguity, which people deal with by using contextual clues and other information.
Formal languages are designed to be nearly or completely unambiguous, which means that any statement has exactly one meaning, regardless of context.

\term{redundancy}
In order to make up for ambiguity and reduce misunderstandings, natural languages employ lots of redundancy.
As a result, they are often verbose.
Formal languages are less redundant and more concise.

\term{literalness}
Natural languages are full of idiom and metaphor.
When someone says ``the penny dropped'' there is no penny and nothing dropping.
This idiom means that someone finally realized something after a period of confusion.
In contrast, formal languages mean exactly what they say.

\end{description}

In some ways, the difference between natural and formal language is like the difference between poetry and prose, but more so.

\begin{description}

\term{poetry}
Words are used for their sounds as well as for their meaning, and the whole poem together creates an effect or emotional response.
Ambiguity is not only common but often deliberate.

\term{prose}
The literal meaning of words is more important, and the structure contributes more meaning.
Prose is more amenable to analysis than poetry but still often ambiguous.

\term{program}
The meaning of a computer program is unambiguous and literal, and can be understood entirely by analysis of the tokens and grammar.

\end{description}

Here are some suggestions for reading programs (and other formal languages).

Small errors in spelling and punctuation, which you can get away with in natural languages, can make a big difference in a formal language.

Also, formal languages are more dense than natural languages, so it takes longer to read them.
The structure is very important, so it is not always a good idea to read from top to bottom, left to right.
Over time you will learn to parse programs in your head, identifying the tokens and interpreting the structure.
And you will learn to read and write programs more quickly.


\term{natural language}
Any of the languages people speak that have evolved naturally.

\term{formal language}
A language people have designed for specific purposes, like representing mathematical ideas or computer programs.

\term{programming language}
A formal language that has been designed to express computations.

\term{syntax}
The structure of a program.

\term{semantics}
The meaning of a program.

\term{token}
A basic element of a program, such as a word, space, symbol, or number.

\term{grammar}
A set of rules that determines whether a statement is legal.

\term{parse}
To examine a program and analyze the syntactic structure.


\section{Emotional debugging}

\index{emotional debugging}
\index{debugging!emotional response}

There is evidence that people naturally respond to computers as if they were people.
When they work well, we think of them as teammates, and when they are obstinate or rude, we respond to them the same way we respond to rude, obstinate people.
(Reeves and Nass, {\it The Media Equation: How People Treat Computers, Television, and New Media Like Real People and Places})

Preparing for these reactions might help you deal with them.
One approach is to think of the computer as an employee with certain strengths, like speed and precision, and particular weaknesses, like lack of empathy and inability to grasp the big picture.

Your job is to be a good manager: find ways to take advantage of the strengths and mitigate the weaknesses.
And find ways to use your emotions to engage with the problem, without letting your reactions interfere with your ability to work effectively.

Learning to debug can be frustrating, but it is a valuable skill that is useful for many activities beyond programming.
At the end of each chapter there is a debugging section, like this one, with my thoughts about debugging.
I hope they help!


\section{Syntax errors}

\index{syntax error}
\index{error!syntax}

{\bf Syntax} pertains to the structure of a program and the arrangement of the words and symbols it contains.
Programming languages have syntax rules.
For example, parentheses have to come in matching pairs.
So \java{(1 + 2)} is legal, but \java{8)} is not.
If you violate a syntax rule, you have committed a {\bf syntax error}.
In that case, you program cannot be translated or run; instead, the compiler stops and displays an error message.

\begin{figure}[!h]
\begin{center}
\includegraphics[width=\textwidth]{figs/syntax-error.png}
\caption{A syntax error caused by a missing brace.}
\label{fig:syntax}
\end{center}
\end{figure}

As shown in Figure~\ref{fig:syntax}, removing the closing brace on line 8 of the hello world program results in ``Error: reached end of file while parsing.''
The compiler also reports that the problem was found on line 6, which in this case is not at fault.
Since line 8 was deleted, the compiler reported the last line of the file.


\section{OS abstraction}

\index{object}

Both \java{System} and \java{PrintStream} are written in Java, and later in the book we'll examine their source code.
For now, you should understand that \java{System.out} is a \java{PrintStream} object.
Because Java is an {\em object-oriented} language, much of the library is organized around objects that perform specific actions.

% ABD: there is so much new vocab in these sections, I want to reduce the number of new ideas

\index{operating system}

As with most software, Java programs run on top of an {\bf operating system} that manages the keyboard, the display, main memory, disk drives, printers, the network, and other hardware resources.
Common examples of operating systems include Android, iOS, Linux, Mac OS~X, and Windows.
When starting Java programs, the operating system directs \java{System.out} to the screen.

\index{abstraction}

Note the exact type of display doesn't matter, whether it's a 5-inch touch screen or 30-inch monitor.
From the programmer's point of view, \java{System.out} simply provides the means for printing messages.
Computer scientists often use {\bf abstraction} to deal with the complexity of software.
The \java{System} class is a platform-independent abstraction of the operating system.
The operating system itself is a layer of abstraction on top of computer hardware.

% ABD: Since I killed the previous reference to abstraction, I am inclined
% to kill this one too.  The problem in both places is that it pulls the
% focus off topic.

Redirecting a program's input and output is an example of how computer scientists use abstraction.
Notice that \java{System.in} is not called \java{Keyboard}, and \java{System.out} is not called \java{Display}.
In practice, these objects could be text files, network connections, microphones and speakers, or some other byte streams.
What's great is that doesn't change anything about how you write the code.


\section{Type conversion}

The difference is when the conversion from integer to string actually takes place.

Fortunately, this situation only happens when using the plus operator.
You cannot, for example, store an integer directly in a string variable.

\begin{code}
String number = 5;  // syntax error
\end{code}

In general, it's better not to compose multiple additions of varying data types.
Instead you can break those statements into multiple lines, or use another method like \java{printf} to achieve the same results.

% TODO: add the following subsection before/after operators for strings?
% ABD: maybe not: we have an exercise about this

\index{type!conversion}
\index{typecasting}

You might wonder how you can get away with an expression like \java{
"The log of x is " + result}, since one of the operands is a \java{String}
and the other is a \java{double}.  In this case Java is being
smart on our behalf, automatically converting the \java{double} to a
\java{String} before it does the string concatenation.

This kind of feature is an example of a common problem in designing a
programming language, which is that there is a conflict between {\em
formalism}, which is the requirement that formal languages should have
simple rules with few exceptions, and {\em convenience}, which is the
requirement that programming languages be easy to use in practice.

More often than not, convenience wins, which is usually good for
expert programmers (who are spared from rigorous but unwieldy
formalism), but bad for beginning programmers, who are often baffled
by the complexity of the rules and the number of exceptions.  In this
book I have tried to simplify things by emphasizing the rules and
omitting many of the exceptions.

Whenever you try to ``add'' two
expressions, if one of them is a \java{String}, Java converts the
other to a \java{String} and then performs string concatenation.
What do you think happens if you perform an operation between
an integer and a floating-point value?


\section{Computational thinking}

A number of years ago, Jeannette Wing published a terrific editorial with the title {\it Computational Thinking}, or in her own words, ``Ways to Think Like a Computer Scientist'' (see Communications of the ACM, March 2006).
This 3-page article summarizes many of the problem solving techniques you will discover while learning to program.
Everyone interested in learning computer science beyond programming should read it.
She defines the field this way:

\index{computer science}

\begin{quote}
{\bf ``Computer science is the study of computation -- what can be computed and how to compute it.''}
\end{quote}


\section{Parity (in a method)}
\label{alternative}

\index{parity}

To follow up the previous chapter, if you need to check the {\bf parity} (evenness or oddness) of numbers often, you might want to ``wrap'' this code up in a method:

\begin{code}
public static void printParity(int x) {
    if (x % 2 == 0) {
        System.out.println("x is even");
    } else {
        System.out.println("x is odd");
    }
}
\end{code}

Now you have a method named \java{printParity} that will print an appropriate message for any integer you care to provide.
In \java{main} you would invoke this method as follows:

\begin{code}
printParity(17);
\end{code}

Always remember that when you invoke a method, you do not have to declare the types of the arguments you provide.
Java can figure out what type they are.
You should resist the temptation to write things like:

\begin{code}
int number = 17;
printParity(int number);        // WRONG!!!
\end{code}


\section{Euclid's algorithm}

\begin{exercise}
\label{gcd}

Write a method called \java{gcd} that takes two integer parameters and that uses Euclid's algorithm to compute and return the greatest common divisor of the two numbers.

Euclid's Algorithm, which appears in Euclid's {\it Elements} (ca.~300 BC), might be the oldest recorded nontrivial algorithm.
The process is based on the observation that, if $r$ is the remainder when $a$ is divided by $b$, the common divisors of $a$ and $b$ are the same as the common divisors of $b$ and $r$.
\[ gcd(a, b) = gcd(b, r) \]
%
We can use this fact to reduce the problem of computing a GCD to the problem of computing the GCD of smaller and smaller pairs of integers.
For example:
\[ gcd(36, 20) = gcd(20, 16) = gcd(16, 4) = gcd(4, 0) = 4 \]
%implies that the GCD of 36 and 20 is 4.

%It can be shown that for any two starting numbers, this repeated reduction eventually produces a pair where the second number is 0.
%Then the GCD is the other number in the pair.

(This exercise is based on page 44 of Abelson and Sussman's {\it Structure and Interpretation of Computer Programs}, MIT Press, 1984.)

\end{exercise}


\section{Increment and decrement}

\index{operator!increment}
\index{operator!decrement}

Incrementing and decrementing are such common operations that Java provides special operators for them.
The {\tt ++} operator adds one to the current value of an {\tt int} or {\tt char}.
{\tt --} subtracts one.
Neither operator works on {\tt double}s, {\tt boolean}s or {\tt String}s.

Technically, it is legal to increment a variable and use it in an expression at the same time.
For example, you might see something like:

\begin{code}
System.out.println(i++);
\end{code}

Looking at this, it is not clear whether the increment will take effect before or after the value is printed.
Because expressions like this tend to be confusing, I discourage you from using them.
In fact, to discourage you even more, I'm not going to tell you what the result is.
If you really want to know, you can try it.

Using the increment operators, we can rewrite the letter-counter:

\begin{code}
int index = 0;
while (index < length) {
    if (fruit.charAt(index) == 'a') {
        count++;
    }
    index++;
}
\end{code}

It is a common error to write something like

\begin{code}
index = index++;             // WRONG!!
\end{code}

Unfortunately, this is syntactically legal, so the compiler will not warn you.
The effect of this statement is to leave the value of {\tt index} unchanged.
This is often a difficult bug to track down.

Remember, you can write {\tt index = index+1}, or you can write {\tt index++}, but you shouldn't mix them.


\section{Bottom-up development}

\index{program development}
\index{bottom-up}

The next few sections develop the code to generate a histogram.
A good approach to solving problems like this one is to think of simple methods that are easy to write and then combine them into a solution.
This process is called {\bf bottom-up} development.
It is not always obvious where to start, but a good approach is to look for subproblems that fit a pattern you have seen before.

\index{traverse!array}
\index{array!traverse}
\index{looping and counting}

In Section~\ref{loopcount}, we saw a loop that traversed a string and counted the number of times a given letter appeared.
You can think of this program as an example of a pattern called ``traverse and count''.
The elements of this pattern are:

\begin{itemize}
\item A container that can be traversed, like an array or a string.
\item A test you can apply to each element in the container.
\item A counter that keeps track of how many elements pass the test.
\end{itemize}

In the case of building a histogram, the container is an array of integers.
The test is whether or not a given score falls in a given range of values.
And the counter is the histogram itself.


\section{Class definitions and object types}

Here are some syntax issues about class definitions:

\begin{itemize}

\item Class names (and hence object types) should begin with a capital letter, which helps distinguish them from primitive types and variable names.

\item You usually put one class definition in each file, and the name of the file must be the same as the name of the class, with the suffix {\tt .java}.
For example, the \java {class Time} is defined in the file named {\tt Time.java}.

\item In any program, one class is designated as the {\bf startup class} that contains a method named \java{main} where the execution of the program begins.
Other classes {\em may} have a method named \java{main}, but it will not be executed (unless another method calls it directly for some reason).

\end{itemize}

\term{startup class}
The class that contains the \java{main} method where execution of the program begins.

\term{pure function}
A method whose result depends only on its parameters, and that has no side-effects other than returning a value.


\section{Objects and primitives}

\index{type!object}
\index{type!primitive}
\index{object type}
\index{primitive type}

There are two kinds of types in Java, primitive types and reference types.
Primitives, like \java{int} and \java{char} begin with lowercase letters; reference types like \java{String} begin with uppercase letters.
This distinction is useful because it reminds us of some of the differences between them:

\begin{itemize}

\item When you declare a primitive variable, you get storage space for a primitive value.
When you declare a reference variable, you only get space for a reference to an object.
To get space for the object itself, you have to use \java{new}.

\item If you don't initialize a primitive type, it is given a default value that depends on the type.
For example, {\tt 0} for {\tt int}s and {\tt false} for {\tt boolean}s.
The default value for object types is {\tt null}, which indicates no object.

\item Primitive variables are well isolated in the sense that there is nothing you can do in one method that will affect a variable in another method.
Object variables can be tricky to work with because they are not as well isolated.
If you pass a reference to an object as an argument, the method you invoke might modify the object, in which case you will see the effect.
Of course, that can be a good thing, but you have to be aware of it.

\end{itemize}

There is one other difference between primitives and object types.
You cannot add new primitives to Java (unless you get yourself on the standards committee), but you can create new object types!  We'll see how in the next chapter.


% was in Chapter 8 Strings and Things
\begin{exercise}
If you did the GridWorld exercises in Chapter~\ref{gridworld1}, you
might enjoy this exercise.  The goal is to use trigonometry to get the
Bugs to chase each other.

Make a copy of {\tt BugRunner.java} named {\tt ChaseRunner.java} and
import it into your development environment.  Before you change
anything, check that you can compile and run it.

\begin{itemize}

\item Create two Bugs, one red and one blue.

\item Write a method called {\tt distance} that takes two Bugs
and computes the distance between them.  Remember that you can
get the x-coordinate of a Bug like this:

\begin{code}
int x = bug.getLocation().getCol();
\end{code}

\item Write a method called {\tt turnToward} that takes two
Bugs and turns one to face the other.  HINT: use {\tt Math.atan2},
but remember that the result is in radians, so you have to
convert to degrees.  Also, for Bugs, 0 degress is North, not East.

\item Write a method called {\tt moveToward} that takes two
Bugs, turns the first to face the second, and then moves the
first one, if it can.

\item Write a method called {\tt moveBugs} that takes two Bugs
and an integer {\tt n}, and moves each Bug toward the other {\tt n}
times.  You can write this method recursively, or use a while loop.

\item Test each of your methods as you develop them.  When they are
  all working, look for opportunities to improve them.  For example,
  if you have redundant code in {\tt distance} and {\tt turnToward},
  you could encapsulate the repeated code in a method.

\end{itemize}
\end{exercise}


% was in Chapter 8 Strings and Things
\begin{exercise}
What is the output of the following program?

\begin{code}
public class Enigma {

    public static void enigma(int x) {
        if (x == 0) {
            return;
        } else {
            enigma(x / 2);
        }
        System.out.print(x % 2);
    }

    public static void main(String[] args) {
        enigma(5);
        System.out.println("");
    }
}
\end{code}

Explain in 4-5 words what the method {\tt enigma} really does.
\end{exercise}


\section{Object methods and class methods}

\index{object method}
\index{method!object}
\index{class method}
\index{method!class}
\index{static}

There are two types of methods in Java, called {\bf class methods} and
{\bf object methods}.  Class methods are identified by the keyword {\tt
  static} in the first line.  Any method that does {\em not} have the
keyword {\tt static} is an object method.

Although we have not written object methods, we have invoked some.
Whenever you invoke a method ``on'' an object, it's an object method.
For example, {\tt charAt} and the other methods we invoked on {\tt String}
objects are all object methods.

For example, here is {\tt printCard} as a class method:

\begin{code}
public static void printCard(Card c) {
    System.out.println(ranks[c.rank] + " of " + suits[c.suit]);
}
\end{code}

Anything that can be written as a class method can also be written as an
object method, and vice versa.  But sometimes it is more natural to
use one or the other.
Here it is re-written as an object method:

\begin{code}
public void print() {
    System.out.println(ranks[rank] + " of " + suits[suit]);
}
\end{code}

Here are the changes:

\begin{enumerate}

\item I removed {\tt static}.

\item I changed the name of the method to be more idiomatic.

\item I removed the parameter.

\item Inside an object method you can refer to instance variables
as if they were local variables, so I changed {\tt c.rank} to {\tt rank},
and likewise for {\tt suit}.

\end{enumerate}

Here's how this method is invoked:

\begin{code}
Card card = new Card(1, 1);
card.print();
\end{code}

When you invoke a method on an object, that object becomes the {\bf
current object}, also known as {\tt this}.  Inside {\tt print},
the keyword {\tt this} refers to the card the method was invoked on.
\index{current object}
\index{object!current}
\index{this}


\section{Oddities and errors}

\index{method!object}
\index{method!class}
\index{overloading}

If you have object methods and class methods in the same class, it is
easy to get confused.  A common way to organize a class definition is
to put all the constructors at the beginning, followed by all the
object methods and then all the class methods.

You can have an object method and a class method with the same
name, as long as they do not have the same number and types of
parameters.  As with other kinds of overloading, Java decides
which version to invoke by looking at the arguments you provide.
\index{static}

Now that we know what the keyword {\tt static} means, you
have probably figured out that {\tt main} is a class method,
which means that there is no ``current object'' when it is invoked.
\index{current object}
\index{this}
\index{instance variable}
\index{variable!instance}
%
Since there is no current object in a class method, it is an
error to use the keyword {\tt this}.  If you try, you get
an error message like: ``Undefined variable: this.''

Also, you cannot refer to instance variables without using dot
notation and providing an object name.  If you try, you get a message
like ``non-static variable... cannot be referenced from a static
context.''  By ``non-static variable'' it means ``instance variable.''


\section{Operations on objects}
\label{objectops}
\index{object}
\index{operator!object}

In the next few
sections, I demonstrate three kinds of methods that
operate on objects:

\begin{description}

\item[pure function:]  Takes objects as
arguments but does not modify them.  The return value is
either a primitive or a new object created inside the method.

\item[modifier:]  Takes objects as arguments and modifies some
or all of them.  Often returns void. \index{void}

\item[fill-in method:]  One of the arguments is an ``empty''
object that gets filled in by the method.  Technically, this is
a type of modifier.

\end{description}

Often it is possible to write a given method as a pure function, a modifier,
or a fill-in method.  I will discuss the pros and cons of each.


\section{Fill-in methods}
\index{fill-in method}
\index{method!fill-in}

Instead of creating a new object every time {\tt addTime} is invoked, we could require the caller to provide an object where {\tt addTime} stores the result.
Compare this to the previous version:

\begin{code}
public static void addTimeFill(Time t1, Time t2, Time sum) {
    sum.hour = t1.hour + t2.hour;
    sum.minute = t1.minute + t2.minute;
    sum.second = t1.second + t2.second;

    if (sum.second >= 60.0) {
        sum.second -= 60.0;
        sum.minute += 1;
    }
    if (sum.minute >= 60) {
        sum.minute -= 60;
        sum.hour += 1;
    }
}
\end{code}

The result is stored in {\tt sum}, so the return type is {\tt void}.

Modifiers and fill-in methods are efficient because they don't have to create new objects.
But they make it more difficult to isolate parts of a program; in large projects they can cause errors that are hard to find.

Pure functions help manage the complexity of large projects, in part by making certain kinds of errors impossible.
Also, they lend themselves to certain kinds of composition and nesting.
And because the result of a pure function depends only on the parameters, it is possible to speed them up by storing previously-computed results.

\index{pure function}

I recommend that you write pure functions whenever it is reasonable, and resort to modifiers only if there is a compelling advantage.

%\term{fill-in method}
%A type of method that takes an ``empty'' object as a parameter and fills in its instance variables instead of generating a return value.


\section{Incremental development}

\index{incremental development}
\index{prototyping}
\index{program development!incremental}
\index{program development!planning}

In this chapter I demonstrated a program development process called
{\bf rapid prototyping}\footnote{What I am calling rapid prototyping
  is similar to test-driven development (TDD); the difference is that
  TDD is usually based on automated testing.  See
  \url{http://en.wikipedia.org/wiki/Test-driven_development}.}.  For
each method, I wrote a rough draft that performed the
basic calculation, then tested it on a few cases, correcting flaws
as I found them.

This approach can be effective, but it can lead to code
that is unnecessarily complicated---since it deals with many
special cases---and unreliable---since it is hard to convince
yourself that you have found {\em all} the errors.

An alternative is to look for insight
into the problem that can make the programming easier.  In
this case the insight is that a {\tt Time} is really a three-digit
number in base 60!  The {\tt second} is the ``ones column,''
the {\tt minute} is the ``60's column'', and the {\tt hour}
is the ``3600's column.''

When we wrote {\tt addTime} and {\tt increment}, we were effectively
doing addition in base 60, which is why we had to ``carry'' from one
column to the next.

\index{arithmetic!floating-point}

Another approach to the whole problem is to convert
{\tt Time}s into {\tt double}s and take advantage of the fact that
the computer already knows how to do arithmetic with {\tt double}s.
Here is a method that converts a {\tt Time} into a {\tt double}:

\begin{code}
public static double convertToSeconds(Time t) {
    int minutes = t.hour * 60 + t.minute;
    double seconds = minutes * 60 + t.second;
    return seconds;
}
\end{code}

Now all we need is a way to convert from a {\tt double}
to a {\tt Time} object.  We could write a method to
do it, but it might make more sense to write it as a third
constructor:

\begin{code}
public Time(double secs) {
    this.hour =(int)(secs / 3600.0);
    secs -= this.hour * 3600.0;
    this.minute =(int)(secs / 60.0);
    secs -= this.minute * 60;
    this.second = secs;
}
\end{code}

This constructor is a little different from the others;
it involves some calculation along with assignments to the
instance variables.

You might have to think to convince yourself that the technique
I am using to convert from one base to another is correct.  But once
you're convinced, we can use these methods to rewrite {\tt addTime}:

\begin{code}
public static Time addTime(Time t1, Time t2) {
    double seconds = convertToSeconds(t1) + convertToSeconds(t2);
    return new Time(seconds);
}
\end{code}

This is shorter than the original version, and it is much easier
to demonstrate that it is correct (assuming, as usual, that the
methods it invokes are correct).  As an exercise, rewrite {\tt
increment} the same way.


\section{Generalization and algorithms}

\index{generalization}

In some ways converting from base 60 to base 10 and back is
harder than just dealing with times.  Base conversion is more
abstract; our intuition for dealing with times is better.

But if we have the insight to treat times as base 60 numbers,
and make the investment of writing the conversion methods
({\tt convertToSeconds} and the third constructor), we get
a program that is shorter, easier to read and debug, and more
reliable.

It is also easier to add features later.  Imagine
subtracting two {\tt Time}s to find the duration between them.  The
naive approach would be to implement subtraction complete with
``borrowing.''  Using the conversion methods would be much easier.

Ironically, sometimes making a problem harder (more general)
makes it easier (fewer special cases, fewer opportunities for error).

%TODO show solution?

%\section{Algorithms}
%\label{algorithm}

\index{algorithm}

When you write a general solution for a class of problems, as
opposed to a specific solution to a single problem, you have
written an {\bf algorithm}.  This word is
not easy to define, so I will try a couple of approaches.

First, consider some things that are not algorithms.  When you learned
to multiply single-digit numbers, you probably memorized the
multiplication table.  In effect, you memorized 100 specific
solutions, so that knowledge is not really algorithmic.

But if you were ``lazy,'' you probably learned a few
tricks.  For example, to find the product of $n$ and 9, you can
write $n-1$ as the first digit and $10-n$ as the second digit.  This
trick is a general solution for multiplying any single-digit number by 9.
That's an algorithm!

Similarly, the techniques you learned for addition with carrying,
subtraction with borrowing, and long division are all algorithms.  One
of the characteristics of algorithms is that they do not require any
intelligence to carry out.  They are mechanical processes in which
each step follows from the last according to a simple set of rules.

In my opinion, it is embarrassing that humans spend so much
time in school learning to execute algorithms that,
quite literally, require no intelligence.
%
On the other hand, the process of designing algorithms is
interesting, intellectually challenging, and a central part
of what we call programming.

Some of the things that people do naturally, without difficulty
or conscious thought, are the most difficult to express
algorithmically.  Understanding natural language is a good
example.  We all do it, but so far no one has been able to
explain {\em how} we do it, at least not in the form of an
algorithm.

%~ Soon you will have the opportunity to design
%~ simple algorithms for a variety of problems.

%\item[algorithm:]  A set of instructions for solving a class of
%problems by a mechanical process.


\section{Cards graphics exercises}

\begin{exercise}
Working with cards is more interesting if you can display them on the screen.
If you haven't played with the graphics examples in Appendix~\ref{graphics}, you might want to do that now.

First download
\url{http://thinkapjava.com/code/CardTable.java}
and
\url{http://thinkapjava.com/code/cardset.zip} into the same folder.
Then unzip {\tt cardset.zip}, which contains a {\tt cardset-oxymoron}
subfolder with all the card images. (Note the variable \java{cardset}
in \java{CardTable.main} is the name of this folder.)
Run \java{CardTable.java} and you
should see images of a pack of cards laid out on a green table.

You can use this class as a starting place to implement your own
card games.
\end{exercise}

% TODO from Leslie Klein:
% Need more descriptive text on how to modify CardTable.java so that it can find the gif files that are extracted from cardset.zip.
% If CardTable.java and all the .gif files are in the same package, and I run CardTable, I just get a green table, without the cards.
% Need text on how to set the variable cardset: the String name of the folder that contains the card images.
%-----
% Create a folder under your project called “images”. Put all the .gif files from cardset.zip into this folder.
% Make the following change in main(String[] args): change value of cardset to the name of the folder containing the images. For example,
% cardset = "images";
% Now when main() calls CardTable(cardset), CardTable can find all the gif files.


\section{Decks and subdecks}
\index{deck}
\index{subdeck}

\index{prototype}
Here is the prototype (see Section~\ref{documentation}) of \java{findBisect}:

\begin{code}
public static int findBisect(Card[] deck, Card card, int low, int high)
\end{code}

\index{parameter!abstract}
\index{abstract parameter}

We can think of \java{cards}, \java{low}, and \java{high} as a single parameter that specifies a {\bf subdeck}.
This way of thinking is common, and is sometimes referred to as an {\bf abstract parameter}.
What I mean by ``abstract'' is something that is not literally part of the program text, but which describes the function of the program at a higher level.

For example, when you invoke a method and pass an array and the bounds \java{low} and \java{high}, there is nothing that prevents the invoked method from accessing parts of the array that are out of bounds.
So you are not literally sending a subset of the deck; you are really sending the whole deck.
But as long as the recipient plays by the rules, it makes sense to think of it abstractly as a subdeck.

This kind of thinking, in which a program takes on meaning beyond what is literally encoded, is an important part of thinking like a computer scientist.
The word ``abstract'' gets used so often and in so many contexts that it comes to lose its meaning.
Nevertheless, {\bf abstraction} is a central idea in computer science (and many other fields).

\index{abstraction}

A more general definition of ``abstraction'' is ``The process of modeling a complex system with a simplified description to suppress unnecessary details while capturing relevant behavior.''

%\term{abstract parameter}
%A set of parameters that act together as a single parameter.

%\term{abstraction}
%The process of interpreting a program (or anything else) at a higher level than what is literally represented by the code.


\section{The Point class}

When you define a class in Java, you are also defining a new data type.
It is helpful to think of classes as the blueprints (or a template) for objects.
To illustrate this point (pun intended), here is a simplified version of the source code for the \java{java.awt.Point} class:

\begin{code}
public class Point {

    public int x;
    public int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public String toString() {
        return "Point[x=" + x + ",y=" + y + "]";
    }

}
\end{code}

There are several details to note in this example.

\begin{itemize}

\item The class defines two variables (attributes) named \java{x} and \java{y} that are shared across all methods.
Because they are declared at the class level, their scope is the entire class.

\item The method \java{public Point(int x, int y)} is called a {\bf constructor}.
Its purpose is to initialize new objects, and it is called by the \java{new} operator.
Notice that it has no return type (not even \java{void}).

\item The parameters \java{x} and \java{y} in the constructor happen to have the same name as the attributes.
In order to distinguish one variable from the other, the keyword \java{this} refers to the current object.

%\item None of the variables or methods are \java{static}.
%In other words, they apply to each object of the class as opposed to the class itself.
%We will discuss this issue more deeply in the next chapter.

\end{itemize}

\index{instance variable}
\index{variable!instance}

The attributes that make up an object are also called instance variables, because each object has its own copy of the variables.
Classes define new data types, and each object is an {\bf instance} of that type.

It's like the glove compartment of a car.
Each car is an instance of the type ``Car,'' and each car has its own glove compartment.
If you ask me to get something from the glove compartment of your car, you have to tell me which car is yours.


\section{Local variables}

%TODO: this section is not up to date with previous discussion of this topic

You might wonder how we can use the same variable \java{i} in both \java{printMultiples} and \java{printMultTable}.
Isn't it true that you can only declare a variable once?
And doesn't it cause problems when one of the methods changes the value of the variable?

The answer to both questions is ``no,'' because the \java{i} in \java{printMultiples} and the \java{i} in \java{printMultTable} are {\em not the same variable}.
They have the same name, but they do not refer to the same storage location.
Changing the value of one variable has no effect on the other.
Consider the stack diagram at the moment the program begins printing the second row of the table:

\begin{center}
\vspace{1em}
\includegraphics{figs/stack4.pdf}
\vspace{1em}
\end{center}

%\begin{tabular}{rl}
%          main & \framebox[3cm][r]{\strut args ~\framebox[1cm]{\strut  }~} \\[1em]
%printMultTable & \framebox[3cm][r]{\strut    i ~\framebox[1cm]{\strut 2}~} \\[1em]
%printMultiples & \framebox[3cm][r]{\strut    i ~\framebox[1cm]{\strut 2}~} \\[1em]
%\end{tabular}

\index{local variable}
\index{variable!local}

Variables and parameters declared inside a method definition are called {\bf local variables} because they only exist inside the method.
You cannot access a local variable from outside its method, and you are free to have multiple variables with the same name as long as they are not in the same method.

\index{loop variable}
\index{variable!loop}

Although it can be confusing, there are good reasons to reuse names.
For example, it is common to use the names \java{i}, \java{j} and \java{k} as loop variables.
If you avoid using them in one method just because you used them somewhere else, you make the program harder to read.
Another reason is when two or more methods are based on the same parameter.
It's awkward to come up with many different names for the same data.


%TODO: make these exercises

Because they make the code more readable, you should use enhanced \java{for} loops whenever possible.
For example, the following loop finds the maximum value in an array of integers:

\begin{code}
int max = Integer.MIN_VALUE;
for (int value : numbers) {
    if (value > max) {
        max = value;
    }
}
\end{code}

But notice that the enhanced \java{for} loop does not give you the index the value.
If you need to find the index of the maximum value, you have to use a standard \java{for} loop.

\begin{code}
int index = -1;
int max = Integer.MIN_VALUE;
for (int i = 0; i < numbers.length; i++) {
    if (numbers[i] > max) {
        index = i;
        max = numbers[i];
    }
}
\end{code}


\begin{exercise}
One not-very-efficient way to sort the elements of an array is to find the largest element and swap it with the first element, then find the second-largest element and swap it with the second, and so on.
This algorithm is called selection sort (see \url{http://en.wikipedia.org/wiki/Selection_sort}).

\begin{enumerate}

\item Write a method called \java{indexOfMaxInRange} that takes an array of integers, finds the largest element in the given range, and returns its {\em index}.
%You can modify your recursive version of \java{maxInRange} or you can write an iterative version from scratch.

\item Write a method called \java{swapElement} that takes an array of integers and two indexes, and that swaps the elements at the given indexes.

\item Write a method called \java{selectionSort} that takes an array of integers and that uses \java{indexOfMaxInRange} and \java{swapElement} to sort the array from largest to smallest.

\end{enumerate}

% TODO: Should we cut this, since we do selection sort later?
%  call back to this exercise when we sort cards
\end{exercise}


%TODO add this exercise to the modulus chapter?
\begin{exercise}

A friend shows you the following method and claims that if the value of \java{number} is any two-digit number, the program will output the number backwards.
For example if \java{number} is 17, the code should output {\tt 71}.

\begin{code}
Scanner in = new Scanner(System.in);
int number = in.nextInt();

int lastDigit = number % 10;
int firstDigit = number / 10;

System.out.println(lastDigit + firstDigit);
\end{code}

Explain what the program actually does, and modify it so that it does the right thing.
You can assume the input will be a two-digit positive integer.

\end{exercise}


\section{Looping and counting}
\label{loopcount}

\index{loop!counting}
\index{traverse!counting}

Other string traversals involve looping and counting.
The following method counts the number of times a given character appears in a string.
For example, \java{numberOf("banana", 'a')} returns 3.

\begin{code}
public static int numberOf(String s, char c) {
    int count = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == c) {
            count++;
        }
    }
    return count;
}
\end{code}

\index{counter}

This method demonstrates a common idiom, called a {\bf counter}.
The variable \java{count} is initialized to zero and then incremented each time we find an \java{'a'}.
When we exit the loop, \java{count} contains the result: the total number of a's.


\begin{exercise}

What is the output of the following program?
Describe in a sentence what \java{mystery} does (not how it works).

\begin{code}
public class Mystery {

    public static String mystery(String s) {
        String total = "";
        int i = s.length() - 1;

        while (i >= 0) {
            char ch = s.charAt(i);
            System.out.println(i + "     " + ch);

            total = total + ch;
            i--;
        }
        return total;
    }

    public static void main(String[] args) {
        System.out.println(mystery("Think Java"));
    }

}
\end{code}

\end{exercise}


\section{Bounds checking}
\label{StringIndexOutOfBounds}

\index{runtime error}
\index{error!runtime}
\index{exception}

If you call the \java{charAt} method with an index that is either negative or greater than \java{length - 1}, you will get an exception, specifically a \java{StringIndexOutOfBounds} exception.
%The same is true when calling \java{substring} with invalid start or end indexes.

For example, notice the error in the \java{getLastLetter} method below.
It should be looking at \java{index - 1} instead of \java{index}.

\begin{code}
public class BadString {
    public static void main(String[] args) {
        processWord("banana");
    }

    public static void processWord(String s) {
        char c = getLastLetter(s);
        System.out.println(c);
    }

    public static char getLastLetter(String s) {
        int index = s.length();
        char c = s.charAt(index);  // WRONG!
        return c;
    }
}
\end{code}

When you run the \java{BadString} program, Java prints the following message.

\begin{small}
\begin{stdout}
Exception in thread "main" java.lang.StringIndexOutOfBoundsException:
String index out of range: 6
    at java.lang.String.charAt(String.java:658)
    at BadString.getLastLetter(BadString.java:14)
    at BadString.processWord(BadString.java:8)
    at BadString.main(BadString.java:4)
\end{stdout}
\end{small}

\index{stack trace}

% TODO: we should define stack trace earlier

This information is called a {\bf stack trace}, which shows the methods that were running when the error occurred.
The stack trace can be difficult to read, but it contains a lot of useful information.
For one, it tells you that the index 6 was out of range.

More importantly, it shows the line of code where the error occurred.
It may be helpful to read the stack trace bottom-up.
On line~4, \java{main} called \java{processWord}, which on line~8 called \java{getLastLetter}, which on line~14 called \java{charAt}.
The actual error occurred on line 658 of String.java, which is in the source code for the \java{String} class itself.

Although possible, it's unlikely that the Java library code has mistakes that cause programs to crash.
When reading stack diagrams, look for the top line that refers to a file you wrote.
In this example, \java{BadString.java:14} is the most useful debugging information.

\label{immutable}

\index{toUpperCase}
\index{toLowerCase}
\index{immutable}

As you read the documentation of the \java{String} methods, you might notice \java{toUpperCase} and \java{toLowerCase}.
These methods are often a source of confusion, because it sounds like they have the effect of changing (or mutating) an existing string.
But neither these methods nor any others can change a string, because strings are {\bf immutable}.

When you invoke \java{toUpperCase} on a string object, you get a new string object as a return value.
For example:

\begin{code}
String name = "Alan Turing";
String upperName = name.toUpperCase();
\end{code}

\index{Turing, Alan}

After the second line runs, \java{upperName} contains the value \java{"ALAN TURING"}.
But \java{name} still contains \java{"Alan Turing"} as before.


\section{Character arithmetic}
\index{arithmetic!character}

Like the \java{compareTo} method, you too can do arithmetic with characters.
For example, if \java{letter} refers to a lower-case letter, \java{letter - 'a'} yields its position in the alphabet (keeping in mind that 'a' is the zeroeth letter of the alphabet and 'z' is the 25th).

Performing arithmetic on characters is rarely necessary in programs, but it helps demonstrate how text is represented in Java.
For example, we often need to convert between characters that contain numbers, like \java{'0'} and \java{'1'}, and their corresponding integers.
A common mistake beginning programmers make is to cast a \java{char} to an \java{int}:

\begin{code}
char letter = '3';
int x = (int) letter;
System.out.println(x);
\end{code}

You might expect the value to be 3, but instead you get 51, which is the Unicode value for the character \java{'3'}.
%Remember, not all languages in the world use Arabic numerals like English does.
To convert \java{'3'} to the corresponding integer value, you could subtract \java{'0'}:

\begin{code}
int x = (int) (letter - '0');
\end{code}

But it is better to use the \java{digit} method in the \java{Character} class instead.
For example, this code converts \java{letter} to the corresponding digit, interpreting it as a base 10 number.

\begin{code}
int x = Character.digit(letter, 10);
\end{code}

\java{Character} is a built-in class that provides methods for working with characters.

Another use for character arithmetic is to loop through the letters of the alphabet in order.
For example, in Robert McCloskey's book {\em Make Way for Ducklings}, the names of the ducklings form an Abecedarian series: Jack, Kack, Lack, Mack, Nack, Ouack, Pack and Quack.
Here is a loop that prints these names in order:

\begin{code}
char letter = 'J';
while (letter <= 'Q') {
    System.out.println(letter + "ack");
    letter++;
}
\end{code}

Notice that in addition to the arithmetic operators, we can also use the logical operators on characters.
The output of this program is:

\begin{stdout}
Jack
Kack
Lack
Mack
Nack
Oack
Pack
Qack
\end{stdout}

Of course, that's not quite right because it misspelled ``Ouack'' and ``Quack''.
As an exercise, you can modify the program to correct this error.


\begin{exercise}

ROT13 is a {\em shift cipher} that works by taking each letter in a string and adding 13 to it.
For example, \java{'a'} becomes \java{'n'} and \java{'b'} becomes \java{'o'}.
The letters wrap around at the end, so \java{'z'} becomes \java{'m'}.

\begin{enumerate}

\item Write a method that takes a string and returns a new string containing the ROT13 encoded version.
You should assume that the string contains upper and lower case letters and spaces, but no other characters.
Lower case letters should be transformed into other lower-case letters, and uppercase into uppercase.
You should not transform the spaces.

\item Generalize the method so that instead of adding 13 to each letter, it adds any given amount.
Now you should be able to encode things by adding 13 and decode them by adding -13.

\item Use your method to decrypt the string \java{"Jnl gb Tb"}.

\item Figure out how to decrypt \java{"Tjp adbpmzy do jpo"}.
It wasn't created by adding 13 to each letter.
Write a loop to try other possible values.

\end{enumerate}

\end{exercise}


\section{The compareTo method}
% ABD: It's hard to motivate compareTo in chapter 11. Let's postpone until Cards.

\index{pure function}
\index{method!pure function}

, and it has no side effects like modifying an argument or printing something.
The only result of invoking a pure method is the return value.

In contrast to instance methods, \java{static} methods do not refer to a specific object.
The result of a \java{static} method depends only on the arguments.
For example, \java{isAfter} compares two \java{Time}s and returns a \java{boolean} that indicates whether the first operand comes after the second:

\begin{code}
public static boolean isAfter(Time time1, Time time2) {
    if (time1.hour < time2.hour) return false;
    if (time1.hour > time2.hour) return true;

    if (time1.minute < time2.minute) return false;
    if (time1.minute > time2.minute) return true;

    if (time1.second < time2.second) return false;
    return true;
}
\end{code}

What is the result of this method if the two times are equal?
Does that seem like the appropriate result for this method?
If you were writing the documentation for this method, would you mention that case specifically?

A better solution would be to define a \java{compareTo} method.
We have already seen how to compare two strings in this way: \java{time1.compareTo(time2)}.

\begin{code}
public int compareTo(Time t2) {
    if (this.hour < t2.hour) return -1;
    if (this.hour > t2.hour) return +1;

    if (this.minute < t2.minute) return -1;
    if (this.minute > t2.minute) return +1;

    if (this.second < t2.second) return -1;
    if (this.second > t2.second) return +1;

    return 0;
}
\end{code}

If \java{this} time comes before the other time, then compareTo returns \java{-1}.
It returns \java{+1} when \java{this} time comes after the other time.
If both times are the same (in the \java{equals} sense), \java{compareTo} returns \java{0}.


\section{Object equals instanceof}

% ABD: I believe this equals method is sufficient.  If someone passes
% another object type, they'll get the default behavior, which will
% return false.  So let's avoid introducing Object here.

So in order to override the default \java{equals} method, you need to write it this way:

\begin{code}
public boolean equals(Object obj) {
    if (!(obj instanceof Time)) {
        return false;
    }
    Time t2 = (Time) obj;
    return this.hour == t2.hour
        && this.minute == t2.minute
        && this.second == t2.second;
}
\end{code}

Because the parameter is declared as an \java{Object}, one could in theory pass any type of data (like a \java{String} or \java{Scanner}) to this method.
The \java{instanceof} operator tests whether \java{obj} references an actual \java{Time} object.
If it passes the test, we can safely cast \java{obj} to a \java{Time} reference and perform the equality test as before.

Of course, the \java{equals} method may be arbitrarily complex.
You could design it, for example, to allow \java{Time} and \java{String} objects to be equal if they represent the same time.
However that design would likely confuse other programmers, since normally objects are only considered equal if they are of the same type.


%(CM) I just realized we have this same figure/example twice,
% for Time and again for Card; but maybe that's a good thing?

\section{The equals method}
\label{equivalence}

As we saw in Section~\ref{equals}, you can use the \java{==} operator with object types, but it might not do what you want.
The \java{==} operator checks whether two objects are identical.
For example, suppose we create three \java{Card} variables:

\index{identical}

\begin{code}
Card card1 = new Card(11, 1);
Card card2 = card1;
Card card3 = new Card(11, 1);
\end{code}

Figure~\ref{fig.card} is a state diagram showing the result.

\begin{figure}[!ht]
\begin{center}
\includegraphics{figs/card.pdf}
\caption{State diagram of three \java{Card} variables.}
\label{fig.card}
\end{center}
\end{figure}

Since \java{card1} and \java{card2} refer to the same object, \java{card1 == card2} is \java{true}.
But \java{card1} and \java{card3} are references to different objects, so \java{card1 == card3} is \java{false}.

When we compare cards, this is probably not the behavior we want.
Rather, we want to check whether the cards are equivalent.
To do that, we can provide an \java{equals} method.

\index{equivalent}

\begin{code}
public boolean equals(Card that) {
    return this.suit == that.suit && this.rank == that.rank;
}
\end{code}

This method defines what ``equivalent'' means for cards: they must have the same suit and the same rank.
Because \java{suit} and \java{rank} are primitive types, we can use \java{==} to compare them.

Now if we invoke \java{card1.equals(card3)}, the result is \java{true}.
Note that if two objects are identical, they are also equivalent.
So \java{card1.equals(card2)} is \java{true} as well.


\section{Insertion sort}
\label{insertion}

\index{insertion sort}
\index{sort!insertion}

The final sorting algorithm we'll look at is called {\bf insertion sort}.
It's based on inserting an item into a previously sorted list.
People often use this algorithm when they are dealt new cards:

\begin{enumerate}
\item Use sequential search to find the ``insertion point''; that is, the index in the array where the new card belongs.
\item Insert the new card at that position.
\end{enumerate}

That's easy enough when holding a few cards in your hand; you generally can make room for one more card.
But in Java, you can't change the length of an array.
If the array has capacity for only five \java{Card}s, you can't just insert a sixth \java{Card} in the middle of it.

Consequently, the actual algorithm is a bit more complicated:

\begin{enumerate}
\item Use sequential search to find the insertion point.
\item Create a new array with room for one more element.
\item Copy existing elements from the old array to their corresponding position in the new array (skipping the insertion point).
\item Insert the new card at the insertion point.
\end{enumerate}

We can refine this insertion algorithm to sort an entire (unsorted) deck of cards.
For efficiency, we will avoid running steps 2--3 over and over again by creating the new array just once.
Here is the pseudocode:

\begin{code}
public Deck insertionSort() {
    // create a new deck with the same length as this deck
  
    for each card in this deck {
        // find the insertion point, i, in the sorted deck
        // starting at i, shift cards to the right by one
        // insert the card at i (into the sorted deck)
    }
}
\end{code}

One of the exercises at the end of the chapter asks you to implement this version of \java{insertionSort}.%, which creates and returns the sorted array.

%There is another version that sorts the original array in place.
%Read about it at \url{https://en.wikipedia.org/wiki/Insertion_sort}.


%%% Exercises

\item Write a method called \java{insertionSort} that implements the insertion sort algorithm in Section~\ref{insertion}.

\item How many comparisons does insertion sort need to sort an array with $n$ elements?
Do you expect it to be proportional to $n^2$ like selection sort, or proportional to $n \log n$ like merge sort?