Goals of CS 61B

  1. Learning efficient data structures and algorithms that use them.
  2. Designing and writing large programs.
  3. Understanding and designing data abstraction and interfaces.
  4. Learning Java.

THE LANGUAGE OF OBJECT-ORIENTED PROGRAMMING

  • Object: An object is a repository of data. For example, if MyList is a ShoppingList object, MyList might record your shopping list.
  • Class: A class is a type of object. Many objects of the same class might exist; for instance, MyList and YourList may both be ShoppingList objects.
  • Method: A procedure or function that operates on an object or a class. A method is associated with a particular class. For instance, addItem might be a method that adds an item to any ShoppingList object. Sometimes a method is associated with a family of classes. For instance, addItem might operate on any List, of which a ShoppingList is just one type.
  • Inheritance: A class may inherit properties from a more general class. For example, the ShoppingList class inherits from the List class the property of storing a sequence of items.
  • Polymorphism: The ability to have one method call work on several different classes of objects, even if those classes need different implementations of the method call. For example, one line of code might be able to call the addItem method on every kind of List, even though adding an item to a ShoppingList is completely different from adding an item to a ShoppingCart.
  • Object-Oriented: Each object knows its own class and which methods manipulate objects in that class. Each ShoppingList and each ShoppingCart knows which implementation of addItem applies to it.

In this list, the one thing that truly distinguishes object-oriented languages from procedural languages (C, Fortran, Basic, Pascal) is polymorphism.

Java

  • Variables. Java allows you to store data in variables, but first you must declare them and specify their type.

    • Python: x = 1
    • Scheme: (let ((x 1)) )
    • Java:
      int x;
      x = 1;

This Java declaration does two things.

  1. It allocates a chunk of memory big enough to store an integer, which Java calls type int.
  2. It names the variable (chunk of memory) x.

x

Variables are used not just to store numbers, but also to reference objects. There are two ways to get classes of objects to play with:

  1. Use one defined by somebody else. Java has tons of pre-defined classes you can use. Many come in the Java standard library provided with every Java compiler.
  2. Define your own.

For example, Java has a built-in class called String.

1
String myString;

This does not create a String object. Instead, it declares a variable (chunk of memory) that can store a reference to a String object. I draw it as a box.

variable

Initially, myString doesn't reference anything. You can make it reference a String object by writing an assignment statement. But how do we get ahold of an actual String object? You can create one.

1
myString = new String();

This line performs two distinct steps. (right to left)

  1. First, the phrase new String() is called a constructor. It constructs a brand new String object.
  2. Second, the assignment = causes myString to reference the object. You can think of this as myString pointing to the object.

myString

Unlike Scheme and Python, Java programs must be compiled before you can run them. Compilation (javac) converts your written code to a machine-readable bytecode (not quite machine language but lower level code). Execution by Java Virtual Machine (JVM). The advantage is a faster program than one written in Scheme. The disadvantage is that you have to wait for it to compile.

Java

Postscript: Anatomy of a Small Java Program (for discussion section)

Assume the following code is in a file called HelloWorld.java:

1
2
3
4
5
class HelloWorld {
    public static void main(String[] args) {
        System.out.println("Hello, world");
    }
}

The classes are HelloWorld, String, and System.
The objects are args, System.out, and the string Hello, world.
(Actually, the first two of these are references to objects.)
The methods are main and println. The println method prints its parameter, and the main method prints the string Hello, world.

You don’t have the knowledge to completely understand this code yet, but don’t worry about it. We’ll take the first two lines on faith as the standard way to start a Java program. They’ll become clear in the coming weeks.

Let’s look at the innermost line first; it does all the action. out references an object whose class is PrintStream. A PrintStream is a path by which characters can be output by a program. The characters that are sent through out find their way to your computer screen.

1
2
3
4
5
6
public final class System {
    private System() {
    }

    public final static PrintStream out;
}

System is a class which happens to contain the variable out (among many other variables). We have to write System.out to address the output stream, because other classes might have variables called out too, with their own meanings.

println is a method (procedure) of the class PrintStream. Hence, we can invoke println from any PrintStream object, including System.out. println takes one parameter, which can be a string.

main is a method in the HelloWorld class. The HelloWorld class knows how to do the main operation, just like the PrintStream class knows how to do the println operation.

class

The classes System and PrintStream are all automatically provided for you by any Java compiler. Somebody has programmed them for you, so that you don't have to figure out for yourself how to send characters to the terminal.

Compile language.
Interpreted language.

OBJECTS AND CONSTRUCTORS

1
2
String s; // Step 1: declare a String variable.
s = new String(); // Steps 2, 3: construct new empty String; assign it to s.

At this point, s is a variable that references an "empty" String, i.e. a String containing zero characters.

s

1
2
String s = new String(); // Steps 1, 2, 3 combined.
s = "Yow!"; // Construct a **new** String; make s a reference to it.

sYow

1
String s2 = s; // Copy the reference stored in s into s2.

s2s

Now s and s2 reference the same object.

1
s2 = new String(s); // **Construct a copy of object**; store reference in s2.

news2

Now they refer to two different, but identical, objects.

