ch01.tex

\chapter{Computer Programming}
\label{theway}

The goal of this book is to teach you to think like a computer scientist.
This way of thinking combines some of the best features of mathematics, engineering, and natural science.
Like mathematicians, computer scientists use formal languages to denote ideas---specifically, computations.
Like engineers, they design things, assembling components into systems and evaluating trade-offs among alternatives.
And like scientists, they observe the behavior of complex systems, form hypotheses, and test predictions.

\index{problem solving}

An important skill for a computer scientist is {\bf problem solving}.
It involves the ability to formulate problems, think creatively about solutions, and express solutions clearly and accurately.
As it turns out, the process of learning to program computers is an excellent opportunity to develop problem-solving skills.
%That's why this chapter is called, ``The way of the program''.
On one level, you will be learning to write Java programs, a useful skill by itself.
But on another level, you will use programming as a means to an end.
As we go along, that end will become clearer.


\section{What Is a Computer?}

When people hear the word {\em computer}, they often think of a desktop or a laptop.
Not surprisingly, searching for ``computer'' on Google Images (\url{https://images.google.com/}) displays rows and rows of these types of machines.
However, in a more general sense, a computer can be any type of device that stores and processes data.

Dictionary.com defines a computer as ``a programmable electronic device designed to accept data, perform prescribed mathematical and logical operations at high speed, and display the results of these operations.
Mainframes, desktop and laptop computers, tablets, and smartphones are some of the different types of computers.''

\index{hardware}
\index{processor}
\index{memory}
\index{CPU}
\index{RAM}

Each type of computer has its own unique design, but internally they all share the same type of {\bf hardware}.
The two most important hardware components are {\bf processors} (or CPUs) that perform simple calculations and {\bf memory} (or RAM) that temporarily stores information.
Figure~\ref{fig.cpuram} shows what these components look like.

\begin{figure}[!ht]
\begin{center}
%https://commons.wikimedia.org/wiki/File:Intel_80486DX2_top.jpg
\includegraphics[height=11em]{figs/CPU.jpg}
\hspace{2em}
%https://commons.wikimedia.org/wiki/File:Memory_module_DDRAM_20-03-2006.jpg
\includegraphics[height=11em]{figs/RAM.jpg}
\caption{Example processor and memory hardware.}
\label{fig.cpuram}
\end{center}
\end{figure}

Users generally see and interact with touchscreens, keyboards, and monitors, but it's the processors and memory that perform the actual computation.
Nowadays it's fairly standard, even for a smartphone, to have at least eight processors and four gigabytes (four billion cells) of memory.


\section{What Is Programming?}

\index{program}

A {\bf program} is a sequence of instructions that specifies how to perform a computation on computer hardware.
The computation might be something mathematical, like solving a system of equations or finding the roots of a polynomial.
It could also be a symbolic computation, like searching and replacing text in a document or (strangely enough) compiling a program.

The details look different in different languages, but a few basic instructions appear in just about every language:

\begin{description}
\item[input:] Get data from the keyboard, a file, a sensor, or some other device.
\item[output:] Display data on the screen, or send data to a file or other device.
\item[math:] Perform basic mathematical operations like addition and division.
\item[decision:] Check for certain conditions and execute the appropriate code.
\item[repetition:] Perform an action repeatedly, usually with some variation.
\end{description}

\index{programming}

Believe it or not, that's pretty much all there is to it.
Every program you've ever used, no matter how complicated, is made up of small instructions that look much like these.
So you can think of {\bf programming} as the process of breaking down a large, complex task into smaller and smaller subtasks.
The process continues until the subtasks are simple enough to be performed with the electronic circuits provided by the hardware.


\section{The Hello World Program}
\label{hello}

Traditionally, the first program you write when learning a new programming language is called the ``Hello World'' program.
All it does is output the words {\tt Hello, World!} to the screen.
In Java, it looks like this:

% NOTE(ABD): I changed a lot of ``print'' to ``display'', partly to be
% more precise, but also to reduce the number of times ``print'' appears,
% which is a lot!

\index{Hello.java}

% height = 130 + 15 * num_lines
\begin{trinket}[235]{Hello.java}
public class Hello {

    public static void main(String[] args) {
        // generate some simple output
        System.out.println("Hello, World!");
    }
}
\end{trinket}

When this program runs, it displays the following:

\begin{stdout}
Hello, World!
\end{stdout}

Notice that the output does not include the quotation marks.

%\index{public}
%\index{static}
%The word \java{public} means the code can be accessed from other source files.
%The word \java{static} means that memory is allocated for the program in advance.

%Unfortunately, this simple example uses language features (like \java{public} and \java{static}) that are hard to explain.
%In fact, we won't be able to explain all of them for several more chapters.
%But we can start with the structure.

\index{statement}
\index{print statement}

Java programs are made up of {\em class} and {\em method} definitions, and methods are made up of {\em statements}.
A {\bf statement} is a line of code that performs a basic action.
In the Hello World program, this line is a {\bf print statement} that displays a message to the user:

\begin{code}
System.out.println("Hello, World!");
\end{code}

\index{println}
\index{semicolon}
\index{; semicolon}

\java{System.out.println} displays results on the screen; the name \java{println} stands for ``print line''.
Confusingly, {\em print} can mean both ``display on the screen'' and ``send to the printer''.
In this book, we'll try to say ``display'' when we mean output to the screen.
Like most statements, the print statement ends with a semicolon (\java{;}).

\index{case-sensitive}

Java is ``case-sensitive'', which means that uppercase and lowercase are not the same.
In the Hello World program, \java{System} has to begin with an uppercase letter; \java{system} and \java{SYSTEM} won't work.

\index{method}

A {\bf method} is a named sequence of statements.
This program defines one method named \java{main}:

\begin{code}
public static void main(String[] args)
\end{code}

\index{main}

The name and format of \java{main} is special: when the program runs, it starts at the first statement in \java{main} and ends when it finishes the last statement.
Later, you will see programs that define more than one method.

\index{class}

This program defines a class named \java{Hello}.
For now, a {\bf class} is a collection of methods; we'll have more to say about this later.
You can give a class any name you like, but it is conventional to start with a capital letter.
The name of the class has to match the name of the file it is in, so this class has to be in a file named {\it Hello.java}.

\index{\{\} curly braces}

Java uses curly braces (\java{\{} and \java{\}}) to group things together.
In {\it Hello.java}, the outermost braces contain the class definition, and the inner braces contain the method definition.

\index{comment!end-of-line}

The line that begins with two slashes (\java{//}) is a {\bf comment}, which is a bit of English text that explains the code.
When Java sees \java{//}, it ignores everything from there until the end of the line.
Comments have no effect on the execution of the program, but they make it easier for other programmers (and your future self) to understand what you meant to do.


\section{Compiling Java Programs}

\index{high-level language}
\index{language!high-level}

The programming language you will learn in this book is Java, which is a {\bf high-level language}.
Other high-level languages you may have heard of include Python, C and C++, PHP, Ruby, and JavaScript.

\index{low-level language}
\index{language!low-level}

Before they can run, programs in high-level languages have to be translated into a {\bf low-level language}, also called ``machine language''.
This translation takes some time, which is a small disadvantage of high-level languages.
But high-level languages have two major advantages:

\begin{itemize}

\item It is {\em much} easier to program in a high-level language.
Programs take less time to write, they are shorter and easier to read, and they are more likely to be correct.

\index{portable}

\item High-level languages are {\bf portable}, meaning they can run on different kinds of computers with few or no modifications.
Low-level programs can run on only one kind of computer. %, and have to be rewritten to run on another.

\end{itemize}

\index{interpret}

Two kinds of programs translate high-level languages into low-level languages: interpreters and compilers.
An {\bf interpreter} reads a high-level program and executes it, meaning that it does what the program says.
It processes the program a little at a time, alternately reading lines and performing computations.
%Python and JavaScript are examples of interpreted languages.
Figure~\ref{fig.interpreter} shows the structure of an interpreter.

\begin{figure}[!ht]
\begin{center}
\includegraphics{figs/interpreter.pdf}
\caption{How interpreted languages are executed.}
\label{fig.interpreter}
\end{center}
\end{figure}

\index{compile}
\index{source code}
\index{object code}
\index{executable}

In contrast, a {\bf compiler} reads the entire program and translates it completely before the program starts running.
The high-level program is called the {\bf source code}.
The translated program is called the {\bf object code}, or the {\bf executable}.
Once a program is compiled, you can execute it repeatedly without further translation of the source code.
As a result, compiled programs often run faster than interpreted programs.

Note that object code, as a low-level language, is not portable.
You cannot run an executable compiled for a Windows laptop on an Android phone, for example.
To run a program on different types of machines, it must be compiled multiple times.
It can be difficult to write source code that compiles and runs correctly on different types of machines.

\index{byte code}
\index{virtual machine}

To address this issue, Java is {\em both} compiled and interpreted.
Instead of translating source code directly into an executable, the Java compiler generates code for a {\bf virtual machine}.
This ``imaginary'' machine has the functionality common to desktops, laptops, tablets, phones, etc.
Its language, called Java {\bf byte code}, looks like object code and is easy and fast to interpret.

\index{javac}
\index{JVM}

As a result, it's possible to compile a Java program on one machine, transfer the byte code to another machine, and run the byte code on that other machine.
Figure~\ref{fig.compiler} shows the steps of the development process.
The Java compiler is a program named {\tt javac}.
It translates {\it .java} files into {\it .class} files that store the resulting byte code.
The Java interpreter is another program, named {\tt java}, which is short for ``Java Virtual Machine'' (JVM).

\begin{figure}[!ht]
\begin{center}
\includegraphics{figs/compiler.pdf}
\caption{The process of compiling and running a Java program.}
\label{fig.compiler}
\end{center}
\end{figure}

The programmer writes source code in the file {\it Hello.java} and uses {\tt javac} to compile it.
If there are no errors, the compiler saves the byte code in the file {\it Hello.class}.
To run the program, the programmer uses {\tt java} to interpret the byte code.
The result of the program is then displayed on the screen.

Although it might seem complicated, these steps are automated for you in most development environments.
Usually, you only have to press a button or type a single command to compile and interpret your program.
On the other hand, it is important to know what steps are happening in the background, so if something goes wrong you can figure out what it is.


\section{Displaying Two Messages}

You can put as many statements as you like in the \java{main} method.
For example, to display more than one line of output:

\begin{trinket}[250]{Hello2.java}
public class Hello2 {

    public static void main(String[] args) {
        // generate some simple output
        System.out.println("Hello, World!");  // first line
        System.out.println("How are you?");   // another line
    }
}
\end{trinket}

As this example also shows, you can put comments at the end of a line as well as on lines all by themselves.

\index{quote mark}
\index{string}
\index{type!String}
\index{char}

Phrases that appear in quotation marks are called {\bf strings}, because they contain a sequence of characters strung together in memory.
Characters can be letters, numbers, punctuation marks, symbols, spaces, tabs, etc.

\index{newline}
\index{print}
\index{statement!print}

\java{System.out.println} appends a special character, called a {\bf newline}, that moves to the beginning of the next line.
If you don't want a newline at the end, you can use \java{print} instead of \java{println}:

\index{Goodbye.java}

\begin{trinket}[235]{Goodbye.java}
public class Goodbye {

    public static void main(String[] args) {
        System.out.print("Goodbye, ");
        System.out.println("cruel world");
    }
}
\end{trinket}

\label{goodbye}

In this example, the first statement does not add a newline, so the output appears on a single line:

\begin{stdout}
Goodbye, cruel world
\end{stdout}

Notice that there is a space at the end of the first string, which appears in the output just before the word {\tt cruel}.


\section{Formatting Source Code}
\label{formatting}

In Java source code, some spaces are required.
For example, you need at least one space between words, so this program is not legal:

\begin{code}
publicclassGoodbye{

    publicstaticvoidmain(String[] args) {
        System.out.print("Goodbye, ");
        System.out.println("cruel world");
    }
}
\end{code}

But most other spaces are optional.
For example, this program {\em is} legal:

\begin{trinket}[220]{Goodbye.java}
public class Goodbye {
public static void main(String[] args) {
System.out.print("Goodbye, ");
System.out.println("cruel world");
}
}
\end{trinket}

The newlines are optional, too.
So we could just write this:

\begin{trinket}[175]{Goodbye.java}
public class Goodbye { public static void main(String[] args)
{ System.out.print("Goodbye, "); System.out.println
("cruel world");}}
\end{trinket}

It still works, but the program is getting harder and harder to read.
Newlines and spaces are important for visually organizing your program, making it easier to understand the program and find errors when they occur.

Many editors will automatically format source code with consistent indenting and line breaks.
For example, in DrJava (see Appendix~\ref{drjava}) you can indent your code by selecting all text ({\sf Ctrl+A}) and pressing the {\sf Tab} key.


%\section{Style Guidelines}

%\index{whitespace}
%
%As we saw in Section~\ref{formatting}, the compiler generally ignores spaces, tabs, and newlines.
%These characters, which are called {\bf whitespace}, affect the format of the code, but they don't affect its behavior.

%You have a lot of freedom in how you arrange your code.
%However, with that freedom comes responsibility, both to yourself (when you look at the code in the future) and others who will be reading, understanding, and debugging it.

\index{Google style}
\index{style guide}

Organizations that do a lot of software development usually have strict guidelines on how to format source code.
For example, Google publishes its Java coding standards for use in open source projects: \url{https://google.github.io/styleguide/javaguide.html}.
%It is easier to understand a large codebase when all the source code is formatted consistently.
%Plus following style guidelines helps you to avoid common programming mistakes that are difficult to debug.

You probably won't understand these guidelines now, because they refer to language features you haven't yet seen.
But you might want to refer to them periodically as you read this book.

%In the meantime, there are software tools that help programmers find and correct style issues.
%One of the most popular is Checkstyle, which enforces most of Google's guidelines.
%Instructions for downloading and running Checkstyle are in Appendix~\ref{checkstyle}.


\section{Using Escape Sequences}

It's possible to display multiple lines of output with only one line of code.
You just have to tell Java where to put the line breaks:

\begin{trinket}[220]{Hello3.java}
public class Hello3 {

    public static void main(String[] args) {
        System.out.print("Hello!\nHow are you doing?\n");
    }
}
\end{trinket}

The output is two lines, each ending with a newline character:

\begin{stdout}
Hello!
How are you doing?
\end{stdout}

\index{escape sequence}

Each \verb"\n" is an {\bf escape sequence}, or two characters of source code that represent a single character.
(The backslash allows you to {\em escape} the string to write special characters.)
Notice there is no space between \verb"\n" and \verb"How".
If you add a space there, there will be a space at the beginning of the second line.

\begin{table}[!ht]
\begin{center}
\begin{tabular}{|c|c|}
\hline
\verb"\n" & newline \\
\hline
\verb"\t" & tab \\
\hline
\verb'\"' & double quote \\
\hline
\verb"\\" & backslash \\
\hline
\end{tabular}
\caption{Common escape sequences}
\label{tab:escape}
\end{center}
\end{table}

Java has a total of eight escape sequences, and the four most commonly used ones are listed in Table~\ref{tab:escape}.
For example, to write quotation marks inside of strings, you need to escape them with a backslash:

\begin{code}
System.out.println("She said \"Hello!\" to me.");
\end{code}

The result is as follows:

\begin{stdout}
She said "Hello!" to me.
\end{stdout}


\section{What Is Computer Science?}

This book intentionally omits some details about the Java language (such as the other escape sequences), because our main goal is teaching you how to think like a computer scientist.
Being able to understand computation is much more valuable than just learning how to write code.

If you're interested in learning more about Java itself, Oracle maintains an official set of tutorials on its website (\url{https://thinkjava.org/tutorial}).
The ``Language Basics'' tutorial, found under ``Learning the Java Language'', is a good place to start.

One of the most interesting aspects of writing programs is deciding how to solve a particular problem, especially when there are multiple solutions.
For example, there are numerous ways to sort a list of numbers, and each way has its advantages.
%Sorting-algorithms.com provides animations and descriptions for eight of the most common ways.
In order to determine which way is best for a given situation, we need techniques for describing and analyzing solutions formally.

\index{algorithm}
\index{computer science}

An {\bf algorithm} is a sequence of steps that specifies how to solve a problem.
Some algorithms are faster than others, and some use less space in computer memory.
{\bf Computer science} is the science of algorithms, including their discovery and analysis.
As you learn to develop algorithms for problems you haven't solved before, you will learn to think like a computer scientist.
%It's much more fun to discover new algorithms than to write the code for solutions that other people came up with!

\index{bug}
\index{debugging}

Designing algorithms and writing code is difficult and error-prone.
For historical reasons, programming errors are called {\bf bugs}, and the process of tracking them down and correcting them is called {\bf debugging}.
As you learn to debug your programs, you will develop new problem-solving skills.
You will need to think creatively when unexpected errors happen.

Although it can be frustrating, debugging is an intellectually rich, challenging, and interesting part of computer science.
In some ways, debugging is like detective work.
You are confronted with clues, and you have to infer the processes and events that led to the results you see.
Thinking about how to correct programs and improve their performance sometimes even leads to the discovery of new algorithms.


\section{Debugging Programs}
\label{sec:examples}

It is a good idea to read this book in front of a computer so you can try out the examples as you go.
You can run many of the examples directly in DrJava's Interactions pane (see Appendix~\ref{interactions}).
But if you put the code in a source file, it will be easier to try out variations.

\index{error!message}

Whenever you are experimenting with a new feature, you should also try to make mistakes.
For example, in the Hello World program, what happens if you leave out one of the quotation marks?
What if you leave out both?
What if you spell \java{println} wrong?
These kinds of experiments help you remember what you read.
They also help with debugging, because you learn what the error messages mean.
It is better to make mistakes now and on purpose than later on and accidentally.

\index{experimental debugging}
\index{debugging!experimental}

%\index{Holmes, Sherlock}
%\index{Doyle, Arthur Conan}

Debugging is like an experimental science: once you have an idea about what is going wrong, you modify your program and try again.
If your hypothesis was correct, then you can predict the result of the modification, and you take a step closer to a working program.
If your hypothesis was wrong, you have to come up with a new one.
%As Sherlock Holmes pointed out, ``When you have eliminated the impossible, whatever remains, however improbable, must be the truth.''
%(A.~Conan Doyle, {\it The Sign of Four}.)

Programming and debugging should go hand in hand.
Don't just write a bunch of code and then perform trial-and-error debugging until it all works.
Instead, start with a program that does {\em something} and make small modifications, debugging them as you go, until the program does what you want.
That way, you will always have a working program, and isolating errors will be easier.

\index{Linux}
\index{Torvalds, Linus}
\index{Greenfield, Larry}

A great example of this principle is the Linux operating system, which contains millions of lines of code.
It started out as a simple program Linus Torvalds used to explore the Intel 80386 chip.
According to Larry Greenfield in {\it The Linux Users' Guide}, ``One of Linus's earlier projects was a program that would switch between printing AAAA and BBBB.
This later evolved to Linux.''

%Later chapters will make more suggestions about debugging and other programming practices.

Finally, programming sometimes brings out strong emotions.
If you are struggling with a difficult bug, you might feel angry, despondent, or embarrassed.
Remember that you are not alone, and virtually every programmer has had similar experiences.
Don't hesitate to reach out to a friend and ask questions!


\section{Vocabulary}

Throughout the book, we try to define each term the first time we use it.
At the end of each chapter, we include the new terms and their definitions in order of appearance.
If you spend some time learning this vocabulary, you will have an easier time reading the following chapters.

\begin{description}

\term{problem solving}
The process of formulating a problem, finding a solution, and expressing the solution.

\term{hardware}
The electronic and mechanical components of a computer, such as CPUs, RAM, and hard disks.

\term{processor}
A computer chip that performs simple instructions like basic arithmetic and logic.

\term{memory}
Circuits that store data as long as the computer is turned on.
Not to be confused with permanent storage devices like hard disks and flash.

\term{program}
A sequence of instructions that specifies how to perform tasks on a computer.
Also known as ``software''.

\term{programming}
The application of problem solving to creating executable computer programs.

\term{statement}
Part of a program that specifies one step of an algorithm.

\term{print statement}
A statement that causes output to be displayed on the screen.

\term{method}
A named sequence of statements.

\term{class}
For now, a collection of related methods.
(You will see later that there is a lot more to it.)

\term{comment}
A part of a program that contains information about the program but has no effect when the program runs.

\term{high-level language}
A programming language that is designed to be easy for humans to read and write.

\term{low-level language}
A programming language that is designed to be easy for a computer to run.
Also called ``machine language''. % or ``assembly language''.

\term{portable}
The ability of a program to run on more than one kind of computer.

\term{interpret}
To run a program in a high-level language by translating it one line at a time and immediately executing the corresponding instructions.

\term{compile}
To translate a program in a high-level language into a low-level language, all at once, in preparation for later execution.

\term{source code}
A program in a high-level language, before being compiled.

\term{object code}
The output of the compiler, after translating the program.

\term{executable}
Another name for object code that is ready to run on specific hardware.

\term{virtual machine}
An emulation of a real machine. The JVM enables a computer to run Java programs.

\term{byte code}
A special kind of object code used for Java programs.
Byte code is similar to object code, but it is portable like a high-level language.

\term{string}
A sequence of characters; the primary data type for text.

\term{newline}
A special character signifying the end of a line of text.
Also known as ``line ending'', ``end of line'' (EOL), or ``line break''.

%\term{whitespace}
%Newlines, tab characters, and other spaces in a source program.
%Whitespace characters are used to separate words, but other than that, they don't affect the behavior of the program.

\term{escape sequence}
A sequence of code that represents a special character when used inside a string.

\term{algorithm}
A procedure or formula for solving a problem, with or without a computer.

\term{computer science}
The scientific and practical approach to computation and its applications.

\term{bug}
An error in a program.

\term{debugging}
The process of finding and removing errors.

\end{description}


\section{Exercises}

At the end of each chapter, we include exercises you can do with the things you've learned.
We encourage you to at least attempt every problem.
You can't learn to program only by reading about it; you have to practice.

Before you can compile and run Java programs, you might have to download and install a few tools.
There are many good options, but we recommend DrJava, which is an ``integrated development environment'' (IDE) well suited for beginners.
Instructions for getting started are in Appendix~\ref{tools}.

The code for this chapter is in the {\it ch01} directory of {\it ThinkJavaCode2}.
See page~\pageref{code} for instructions on how to download the repository.
Before you start the exercises, we recommend that you compile and run the examples.


\begin{exercise}  %%V6 Ex1.1

Computer scientists have the annoying habit of using common English words to mean something other than their common English meanings.
For example, in English, statements and comments are the same thing, but in programs they are different.

\begin{enumerate}
\item In computer jargon, what's the difference between a {\em statement} and a {\em comment}?
\item What does it mean to say that a program is {\em portable}?
\item In common English, what does the word {\em compile} mean?
\item What is an {\em executable}? Why is that word used as a noun?
\end{enumerate}

The vocabulary section at the end of each chapter is intended to highlight words and phrases that have special meanings in computer science.
When you see familiar words, don't assume that you know what they mean!

\end{exercise}


\begin{exercise}  %%V6 Ex1.2

Before you do anything else, find out how to compile and run a Java program.
Some environments provide sample programs similar to the example in Section~\ref{hello}.

\begin{enumerate}
\item Type in the Hello World program; then compile and run it.

\item Add a print statement that displays a second message after the {\tt Hello, World!}.
Say something witty like, {\tt How are you?}.
Compile and run the program again.

\item Add a comment to the program (anywhere), recompile, and run it again.
The new comment should not affect the result.
\end{enumerate}

This exercise may seem trivial, but it is the starting place for many of the programs we will work with.
To debug with confidence, you will need to have confidence in your programming environment.

In some environments, it is easy to lose track of which program is executing.
You might find yourself trying to debug one program while you are accidentally running another.
Adding (and changing) print statements is a simple way to be sure that the program you are looking at is the program you are running.

\end{exercise}


\begin{exercise}  %%V6 Ex1.3

It is a good idea to commit as many errors as you can think of, so that you see what error messages the compiler produces.
Sometimes the compiler tells you exactly what is wrong, and all you have to do is fix it.
But sometimes the error messages are misleading.
Over time you will develop a sense for when you can trust the compiler and when you have to figure things out yourself.

Starting with the Hello World program, try out each of the following errors.
After you make each change, compile the program, read the error message (if there is one), and then fix the error.

\begin{enumerate}
\item Remove one of the opening curly braces.
\item Remove one of the closing curly braces.
\item Instead of \java{main}, write \java{mian}.
\item Remove the word \java{static}.
\item Remove the word \java{public}.
\item Remove the word \java{System}.
\item Replace \java{println} with \java{Println}.
\item Replace \java{println} with \java{print}.
\item Delete one parenthesis.
\item Add an extra parenthesis.
\end{enumerate}

\end{exercise}