1
2
3
4
5
String s;
String s2 = s;
s = "Yow!"; // s2 still **null**!
s2 = "Yow!"; // Java has secret hashing operation. Reuse String.
s2 = new String(s); // force Java to make a new String.
1
s2 = new String(s); // **Construct a copy of object**; store reference in s2.

Think about that. When Java executes that line, it does the following things, in the following order.

  • Java looks inside the variable s to see where it's pointing.
  • Java follows the pointer to the String object.
  • Java reads the characters stored in that String object.
  • Java creates a new String object that stores a copy of those characters.
  • Java stores a reference to the new String object in s2.

We've seen three String constructors:

  1. new String() constructs an empty string--it's a string, but it contains zero characters.
  2. "Yow!" constructs a string containing the characters Yow!.
  3. new String(s) takes a parameter s. Then it makes a copy of the object that s references.

Constructors always have the same name as their class, except the special constructor stuffinquotes. That's the only exception.

Observe that new String() can take no parameters, or one parameter. These are two different constructors--one that is called by new String(), and one that is called by new String(s). (Actually, there are many more than two--check out the online Java API to see all the possibilities.)

METHODS

Let's look at some methods that aren't constructors.

1
s2 = s.toUppercase(); // **Create a String** like s, but in all upper case.

s2

1
String s3 = s2.concat("!!"); // Also written: s3 = s2 + "!!";

s3

1
String s4 = "*".concat(s2).concat("*"); // Also written: s4 = "*" + s + "*";

s4

Now, here's an important fact: when Java executed the line

1
s2 = s.toUppercase();

the String object "Yow!" did not change. Instead, s2 itself changed to reference a new object. Java wrote a new pointer into the variable s2, so now s2 points to a different object than it did before.

Unlike in C, in Java Strings are immutable--once they've been constructed, their contents never change. If you want to change a String object, you've got to create a brand new String object that reflects the changes you want. This is not true of all objects; most Java objects let you change their contents.

You might find it confusing that methods like toUppercase and concat return newly created String objects, though they are not constructors. The trick is that those methods calls constructors internally, and return the newly constructed Strings.

I/O Class & Objects

Objects in System class for interacting with a user:
System.out is a PrintStream object that output to the stream.
System.in is an InputStream object that reads from the keyboard.
readLine is defined on BufferedReader objects.

  • How do we construct a BufferedReader? With an InputStreamReader.
  • How do we construct a InputStreamReader? With InputStream.
  • How do we construct a InputStream? System is one.

Figure this out via online Java libraries API - java.io

  • InputStream: Reads row data.
  • InputStreamReader: Compose into characters (2 bytes long).
  • BufferedReader: Compose into entire lines of text.
1
2
3
4
5
6
7
import java.io.*;
class SimpleIO {
    public static void main(String[] args) throws Exception {
        BufferedReader keybd = new BufferedReader(new InputStreamReader(System.in));
        System.out.println(keybd.readLine());
    }
}

Don’t worry if you don’t understand the first three lines; we’ll learn the underlying ideas eventually. The first line is present because to use the Java libraries, other than java.lang, you need to "import" them. java.io includes the InputStreamReader and BufferedReader classes.

The second line just gives the program a name, "SimpleIO".

The third line is present because any Java program always begins execution at a method named main, which is usually defined more or less as above. When you write a Java program, just copy the line of code, and plan to understand it a few weeks from now.

To use Java libraries, other than java.lang, you import them. java.io includes InputStreamReader, BufferedReader, etc. Java program always begins at a method called main.

Classes for Web Access

Let’s say we want to read a line of text from the White House Web page. (The line will be HTML, which looks ugly. You don’t need to understand HTML.)

How to read a line of text? With readLine on BufferedReader.
How to create a BufferedReader? With an InputStreamReader.
How to create a InputStreamReader? With an InputStream.
How to create an InputStream? With a URL.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import java.net.*;
import java.io.*;

class WHWWW {

    public static void main(String[] arg) throws Exception {
        URL u = new URL("http://www.whitehouse.gov/");
        InputStream ins = u.openStream();
        InputStreamReader isr = new InputStreamReader(ins);
        BufferedReader whiteHouse = new BufferedReader(isr);
        System.out.println(whiteHouse.readLine());
    }

}

Postscript: Object-Oriented Terminology (not examinable)

In the words of Turing Award winner Nicklaus Wirth, "Object-oriented programming (OOP) solidly rests on the principles and concepts of traditional procedural programming. OOP has not added a single novel concept ... along with the OOP paradigm came an entirely new terminology with the purpose of mystifying the roots of OOP." Here’s a translation guide.

Procedural Programming Procedural Programming
record / structure object
record type class
extending a type declaring a subclass
procedure method
procedure call sending a message to the method [ack! phthhht!]

I won’t ever talk about "sending a message" in this class. I think it’s a completely misleading metaphor. In computer science, message-passing normally implies asynchrony: that is, the process that sends a message can continue executing while the receiving process receives the message and acts on it.

But that’s NOT what it means in object-oriented programming: when a Java method "sends a message" to another method, the former method is frozen until the latter methods completes execution, just like with procedure calls in most languages. But you should probably know that this termology exists, much as it sucks, because you’ll probably run into it sooner or later.